Characterizing the complexity of physical quantum problems with oracle complexity classes

量子计算背后的一个主要动机是有效地计算自然界中量子系统的性质。然而，使用计算机科学的工具，人们可以证明(达到标准猜想)，自然的某些属性根本不能用经典计算机或量子计算机有效地计算出来。近些年来，这种公认的“难以计算”的量子性质的集合已经增长，最终导致了对近似模拟(APX-SIM)问题的研究，这个问题问道：“模拟一个冷却到接近绝对零度的量子系统的测量有多难？”这种低温状态特别令人感兴趣，因为它是超导和超流等现象表现出来的地方。对这些现象的理解在材料设计等重要领域具有潜在的应用价值。APX-SIM的研究为量子复杂性理论领域引入了一个相对较新的工具--“Oracle复杂性类”。这项提议旨在探索这种预言复杂性类在描述物理激励的量子问题的难度方面的进一步使用。我们特别要问：1)在量子信息的核心复杂性类之一，量子梅林·阿瑟(QMA)上，Oracle复杂性类能否产生更严格的上界？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.