A complexity phase transition at the EPR Hamiltonian

Kunal Marwaha, James Sud · 2026

Read A complexity phase transition at the EPR Hamiltonian by Kunal Marwaha, James Sud (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-13026.txt.

Introduction

Marwaha and Sud sort 2-local Hamiltonian problems, built from a positive-weight symmetric interaction term, into three complexity phases. The phases, QMA-complete, StoqMA-complete, and reducible to a new problem called EPR*, track the energy ordering of the local term. The authors conjecture EPR* lies in BPP, which would complete the classification and mark EPR* as the boundary between easy and hard local Hamiltonians. Their proofs use perturbative gadgets, including a large spin chain analyzed through the Jordan-Wigner transformation.

Catalog record

CREATORKunal Marwaha, James Sud
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE140434
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.13026

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A complexity phase transition at the EPR Hamiltonian 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: 𝖰𝖬𝖠 {\mathsf{QMA}} -complete, 𝖲𝗍𝗈𝗊𝖬𝖠 {\mathsf{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 [ Kin23 ] . Inspired by empirically efficient algorithms for EPR , we conjecture that EPR* is in 𝖡𝖯𝖯 {\mathsf{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. 1 Introduction We study the computational complexity of the local Hamiltonian problem, which asks us to estimate the ground state energy of a physical system. While this problem is {\mathsf{QMA}} -complete in general [ KSV02 ] , it becomes efficiently solvable for certain restricted families, for example via Markov chain Monte Carlo methods or the quantum adiabatic algorithm. This raises a natural question: Which local Hamiltonians admit efficient algorithms for ground state energy estimation? Identifying tractable families, however, does not by itself explain why certain Hamiltonians are easy or hard. Ideally, we would like go further, by characterizing complexity directly from simple structural features: What physical properties of a local Hamiltonian problem determine its complexity? We approach these questions through the lens of computational phase transitions . For a family of problems controlled by a real parameter \theta , we say that a phase transition occurs if there is a threshold t where the complexity of the problem P(\theta) abruptly changes at \theta=t . Commonly, the problems in \{P(\theta)\ |\ \theta<t\} all have the same complexity, which is different from the problems in \{P(\theta)\ |\ \theta>t\} . We may think of these two subsets as phases , just as a physical system can exhibit different phases of matter. We show how to answer these questions for Hamiltonians generated by a symmetric 2 -local interaction term with positive interaction strength. This family was first introduced by Piddock and Montanaro [ PM15 ] , and covers a range of important problems in statistical physics and computer science. We show a trichotomy theorem, e.g. the existence of three computational phases, with phase transitions driven by energy level crossings in the local term. The complexity of each phase is encoded in a simple physical property of the local term’s energy level diagram (see Figs. 1 and 2 ). To build intuition, we first restrict to a toy model in which each local term is a weighted sum of two projectors. In this toy model, one phase transition occurs at the EPR problem of [ Kin23 ] . Prior work suggests that this problem may lie in {\mathsf{BPP}} [ RT25 ] , which would place it at the boundary between easy and hard instances. In the general family of local Hamiltonian problems, the analogous phase transition corresponds to an augmented EPR problem, which we call the EPR* problem. Showing EPR* is in {\mathsf{BPP}} would thus complete the complexity classification of this family. 1.1 Results A k -local Hamiltonian can be written as H\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\sum_{\ell}H_{\ell} , where each term H_{\ell} acts nontrivially on at most k qubits and as the identity on the rest. The k - Local Hamiltonian problem asks: given thresholds a and b with b-a\geq 1/{\mathsf{poly}}(n) , determine whether the ground-state energy of a k -local H on n qubits is at most a or at least b . This problem was shown to be {\mathsf{QMA}} -complete when k=5 in [ KSV02 ] , and even when k=2 by [ KKR05 ] . 1.1.1 The toy model Consider the following 2 -local interaction term J(s) , parameterized by the real value s \displaystyle J(s)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}-s\ket{\psi^{-}}\bra{\psi^{-}}-\ket{\psi^{+}}\bra{\psi^{+}}, where \ket{\psi^{\pm}}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\tfrac{1}{\sqrt{2}}\left(\ket{01}\pm\ket{10}\right) are Bell states. We define Toy (s) to be a restriction of 2 - Local Hamiltonian where the local terms of the Hamiltonian are all proportional to J(s) \displaystyle H=\sum_{(i,j)\in E}w_{ij}J(s)_{ij}\,, for some graph G with vertices [n] , edges E , and positive edge weights \left\{w_{ij}\right\} . It can be shown as a corollary of [ PM15 , Theorem 2] that Toy (s) is {\mathsf{QMA}} -complete when s>1 . However, this result only shows that Toy (s) is in {\mathsf{StoqMA}} when s<1 . We prove that a matching lower bound holds when 0<s<1 : Claim 1 . For 0<s<1 , Toy (s) is {\mathsf{StoqMA}} -complete. Furthermore, we show that all problems Toy (s) for s<0 are no harder than Toy (0) : Claim 2 . For s<0 , Toy (s) is reducible to Toy (0) , also known as the EPR problem [ Kin23 ] . Here, and throughout the text, by reducible we mean there exists a polynomial-time reduction. The computational phases in our toy model have a remarkable physical interpretation. The interaction J(s) projects into the unique singlet state \ket{\psi^{-}} and a triplet state \ket{\psi^{+}} . The singlet state is the only Bell state that is antisymmetric under interchanging qubits (i.e. \ket{\psi^{-}}_{ij}=-\ket{\psi^{-}}_{ji} ). On the other hand, \ket{\psi^{+}} , along with the remaining Bell states \ket{\phi^{\pm}}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\tfrac{1}{\sqrt{2}}\left(\ket{00}\pm\ket{11}\right) , are symmetric under interchange of qubits. It turns out that we can predict the complexity of a problem in the toy model simply by the location of the singlet in the energy level ordering of J(s) . When the singlet is the unique ground state, Toy (s) is {\mathsf{QMA}} -complete; when the singlet is the first excited state, Toy (s) is {\mathsf{StoqMA}} -complete; and when the singlet is the second or third excited state, Toy (s) is reducible to EPR. We visualize these phases in Fig. 1 . The phase transitions occur at Toy (0) and Toy (1) , which correspond to the EPR problem and the {\mathsf{NP}} -complete MaxCut problem, respectively. Figure 1 : Computational phase diagram of Toy (s) . There are three distinct phases, depending on the energy level ordering of the Bell states in the local term. The notation “ \leq EPR ” denotes reducibility to the EPR problem. The energy level diagrams depict the energies (-1,0,0) of the triplet states with gray lines and the energy of the singlet -s with a red box. Toy (0) , or the EPR problem, was first introduced by [ Kin23 ] . Here s=0 , so the local term J(s) simply projects each edge into a triplet state (the original work chooses the “EPR state” \ket{\phi^{+}} ). The complexity of the EPR problem is unknown. It was raised as an open problem when restricted to bipartite graphs [ Gha23 , RT25 ] , where it may be solvable in polynomial time by quantum Monte Carlo (QMC) [ RT25 ] or quantum

Read the complete text