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.