Simulated Quantum Annealing is Efficient on the Spike Hamiltonian

Abstract

In this work we study the convergence of a classical algorithm called Simulated Quantum Annealing (SQA) on the Spike Hamiltonian, a specific toy model Hamiltonian for quantum-mechanical tunneling introduced by [FGG02]. This toy model Hamiltonian encodes a simple bit-symmetric cost function f in the computational basis, and is used to emulate local minima in more complex optimization problems. In previous work [CH16] showed that SQA runs in polynomial time in much of the regime of spikes that QA does, pointing to evidence against an exponential speedup through tunneling. In this paper we extend their analysis to the remaining polynomial regime of energy gaps of the spike Hamiltonian, to show that indeed QA presents no exponential speedup with respect to SQA on this family of toy models.

References in corpus (7)

• Quantum annealing with more than one hundred qubits
• Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• Merlin-Arthur Games and Stoquastic Complexity
• The Power of Adiabatic Quantum Computation with No Sign Problem
• Spectral Gap Analysis for Efficient Tunneling in Quantum Adiabatic Optimization
• Tunneling through high energy barriers in simulated quantum annealing