2017/09/30 by Jacob Bringewatt, W. Dorland, William Dorland +2 · 12 citations
Computer Science · Materials Science · Mathematics · Physics and Astronomy · #Adiabatic process #Adiabatic quantum computation #Advanced Chemical Physics Studies #Counterexample #Diffusion #Diffusion Monte Carlo #Discrete mathematics #Dynamic Monte Carlo method #Hybrid Monte Carlo #Kinetic Monte Carlo #Machine Learning in Materials Science #Markov chain Monte Carlo #Mathematics #Monte Carlo integration #Monte Carlo method #Monte Carlo method in statistical physics #Monte Carlo molecular modeling #Path integral Monte Carlo #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Monte Carlo #Quantum annealing #Quantum computer #Quantum mechanics #Quasi-Monte Carlo method #Statistical physics #quant-ph
paper · pdf · doi:10.1103/physreva.97.022323
published in Physical Review A 97(2) (American Physical Society) · 7 pages, 5 figures, updated organization, typos, journal reference added (results unchanged)
openalex publication_date 2018/02/15 · arxiv created 2018/02/19 · arxiv updated 2018/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Most research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians, whose ground states can be expressed with only real non-negative amplitudes and thus for whom destructive interference is not manifest. This raises the question of whether classical Monte Carlo algorithms can efficiently simulate quantum adiabatic optimization with stoquastic Hamiltonians. Recent results have given counterexamples in which path-integral and diffusion Monte Carlo fail to do so. However, most adiabatic optimization algorithms, such as for solving MAX-k-SAT problems, use k-local Hamiltonians, whereas our previous counterexample for diffusion Monte Carlo involved n-body interactions. Here we present a 6-local counterexample which demonstrates that even for these local Hamiltonians there are cases where diffusion Monte Carlo cannot efficiently simulate quantum adiabatic optimization. Furthermore, we perform empirical testing of diffusion Monte Carlo on a standard well-studied class of permutation-symmetric tunneling problems and similarly find large advantages for quantum optimization over diffusion Monte Carlo.