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.

Comments
47 pages

Related papers

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

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

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

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

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•0 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.
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→∞.
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.
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 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.
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.