Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2604.13026

A complexity phase transition at the EPR Hamiltonian

Kunal Marwaha, James Sud

quant-phcond-mat.stat-mechcs.CCSubmitted Apr 14, 2026• Announced Apr 15, 2026• 5 citations
arXivHTMLPDF

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.

Comments
47 pages, 8 figures

Related papers

The Complexity of Single-Interaction Hamiltonians

Elad Hecker

We study the complexity of Local Hamiltonian problems under the restriction that every local term is an unweighted occurrence of the same fixed interaction. In the resulting Single-Interaction Hamiltonian (SIH) model, once the interaction is fixed, the Hamiltonian is specified entirely by its ordered interaction hypergraph. Our main technical tool is an exact compiler that converts any fixed finite alphabet of local interactions into a single interaction. On a designated auxiliary subspace, the compiled Hamiltonian reproduces the source Hamiltonian exactly, while the complete spectrum below a chosen separation scale is preserved with multiplicity. Combined with a finite-alphabet normalization, this gives a universal polynomial-time reduction from $k$-Local Hamiltonian to SIH$_{3k+3}$ up to a known global energy scale and inverse-polynomial approximation. Sharper constructions give QMA-completeness of SIH$_3$ and of geometrically local SIH$_8$ with bounded degree and interaction range. In the stoquastic setting, we obtain StoqMA-completeness of Stoq-SIH$_3$ and QMA-completeness of 1-Pinned Stoq-SIH$_4$. We also establish hardness results for uniformly system-size-dependent interactions and derive single-interaction formulations of the Hamiltonian quantum PCP conjecture, frustration-free, exponentially precise, and guided Local Hamiltonian problems. These results show that independently chosen local matrices and independently tunable coupling strengths are not necessary for a broad range of Hamiltonian-complexity phenomena.

quant-pharXiv:2609.39592•Oct 1, 2026•0 citations

Complexity Classification of Local Hamiltonian Problems

Toby S. Cubitt, Ashley Montanaro

The calculation of ground-state energies of physical systems can be formalised as the k-local Hamiltonian problem, which is the natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterise the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P, NP-complete, polynomial-time equivalent to the Ising model with transverse magnetic fields, or QMA-complete. The third of these classes contains NP and is contained within StoqMA. The characterisation holds even if S does not contain any 1-local terms, for example, we prove for the first time QMA-completeness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterisation that goes beyond 2-local interactions: for any constant k, all k-local qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P, polynomial-time equivalent to the Ising model with transverse magnetic fields, or QMA-complete. These results are a quantum analogue of Schaefer's dichotomy theorem for boolean constraint satisfaction problems.

Annual Symposium on Foundations of Computer Science•Oct 1, 2014•42 citations

Oracle Complexity Classes and Local Measurements on Physical Hamiltonians

Sevag Gharibian, Stephen Piddock, Justin Yirka

