BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Proving polynomial-time mixing of the Quantum Monte Carlo method -
  Jun Takahashi\, University of Tokyo
DTSTART:20260205T141500Z
DTEND:20260205T153000Z
UID:TALK243949@talks.cam.ac.uk
CONTACT:Alex Turzillo
DESCRIPTION: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 Heisenbe
 rg interaction on a square lattice [1]\, and thus is empirically extremely
  efficient\, rigorous proof has been lacking on the theoretical guarantee 
 of convergence times. \nRecently\, 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 que
 stion comes from a broader context of understanding the complexity of vari
 ous physically motivated Hamiltonian families\, and in a sense characteriz
 ing which ones are "more quantum". Although QMC is empirically efficient o
 n bipartite AFM Heisenberg models\, a theoretical proof will require a spe
 ctral 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. \nIn this talk\, I will explain our recent results on proving fa
 st-mixing (polynomial upper bound on the convergence) of QMC algorithms fo
 r some sign-problem free (stoquastic) systems: AFM Heisenberg models on bi
 partite 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 res
 ults\, such as lack of certain phase transitions. \n\n[1] For example\, B.
  Zhao\, J. Takahashi\, & A. W. Sandvik\, PRL 125 (25)\, 257204 (2020). \n[
 2] S. Gharibian\, "Guest Column: The 7 faces of quantum NP" ACM SIGACT New
 s 54\, 54 (2024). Open question 3.4\n[3] J. Takahashi\, S. Slezak\, & E. C
 rosson\, arXiv:2411.01452\, Talk at QIP 2025\n[4] C. Rayudu & J. Takahashi
 \, arXiv:2509.21683. \n[5] M. Jerrum & A. Sinclair\, SIAM J. Comput. 18\, 
 1149 (1989). 
LOCATION:Center for Mathematical Sciences\, MR2
END:VEVENT
END:VCALENDAR