Tunneling through high energy barriers in simulated quantum annealing

Abstract

We analyze the performance of simulated quantum annealing (SQA) on an optimization problem for which simulated classical annealing (SA) is provably inefficient because of a high energy barrier. We present evidence that SQA can pass through this barrier to find the global minimum efficiently. This demonstrates the potential for SQA to inherit some of the advantages of quantum annealing (QA), since this problem has been previously shown to be efficiently solvable by quantum adiabatic optimization.

References in corpus (4)

• Quantum annealing with more than one hundred qubits
• Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
• Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
• Monte Carlo simulation of stoquastic Hamiltonians

Cited by in corpus (5)

• Adiabatic Quantum Computing
• Practical designs for permutation symmetric problem Hamiltonians on hypercubes
• Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians
• Polynomial Time Algorithms for Estimating Spectra of Adiabatic Hamiltonians
• Simulated Quantum Annealing is Efficient on the Spike Hamiltonian