Characterizing the complexity of physical quantum problems with oracle complexity classes

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.

DFG Programme Research Grants