Quantum Information, Computation, and Complexity

现代计算机是经典设备：经典计算机的每个组件在计算的每个步骤之前和之后都有一个确定的逻辑状态，并且计算根据确定性（有时是随机的）逻辑操作序列所规定的规则进行。然而，根据量子信息理论，它提供了量子力学系统的信息理论方面的抽象，经典计算只代表了可以通过物理设备实现的计算的有限子集。就像原子中的电子存在于叠加态中，无法在牛顿物理学的背景下明确描述，量子计算机可以存在于逻辑状态的叠加态中，并且它们的计算可以同时沿着沿着多个计算路径进行，这些计算路径可能会建设性地或破坏性地相互干扰。量子计算理论研究了这种计算范式的力量和局限性。 我的研究计划的主要目标是更好地理解量子计算机可能实现的计算的性质，无论是在孤立的情况下，还是在合作和竞争的情况下。我也对量子信息的基本方面感兴趣，以及对量子信息和计算推理有用的数学技术的发展。这项工作的一个主要目标是确定量子计算模型可解决的计算问题的性质和之间的关系，以及它们与经典计算模型可解决的问题的关系。这包括对各种模型和问题类别的研究，包括抽象单个量子计算机编程以尽快解决计算问题的概念的模型;描述多个量子计算机之间交互的模型;以及通过对量子模型施加资源约束来定义的问题类别。量子信息有可能给我们构建和使用计算机的方式带来革命性的变化，私密通信和实现加密协议，以及研究物理系统的性质。如果成功，拟议的研究将导致对量子信息和计算的更好的理论理解，对其研究有用的新数学方法，以及可以使用的新方法。

Present-day computers are classical devices: each component of a classical computer has a definite logical state before and after each step of a computation, and computations proceed according to rules dictated by sequences of deterministic (or sometimes randomized) logical operations. According to the theory of quantum information, however, which offers an abstraction of the information-theoretic aspects of quantum mechanical systems, classical computations represent only a limited subset of the computations that can potentially be implemented by physical devices. Much like electrons in atoms exist in superpositions that cannot be described definitively within the context of Newtonian physics, quantum computers can exist in superpositions of logical states, and their computations can proceed along multiple computation paths simultaneously that may constructively or destructively interfere with one another. The theory of quantum computation studies the powers and limitations of this computational paradigm. The main objective of my research program is to better understand the nature of the computations that can potentially be implemented by quantum computers, both in isolation and in cooperative and competitive settings. I am also interested in fundamental aspects of quantum information, and in the development of mathematical techniques that are useful for reasoning about quantum information and computation. A principal goal of this work is to identify properties of and relationships among computational problems solvable by quantum models of computation, as well as their relationships to problems solvable by classical computational models. This includes the study of a variety of models and classes of problems, including models that abstract the notion of a single quantum computer programmed to solve computational problems as rapidly as possible; of models that describe interactions among multiple quantum computers; and classes of problems defined by placing resource constraints on quantum models. Quantum information has the potential to bring a transformative change to the way we build and use computers, communicate privately and implement cryptographic protocols, and study the nature of physical systems. If it is successful, the proposed research will lead to a better theoretical understanding of quantum information and computation, to new mathematical methods that are useful in its study, and to new ways that it can be used.