{"id":"arxiv/2604.13026","url":"https://arxiv.org/abs/2604.13026","tags":["quant-ph","cond-mat.stat-mech","cs.CC"],"score":0,"title":"A complexity phase transition at the EPR Hamiltonian","domain":"quant-ph","source":"arxiv","authors":["Kunal Marwaha","James Sud"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-04-14","reactions":{}}