The canonical hard problems for NP and its quantum analogue, Quantum Merlin-Arthur (QMA), are MAX-k-SAT and the k-local Hamiltonian problem (k-LH), the quantum generalization of MAX-k-SAT, respectively. In recent years, however, an arguably even more physically motivated problem than k-LH has been formalized - the problem of simulating local measurements on ground states of local Hamiltonians (APX-SIM). Perhaps surprisingly, [Ambainis, CCC 2014] showed that APX-SIM is likely harder than QMA. Indeed, [Ambainis, CCC 2014] showed that APX-SIM is P^{QMA[log]}-complete, for P^{QMA[log]} the class of languages decidable by a P machine making a logarithmic number of adaptive queries to a QMA oracle. In this work, we show that APX-SIM is P^{QMA[log]}-complete even when restricted to physically motivated Hamiltonians, obtaining as intermediate steps a variety of related complexity-theoretic results. Specifically, we first give a sequence of results which together yield P^{QMA[log]}-hardness for APX-SIM on well-motivated Hamiltonians such as the 2D Heisenberg model: - We show that for NP, StoqMA, and QMA oracles, a logarithmic number of adaptive queries is equivalent to polynomially many parallel queries. Formally, P^{NP[log]}=P^{||NP}, P^{StoqMA[log]}=P^{||StoqMA}, and P^{QMA[log]}=P^{||QMA}. (The result for NP was previously shown using a different proof technique.) These equalities simplify the proofs of our subsequent results. - Next, we show that the hardness of APX-SIM is preserved under Hamiltonian simulations (à la [Cubitt, Montanaro, Piddock, 2017]) by studying a seemingly weaker problem, ∀-APX-SIM. As a byproduct, we obtain a full complexity classification of APX-SIM, showing it is complete for P, P^{||NP},P^{||StoqMA}, or P^{||QMA} depending on the Hamiltonians employed. - Leveraging the above, we show that APX-SIM is P^{QMA[log]}-complete for any family of Hamiltonians which can efficiently simulate spatially sparse Hamiltonians. This implies APX-SIM is P^{QMA[log]}-complete even on physically motivated models such as the 2D Heisenberg model. Our second focus considers 1D systems: We show that APX-SIM remains P^{QMA[log]}-complete even for local Hamiltonians on a 1D line of 8-dimensional qudits. This uses a number of ideas from above, along with replacing the "query Hamiltonian" of [Ambainis, CCC 2014] with a new "sifter" construction.

arXiv:1909.05981•Leibniz international proceedings in informatics•Sep 12, 2019•10 citations

Complexity of geometrically local stoquastic Hamiltonians

Asad Raza, Jens Eisert, Alex B. Grilo

The QMA-completeness of the local Hamiltonian problem is a landmark result of the field of Hamiltonian complexity that studies the computational complexity of problems in quantum many-body physics. Since its proposal, substantial effort has been invested in better understanding the problem for physically motivated important families of Hamiltonians. In particular, the QMA-completeness of approximating the ground state energy of local Hamiltonians has been extended to the case where the Hamiltonians are geometrically local in one and two spatial dimensions. Among those physically motivated Hamiltonians, stoquastic Hamiltonians play a particularly crucial role, as they constitute the manifestly sign-free Hamiltonians in Monte Carlo approaches. Interestingly, for such Hamiltonians, the problem at hand becomes more ''classical'', being hard for the class MA (the randomized version of NP) and its complexity has tight connections with derandomization. In this work, we prove that both the two- and one-dimensional geometrically local analogues remain MA-hard with high enough qudit dimension. Moreover, we show that related problems are StoqMA-complete.

arXiv:2407.15499•Quantum•Feb 11, 2026•5 citations

The complexity of quantum spin systems on a two-dimensional square lattice

Roberto I. Oliveira, Barbara M. Terhal

The problem 2-LOCAL HAMILTONIAN has been shown to be complete for the quantum computational class QMA. In this paper we show that this important problem remains QMA-complete when the interactions of the 2-local Hamiltonian are between qubits on a two-dimensional (2-D) square lattice. Our results are partially derived with novel perturbation gadgets that employ mediator qubits which allow us to manipulate k-local interactions. As a side result, we obtain that quantum adiabatic computation using 2-local interactions restricted to a 2-D square lattice is equivalent to the circuit model of quantum computation. Our perturbation method also shows how any stabilizer space associated with a k-local stabilizer (for constant k) can be generated as an approximate ground-space of a 2-local Hamiltonian.

arXiv:quant-ph/0504050•Quantum Information and Computation•Nov 1, 2008•286 citations

On the Computational Complexity of Guided Berry Phase Estimation

Gabriel Waite

