We investigate the basic behavior and performance of simulated quantum annealing (QA) in comparison with classical annealing (CA). Three simple one-dimensional case study systems are considered: namely, a parabolic well, a double well, and a curved washboard. The time-dependent Schr\"odinger evolution in either real or imaginary time describing QA is contrasted with the Fokker-Planck evolution of CA. The asymptotic decrease of excess energy with annealing time is studied in each case, and the reasons for differences are examined and discussed. The Huse-Fisher classical power law of double-well CA is replaced with a different power law in QA. The multiwell washboard problem studied in CA by Shinomoto and Kabashima and leading classically to a logarithmic annealing even in the absence of disorder turns to a power-law behavior when annealed with QA. The crucial role of disorder and localization is briefly discussed.
We investigate the basic behavior and performance of simulated quantum annealing (QA) in comparison with classical annealing (CA). Three simple one-dimensional case study systems are considered: namely, a parabolic well, a double well, and a curved washboard. The time-dependent Schr"odinger evolution in either real or imaginary time describing QA is contrasted with the Fokker-Planck evolution of CA. The asymptotic decrease of excess energy with annealing time is studied in each case, and the reasons for differences are examined and discussed. The Huse-Fisher classical power law of double-well CA is replaced with a different power law in QA. The multiwell washboard problem studied in CA by Shinomoto and Kabashima and leading classically to a logarithmic annealing even in the absence of disorder turns to a power-law behavior when annealed with QA. The crucial role of disorder and localization is briefly discussed.
We review here some recent work in the field of quantum annealing, alias adiabatic quantum computation. The idea of quantum annealing is to perform optimization by a quantum adiabatic evolution which tracks the ground state of a suitable time-dependent Hamiltonian, where 'ℏ' is slowly switched off. We illustrate several applications of quantum annealing strategies, starting from textbook toy-models—double-well potentials and other one-dimensional examples, with and without disorder. These examples display in a clear way the crucial differences between classical and quantum annealing. We then discuss applications of quantum annealing to challenging hard optimization problems, such as the random Ising model, the travelling salesman problem and Boolean satisfiability problems. The techniques used to implement quantum annealing are either deterministic Schrödinger's evolutions, for the toy models, or path-integral Monte Carlo and Green's function Monte Carlo approaches, for the hard optimization problems. The crucial role played by disorder and the associated non-trivial Landau–Zener tunnelling phenomena is discussed and emphasized.
The protocol of quantum annealing is applied to an optimization problem with a one-dimensional continuous degree of freedom, a variant of the problem proposed by Shinomoto and Kabashima. The energy landscape has a number of local minima, and the classical approach of simulated annealing is predicted to have a logarithmically slow convergence to the global minimum. We show by extensive numerical analyses that quantum annealing yields a power-law convergence, thus an exponential improvement over simulated annealing. The power is larger, and thus the convergence is faster, than a prediction by an existing phenomenological theory for this problem. Performance of simulated annealing is shown to be enhanced by introducing quasiglobal searches across energy barriers, leading to a power-law convergence but with a smaller power than in the quantum case and thus a slower convergence classically even with quasiglobal search processes. We also reveal how diabatic quantum dynamics, quantum tunneling in particular, steers the systems toward the global minimum by a meticulous choice of annealing schedule. This latter result explicitly contrasts the role of tunneling in quantum annealing against the classical counterpart of stochastic optimization by simulated annealing.
A summary of the results of recent applications of PIMC-QA on different optimization problems is given in Chapter 1. In order to gain understanding on these problems, we have moved one step back, and concentrated attention on the simplest textbook problems where the energy landscape is well under control: essentially, one-dimensional potentials, starting from a double-well potential, the simplest form of barrier. On these well controlled landscapes we have carried out a detailed and exhaustive comparison between quantum adiabatic Schrödinger evolution, both in real and in imaginary time, and its classical deterministic counterpart, i.e., Fokker-Planck evolution [17]. This work will be illustrated in Chapter 2. On the same double well-potential, we have also studied the performance of different stochastic annealing approaches, both classical Monte Carlo annealing and PIMCQA. The CA work is illustrated in Chapter 3, where we analyze the different annealing behaviors of three possible types of Monte Carlo moves (with Box, Gaussian, and Lorentzian distributions) in a numerical and analytical way. The PIMC-QA work is illustrated in Chapter 4, were we show the difficulties that a state-of-the-art PIMCQA algorithm can encounter in describing tunneling even in a simple landscape, and we also investigate the role of the kinetic energy choice, by comparing the standard non-relativistic dispersion, Hkin = Tau(t)p^2, with a relativistic one, Hkin = Tau(t)|p|, which turns out to be definitely more effective. In view of the difficulties encountered by PIMC-QA even in a simple double-well potential, we finally explored the capabilities of another well established QMC technique, the Green's Function Monte Carlo (GFMC), as a base for a QA algorithm. This time, we concentrated our attention on a very studied and challenging optimization problem, the random Ising model ground state search, for which both CA and PIMC-QA data are available [10, 11]. A more detailed summary of the results and achievements described in this Thesis, and a discussion of open issues, is contained in the final section `Conclusions and Perspectives'. Finally, in order to keep this Thesis as self-contained as possible, we include in the appendices a large amount of supplemental material.
The path integral Monte Carlo simulated quantum annealing algorithm is applied to the optimization of a large hard instance of the random satisfiability problem (N = 10,000). The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the traveling salesman problem, in the present case the linear-schedule quantum annealing performance is definitely worse than classical annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.
In many real-life situations in engineering (and in other disciplines), we need to solve an optimization problem: we want an optimal design, we want an optimal control, etc. One of the main problems in optimization is avoiding local maxima (or minima). One of the techniques that helps with solving this problem is annealing: whenever we find ourselves in a possibly local maximum, we jump out with some probability and continue search for the true optimum. A natural way to organize such a probabilistic perturbation of the deterministic optimization is to use quantum effects. It turns out that often, quantum annealing works much better than non-quantum one. Quantum annealing is the main technique behind the only commercially available computational devices that use quantum effects-D-Wave computers. The efficiency of quantum annealing depends on the proper selection of the annealing schedule, i.e., schedule that describes how the perturbations decrease with time. Empirically, it has been found that two schedules work best: power law and exponential ones. In this paper, we provide a theoretical explanation for these empirical successes, by proving that these two schedules are indeed optimal (in some reasonable sense).