Characterizing the complexity of physical quantum problems with oracle complexity classes

用预言复杂度类表征物理量子问题的复杂性

• 批准号: 450041824
• 负责人: Professor Dr. Sevag Gharibian, Ph.D.
• 金额: --
• 依托单位: Fachgebiet Algorithmen und Komplexität
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/450041824?language=en
• 关键词: Characterizing; complexity; physical; quantum; problems

A primary motivation behind quantum computation is to efficiently compute properties of quantum systems in Nature. Yet, using tools from computer science, one can prove (up to standard conjectures) that certain properties of Nature simply cannot be computed efficiently by either a classical nor quantum computer. In recent years, the set of such provably "difficult-to-compute" quantum properties has grown, culminating in the study of the Approximate Simulation (APX-SIM) problem, which asks: "How hard is it to simulate a measurement of a quantum system which is cooled to near absolute zero"? This low temperature regime is of particular interest, as it is where phenomena such as superconductivity and superfluidity manifest themselves. Understanding these phenomena, in turn, has potential applications to important areas such as materials design.The study of APX-SIM introduced a relatively new tool to the field of quantum complexity theory, that of "oracle complexity classes". This proposal aims to explore further uses of such oracle complexity classes in the characterization of the difficulty of physically motivated quantum problems. In particular, we ask:1) Can oracle complexity classes yield a tighter upper bound on one of the central complexity classes in quantum information, Quantum Merlin Arthur (QMA)?2) Can oracle complexity classes allow us to prove that computing low temperature properties involving entanglement, energy barriers, and bosonic/fermionic systems are also "difficult"?3) Can oracle complexity classes allow us to more precisely prove that some low temperature quantum systems are, in a formal sense, more "powerful" than others?A successful completion of these objectives will yield deep new insights into the fine line between which properties of Nature can, or cannot, be computed efficiently.

量子计算背后的主要动机是有效地计算自然界中量子系统的性质。然而，使用计算机科学的工具，人们可以证明（达到标准的假设），自然界的某些性质根本无法通过经典计算机或量子计算机有效地计算。近年来，这种可证明的“难以计算”的量子性质的集合已经增长，最终在近似模拟（APX-SIM）问题的研究中达到高潮，该问题问道：“模拟冷却到接近绝对零度的量子系统的测量有多难？”这种低温状态特别令人感兴趣，因为它是超导性和超流性等现象的表现。APX-SIM的研究为量子复杂性理论领域引入了一个相对较新的工具，即“预言复杂性类”。该提案旨在探索此类Oracle复杂性类在表征物理驱动的量子问题的难度方面的进一步用途。特别是，我们问：1）甲骨文复杂性类可以产生一个更严格的上限的中央复杂性类之一，在量子信息，量子梅林亚瑟（QMA）？2)Oracle复杂性类能让我们证明计算涉及纠缠、能垒和玻色子/费米子系统的低温性质也是“困难的”吗？3)甲骨文复杂性类能让我们更精确地证明某些低温量子系统在形式意义上比其他系统更“强大”吗？这些目标的成功完成将产生深刻的新见解之间的细线自然属性可以或不能有效地计算。