## Abstract

Traditional simulated annealing uses thermal fluctuations for convergence in optimization problems. Quantum tunneling provides a different mechanism for moving between states, with the potential for reduced time scales. Thermal and quantum annealing are compared in a model disordered magnet, where the effects of quantum mechanics can be tuned by varying an applied magnetic field. The results indicate that quantum annealing hastens convergence to the optimum state.

In their presentation of simulated annealing, Kirkpatrick, Gelatt, and Vecchi (1) described a fundamental connection between statistical mechanics and combinatorial optimization. Complex systems subject to conflicting constraints, from the traveling salesman problem and circuit design on one hand to spin glasses and protein folding on the other, are difficult to solve because of the vast number of nearly degenerate solutions. The introduction of a variable “temperature” permits the simulation to naturally subdivide a problem by energy scale, and as the temperature approaches zero the system settles into a local minimum (Fig. 1) that should be comparable to the ground state of the system.

If the settling is performed sufficiently slowly, then the minimum is guaranteed to be the ground state (2). However, complex systems with many degrees of freedom may require impracticably long annealing schedules to achieve the true lowest energy configuration. If barriers between adjacent energy minima are very high yet sufficiently narrow, it may be that quantum tunneling is a more effective means at energy minimization than pure thermal processes, with the potential to hasten convergence to the ground state.

As an example, consider the two-state spin system (“up” and “down”) used to introduce tunneling in quantum mechanics. The application of a magnetic field perpendicular to the up-down axis induces off-diagonal terms in the Hamiltonian and enables tunneling between the two measured states. The assembly of a macroscopic number of such quantum spins on a lattice represents Feynman's original concept (3) of a quantum mechanical computer. Information at the inputs (the original spin state of the system) undergoes a series of quantum mechanical operations, with the final set of ones and zeroes read at the outputs (the optimized, low-energy spin state). Our experiment investigated a nontrivial optimization problem in statistical mechanics, namely, that of finding the ground state for a ferromagnet with a certain proportion of randomly inserted antiferromagnetic bonds (which favor antiparallel alignment of spins), and whether this problem can be solved more rapidly by quantum annealing than by classical thermal annealing. We started from the disordered, paramagnetic, high-temperature state in the dipolar-coupled Ising ferromagnet LiHo_{x}Y_{1−}
_{x}F_{4}, and read out the optimized low-temperature state using conventional magnetic susceptometry.

The Ising magnet LiHo_{x}Y_{1−}
_{x}F_{4}in a transverse magnetic field *H*
_{t} is the experimental realization of the simplest quantum spin model. The corresponding Hamiltonian (ℋ) is(1)where the σ's are Pauli spin matrices, the*J _{ij}
*'s are longitudinal couplings, and Γ is a transverse field. Given that the commutator (ℋ, σ

^{z}) is finite when Γ ≠ 0, σ

^{z}is no longer conserved and zero-point (quantum) fluctuations appear. The fluctuations increase with Γ, which tunes an order-disorder transition at temperature

*T*= 0. Our experiments are very different from traditional experiments on disordered magnets where fields are applied parallel to an easy direction for magnetization (4,5). In particular, for Ising systems such as ferromagnetic LiHo

_{x}Y

_{1−}

_{x}F

_{4}, a longitudinal field simply polarizes the spins at all

*T*and removes the possibility of a ferromagnetic phase transition. The transverse field Γ, however, is not conjugate to the order parameter and retains a true phase transition. With this system we can directly compare the efficiency of quantum tunneling to classical thermal relaxation in finding the minima of a complicated energy landscape consisting of

*N*∼ 10

^{23}spins.

In our experiments, the magnetic field *H*
_{t} was applied perpendicular to the Ising axis (crystalline *c* axis) for the Ho spins. At low temperatures (*T* < 1 K), the only Ho^{3+} crystal field state that is appreciably populated is the (*H*
_{t} = 0) ground-state doublet, which can be split in continuous fashion with great precision by the laboratory field *H*
_{t} (6, 7). The splitting Γ plays the role of the transverse field in Eq. 1, whereas the doublet plays the role of the spin-1/2 eigenstates. For the present experiment, we selected a single crystal with 56% substitution of magnetically inert Y for Ho. The random dilution of magnetic by nonmagnetic ions yields couplings between the magnetic ions of effectively random sign (8), which make the search for the ground state difficult in the rare earth lithium fluorides. The crystal was ground to a needle-like cylinder of aspect ratio three to minimize demagnetization effects. We suspended the cylinder from the mixing chamber of a helium dilution refrigerator inside the bore of an 80 kOe superconducting magnet, with the field direction oriented along the crystal *a* axis (within 5°), perpendicular to the Ising axis (within 0.5°). A trim coil oriented along the Ising direction nulled any unwanted longitudinal field component. The protocol for comparing equilibration due to quantum tunneling and thermal hopping was straightforward. We annealed using both methods to the same point in the temperature–transverse field plane, and then measured the complete ac susceptibility, χ(*f*) = χ′(*f*) + iχ"(*f*), along the Ising axis with a standard gradiometer configuration and spectrum analyzer. Typical measuring frequencies (*f*) ranged between 1 and 10^{5} Hz.

