Quantum Annealing and Analog Quantum Computation
We review here the recent success in quantum annealing, i.e., optimization of the cost or energy functions of complex systems utilizing quantum fluctuations. The concept is ntroduced in succes-sive steps through the studies of mapping of such computationally hard problems to the classical spin glass problems. The quantum spin glass problems arise w
ith the introduction of quantum fluctuations, and the annealing behavior of the systems as these fluctuations are reduced slowly to zero. This provides a general framework for realizing analog quantum computation.
I. INTRODUCTION
Utilization of quantum mechanical tunneling throughclassically localized states in annealing of glasses has opened up a new paradigm for solving hard optimiza-tion problems through adiabatic reduction of quantum fluctuations. This will be introduced and reviewed here. Consider the example of a ferromagnet consisting of N
tiny interacting magnetic elements; the spins. For a macroscopic sample N
is very large; of the order of Avo-gadro number. Assume that each spin can be in any of
the two simple states: up or down. Also, the pairwise interactions between the spins are such that the energy of interaction (potential energy or PE) between any pair
of spins is negative (smaller) if both the spins in the pair are in the same state and is positive (higher) if their states differ. As such, the collective energy of the N-spin system (given by the Hamiltonian H) is minimum when all the spins are aligned in the same direction; all up or all down, giving the full order. We call these two minimum energy configurations the ground states. The rest of the 2 N configurations are called excited states. The plot of the interaction energy of the whole system with respect to the configurations is called the potential energy-configuration landscape, or simply, the potential energy landscape (PEL). For a ferromagnet, this land-scape has a smooth double-valley structure (two mirror-symmetric valleys with the two degenerate ground states, all up and all down, at their respective bottoms). At zero-temperature the equilibrium state is the state of mini-mum potential energy, and the system stably esides at the bottom of any of the two valleys. At finite temperature, the thermal luctuations allow the system to visit higher energy configurations with some finite robability (given by the Boltzmann factor) and thus the system spends time in other part of the PEL also. The probability that a system is found in a particular macroscopic 3.
While optimizing the cost function of a computationally hard problem (like the ground state energy of a spin glass or the minimum travel distance for a traveling salesman problem),one has to get out of a shallower local minimum like the configuration C
(spin configuration or travel route), to reach a deeper minimum C. This requires jumps or tunneling like fluctuations in the dynamics. Classically one has to jump over the energy or the cost barriers separating them, while quantum mechanically one can tunnel through the same. If the barrier is high enough, thermal jump becomes very difficult. However, if the barrier is narrow enough, quantum tunneling often becomes quite easy.
tion of all classical configurations) is trivially realizable. Simulations clearly demonstrate that quantum annealing can occasionally help reaching the ground state of a complex glassy system much faster than could be done using thermal annealing (discussed later in Sec. III). An experiment comparing the classical and quantum annealing for a spin glass also shows that the relaxations in course of quantum annealing are often much faster than those during the corresponding classical annealing, as discussed in Sec. IIID. What makes quantum annealing fundamentally different from the classical annealing, is the nonlocal nature (Sec. III) and its higher tunneling ability (Secs. IID & IIIC).
Quantum annealing thus permits a realization of analog quantum computation, which is an independent and powerful complement to digital quantum computation, where discrete unitary transformations are implemented through quantum logic gates.
Soon I'll upload more content. Thanks for reading.