We prove that deciding the Berry phase for parameterised 2-local qubit Hamiltonians is BQP-complete when presented with a classical description of a guiding state, promised to overlap with the ground state of the system. Our results extend to systems with weighted Heisenberg interactions and when restricted to a 2D square or triangular lattice geometry. The techniques we develop leverage the Schrieffer--Wolff transformation, typically used in the construction of perturbative gadget reductions for local Hamiltonian problems, extending it to parameterised families of Hamiltonians. We demonstrate that there exists a choice of parameterised simulator Hamiltonians whose Berry phase well-approximates that of a parameterised target family. Using the perturbative gadget reduction framework of Oliveira and Terhal and of Schuch and Verstraete, we adapt the arguments to parameterised interactions and demonstrate the error bounds in the resulting simulation can be controlled. Additionally, we provide an explicit proof that families of 1-local Hamiltonians have a Berry phase that can be efficiently computed to inverse-polynomial precision. This establishes a complexity transition between 1-local and 2-local Hamiltonian families.

quant-pharXiv:2609.25929•Sep 23, 2026•1 citation
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.
We study the complexity of Local Hamiltonian problems under the restriction that every local term is an unweighted occurrence of the same fixed interaction. In the resulting Single-Interaction Hamiltonian (SIH) model, once the interaction is fixed, the Hamiltonian is specified entirely by its ordered interaction hypergraph. Our main technical tool is an exact compiler that converts any fixed finite alphabet of local interactions into a single interaction. On a designated auxiliary subspace, the compiled Hamiltonian reproduces the source Hamiltonian exactly, while the complete spectrum below a chosen separation scale is preserved with multiplicity. Combined with a finite-alphabet normalization, this gives a universal polynomial-time reduction from kkk-Local Hamiltonian to SIH3k+3_{3k+3}3k+3​ up to a known global energy scale and inverse-polynomial approximation. Sharper constructions give QMA-completeness of SIH3_33​ and of geometrically local SIH8_88​ with bounded degree and interaction range. In the stoquastic setting, we obtain StoqMA-completeness of Stoq-SIH3_33​ and QMA-completeness of 1-Pinned Stoq-SIH4_44​. We also establish hardness results for uniformly system-size-dependent interactions and derive single-interaction formulations of the Hamiltonian quantum PCP conjecture, frustration-free, exponentially precise, and guided Local Hamiltonian problems. These results show that independently chosen local matrices and independently tunable coupling strengths are not necessary for a broad range of Hamiltonian-complexity phenomena.
The calculation of ground-state energies of physical systems can be formalised as the k-local Hamiltonian problem, which is the natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterise the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P, NP-complete, polynomial-time equivalent to the Ising model with transverse magnetic fields, or QMA-complete. The third of these classes contains NP and is contained within StoqMA. The characterisation holds even if S does not contain any 1-local terms, for example, we prove for the first time QMA-completeness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterisation that goes beyond 2-local interactions: for any constant k, all k-local qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P, polynomial-time equivalent to the Ising model with transverse magnetic fields, or QMA-complete. These results are a quantum analogue of Schaefer's dichotomy theorem for boolean constraint satisfaction problems.
The canonical hard problems for NP and its quantum analogue, Quantum Merlin-Arthur (QMA), are MAX-k-SAT and the k-local Hamiltonian problem (k-LH), the quantum generalization of MAX-k-SAT, respectively. In recent years, however, an arguably even more physically motivated problem than k-LH has been formalized - the problem of simulating local measurements on ground states of local Hamiltonians (APX-SIM). Perhaps surprisingly, [Ambainis, CCC 2014] showed that APX-SIM is likely harder than QMA. Indeed, [Ambainis, CCC 2014] showed that APX-SIM is P^{QMA[log]}-complete, for P^{QMA[log]} the class of languages decidable by a P machine making a logarithmic number of adaptive queries to a QMA oracle. In this work, we show that APX-SIM is P^{QMA[log]}-complete even when restricted to physically motivated Hamiltonians, obtaining as intermediate steps a variety of related complexity-theoretic results. Specifically, we first give a sequence of results which together yield P^{QMA[log]}-hardness for APX-SIM on well-motivated Hamiltonians such as the 2D Heisenberg model: - We show that for NP, StoqMA, and QMA oracles, a logarithmic number of adaptive queries is equivalent to polynomially many parallel queries. Formally, P^{NP[log]}=P^{||NP}, P^{StoqMA[log]}=P^{||StoqMA}, and P^{QMA[log]}=P^{||QMA}. (The result for NP was previously shown using a different proof technique.) These equalities simplify the proofs of our subsequent results. - Next, we show that the hardness of APX-SIM is preserved under Hamiltonian simulations (à la [Cubitt, Montanaro, Piddock, 2017]) by studying a seemingly weaker problem, ∀-APX-SIM. As a byproduct, we obtain a full complexity classification of APX-SIM, showing it is complete for P, P^{||NP},P^{||StoqMA}, or P^{||QMA} depending on the Hamiltonians employed. - Leveraging the above, we show that APX-SIM is P^{QMA[log]}-complete for any family of Hamiltonians which can efficiently simulate spatially sparse Hamiltonians. This implies APX-SIM is P^{QMA[log]}-complete even on physically motivated models such as the 2D Heisenberg model. Our second focus considers 1D systems: We show that APX-SIM remains P^{QMA[log]}-complete even for local Hamiltonians on a 1D line of 8-dimensional qudits. This uses a number of ideas from above, along with replacing the "query Hamiltonian" of [Ambainis, CCC 2014] with a new "sifter" construction.
The QMA-completeness of the local Hamiltonian problem is a landmark result of the field of Hamiltonian complexity that studies the computational complexity of problems in quantum many-body physics. Since its proposal, substantial effort has been invested in better understanding the problem for physically motivated important families of Hamiltonians. In particular, the QMA-completeness of approximating the ground state energy of local Hamiltonians has been extended to the case where the Hamiltonians are geometrically local in one and two spatial dimensions. Among those physically motivated Hamiltonians, stoquastic Hamiltonians play a particularly crucial role, as they constitute the manifestly sign-free Hamiltonians in Monte Carlo approaches. Interestingly, for such Hamiltonians, the problem at hand becomes more ''classical'', being hard for the class MA (the randomized version of NP) and its complexity has tight connections with derandomization. In this work, we prove that both the two- and one-dimensional geometrically local analogues remain MA-hard with high enough qudit dimension. Moreover, we show that related problems are StoqMA-complete.
The problem 2-LOCAL HAMILTONIAN has been shown to be complete for the quantum computational class QMA. In this paper we show that this important problem remains QMA-complete when the interactions of the 2-local Hamiltonian are between qubits on a two-dimensional (2-D) square lattice. Our results are partially derived with novel perturbation gadgets that employ mediator qubits which allow us to manipulate k-local interactions. As a side result, we obtain that quantum adiabatic computation using 2-local interactions restricted to a 2-D square lattice is equivalent to the circuit model of quantum computation. Our perturbation method also shows how any stabilizer space associated with a k-local stabilizer (for constant k) can be generated as an approximate ground-space of a 2-local Hamiltonian.
We prove that deciding the Berry phase for parameterised 2-local qubit Hamiltonians is BQP-complete when presented with a classical description of a guiding state, promised to overlap with the ground state of the system. Our results extend to systems with weighted Heisenberg interactions and when restricted to a 2D square or triangular lattice geometry. The techniques we develop leverage the Schrieffer--Wolff transformation, typically used in the construction of perturbative gadget reductions for local Hamiltonian problems, extending it to parameterised families of Hamiltonians. We demonstrate that there exists a choice of parameterised simulator Hamiltonians whose Berry phase well-approximates that of a parameterised target family. Using the perturbative gadget reduction framework of Oliveira and Terhal and of Schuch and Verstraete, we adapt the arguments to parameterised interactions and demonstrate the error bounds in the resulting simulation can be controlled. Additionally, we provide an explicit proof that families of 1-local Hamiltonians have a Berry phase that can be efficiently computed to inverse-polynomial precision. This establishes a complexity transition between 1-local and 2-local Hamiltonian families.