Implications of quantum information for computational complexity

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

The area of quantum information and computation studies the consequences of storing and processing information in devices at the atomic scale. In this regime, nature follows laws of physics discovered early in the 20th century, the laws of quantum mechanics, which are fundamentally different from those we experience in our daily lives. These laws enable astonishing tasks, from algorithms more efficient than possible with current technology, to cryptography that would be provably impossible under the laws they replace (the laws of classical physics). Considerable progress has been made in understanding the power of quantum mechanical computers, and in the building of experimental prototypes. Commercial systems implementing quantum cryptography have long been deployed. Within computer science, quantum computation has had a profound impact on traditional areas of research, especially in the last five years. For instance, it has led to the development of efficient parallel algorithms for certain semi-definite optimization problems, to unconditional proofs of impossibility of solving NP-hard problems using extended formulations of linear programs, and to the discovery of an efficient (classical) algorithm for a well-studied many-body system in quantum physics. Prominent themes in these developments are the use of convex optimization and quantum information-theoretic techniques. My current research is inspired by these developments, and focuses on the analysis of quantum information and its consequences for algorithms, communication, and cryptography. Along with my research group and collaborators, I plan to: study entanglement as a resource, and quantify the amount of this resource needed in information processing tasks; use methods from convex optimization to study entropic quantities in non-asymptotic information theory, and their applications to communication and cryptography; study the information content properties of quantum states, and bring these to bear on the efficiency of algorithms and protocols; and analyze ground states of quantum physical systems, and their connection with the complexity of the associated computational problems. The projects draw from and connect to rich areas of study in mathematics and computer science. We expect that our research will have repercussions for these areas as well, while making strides in quantum computing.