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.