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

Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders

Stuart Wayland, Zackary Jorquera, Alexandra Kolla

quant-phSubmitted Oct 2, 2026• Announced Oct 5, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum Max-Cut is a well-studied local Hamiltonian problem for which the classical complexity of the bipartite case remains open. We give a polynomial-time classical randomized algorithm for the spin-$\tfrac12$ antiferromagnetic Heisenberg model, equivalently Quantum Max-Cut, on dense balanced bipartite expanders. This class includes $G(n,n,p)$ with high probability for every fixed $p>0$. The algorithm estimates the ground energy and any ground state edge correlation to additive error $\varepsilon$ in time polynomial in $n$ and $1/\varepsilon$. We construct a Markov chain on perfect matchings of the complete bipartite graph, each matching representing a product of singlets, that converges to the ground state, and use the expansion of the graph to show that polynomially many steps and samples of this chain suffice.

AI Summary

Bipartite Quantum Max-Cut, equivalently the spin-$\tfrac12$ antiferromagnetic Heisenberg ground-energy problem, is known to admit a quantum polynomial-time algorithm, but its classical complexity remains open. This paper gives a classical randomized algorithm for connected, balanced bipartite graphs with $n$ vertices per side, constant density $\hat p\ge p>0$, and degree deviations and doubly centered adjacency norm bounded by $C\sqrt{n\log n}$. This includes $G(n,n,p)$ with high probability at fixed density. The algorithm estimates any ground-state edge correlation to additive error $\varepsilon$, with failure probability at most $\delta$, in time $\mathrm{poly}(n)(n/\varepsilon)^{O(1/p)}(1+\log(1/\delta))$. Estimating and summing correlations also gives arbitrary additive accuracy for the total ground energy. For sufficiently large $n$, the spectral analysis establishes a singlet-sector gap $\gamma\ge pn/4$ and Lieb–Mattis starting-state overlap at least $\tfrac12e^{-(4/p+1)/2}$. The estimator samples reference walks on perfect matchings representing products of singlets, reweighting trajectories to implement Hamiltonian projection. A relative-second-moment bound controls sample complexity without proving mixing of a ground-state sampling chain. The spectral inputs follow from a representation-theoretic level decomposition, comparison of low levels with a quadratic bosonic model diagonalized by a Bogoliubov transformation, high-level energy bounds, and localization. The gap guarantee is only within the singlet sector. General bipartite graphs and sparse expanders remain unresolved: decreasing density worsens both trajectory-weight bounds and starting-state overlap. The stated analysis reaches density $\Theta(1/\log n)$ with quasipolynomial runtime.

No sign of AI-generated textAI use disclosedStrong assumptions
The authors used AI-based tools to find the original proof strategy. In particular, the connection to the Bogoliubov transformation was made by Claude. AI was also used in improving the presentation.

