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:2512.09896 · Leibniz international proceedings in informatics

A 0.8395-approximation algorithm for the EPR problem

Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, Lennart Sinjorgo, James Sud

quant-phcs.DSSubmitted Dec 10, 2025• Announced Dec 11, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
27 pages

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•0 citations

An Improved Approximation Algorithm for Quantum Max-Cut on Triangle-Free Graphs

Robbie King

We give an approximation algorithm for Quantum Max-Cut which works by rounding an SDP relaxation to an entangled quantum state. The SDP is used to choose the parameters of a variational quantum circuit. The entangled state is then represented as the quantum circuit applied to a product state. It achieves an approximation ratio of 0.582 on triangle-free graphs. The previous best algorithms of Anshu, Gosset, Morenz, and Parekh, Thompson achieved approximation ratios of 0.531 and 0.533 respectively. In addition, we study the EPR Hamiltonian, which we argue is a natural intermediate problem which isolates some key quantum features of local Hamiltonian problems. For the EPR Hamiltonian, we give an approximation algorithm with approximation ratio 1/2 on all graphs.

arXiv:2209.02589•Quantum•Nov 9, 2023•11 citations

Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians

Zackary Jorquera, Alexandra Kolla, Steven Kordonowy +2 more

We prove new monogamy of entanglement bounds for two-local qudit Hamiltonians of rank-one projectors without one-local terms. In particular, we certify the maximum energy in terms of the maximum matching of the underlying interaction graph via low-degree sum-of-squares proofs. Algorithmically, we show that a simple matching-based algorithm approximates the maximum energy to at least 1 / d for general graphs and to at least 1 / d + Θ ( 1 / D ) for graphs with bounded degree, D . This outperforms random assignment, which, in expectation, achieves energy of only 1 / d 2 of the maximum energy for general graphs. Notably, on D -regular graphs with degree, D ≤ 5 , and for any local dimension, d , we show that this simple matching-based algorithm has an approximation guarantee of 1 / 2 . Lastly, when d = 2 , we present an algorithm achieving an approximation guarantee of 0.595 , beating that of \cite{parekh_optimal_2022}, which gave an approximation ratio of 1 / 2 .

arXiv:2410.15544•Quantum•Apr 28, 2026•0 citations

Improved Approximation Algorithms for the EPR Hamiltonian

Ju, Nathan, Nagda, Ansh

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].

Leibniz international proceedings in informatics•Jan 1, 2025•0 citations

Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings

Anuj Apte, Eunou Lee, Kunal Marwaha +2 more

We introduce a $0.611$-approximation algorithm for Quantum MaxCut and a $\frac{1+\sqrt{5}}{4} \approx 0.809$-approximation algorithm for the EPR Hamiltonian of [arXiv:2209.02589]. A novel ingredient in both of these algorithms is to partially entangle pairs of qubits associated to edges in a matching, while preserving the direction of their single-qubit Bloch vectors. This allows us to interpolate between product states and matching-based states with a tunable parameter.

quant-pharXiv:2504.15276•Apr 22, 2025

A Refined Algorithm For the EPR model

Wenxuan Tao, Fen Zuo

The Einstein-Podolsky-Rosen~(EPR) model is an analogous model of the anti-ferromagnetic Heisenberg model or the equivalent quantum maximum-cut problem, proposed by R. King two years ago. Adjacent qubits in the model prefer symmetric EPR/Bell parings rather than the antisymmetric one, in order to maximize the energy. Recently, two groups independently develop specific algorithms for the highest-energy state with approximation ratio $\frac{1+\sqrt{5}}{4}\approx.809$, based on maximum fractional matchings. Here we try to refine one of the two algorithms by devising homogeneous/quasi-homogeneous fractional matchings, with the aim to distribute quantum entanglement as much as possible. For regular graphs $G_d$, we immediately obtain increasing approximation ratios $r_d$ with $r_2=\frac{3+\sqrt{5}}{6}\approx.872$. For irregular graphs, we show such a refinement could still guarantee nice performance if the fractional matchings are chosen properly.

arXiv:2506.08547•Jun 10, 2025•0 citations
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.
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 give an approximation algorithm for Quantum Max-Cut which works by rounding an SDP relaxation to an entangled quantum state. The SDP is used to choose the parameters of a variational quantum circuit. The entangled state is then represented as the quantum circuit applied to a product state. It achieves an approximation ratio of 0.582 on triangle-free graphs. The previous best algorithms of Anshu, Gosset, Morenz, and Parekh, Thompson achieved approximation ratios of 0.531 and 0.533 respectively. In addition, we study the EPR Hamiltonian, which we argue is a natural intermediate problem which isolates some key quantum features of local Hamiltonian problems. For the EPR Hamiltonian, we give an approximation algorithm with approximation ratio 1/2 on all graphs.
We prove new monogamy of entanglement bounds for two-local qudit Hamiltonians of rank-one projectors without one-local terms. In particular, we certify the maximum energy in terms of the maximum matching of the underlying interaction graph via low-degree sum-of-squares proofs. Algorithmically, we show that a simple matching-based algorithm approximates the maximum energy to at least 1 / d for general graphs and to at least 1 / d + Θ ( 1 / D ) for graphs with bounded degree, D . This outperforms random assignment, which, in expectation, achieves energy of only 1 / d 2 of the maximum energy for general graphs. Notably, on D -regular graphs with degree, D ≤ 5 , and for any local dimension, d , we show that this simple matching-based algorithm has an approximation guarantee of 1 / 2 . Lastly, when d = 2 , we present an algorithm achieving an approximation guarantee of 0.595 , beating that of \cite{parekh_optimal_2022}, which gave an approximation ratio of 1 / 2 .
We introduce a 0.6110.6110.611-approximation algorithm for Quantum MaxCut and a 1+54≈0.809\frac{1+\sqrt{5}}{4} \approx 0.80941+5​​≈0.809-approximation algorithm for the EPR Hamiltonian of [arXiv:2209.02589]. A novel ingredient in both of these algorithms is to partially entangle pairs of qubits associated to edges in a matching, while preserving the direction of their single-qubit Bloch vectors. This allows us to interpolate between product states and matching-based states with a tunable parameter.
The Einstein-Podolsky-Rosen~(EPR) model is an analogous model of the anti-ferromagnetic Heisenberg model or the equivalent quantum maximum-cut problem, proposed by R. King two years ago. Adjacent qubits in the model prefer symmetric EPR/Bell parings rather than the antisymmetric one, in order to maximize the energy. Recently, two groups independently develop specific algorithms for the highest-energy state with approximation ratio 1+54≈.809\frac{1+\sqrt{5}}{4}\approx.80941+5​​≈.809, based on maximum fractional matchings. Here we try to refine one of the two algorithms by devising homogeneous/quasi-homogeneous fractional matchings, with the aim to distribute quantum entanglement as much as possible. For regular graphs GdG_dGd​, we immediately obtain increasing approximation ratios rdr_drd​ with r2=3+56≈.872r_2=\frac{3+\sqrt{5}}{6}\approx.872r2​=63+5​​≈.872. For irregular graphs, we show such a refinement could still guarantee nice performance if the fractional matchings are chosen properly.