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

Leibniz international proceedings in informatics

Improved Approximation Algorithms for the EPR Hamiltonian

Ju, Nathan, Nagda, Ansh

Published Jan 1, 2025• 1 citation
Publisher

Abstract

The EPR Hamiltonian is a family of 2-local quantum Hamiltonians introduced by King [King, 2023]. We introduce a polynomial time (1+√5)/4≈0.809-approximation algorithm for the problem of computing the ground energy of the EPR Hamiltonian, improving upon the previous state of the art of 0.72 [Jorquera et al., 2024].
DOI
10.4230/lipics.approx/random.2025.24

Related papers

Improved approximation algorithms for the EPR Hamiltonian

Nathan Ju, Ansh Nagda

The EPR Hamiltonian is a family of 2-local quantum Hamiltonians introduced by King (arXiv:2209.02589). We introduce a polynomial time $\frac{1+\sqrt{5}}{4}\approx 0.809$-approximation algorithm for the problem of computing the ground energy of the EPR Hamiltonian, improving upon the previous state of the art of $0.72$ (arXiv:2410.15544). As a special case, this also implies a $\frac{1+\sqrt{5}}{4}$-approximation for Quantum Max Cut on bipartite instances, improving upon the approximation ratio of $3/4$ that one can infer in a relatively straightforward manner from the work of Lee and Parekh (arXiv:2401.03616).

arXiv:2504.10712•Apr 14, 2025•10 citations

A 0.8395-approximation algorithm for the EPR problem

Anuj Apte, Eunou Lee, Kunal Marwaha +3 more

We give an efficient 0.8395-approximation algorithm for the EPR Hamiltonian. Our improvement comes from a new nonlinear monogamy-of-entanglement bound on star graphs and a refined parameterization of a shallow quantum circuit from previous works. We also prove limitations showing that current methods cannot achieve substantially better approximation ratios, indicating that further progress will require fundamentally new techniques.

quant-pharXiv:2512.09896•Leibniz international proceedings in informatics•Dec 11, 2025•8 citations

Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians

François Le Gall

We construct classical algorithms computing an approximation of the ground state energy of an arbitrary $k$-local Hamiltonian acting on $n$ qubits. We first consider the setting where a good ``guiding state'' is available, which is the main setting where quantum algorithms are expected to achieve an exponential speedup over classical methods. We show that a constant approximation (i.e., an approximation with constant relative accuracy) of the ground state energy can be computed classically in $\mathrm{poly}\left(1/χ,n\right)$ time and $\mathrm{poly}(n)$ space, where $χ$ denotes the overlap between the guiding state and the ground state (as in prior works in dequantization, we assume sample-and-query access to the guiding state). This gives a significant improvement over the recent classical algorithm by Gharibian and Le Gall (SICOMP 2023), and matches (up a to polynomial overhead) both the time and space complexities of quantum algorithms for constant approximation of the ground state energy. We also obtain classical algorithms for higher-precision approximation. For the setting where no guided state is given (i.e., the standard version of the local Hamiltonian problem), we obtain a classical algorithm computing a constant approximation of the ground state energy in $2^{O(n)}$ time and $\mathrm{poly}(n)$ space. To our knowledge, before this work it was unknown how to classically achieve these bounds simultaneously, even for constant approximation. We also discuss complexity-theoretic aspects of our results.

arXiv:2410.21833•Leibniz international proceedings in informatics•Oct 29, 2024•7 citations

A complexity phase transition at the EPR Hamiltonian

Kunal Marwaha, James Sud

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.

quant-pharXiv:2604.13026•Apr 15, 2026•5 citations

Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States

Chris Cade, Marten Folkertsma, Gharibian, Sevag +4 more

Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with 6-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to 1/2 with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.

arXiv:2207.10097•Leibniz international proceedings in informatics•Jul 20, 2022•19 citations

Improved Approximation Algorithms for Bounded-Degree Local Hamiltonians

Anurag Anshu, David Gosset, Karen J. Morenz Korol +1 more

The low-temperature properties of interacting quantum systems are believed to require exponential resources to compute in the general case. Quantifying the extent to which such properties can be approximated using efficient algorithms remains a significant open challenge. Here, we consider the task of approximating the ground state energy of two-local quantum Hamiltonians with bounded-degree interaction graphs. Most existing algorithms optimize the energy over the set of product states. We propose and analyze a family of shallow quantum circuits that can be used to improve the approximation ratio achieved by a given product state. The algorithm takes as input an n-qubit product state with variance Var and improves its energy by an amount proportional to Var^{2}/n. In a typical case, this results in an extensive improvement in the estimated energy. We extend our results to k-local Hamiltonians and entangled initial states.

arXiv:2105.01193•Physical Review Letters•Dec 17, 2021•25 citations
The EPR Hamiltonian is a family of 2-local quantum Hamiltonians introduced by King (arXiv:2209.02589). We introduce a polynomial time 1+54≈0.809\frac{1+\sqrt{5}}{4}\approx 0.80941+5​​≈0.809-approximation algorithm for the problem of computing the ground energy of the EPR Hamiltonian, improving upon the previous state of the art of 0.720.720.72 (arXiv:2410.15544). As a special case, this also implies a 1+54\frac{1+\sqrt{5}}{4}41+5​​-approximation for Quantum Max Cut on bipartite instances, improving upon the approximation ratio of 3/43/43/4 that one can infer in a relatively straightforward manner from the work of Lee and Parekh (arXiv:2401.03616).
We construct classical algorithms computing an approximation of the ground state energy of an arbitrary kkk-local Hamiltonian acting on nnn qubits. We first consider the setting where a good ``guiding state'' is available, which is the main setting where quantum algorithms are expected to achieve an exponential speedup over classical methods. We show that a constant approximation (i.e., an approximation with constant relative accuracy) of the ground state energy can be computed classically in poly(1/χ,n)\mathrm{poly}\left(1/χ,n\right)poly(1/χ,n) time and poly(n)\mathrm{poly}(n)poly(n) space, where χχχ denotes the overlap between the guiding state and the ground state (as in prior works in dequantization, we assume sample-and-query access to the guiding state). This gives a significant improvement over the recent classical algorithm by Gharibian and Le Gall (SICOMP 2023), and matches (up a to polynomial overhead) both the time and space complexities of quantum algorithms for constant approximation of the ground state energy. We also obtain classical algorithms for higher-precision approximation. For the setting where no guided state is given (i.e., the standard version of the local Hamiltonian problem), we obtain a classical algorithm computing a constant approximation of the ground state energy in 2O(n)2^{O(n)}2O(n) time and poly(n)\mathrm{poly}(n)poly(n) space. To our knowledge, before this work it was unknown how to classically achieve these bounds simultaneously, even for constant approximation. We also discuss complexity-theoretic aspects of our results.
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.
Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with 6-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to 1/2 with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.
The low-temperature properties of interacting quantum systems are believed to require exponential resources to compute in the general case. Quantifying the extent to which such properties can be approximated using efficient algorithms remains a significant open challenge. Here, we consider the task of approximating the ground state energy of two-local quantum Hamiltonians with bounded-degree interaction graphs. Most existing algorithms optimize the energy over the set of product states. We propose and analyze a family of shallow quantum circuits that can be used to improve the approximation ratio achieved by a given product state. The algorithm takes as input an n-qubit product state with variance Var and improves its energy by an amount proportional to Var^{2}/n. In a typical case, this results in an extensive improvement in the estimated energy. We extend our results to k-local Hamiltonians and entangled initial states.