Error found: Theorem B incorrectly asserts its numerical spectral bounds for every graph in G(p,C): two K_{16,16} components joined by an edge of weight 0.1 belong to G(2/5,2) but have singlet-sector gap at most 2.15, below the claimed 3.2; the theorem needs a sufficiently-large-n qualification.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
47 pages

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 [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•Leibniz international proceedings in informatics•Jan 1, 2024•21 citations

The classical limit of Quantum Max-Cut

Vir B. Bulchandani, Stephen Piddock

It is well-known in physics that the limit of large quantum spin $S$ should be understood as a semiclassical limit. This raises the question of whether such emergent classicality facilitates the approximation of computationally hard quantum optimization problems, such as the local Hamiltonian problem. We demonstrate this explicitly for spin-$S$ generalizations of Quantum Max-Cut ($\mathrm{QMaxCut}_S$), equivalent to the problem of finding the ground state energy of an arbitrary spin-$S$ quantum Heisenberg antiferromagnet ($\mathrm{QHA}_S$). We prove that approximating the value of $\mathrm{QHA}_S$ to inverse polynomial accuracy is QMA-complete for all $S$, extending previous results for $S=1/2$. We also present two distinct families of classical approximation algorithms for $\mathrm{QMaxCut}_S$ based on rounding the output of a semidefinite program to a product of Bloch coherent states. The approximation ratios for both our proposed algorithms strictly increase with $S$ and converge to the Briët-Oliveira-Vallentin approximation ratio $α_{\mathrm{BOV}} \approx 0.956$ from below as $S \to \infty$.

arXiv:2401.12968•Jan 23, 2024•1 citation

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

A 0.651-approximation to quantum Max Cut via Rydberg atoms

Tomás Crosta, Matthieu Saubanere, Felix Huber

Quantum Max Cut, also known as the anti-ferromagnetic Heisenberg Hamiltonian, is a QMA-complete problem which serves as a benchmark for approximation algorithms in quantum physics. Here we develop a hybrid approximation algorithm to quantum Max Cut, which uses the natural quantum dynamics of Rydberg atom systems in combination with semidefinite programming and randomized rounding. It achieves a conditional approximation ratio of $0.651$, compared to the best-known ratio of $0.614$ that relies on semidefinite programming alone. The algorithm is robust in the sense that the advantage persists even if the annealing procedure of the Rydberg atom system obtains a state whose energy is only $89\%$ of its true ground state energy. Our approach opens a new route for hybrid quantum-classical algorithms that combine quantum with classical optimization methods.

quant-pharXiv:2606.27224•Jun 26, 2026•0 citations

Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs

Kunal Marwaha, Adrian She, James Sud

We design two variational algorithms to optimize specific 2-local Hamiltonians defined on graphs. Our algorithms are inspired by the Quantum Approximate Optimization Algorithm. We develop formulae to analyze the energy achieved by these algorithms with high probability over random regular graphs in the infinite-size limit, using techniques from [arXiv:2110.14206]. The complexity of evaluating these formulae scales exponentially with the number of layers of the algorithms, so our numerical evaluation is limited to a small constant number of layers. We compare these algorithms to simple classical approaches and a state-of-the-art worst-case algorithm. We find that the symmetry inherent to these specific variational algorithms presents a major \emph{obstacle} to successfully optimizing the Quantum MaxCut (QMC) Hamiltonian on general graphs. Nonetheless, the algorithms outperform known methods to optimize the EPR Hamiltonian of [arXiv:2209.02589] on random regular graphs, and the QMC Hamiltonian when the graphs are also bipartite. As a special case, we show that with just five layers of our algorithm, we can already prepare states within 1.62% error of the ground state energy for QMC on an infinite 1D ring, corresponding to the antiferromagnetic Heisenberg spin chain.

arXiv:2412.15147•Dec 19, 2024•6 citations

Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs

Sander Gribling, Lennart Sinjorgo, Renata Sotirov

We study polynomial-time approximation algorithms for the Quantum Max-Cut (QMC) problem. Given an edge-weighted graph $G$ on n vertices, the QMC problem is to determine the largest eigenvalue of a particular $2^n \times 2^n$ matrix that corresponds to $G$. We provide a sharpened analysis of the currently best-known QMC approximation algorithm for general graphs. This algorithm achieves an approximation ratio of $0.599$, which our analysis improves to $0.603$. Additionally, we propose two new approximation algorithms for the QMC problem on triangle-free and bipartite graphs, that achieve approximation ratios of $0.61383$ and $0.8162$, respectively. These are the best-known approximation ratios for their respective graph classes.

arXiv:2504.11120•Apr 15, 2025•17 citations
Quantum Max-Cut is a well-studied local Hamiltonian problem for which the classical complexity of the bipartite case remains open. We give a polynomial-time classical randomized algorithm for the spin-12\tfrac1221​ antiferromagnetic Heisenberg model, equivalently Quantum Max-Cut, on dense balanced bipartite expanders. This class includes G(n,n,p)G(n,n,p)G(n,n,p) with high probability for every fixed p>0p>0p>0. The algorithm estimates the ground energy and any ground state edge correlation to additive error ε\varepsilonε in time polynomial in nnn and 1/ε1/\varepsilon1/ε. We construct a Markov chain on perfect matchings of the complete bipartite graph, each matching representing a product of singlets, that converges to the ground state, and use the expansion of the graph to show that polynomially many steps and samples of this chain suffice.
Bipartite Quantum Max-Cut, equivalently the spin-12\tfrac1221​ antiferromagnetic Heisenberg ground-energy problem, is known to admit a quantum polynomial-time algorithm, but its classical complexity remains open. This paper gives a classical randomized algorithm for connected, balanced bipartite graphs with nnn vertices per side, constant density p^≥p>0\hat p\ge p>0p^​≥p>0, and degree deviations and doubly centered adjacency norm bounded by Cnlog⁡nC\sqrt{n\log n}Cnlogn​. This includes G(n,n,p)G(n,n,p)G(n,n,p) with high probability at fixed density.
The algorithm estimates any ground-state edge correlation to additive error ε\varepsilonε, with failure probability at most δ\deltaδ, in time poly(n)(n/ε)O(1/p)(1+log⁡(1/δ))\mathrm{poly}(n)(n/\varepsilon)^{O(1/p)}(1+\log(1/\delta))poly(n)(n/ε)O(1/p)(1+log(1/δ)). Estimating and summing correlations also gives arbitrary additive accuracy for the total ground energy. For sufficiently large nnn, the spectral analysis establishes a singlet-sector gap γ≥pn/4\gamma\ge pn/4γ≥pn/4 and Lieb–Mattis starting-state overlap at least 12e−(4/p+1)/2\tfrac12e^{-(4/p+1)/2}21​e−(4/p+1)/2.
The estimator samples reference walks on perfect matchings representing products of singlets, reweighting trajectories to implement Hamiltonian projection. A relative-second-moment bound controls sample complexity without proving mixing of a ground-state sampling chain. The spectral inputs follow from a representation-theoretic level decomposition, comparison of low levels with a quadratic bosonic model diagonalized by a Bogoliubov transformation, high-level energy bounds, and localization.
The gap guarantee is only within the singlet sector. General bipartite graphs and sparse expanders remain unresolved: decreasing density worsens both trajectory-weight bounds and starting-state overlap. The stated analysis reaches density Θ(1/log⁡n)\Theta(1/\log n)Θ(1/logn) with quasipolynomial runtime.
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.
It is well-known in physics that the limit of large quantum spin SSS should be understood as a semiclassical limit. This raises the question of whether such emergent classicality facilitates the approximation of computationally hard quantum optimization problems, such as the local Hamiltonian problem. We demonstrate this explicitly for spin-SSS generalizations of Quantum Max-Cut (QMaxCutS\mathrm{QMaxCut}_SQMaxCutS​), equivalent to the problem of finding the ground state energy of an arbitrary spin-SSS quantum Heisenberg antiferromagnet (QHAS\mathrm{QHA}_SQHAS​). We prove that approximating the value of QHAS\mathrm{QHA}_SQHAS​ to inverse polynomial accuracy is QMA-complete for all SSS, extending previous results for S=1/2S=1/2S=1/2. We also present two distinct families of classical approximation algorithms for QMaxCutS\mathrm{QMaxCut}_SQMaxCutS​ based on rounding the output of a semidefinite program to a product of Bloch coherent states. The approximation ratios for both our proposed algorithms strictly increase with SSS and converge to the Briët-Oliveira-Vallentin approximation ratio αBOV≈0.956α_{\mathrm{BOV}} \approx 0.956αBOV​≈0.956 from below as S→∞S \to \inftyS→∞.
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.
Quantum Max Cut, also known as the anti-ferromagnetic Heisenberg Hamiltonian, is a QMA-complete problem which serves as a benchmark for approximation algorithms in quantum physics. Here we develop a hybrid approximation algorithm to quantum Max Cut, which uses the natural quantum dynamics of Rydberg atom systems in combination with semidefinite programming and randomized rounding. It achieves a conditional approximation ratio of 0.6510.6510.651, compared to the best-known ratio of 0.6140.6140.614 that relies on semidefinite programming alone. The algorithm is robust in the sense that the advantage persists even if the annealing procedure of the Rydberg atom system obtains a state whose energy is only 89%89\%89% of its true ground state energy. Our approach opens a new route for hybrid quantum-classical algorithms that combine quantum with classical optimization methods.
We design two variational algorithms to optimize specific 2-local Hamiltonians defined on graphs. Our algorithms are inspired by the Quantum Approximate Optimization Algorithm. We develop formulae to analyze the energy achieved by these algorithms with high probability over random regular graphs in the infinite-size limit, using techniques from [arXiv:2110.14206]. The complexity of evaluating these formulae scales exponentially with the number of layers of the algorithms, so our numerical evaluation is limited to a small constant number of layers. We compare these algorithms to simple classical approaches and a state-of-the-art worst-case algorithm. We find that the symmetry inherent to these specific variational algorithms presents a major \emph{obstacle} to successfully optimizing the Quantum MaxCut (QMC) Hamiltonian on general graphs. Nonetheless, the algorithms outperform known methods to optimize the EPR Hamiltonian of [arXiv:2209.02589] on random regular graphs, and the QMC Hamiltonian when the graphs are also bipartite. As a special case, we show that with just five layers of our algorithm, we can already prepare states within 1.62% error of the ground state energy for QMC on an infinite 1D ring, corresponding to the antiferromagnetic Heisenberg spin chain.
We study polynomial-time approximation algorithms for the Quantum Max-Cut (QMC) problem. Given an edge-weighted graph GGG on n vertices, the QMC problem is to determine the largest eigenvalue of a particular 2n×2n2^n \times 2^n2n×2n matrix that corresponds to GGG. We provide a sharpened analysis of the currently best-known QMC approximation algorithm for general graphs. This algorithm achieves an approximation ratio of 0.5990.5990.599, which our analysis improves to 0.6030.6030.603. Additionally, we propose two new approximation algorithms for the QMC problem on triangle-free and bipartite graphs, that achieve approximation ratios of 0.613830.613830.61383 and 0.81620.81620.8162, respectively. These are the best-known approximation ratios for their respective graph classes.