At low temperatures and large transverse fields, the mix of quantum mechanics and disorder converts LiHo_{0.44}Y_{0.56}F_{4 }from a classical ferromagnet with Curie temperature*T*
_{C}(*H*
_{t} = 0) = 0.673 K to a magnet with glassy, history-dependent behavior (9). The*H*
_{t}-*T* phase diagram as well as two cooling protocols are shown in Fig. 1. The classical route (blue) crosses the phase boundary in zero transverse field, decreasing*T* from 0.800 to 0.030 K and only then raising*H*
_{t} to 7.2 kOe, whereas the quantum route (red) cools to 0.030 K in large transverse field (24 kOe), proceeding through the order-disorder transition with finite *H*
_{t} and significant tunneling probability to the same nominal end point. The variation of *T*, *H*
_{t}, and the real part of the magnetic susceptibility, χ′(*f* = 15 Hz), with time *t* are compared for the thermal and the quantum computation (Fig. 2). Remarkably, the magnetic susceptibility of the system at the identical place in the*H*
_{t}-*T* plane arrives at a different value depending on the annealing protocol. This difference survives to long times, at least on the order of days.

Spectroscopy provides insight into the distribution and magnitudes of relaxation times for spin reorientation. We plotted χ′(*f*) over four decades of frequency (Fig. 3) at points A to D in the phase diagram of Fig. 1. Spin relaxation proceeds conventionally, independent of the annealing protocol, in the classical ferromagnet (Fig. 3A). As temperature is reduced to *T* = 0.4 K (Fig. 3B), differences start to emerge. The classically cooled spectrum is about half a decade to the left of the quantum-cooled data; the quantum protocol has yielded a state with relaxation times a factor of 3 smaller than its classical counterpart. This effect increases dramatically on cooling deep into the ordered phase (Fig. 3C). As*f* decreases toward 1 Hz, χ′(*f*) grows logarithmically with roughly similar slopes for both annealing histories. The displacement between the two lines is now one and a half decades; quantum cooling has produced a state for which the relaxation times are a factor of 30 faster than those produced by classical cooling. Finally, keeping *T* fixed at 0.030 K and increasing *H*
_{t} back into the paramagnet (Fig. 3D) narrows the spectroscopic response and restores the system's insensitivity to annealing method.

The logarithmic divergence of χ′(*f*) at*T* = 0.030 K is shown (Fig. 4) over nearly five decades in frequency. As *H*
_{t} grows, the spectra move to the right; there is a spectacular acceleration of the relaxation. At the same time, the shift between the spectra obtained by quantum and classical cooling algorithms shrinks so that at 10.8 kOe quantum cooling renormalizes the relaxation times by only a factor of 2.

The different time scales for classical and quantum annealing are also clearly evident in the imaginary part of the susceptibility, χ" (Fig. 5), where the position of the peak response is the inverse of a typical relaxation time. Moreover, the low-frequency dissipative response provides an additional basis for comparison. The quantum annealed data all converge and flatten at low frequencies, independent of transverse field destination at low*T*, whereas the classical curves appear to head toward separate low-frequency, long time values. It is natural to associate the convergent state in the quantum computation with the ground state of the system. If the χ"(*f*,*H*
_{t}) quantum response remains coincident and frequency independent as *f* → 0, then by the Kramers-Kronig relation the real components, χ′(*f*,*H*
_{t}), should be logarithmic in*f*, in agreement with what we have measured directly (filled squares, Fig. 4). By the same token, the more diverse low-frequency behavior of iχ" after classical cooling is reflected in the generally greater bowing and reduced parallelism between the classical χ′ curves of Fig. 4.

The logarithmically divergent χ′(*f*) =*C* ln(*f*/*f*
_{o}) (*C* is a constant), which characterizes the state G in the phase diagram of Fig. 1, implies that G is critical or marginally stable (10). It is a nearly ferromagnetic state with equally probable fluctuations out of that state on all (long) time scales. Quantum and classical annealing protocols yield states that differ primarily in the characteristic frequency *f*
_{o}. The dramatically enhanced *f*
_{o} found for quantum cooling shows that the addition of a tunneling term to the Hamiltonian (Eq. 1) yields a state with more rapid fluctuations. Most importantly, quantum cooling has allowed us to see more clearly and quickly that the ground state is likely a critical state: at *T* = 0.030 K and *H*
_{t} = 7.2 kOe, there is only one decade of logarithmic behavior for classical cooling whereas there are already two and a half decades for quantum cooling.

Our experiments on LiHo_{0.44}Y_{0.56}F_{4}directly demonstrate the power of a quantum mechanical term in the Hamiltonian for reaching a convergent solution, with obvious implications for designing simulated annealing computer algorithms (11). They also raise more fundamental issues about strategies for the design of actual quantum computers. To date, the favored route has involved building a quantum computer qubit by qubit, taking advantage of the extraordinary sensitivity and isolation possible in modern nuclear magnetic resonance techniques (12). Elaborate protocols for addressing and manipulating individual qubits are then required to perform computations. Our work allows speculation about a less refined approach. We cast the computation as a classical spin problem, which we then solve by a combination of thermal cooling and the blanket application of a transverse field. The transverse field, which controls the tunneling probability, is eventually driven to a low or zero value, and the solution can be read out in the form of the resulting and—at that point—frozen spin configuration.

↵* To whom correspondence should be addressed. E-mail: t-rosenbaum{at}uchicago.edu