pith. machine review for the scientific record. sign in

arxiv: 2604.13026 · v1 · submitted 2026-04-14 · 🪐 quant-ph · cond-mat.stat-mech· cs.CC

Recognition: unknown

A complexity phase transition at the EPR Hamiltonian

Kunal Marwaha , James Sud
Authors on Pith no claims yet

Pith reviewed 2026-05-10 15:26 UTC · model grok-4.3

classification 🪐 quant-ph cond-mat.stat-mechcs.CC
keywords 2-local Hamiltonianscomplexity classificationEPR*QMA-completeStoqMA-completeperturbative gadgetsJordan-Wigner transformation
0
0 comments X

The pith

2-local Hamiltonian problems fall into three complexity phases based on the energy ordering of their local interaction term.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper classifies 2-local Hamiltonian problems generated by positive-weight symmetric interactions into three phases according to their computational complexity. The phases are QMA-complete for some energy orderings, StoqMA-complete for others, and reducible to the EPR* problem for the boundary case. The authors conjecture that EPR*, a generalization of the EPR problem, belongs to BPP, which would make it the point separating easy and hard instances. This matters for understanding when problems in quantum many-body physics and optimization are tractable, as the classification ties directly to physical properties like energy level ordering. The proofs use recursive gadgets that flow the interaction terms in a renormalization-like manner, with exact analysis provided by a spin-chain construction.

Core claim

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, including one based on a large spin chain analyzed via the Jordan-Wigner transformation.

What carries the argument

The perturbative gadget constructed from a large spin chain, analyzed exactly with the Jordan-Wigner transformation to produce effective interactions that preserve complexity class.

If this is right

  • The complexity of a given Hamiltonian is determined by the energy level ordering of the local term.
  • If the EPR* conjecture holds, it marks the transition between easy and hard local Hamiltonians.
  • Canonical problems in statistical mechanics and optimization can be placed into one of the three phases.
  • The recursive gadget induces a renormalization-group-like flow that explains the phase structure.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This may help in designing algorithms by identifying the phase of a given model.
  • Similar transitions might exist for other classes of Hamiltonians or higher-order interactions.
  • The conjecture suggests that EPR* could be a natural example for studying the boundary between classical and quantum complexity.
  • Practical computations could use the gadget reductions to simplify hard problems to EPR* instances.

Load-bearing premise

The Jordan-Wigner transformation provides an exact description of the low-energy spectrum of the large spin-chain gadget, and the EPR* problem lies in BPP.

What would settle it

A concrete Hamiltonian in the EPR* phase for which no polynomial-time classical algorithm approximates the ground state energy, or an exact diagonalization of the spin chain gadget that disagrees with the Jordan-Wigner prediction.

Figures

Figures reproduced from arXiv: 2604.13026 by James Sud, Kunal Marwaha.

