Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders

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 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 epsilon in time polynomial in n and 1/epsilon. 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.