Reverse annealing, a variant of quantum annealing, is investigated by probing quantum transitions in a
p-spin model and comparing it with the predictions offered by equilibrium statistical mechanics. It is shown that reverse annealing can provide an exponential speedup over conventional quantum annealing for this particular problem.
Reverse annealing is a variant of quantum annealing that starts from a given classical configuration of spins (qubits). In contrast to the conventional formulation, where one starts from a uniform superposition of all possible states (classical configurations), quantum fluctuations are first increased and only then decreased. One then reads out the state as a proposed solution to the given combinatorial optimization problem. We formulate a mean-field theory of reverse annealing using the fully connected ferromagnetic
p-spin model, with and without random longitudinal fields, and analyze it in order to understand how and when reverse annealing is effective at solving this problem. We find that the difficulty arising from the existence of a first-order quantum phase transition, which leads to an exponentially long computation time in conventional quantum annealing, is circumvented in the context of this particular problem by reverse annealing if the proximity of the initial state to the (known) solution exceeds a threshold. Even when a first-order transition is unavoidable, the difficulty is mitigated due to a smaller jump in the order parameter at a first-order transition, which implies a larger rate of quantum tunneling. Reverse annealing has not been studied analytically before, and this study paves the way toward a systematic understanding of this relatively unexplored protocol in a broader context.
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.