arXiv:2610.03670
Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders
Stuart Wayland, Zackary Jorquera, Alexandra Kolla
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.
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