Theoretical aspects of quantum information and computation

点击翻译按钮获取中文摘要

Present-day computers are classical computing 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 is to better understand the nature of the computations that can potentially be implemented by quantum computers, as well as the nature of interactions among multiple quantum computers 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 primary subject of my work is quantum computational complexity theory. Principal goals of this subject are to identify and understand relationships among classes of computational problems defined by quantum models of computation, and to relate these models and classes to ones defined by classical computational models. This includes the study of a variety of models and classes of computational 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 in both distributed and cryptographic settings; and classes of problems defined by placing resource constraints and other limitations on quantum models. The quantum interactive proof system model is one example of a quantum computational model that has been studied within quantum computational complexity theory -- this model has been the subject of much of my previous work, and is central to the research I intend to pursue in association with this research proposal. Powerful mathematical techniques from different areas of mathematics have been applied to problems in quantum information and computation. I am particularly interested in techniques from combinatorial optimization, convex analysis, matrix analysis, and the study of operator algebras. Semidefinite programming and the matrix multiplicative weights update method represent two examples that have been important in some of my recent work. I intend to continue to investigate the uses of these and other methods within the study of quantum information and computation. 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 quantum physical systems. If it is successful, this research project will lead to a better theoretical understanding of quantum information and computation, to new mathematical methods that are useful in its study, and possibly to new ways that it can be used.