Dynamics of reverse annealing for the fully-connected p-spin model

by Yu Yamashiro, Masaki Ohkuwa, Hidetoshi Nishimori, Daniel A. Lidar

Reverse annealing is a relatively new variant of quantum annealing, in which one starts from a classical state and increases and then decreases the amplitude of the transverse field, in the hope of finding a better classical state than the initial state for a given optimization problem. We numerically study the unitary quantum dynamics of reverse annealing for the mean-field-type p-spin model and show that the results are consistent with the predictions of equilibrium statistical mechanics. In particular, we corroborate the equilibrium analysis prediction that reverse annealing provides an exponential speedup over conventional quantum annealing in terms of solving the p-spin model. This lends support to the expectation that equilibrium analyses are effective at revealing essential aspects of the dynamics of quantum annealing. We also compare the results of quantum dynamics with the corresponding classical dynamics, to reveal their similarities and differences. We distinguish between two reverse annealing protocols we call adiabatic and iterated reverse annealing. We further show that iterated reverse annealing, as has been realized in the D-Wave device, is ineffective in the case of the p-spin model, but note that a recently-introduced protocol ("h-gain"), which implements adiabatic reverse annealing, may lead to improved performance.

Message-passing Algorithm of Quantum Annealing with Nonstoquastic Hamiltonian

by Masayuki Ohzeki

Quantum annealing (QA) is a generic method for solving optimization problems using fictitious quantum fluctuation. The current device performing QA involves controlling the transverse field; it is classically simulatable by using the standard technique for mapping the quantum spin systems to the classical ones. In this sense, the current system for QA is not powerful despite utilizing quantum fluctuation. Hence, we developed a system with a time-dependent Hamiltonian consisting of a combination of the formulated Ising model and the “driver” Hamiltonian with only quantum fluctuation. In the previous study, for a fully connected spin model, quantum fluctuation can be addressed in a relatively simple way. We proved that the fully connected antiferromagnetic interaction can be transformed into a fluctuating transverse field and is thus classically simulatable at sufficiently low temperatures. Using the fluctuating transverse field, we established several ways to simulate part of the nonstoquastic Hamiltonian on classical computers. We formulated a message-passing algorithm in the present study. This algorithm is capable of assessing the performance of QA with part of the nonstoquastic Hamiltonian having a large number of spins. In other words, we developed a different approach for simulating the nonstoquastic Hamiltonian without using the quantum Monte Carlo technique. Our results were validated by comparison to the results obtained by the replica method.