Analytical solution for low energy state estimation by quantum annealing to arbitrary Ising spin Hamiltonian

We point to the existence of an analytical solution to a general quantum annealing (QA) problem of finding low energy states of an arbitrary Ising spin Hamiltonian H I by implementing time evolution with a Hamiltonian H(t) = H I + g(t)H t . We will assume that the nonadiabatic annealing protocol is defined by a specific decaying coupling g(t) and a specific mixing Hamiltonian H t that make the model analytically solvable arbitrarily far from the adiabatic regime. In specific cases of H I , the solution shows the possibility of a considerable quantum speedup of finding the Ising ground state. We then compare predictions of our solution to results of numerical simulations, and argue that the solvable QA protocol produces the optimal performance in the limit of maximal complexity of the computational problem. Our solution demonstrates for the most complex spin glasses a power-law energy relaxation with the annealing time T and uncorrelated from H I annealing schedule. This proves the possibility for spin glasses of a faster than ∼ 1/log β T energy relaxation.