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

Testing APS conjecture on regular graphs

Wenxuan Tao, Fen Zuo

Published Jul 14, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2507.10050

Related papers

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

A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs

Kourosh Mirsohi, Sandy Irani, Michael T. Goodrich

Quantum speed-ups have been obtained for many fundamental graph problems, including most variants of matching. A notable exception, however, is the maximum-weight perfect matching (MWPM) problem in general graphs with integer edge weights, which is arguably the most challenging variant of matching. We present a quantum algorithm for MWPM in general graphs that runs in \( \widetilde{O}(n m^{2/3}\log W) \) time, where $W$ is an upper bound on the magnitude of the edge weights. This is an improvement over the best known classical combinatorial bound of \( \widetilde{O}(m\sqrt n \log W) \) in the dense regime, where $m\ge n^{3/2}$. To the best of our knowledge, this is the first quantum algorithm to obtain an asymptotic improvement over the best classical combinatorial algorithm for the MWPM problem in general graphs. The running time of our method accounts for QRAM initialization and access overheads up to polylogarithmic factors, as well as all classical updates to the data structures. At a high level, our algorithm is based on a classical framework due to Duan, Pettie, and Su, but our algorithm requires replacing certain classical tasks with quantum methods, alternative analysis of classical procedures, and the use of alternative data structures that can be implemented effectively in the QRAM model.

cs.DSCross-listedarXiv:2609.39457•Oct 1, 2026•0 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

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

Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut

Ainesh Bakshi, Arpon Basu, Pravesh Kothari +1 more

We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level $k$ Kikuchi graph of any graph $G$ with $m$ edges is at most $m+k$. This confirms four recent conjectures of Apte, Parekh, and Sud. As applications, we obtain that tensor products of one and two qubit product states achieve an approximation ratio of $5/8$ for Quantum Max Cut and $5/7$ for the XY Hamiltonian. Moreover, combining our bounds with the algorithms analyzed by Apte, Parekh, and Sud, yields efficient algorithms achieving an approximation ratio of $0.614$ for Quantum Max Cut and $0.674$ for the XY Hamiltonian. Finally, we also make modest progress on Brouwer's conjecture and improve Lew's bound on the sum of the top-$k$ eigenvalues of a Graph Laplacian.

quant-pharXiv:2605.14994•May 15, 2026•0 citations

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
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.
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.
Quantum speed-ups have been obtained for many fundamental graph problems, including most variants of matching. A notable exception, however, is the maximum-weight perfect matching (MWPM) problem in general graphs with integer edge weights, which is arguably the most challenging variant of matching. We present a quantum algorithm for MWPM in general graphs that runs in O~(nm2/3log⁡W) \widetilde{O}(n m^{2/3}\log W) O(nm2/3logW) time, where WWW is an upper bound on the magnitude of the edge weights. This is an improvement over the best known classical combinatorial bound of O~(mnlog⁡W) \widetilde{O}(m\sqrt n \log W) O(mn​logW) in the dense regime, where m≥n3/2m\ge n^{3/2}m≥n3/2. To the best of our knowledge, this is the first quantum algorithm to obtain an asymptotic improvement over the best classical combinatorial algorithm for the MWPM problem in general graphs. The running time of our method accounts for QRAM initialization and access overheads up to polylogarithmic factors, as well as all classical updates to the data structures. At a high level, our algorithm is based on a classical framework due to Duan, Pettie, and Su, but our algorithm requires replacing certain classical tasks with quantum methods, alternative analysis of classical procedures, and the use of alternative data structures that can be implemented effectively in the QRAM model.
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 prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level kkk Kikuchi graph of any graph GGG with mmm edges is at most m+km+km+k. This confirms four recent conjectures of Apte, Parekh, and Sud. As applications, we obtain that tensor products of one and two qubit product states achieve an approximation ratio of 5/85/85/8 for Quantum Max Cut and 5/75/75/7 for the XY Hamiltonian. Moreover, combining our bounds with the algorithms analyzed by Apte, Parekh, and Sud, yields efficient algorithms achieving an approximation ratio of 0.6140.6140.614 for Quantum Max Cut and 0.6740.6740.674 for the XY Hamiltonian. Finally, we also make modest progress on Brouwer's conjecture and improve Lew's bound on the sum of the top-kkk eigenvalues of a Graph Laplacian.
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.