April 13, 2014 |
University of Chicago researchers and their colleagues at University College London have performed a proof-of-concept experiment that will aid the future development of programmable quantum computers.
Many complex problems are difficult and slow to solve using conventional computers, and over the last several years, research has grown steadily toward developing quantum computation. In particular, optimization problems such as the “traveling salesman” problem, which calculates the shortest possible route needed to visit a set of towns, become intractable as the number of towns grows.
A quantum computer would exploit effects on the atomic and molecular scales to solve such problems dramatically faster than conventional computers. Recently a first generation of specialized computers has become available—with a new architecture that exploits quantum mechanics to help solve problems akin to the traveling salesman problem, with up to a few hundred towns.
In a study published in the Proceedings of the National Academy of Sciences, a team from the James Franck Institute at UChicago and the London Centre for Nanotechnology at University College London describes an experiment that was performed on a crystal containing trillions, rather than hundreds, of quantum mechanical spins, which replicates some of the features of the current generation of much smaller, specialized computers.
The lead author is Michael Schmidt, PhD’12, now a research scientist with Intel in Portland. His co-authors are Daniel Silevitch, research scientist in the James Franck Institute; Thomas Rosenbaum, the John T. Wilson Distinguished Service Professor in Physics; and Prof. Gabriel Aeppli of University College London.
The crystalline quantum magnet used to perform this experiment contains atoms whose spins (magnetic orientation) oscillate. Thermal annealing and quantum annealing are the processes by which the researchers manipulated the magnetic spins in this experimental magnetic crystal. Many types of magnetic materials can orient spins in any direction, but this special crystal limits the orientation to either up or down.
Quantum annealing relates to quantum tunneling, a phenomenon that allows particles to pass through barriers via interactions that Newtonian physics cannot predict. “If you run the system in a regime where quantum tunneling is completely turned off, then you end up with one solution to your problem, and a different solution when quantum tunneling is turned on,” Silevitch said.
In this magnetic crystal at temperatures near absolute zero (minus 459.67 degrees Fahrenheit), the speed and strength of thermal annealing can be controlled by rods of sapphire attached to a refrigerator via more or less contact with the crystal. At the same time, the rate of quantum annealing can be controlled by means of a magnetic field, which sets the rate of quantum tunneling in the magnetic sample.
Thermal annealing can only be turned down by cooling the system, but it cannot be turned off. But if the system runs in a mode where thermal annealing is turned down and quantum annealing is turned up, the result is a different state of magnetic spins, which represents a different solution to the computational problem.
The special purpose computer solves problems such as the traveling salesman problem in a semi-abstract landscape where the heights and depths of features represent the total distance traveled. The best solution corresponds to the deepest valley.
THERMAL AND QUANTUM ANNEALING
Finding the deepest valley can be visualized as a pool of water moving between valleys, either via a wave splashing over the intermediate saddle points and then descending, or via quantum tunneling between valleys.
The first approach represents thermal annealing, which is comparable to conventional computing methods. The second corresponds to quantum annealing, a characteristic of potentially more capable quantum computing.
Thermal annealing reaches a final state, or problem solution, by hopping over the energy barriers, then gradually restricting the size of the barrier that it can overcome via lowering the temperature. Quantum annealing, by contrast, reaches the final state via quantum tunneling through the barriers, then gradually clamping down (and ultimately turning off) the tunneling rate.
In thermal annealing, the “waves” slosh back and forth, and if they reach a sufficient height, they will splash over the hill and then drain into an adjacent valley.
High-temperature thermal annealing corresponds to violently sloshing water, which means that it can surmount high barriers. As the researchers slowly drop the strength of the waves, the water can only top middle-sized hills. With further cooling of the system, the waves can only wash over molehills.
A problem arises, however, for thermal annealing when a bowl-like valley sits next to a deeper, narrower well. In this situation, most of the sloshing water will end up at the bottom of the valley. Water naturally seeks its lowest level, but as the temperature drops and the wave heights become reduced, the entrance of the well becomes inaccessible.
Quantum annealing allows the water to pass through the hill via the quantum tunneling process.
“If you have this bowl, and then right next to it there’s this really deep well, the odds of getting out of the bowl into the well through thermal annealing is very, very low,” Silevitch explained. “You have to wait for a randomly big wave to come sloshing over. But with quantum annealing, you can go right through the hill and you can find that deep well, which is where you prefer to be.”
The experiments found that when the system reached its final valley via thermal annealing alone, it was dramatically different from the state reached when the thermal annealing was weakened and quantum annealing was turned on.
After the application of quantum annealing, certain regions of the crystal were in “quantum superposition states,” which can simultaneously exist in two different states according to the counter-intuitive rules of quantum physics. Other regions have the characteristics typical of the physics that predominates at macroscopic scales. Thermal annealing in these experiments leaves behind regions exclusively of the latter variety.
Applied to practical and programmable quantum optimization computers, the results imply that quantum optimizers could obtain different solutions to problems such as the traveling salesman problem, when compared with conventional techniques. The research team concluded that these findings would affect both the design and use of quantum optimization systems.