The Quantum Monte Carlo (QMC) method has served as a powerful practical tool for computational condensed matter physics research. While it has been applied to systems with ~10^5 qubits interacting with Heisenberg interaction on a square lattice [1], and thus is empirically extremely efficient, rigorous proof has been lacking on the theoretical guarantee of convergence times.
Recently, it has been explicitly posed as an open question [2] what the computational complexity of the antiferromagnetic (AFM) Heisenberg model ground state energy (also known as "quantum Max Cut" in the complexity community) calculation is for bipartite graphs. The question comes from a broader context of understanding the complexity of various physically motivated Hamiltonian families, and in a sense characterizing which ones are "more quantum". Although QMC is empirically efficient on bipartite AFM Heisenberg models, a theoretical proof will require a spectral gap type of argument for the Markov chain stochastic matrix, which is in general difficult, and is partially the reason why proofs have been lacking.
In this talk, I will explain our recent results on proving fast-mixing (polynomial upper bound on the convergence) of QMC algorithms for some sign-problem free (stoquastic) systems: AFM Heisenberg models on bipartite graphs with large imbalance [3] , and AFM XY models on arbitrary bipartite graphs [4]. I will explain the key ideas of the proof technique we use [5] and discuss the physical implication that is implied by our results, such as lack of certain phase transitions.
[1] For example, B. Zhao, J. Takahashi, & A. W. Sandvik, PRL 125 (25), 257204 (2020).
[2] S. Gharibian, "Guest Column: The 7 faces of quantum NP" ACM SIGACT News 54, 54 (2024). Open question 3.4
[3] J. Takahashi, S. Slezak, & E. Crosson, arXiv:2411.01452, Talk at QIP 2025
[4] C. Rayudu & J. Takahashi, arXiv:2509.21683.
[5] M. Jerrum & A. Sinclair, SIAM J. Comput. 18, 1149 (1989).