Characterizing the complexity of physical quantum problems with oracle complexity classes

量子计算背后的一个主要动机是有效地计算自然界中量子系统的性质。然而，使用计算机科学的工具，人们可以证明（直到标准猜想），自然的某些属性根本无法通过经典计算机或量子计算机有效地计算出来。近年来，这种可证明“难以计算”的量子特性的集合不断增长，在近似模拟（APX-SIM）问题的研究中达到顶峰，该问题提出：“模拟一个冷却到接近绝对零度的量子系统的测量有多难？”这种低温状态是特别有趣的，因为它是超导和超流体等现象表现出来的地方。理解这些现象，反过来，在材料设计等重要领域有潜在的应用。APX-SIM的研究为量子复杂性理论领域引入了一个相对较新的工具，即“oracle复杂性类”。本提案旨在进一步探索这种oracle复杂性类在物理驱动量子问题的难度表征中的应用。特别是，我们要问：1)oracle复杂性类能否产生量子信息中一个中心复杂性类的更紧的上界，quantum Merlin Arthur (QMA)？2) oracle复杂性类是否允许我们证明计算涉及纠缠、能量势垒和玻色子/费米子系统的低温特性也很“困难”？3) oracle复杂性类是否能让我们更精确地证明某些低温量子系统在形式意义上比其他系统更“强大”？这些目标的成功完成将产生新的深刻见解，使我们能够有效地计算自然属性之间的界限。

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.