We present results for a variety of Monte Carlo annealing approaches, both classical and quantum, benchmarked against one another for the textbook optimization exercise of a simple one-dimensional double well. In classical (thermal) annealing, the dependence upon the move chosen in a Metropolis scheme is studied and correlated with the spectrum of the associated Markov transition matrix. In quantum annealing, the path integral Monte Carlo approach is found to yield nontrivial sampling difficulties associated with the tunneling between the two wells. The choice of fictitious quantum kinetic energy is also addressed. We find that a ``relativistic'' kinetic energy form, leading to a higher probability of long real-space jumps, can be considerably more effective than the standard nonrelativistic one.
We present results for a variety of Monte Carlo annealing approaches, both classical and quantum, benchmarked against one another for the textbook optimization exercise of a simple one-dimensional double well. In classical (thermal) annealing, the dependence upon the move chosen in a Metropolis scheme is studied and correlated with the spectrum of the associated Markov transition matrix. In quantum annealing, the path integral Monte Carlo approach is found to yield nontrivial sampling difficulties associated with the tunneling between the two wells. The choice of fictitious quantum kinetic energy is also addressed. We find that a ``relativistic'' kinetic energy form, leading to a higher probability of long real-space jumps, can be considerably more effective than the standard nonrelativistic one.
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.
Quantum annealing was recently found experimentally in a disordered spin-21 magnet to be more effective than its classical, thermal counterpart. We use the random two-dimensional Ising model as a test example and perform on it both classical and quantum (path-integral) Monte Carlo annealing. A systematic study of the dependence of the final residual energy on the annealing Monte Carlo time quantitatively demonstrates the superiority of quantum relative to classical annealing in this system. In order to determine the parameter regime for optimal efficiency of the quantum annealing procedure we explore a range of values of Trotter slice number P and temperature T. This identifies two different regimes of freezing with respect to efficiency of the algorithm, and leads to useful guidelines for the optimal choice of quantum annealing parameters.
We analyze the performance of quantum annealing as a heuristic optimization method to find the absolute minimum of various continuous models, including landscapes with only two wells and also models with many competing minima and with disorder. The simulations performed using a projective quantum Monte Carlo (QMC) algorithm are compared with those based on the finite-temperature path-integral QMC technique and with classical annealing. We show that the projective QMC algorithm is more efficient than the finite-temperature QMC technique, and that both are inferior to classical annealing if this is performed with appropriate long-range moves. However, as the difficulty of the optimization problem increases, classical annealing loses efficiency, while the projective QMC algorithm keeps stable performance and is finally the most effective optimization tool. We discuss the implications of our results for the outstanding problem of testing the efficiency of adiabatic quantum computers using stochastic simulations performed on classical computers.
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.
We propose a path-integral Monte Carlo quantum annealing scheme for the symmetric traveling-salesman problem, based on a highly constrained Ising-like representation, and we compare its performance against standard thermal simulated annealing. The Monte Carlo moves implemented are standard, and consist in restructuring a tour by exchanging two links (two-opt moves). The quantum annealing scheme, even with a drastically simple form of kinetic energy, appears definitely superior to the classical one, when tested on a 1002-city instance of the standard TSPLIB.
The discrete time path integral Monte Carlo with a one-particle density matrix approximation is applied to study the quantum phase transition in the coupled double-well chain. To improve the convergence properties, the exact action for a single particle in a double-well potential is used to construct the many-particle action. The algorithm is applied to the interacting quantum double-well chain for which the zero-temperature phase diagram is determined. The quantum phase transition is studied via finite-size scaling, and the critical exponents are shown to be compatible with the classical two-dimensional Ising universality class--not only in the order-disorder limit (deep potential wells), but also in the displacive regime (shallow potential wells).