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.