{"id":"arxiv/2610.03670","url":"https://arxiv.org/abs/2610.03670","tags":["quant-ph"],"score":0,"title":"Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders","domain":"quant-ph","source":"arxiv","authors":["Stuart Wayland","Zackary Jorquera","Alexandra Kolla"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-02","reactions":{}}