  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.
