Quantum Annealing

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" naturally subdivides a problem by energy scale, and has formed the basis for computer solutions known as "simulated annealing." In some cases, quantum tunneling (fig. 1) may be a more effective means at energy minimization than pure thermal processes, with the potential to hasten convergence to an appropriate solution.

Researchers from the University of Chicago's MRSEC have investigated a difficult 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). Through the experimental realization of the simplest quantum spin model, we are able to introduce quantum mechanics continuously and controllably in the laboratory, and find more than a thirty-fold decrease in the characteristic time to solution.

These results have obvious implications for designing simulated annealing computer algorithms, but they also raise more fundamental issues about strategies for the design of actual quantum computers.