Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders
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-1/2 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 ε in time polynomial in n and 1/ε. 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.
Related
- The quantum-classical bipartite universe and the logical emergence of ℏ from classical temporality
- Classical State Preparation for Variational Quantum Algorithms via Reinforcement Learning
- Provable Classical and Quantum Local Algorithms for Max-k-Cut and Quantum Advantage at Moderate Girth
- Encoding universal quantum computation into quantized Berry phases: Hardness results and classical algorithms
- Exponential quantum speedup for 𝔽3n-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
BibTeX
@misc{wayland2026classical,
title = {{Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders}},
author = {Stuart Wayland and Zackary Jorquera and Alexandra Kolla},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03670},
eprint = {2610.03670},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03670},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders
AU - Stuart Wayland
AU - Zackary Jorquera
AU - Alexandra Kolla
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03670
UR - https://arxiv.org/abs/2610.03670
AB - 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-1/2 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 ε in time polynomial in n and 1/ε. 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.
ER -