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.