Implications of quantum information for computational complexity

量子信息对计算复杂性的影响

• 批准号: RGPIN-2014-06332
• 负责人: Nayak, Ashwin
• 金额: $ 2.84万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=687349
• 关键词: Implications; quantum; information; 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.

量子信息和计算研究的区域在原子量表上存储和处理信息的后果。在这个制度中，大自然遵循20世纪初发现的物理定律，即量子力学定律，这与我们在日常生活中所经历的物理学法则不同。这些法律使令人惊讶的任务从算法比当前技术更有效，再到它们所取代的法律（古典物理学定律）将是不可能的密码学。在理解量子机械计算机的力量以及实验原型的建造方面，已经取得了长足的进步。长期以来，实施量子密码学的商业系统已被部署。例如，这导致开发了某些半准优化问题的有效并行算法，从而无需使用线性程序的扩展公式解决NP-HARD问题的无条件证明，并发现有效的（经典）算法在量子物理学中有效的许多体系系统。 这些发展中的突出主题是使用凸优化和量子信息理论技术。 我目前的研究受到这些发展的启发，并着重于量子信息的分析及其对算法，通信和加密的后果。使用凸优化的方法来研究非反应信息理论中的熵量及其在通信和密码学上的应用；研究量子状态的信息含量特性，并将这些特性带入算法和协议的效率上；并分析量子物理系统的接地状态及其与相关计算问题的复杂性的联系。 这些项目从数学和计算机科学领域的丰富研究领域借鉴。我们希望我们的研究也会对这些领域产生影响，同时在量子计算方面取得了长足的进步。