Quantum Monte Carlo Simulations of Tunneling in Quantum Adiabatic Optimization

Abstract

We explore to what extent path-integral quantum Monte Carlo methods can efficiently simulate the tunneling behavior of quantum adiabatic optimization algorithms. Specifically we look at symmetric cost functions defined over n bits with a single potential barrier that a successful optimization algorithm will have to tunnel through. The height and width of this barrier depend on n, and by tuning these dependencies, we can make the optimization algorithm succeed or fail in polynomial time. In this article we compare the strength of quantum adiabatic tunneling with that of path-integral quantum Monte Carlo methods. We find numerical evidence that quantum Monte Carlo algorithms will succeed in the same regimes where quantum adiabatic optimization succeeds.

10 pages, 11 figures

References in corpus (1)

• Bounds for the adiabatic approximation with applications to quantum computation

Cited by in corpus (20)

• Adiabatic Quantum Computing
• Scaling advantage in quantum simulation of geometrically frustrated magnets
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• Adiabatic optimization versus diffusion Monte Carlo
• An Application of Quantum Annealing Computing to Seismic Inversion
• Understanding Quantum Tunneling using Diffusion Monte Carlo Simulations
• Spectral Gap Analysis for Efficient Tunneling in Quantum Adiabatic Optimization
• Practical designs for permutation symmetric problem Hamiltonians on hypercubes
• Supervised learning of random quantum circuits via scalable neural networks
• Tunneling in projective quantum Monte Carlo simulations with guiding wave functions
• Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians
• Obstacles to quantum annealing in a planar embedding of XORSAT
• The performance of the quantum adiabatic algorithm on spike Hamiltonians
• Zero-temperature Monte Carlo simulations of two-dimensional quantum spin glasses guided by neural network states
• Simultaneous Stoquasticity
• Discrepancies between Asymptotic and Exact Spectral Gap Analyses of Quantum Adiabatic Barrier Tunneling
• Statistical Analysis of Quantum Annealing