Incollection,

Annealing Schedules for Quantum Annealing

, and .
Abstract Book of the XXIII IUPAP International Conference on Statistical Physics, Genova, Italy, (9-13 July 2007)

Abstract

Quantum annealing (QA) attracts much attention as a novel algorithm for optimization problems. This method is based on the adiabatic theorem of quantum mechanics. The non-trivial target state is expected to be obtained from the trivial initial state after the adiabatic evolution. However, too rapid change of the Hamiltonian causes the non-adiavatic transition, and then QA misses the desired solution. Therefore an important problem is how quickly to change the Hamiltonian. We prove, using the adiabatic theorem, that a power decay of the transverse field is sufficient to guarantee the convergence of QA for the transverse field Ising model. The power is in inverse proportion to the system size. This annealing schedule is in agreement with the previous known result, which were obtained via stochastic approaches. It is remarkable that this annealing rate is faster than that for a well-known classical algorithm, simulated annealing. In addition, we propose faster annealing schedules for QA with finite evolution time. It is known that an error rate of the adiabatic evolution is inversely proportional to the square of the annealing time when the Hamiltonian depends linearly on time. We show that the upper bound of the first-order term of the error rate is determined only by the information at the initial and final times. Our new annealing schedules drop this term, thus bring a faster rate of the error decrease.

Tags

Users

  • @statphys23

Comments and Reviews