A complexity phase transition at the EPR Hamiltonian
2026-04-14 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors analyze how hard it is to solve certain physics and optimization problems that involve pairs of interacting particles, described by 2-local Hamiltonians. They categorize these problems into three complexity types: very hard for quantum computers (QMA-complete), somewhat easier but still challenging (StoqMA-complete), and a new middle type they call EPR*. This new type might actually be efficiently solvable by classical algorithms, based on analogies to previous work. Their proofs use complex constructions called perturbative gadgets, including one inspired by spin chains to better understand the problem structure.
2-local HamiltonianQMA-completeStoqMA-completeEPR problemperturbative gadgetsspin chainJordan-Wigner transformationcomplexity phasesrenormalization group
Authors
Kunal Marwaha, James Sud
Abstract
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.