Adiabatic optimization versus diffusion Monte Carlo

Abstract

Most experimental and theoretical studies of adiabatic optimization use stoquastic Hamiltonians, whose ground states are expressible using only real nonnegative amplitudes. This raises a question as to whether classical Monte Carlo methods can simulate stoquastic adiabatic algorithms with polynomial overhead. Here, we analyze diffusion Monte Carlo algorithms. We argue that, based on differences between L1 and L2 normalized states, these algorithms suffer from certain obstructions preventing them from efficiently simulating stoquastic adiabatic evolution in generality. In practice however, we obtain good performance by introducing a method that we call Substochastic Monte Carlo. In fact, our simulations are good classical optimization algorithms in their own right, competitive with the best previously known heuristic solvers for MAX-k-SAT at k=2,3,4.

13 pages plus appendices. Published version

References in corpus (17)

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• Bounds for the adiabatic approximation with applications to quantum computation
• What is the Computational Value of Finite Range Tunneling?
• Anderson localization casts clouds over adiabatic quantum optimization
• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• First Order Quantum Phase Transition in Adiabatic Quantum Computation
• Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
• Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
• Benchmarking a quantum annealing processor with the time-to-target metric
• Quantum Adiabatic Evolution Algorithms with Different Paths
• Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• A note on the switching adiabatic theorem
• Effect of Local Minima on Adiabatic Quantum Optimization
• Quantum Monte Carlo Simulations of Tunneling in Quantum Adiabatic Optimization
• borealis - A generalized global update algorithm for Boolean optimization problems

Cited by in corpus (27)

• Quantum Computing in the NISQ era and beyond
• Adiabatic Quantum Computing
• Perspectives of quantum annealing: Methods and implementations
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Benchmarking Quantum Annealing Controls with Portfolio Optimization
• Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
• Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
• Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
• Automated Design of Pulse Sequences for Magnetic Resonance Fingerprinting using Physics-Inspired Optimization
• The Power of Adiabatic Quantum Computation with No Sign Problem
• Quantum Monte Carlo tunneling from quantum chemistry to quantum annealing
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Understanding Quantum Tunneling using Diffusion Monte Carlo Simulations
• The Effects of the Problem Hamiltonian Parameters on the Minimum Spectral Gap in Adiabatic Quantum Optimization
• A double-slit proposal for quantum annealing
• Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT
• Diffusion Monte Carlo approach versus adiabatic computation for local Hamiltonians
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• Tunneling in projective quantum Monte Carlo simulations with guiding wave functions
• Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians
• Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians
• Modernizing Quantum Annealing II: Genetic algorithms with the Inference Primitive Formalism
• Improving nonstoquastic quantum annealing with spin-reversal transformations
• Polynomial Time Algorithms for Estimating Spectra of Adiabatic Hamiltonians
• Approximate optimization of MAXCUT with a local spin algorithm
• A Novel AQC Factoring Algorithm
• Classical Simulation of High Temperature Quantum Ising Models