Figure 1
Figure 1. 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 “≤ 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 [K… view at source ↗
Figure 2
Figure 2. Figure 2: Cartoon of the computational phase diagram in our larger family of Hamiltonians. There are again three distinct phases, depending on the energy level ordering of the Bell states in the local term. Inspired by the behavior in our toy model, we conjecture that the EPR* problem is easy: Conjecture 2. The EPR* problem is in BPP. We have some intuition for this conjecture: when b = 1, the problem is trivially i… view at source ↗
Figure 3
Figure 3. Figure 3: P3: A simple vertex-replacing perturbative gadget. Bold lines denote strong interactions, and thin lines denote weak interactions. Each chain of three red qubits defines a single logical blue qubit. The logical qubits carry a new local interaction term, but the effective interaction graph is unchanged. Once we have logical qubits, we can make them interact. Since we only have access to the original interac… view at source ↗
Figure 4
Figure 4. Figure 4: (a) Map from interaction terms K to K′ generated by the P3 gadget, viewed as a flow diagram. The base and head of each arrow represent the coefficients (a, b, −1) of K and K′ , respectively. The arrows are rescaled to have unit norm for ease of visibility. The regions of the plane are colored by the complexity results of Theorems 2 to 4. A “flow” is highlighted in blue, implying a recursive reduction from … view at source ↗
Figure 5
Figure 5. Figure 5: The edge-replacing gadgets take each edge (i, j) which we would like to produce an interaction on and adds an ancilla pair (y, z). Then, the interaction on (y, z) will be chosen to be H0 in Lemma 5. The interaction on the middle edges will be Vmain, and the top edge will be Vextra. We use Lemma 5 to compute the effect of sums of interactions between i, j, yij and zij . Lemma 5. The {aXX + bY Y − ZZ} +-Hami… view at source ↗
Figure 6
Figure 6. Figure 6: Outline of the proof of Theorem 3. Unless explicitly noted, an oval region corresponds to the {aXX + bY Y − ZZ} + -Hamiltonian with a > 1 and b as labeled. An arrow pointing from one problem to another means any instance of the latter can be simulated by the former using perturbative gadgets. This constitutes a reduction from the latter to the former. This diagram shows how all Hamiltonians in the orange r… view at source ↗
Figure 7
Figure 7. Figure 7: The 20 distinct arrangements of energy levels of K. In each diagram, the oval denotes the singlet energy and dashes denote triplet energies. Degenerate triplets are shown side by side, while triplets degenerate with the singlet are drawn inside the oval. Red arrangements are QMA-complete by Theorem 2. Orange arrangements are StoqMA-complete by Theorems 2 and 3. The yellow arrangement corresponds to the ant… view at source ↗
Figure 8
Figure 8. Figure 8: The five-node gadget graph T. C.1.3 Simulating b = 0 Finally, we apply a vertex-replacing gadget (Section 3.1), with the five node graph T in [PITH_FULL_IMAGE:figures/full_fig_p027_8.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript classifies 2-local Hamiltonian problems generated by positive-weight symmetric interaction terms into three complexity phases—QMA-complete, StoqMA-complete, and reducible to the newly defined EPR* problem—according to the energy-level ordering of the local term. EPR* is presented as a simple generalization of King’s EPR problem; the authors conjecture that EPR* lies in BPP and, if true, that it marks the transition between easy and hard instances. Proofs rely on perturbative gadgets: a recursive gadget that induces a renormalization-group-like flow (but is not polynomial-time) and a large spin-chain gadget whose reduction to EPR* is analyzed via the Jordan-Wigner transformation.

Significance. If the gadget reductions are made fully rigorous and the BPP conjecture for EPR* is substantiated, the work would furnish a physically interpretable, essentially complete complexity classification for a broad family of local Hamiltonians arising in statistical mechanics and optimization. The recursive-gadget construction that produces an RG-like flow on interaction terms is a technically interesting contribution that may have wider applicability.

major comments (2)
  1. [Section describing the large spin-chain gadget (Jordan-Wigner analysis)] The Jordan-Wigner analysis of the large spin-chain gadget is only sketched; the manuscript does not supply an explicit verification that boundary conditions, higher-order perturbative corrections, and the precise isolation of the low-energy sector preserve the exact decision problem under polynomial-time reduction. This step is load-bearing for the claim that the gadget yields a poly-time reduction to EPR* and therefore for the three-phase partition.
  2. [Introduction and concluding discussion of EPR*] The classification into three phases is presented as complete only conditionally on the conjecture that EPR* ∈ BPP. The manuscript states the conjecture but provides no additional evidence or reduction that would make the “transition point” interpretation unconditional; without it the StoqMA-complete and QMA-complete phases are separated from an unresolved remainder rather than from a proven easy class.
minor comments (2)
  1. The definition of the EPR* problem and its precise relationship to the original EPR problem of King should be stated explicitly (rather than described as “a simple generalization”) to allow readers to verify the claimed reduction.
  2. A diagram or table summarizing the three energy-level orderings and the corresponding complexity phases would improve clarity and make the physical interpretation more immediate.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. We address each major comment point by point below, with a commitment to revisions that strengthen the rigor of the presentation without altering the core claims.

read point-by-point responses

  1. Referee: [Section describing the large spin-chain gadget (Jordan-Wigner analysis)] The Jordan-Wigner analysis of the large spin-chain gadget is only sketched; the manuscript does not supply an explicit verification that boundary conditions, higher-order perturbative corrections, and the precise isolation of the low-energy sector preserve the exact decision problem under polynomial-time reduction. This step is load-bearing for the claim that the gadget yields a poly-time reduction to EPR* and therefore for the three-phase partition.

    Authors: We agree that the Jordan-Wigner analysis is presented concisely in the main text. The full derivation (including the mapping under open boundary conditions that eliminate boundary-induced terms, the exponential suppression of higher-order corrections for polynomially long chains, and the gap-protected isolation of the low-energy sector) is contained in the technical appendix. To address the concern directly, we will expand the main-text section with explicit step-by-step verification of these elements, confirming that the reduction remains polynomial-time and exactly preserves the decision problem. This revision will make the load-bearing step fully rigorous. revision: yes

  2. Referee: [Introduction and concluding discussion of EPR*] The classification into three phases is presented as complete only conditionally on the conjecture that EPR* ∈ BPP. The manuscript states the conjecture but provides no additional evidence or reduction that would make the “transition point” interpretation unconditional; without it the StoqMA-complete and QMA-complete phases are separated from an unresolved remainder rather than from a proven easy class.

    Authors: We acknowledge that the three-phase partition is conditional on the conjecture EPR* ∈ BPP. The manuscript already states this limitation explicitly and motivates the conjecture solely from the empirical performance of known algorithms on the original EPR problem together with the structural similarity of EPR*. No proof or additional reduction is supplied because establishing membership in BPP would require new classical algorithmic techniques outside the scope of the present work. We therefore retain the conditional framing as an honest description of the current state of knowledge; the identification of EPR* as the candidate transition point remains a substantive contribution even under this condition. revision: no

Circularity Check

0 steps flagged

No circularity: phase classification follows from explicit gadget reductions and standard transformations

full rationale

The paper derives the three complexity phases (QMA-complete, StoqMA-complete, reducible to EPR*) via perturbative gadgets: a recursive gadget that induces an RG-like flow on interaction terms (non-polynomial but illustrative) and a large spin-chain gadget whose low-energy behavior is mapped exactly using the Jordan-Wigner transformation. EPR* is introduced as a defined generalization of the EPR problem, with the BPP conjecture stated separately as an open claim rather than an input to the classification. No step equates a derived quantity to its own definition, renames a fitted parameter as a prediction, or relies on a self-citation chain that collapses the central result. The reductions are constructed from external standard techniques and preserve the decision problems by explicit construction, making the derivation self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on the standard definitions of QMA and StoqMA, the validity of perturbative gadget reductions, and the conjecture that EPR* is in BPP. No free parameters are fitted to data. EPR* is introduced as a new problem.

axioms (2)
  • domain assumption Perturbative gadgets preserve the complexity class of the Hamiltonian problem
    Invoked to reduce arbitrary instances to the three canonical phases.
  • standard math Jordan-Wigner transformation exactly diagonalizes the spin-chain gadget
    Used to analyze the large-spin gadget that overcomes the non-polynomial-time RG flow.
invented entities (1)
  • EPR* problem no independent evidence
    purpose: Target problem to which a subset of the Hamiltonians reduce, conjectured to be in BPP
    Defined as a simple generalization of King's EPR problem; serves as the conjectured boundary between easy and hard phases.

pith-pipeline@v0.9.0 · 5484 in / 1505 out tokens · 29536 ms · 2026-05-10T15:26:12.500758+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference

    quant-ph 2026-04 unverdicted novelty 7.0

    StoqMA(2) contains NP with Õ(√n)-qubit proofs and completeness error 2^{-polylog(n)}, is contained in EXP, and satisfies StoqMA(k)=StoqMA(2) for k≥2 when completeness error is negligible.

Reference graph

Works this paper leans on

5 extracted references · cited by 1 Pith paper

  1. [1]

    The spectral gapδis constant

  2. [2]

    3.p 12 andp 22 from Eqs

    The ground state is simple (non-degenerate). 3.p 12 andp 22 from Eqs. (16) and (17) are nonnegative

  3. [3]

    (13) is satisfied

    Eq. (13) is satisfied. We start by analyzing the caseb= 0. By inspection λ(0)≈ −8.613,−5.603,−4.751,−4.472,−3.036,−1.427,−0.773, 0,0,0.773,1.427,3.036,4.472,4.751,5.603,8.613 . In particular,λ 1(0) is a simple eigenvalue and there is a constant spectral gapδ >3. The (unnor- malized) ground state vector is v1(0)≈ 1.532,0.715,−0.874,−0.874,0.519,0.519,−0.57...

  4. [4]

    We do this by representing the observables in thebbasis

    =i(c 1 −c † 1). We do this by representing the observables in thebbasis. Here, the only way⟨ψ|O|ψ⟩is nonzero is through the modeb q. So forc 1 = P2n j=1 W † 1,jbj, we may consider just the effect ofW † 1,qbq +W † 1,L+qb† q = 1 2 (V+U) † 1,qbq + (V−U) † 1,qb† q . Similarly, forc † 1 =P2n j=1 W † L+1,jbj, we consider just the effect of 1 2 (V−U) † 1,qbq + (...

  5. [5]

    In the first inequality, we used that by the AM-GM inequality, p (L−j)(L−(j+ 1)≤ 1 2((L−j) + (L−j−1) =L−j− 1 2 =⇒β j ≤(j+ 1)(L−j− 1 2), and thatλ 1 ≥aL(L−1) (Claim 8)

    + (j+ 1)(L−j− 1 2) √ 2 a j(L−j+ 1 2) =a· L−j− 1 2 L−j+ 1 2 · 2j+ (j+ 1) √ 2 a j ≥a· 3 5 · 2j+ (j+ 1) √ 2 a j ≥ 6(a2 − √ 2) 5a . In the first inequality, we used that by the AM-GM inequality, p (L−j)(L−(j+ 1)≤ 1 2((L−j) + (L−j−1) =L−j− 1 2 =⇒β j ≤(j+ 1)(L−j− 1 2), and thatλ 1 ≥aL(L−1) (Claim 8). The second to last inequality is valid forL≥3 and the last in...