Implications of quantum information for computational complexity

量子信息和计算领域研究在原子尺度的设备中存储和处理信息的后果。在这种制度下，自然遵循的是世纪初发现的物理定律，即量子力学定律，这些定律与我们日常生活中所经历的定律有着根本的不同。这些定律使惊人的任务成为可能，从比现有技术更有效的算法，到在它们所取代的定律（经典物理定律）下被证明是不可能的密码学。在理解量子力学计算机的能力和建造实验原型方面已经取得了相当大的进展。在计算机科学领域，量子计算对传统的研究领域产生了深远的影响，特别是在过去的五年里。例如，它导致了某些半定优化问题的有效并行算法的发展，使用线性规划的扩展公式解决NP-难问题的不可能性的无条件证明，以及在量子物理学中研究充分的多体系统的有效（经典）算法的发现。这些发展中突出的主题是凸优化和量子信息理论技术的使用。我目前的研究受到这些发展的启发，并专注于量子信息及其对算法，通信和密码学的影响的分析。沿着我的研究小组和合作者，我计划：研究纠缠作为一种资源，并量化信息处理任务所需的这种资源的数量;使用凸优化的方法来研究非渐近信息论中的熵量，及其在通信和密码学中的应用;研究量子态的信息内容特性，并将其应用于算法和协议的效率;分析量子物理系统的基态，以及它们与相关计算问题复杂性的联系。这些项目借鉴并连接到数学和计算机科学的丰富研究领域。我们希望我们的研究也能对这些领域产生影响，同时在量子计算方面取得进展。

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.