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:2506.08547

A Refined Algorithm For the EPR model

Wenxuan Tao, Fen Zuo

Published Jun 10, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2506.08547

Related papers

An Improved Quantum Max Cut Approximation via Maximum Matching

Eunou Lee, Ojas Parekh

Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Eunou Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.

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

An improved Quantum Max Cut approximation via matching

Eunou Lee, Parekh, Ojas

Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.

arXiv:2401.03616•Jan 8, 2024•0 citations

Testing APS conjecture on regular graphs

Wenxuan Tao, Fen Zuo

The maximum energy of the EPR model on a weighted graph is known to be upper-bounded by the sum of the total weight and the value of maximum-weight fractional matching~(MWFM). Recently, Apte, Parekh and Sud~(APS) conjecture that the bound could be strengthened by replacing MWFM with maximum weight matching~(MWM). Here we test this conjecture on a special class of regular graphs that Henning and Yeo constructed many years ago. On this class of regular graphs, MWMs achieve tight lower bounds. As for the maximum energy of the EPR model, we have recently devised a new algorithm called Fractional Entanglement Distribution~(FED) based on quasi-homogeneous fractional matchings, which could achieve rather high accuracy. Applying the FED algorithm to the EPR model on Henning-Yeo graphs, we could thus obtain energy as high as possible and matching value as low as possible, and then make high-precision tests of the APS conjecture. Nevertheless, our numerical results do not show any evidence that the APS conjecture could be violated.

arXiv:2507.10050•Jul 14, 2025•0 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•0 citations

Approximation Algorithms for Quantum Max-ddd-Cut

Charlie Carlson, Zackary Jorquera, Alexandra Kolla +2 more

We initiate the algorithmic study of the Quantum Max-$d$-Cut problem, a quantum generalization of the well-known Max-$d$-Cut problem. The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions. Equivalently, this problem is physically motivated by the $SU(d)$-Heisenberg model, a spin glass model that generalized the well-known Heisenberg model over qudits. We develop a polynomial-time randomized approximation algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees. Moreover, we prove the tightness of our analysis by presenting an algorithmic gap instance for Quantum Max-d-Cut problem with $d \geq 3$.

arXiv:2309.10957•Sep 19, 2023•0 citations

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
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.
Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Eunou Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.
Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.
The maximum energy of the EPR model on a weighted graph is known to be upper-bounded by the sum of the total weight and the value of maximum-weight fractional matching~(MWFM). Recently, Apte, Parekh and Sud~(APS) conjecture that the bound could be strengthened by replacing MWFM with maximum weight matching~(MWM). Here we test this conjecture on a special class of regular graphs that Henning and Yeo constructed many years ago. On this class of regular graphs, MWMs achieve tight lower bounds. As for the maximum energy of the EPR model, we have recently devised a new algorithm called Fractional Entanglement Distribution~(FED) based on quasi-homogeneous fractional matchings, which could achieve rather high accuracy. Applying the FED algorithm to the EPR model on Henning-Yeo graphs, we could thus obtain energy as high as possible and matching value as low as possible, and then make high-precision tests of the APS conjecture. Nevertheless, our numerical results do not show any evidence that the APS conjecture could be violated.
We initiate the algorithmic study of the Quantum Max-ddd-Cut problem, a quantum generalization of the well-known Max-ddd-Cut problem. The Quantum Max-ddd-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, ddd-dimensional qudits over all local interactions. Equivalently, this problem is physically motivated by the SU(d)SU(d)SU(d)-Heisenberg model, a spin glass model that generalized the well-known Heisenberg model over qudits. We develop a polynomial-time randomized approximation algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees. Moreover, we prove the tightness of our analysis by presenting an algorithmic gap instance for Quantum Max-d-Cut problem with d≥3d \geq 3d≥3.
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).