A complexity phase transition at the EPR Hamiltonian
For quantum complexity theorists, this provides a complete classification of a broad class of Hamiltonian problems, with a conjectured easy-hard transition point.
The paper classifies 2-local Hamiltonian problems with positive-weight symmetric interactions into three complexity phases: QMA-complete, StoqMA-complete, and a new problem EPR*. It conjectures that EPR* is in BPP, which would mark the transition between easy and hard Hamiltonians.
We study the computational complexity of 2-local Hamiltonian problems generated by a positive-weight symmetric interaction term, encompassing many canonical problems in statistical mechanics and optimization. We show these problems belong to one of three complexity phases: QMA-complete, StoqMA-complete, and reducible to a new problem we call EPR*. The phases are physically interpretable, corresponding to the energy level ordering of the local term. The EPR* problem is a simple generalization of the EPR problem of King. Inspired by empirically efficient algorithms for EPR, we conjecture that EPR* is in BPP. If true, this would complete the complexity classification of these problems, and imply EPR* is the transition point between easy and hard local Hamiltonians. Our proofs rely on perturbative gadgets. One simple gadget, when recursed, induces a renormalization-group-like flow on the space of local interaction terms. This gives the correct complexity picture, but does not run in polynomial time. To overcome this, we design a gadget based on a large spin chain, which we analyze via the Jordan-Wigner transformation.