A US-UK group has 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 towards developing quantum computation has steadily grown.
In particular, optimization problems such as the “traveling salesman” problem, in which the shortest possible route between a number of towns, visiting each once and returning to the point of origin must be determined, becomes intractable as the number of towns grows.
A quantum computer would exploit effects such as entanglement and tunneling that appear on the atomic and molecular size 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 traveling salesman problems with up to a few hundred towns.
In a study published in PNAS a team from the James Franck Institute at the University of Chicago and the London Centre for Nanotechnology at UCL describes a proof-of-concept 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.
One of the key aspects of optimization is the process by which the special purpose computer settles into a solution to the traveling salesman problem. The solutions to the problem exist in a landscape where the heights and depths of features are the total distance travelled – the best solution corresponds to the deepest valley. To find the deepest valley, the optimizer hops between valleys either by climbing to intermediate saddle points and then descending again, or via quantum tunneling between valleys. The first represents thermal annealing, while the second corresponds to quantum annealing. The relative weights of the thermal and quantum processes determine the nature of the final valley found.
The research at Chicago and London looked at the valleys found after annealing with different rations of weights via experiments on a crystalline quantum magnet. In this material, at temperatures near absolute zero, the speed and strength of thermal annealing can be controlled by rods of sapphire attached to a refrigerator with 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 acts to set the rate of quantum tunneling in the magnetic sample.
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. The figure is a schematic of the state found after quantum annealing, where certain regions of the crystal are in “quantum superposition states”, similar to “Schrodinger’s cat” which is alive and dead simultaneously and others have definite classical characteristics, marked by fixed up or down arrows; classical annealing of the same system leaves behind regions of exclusively the latter variety.
Applied to practical and programmable quantum optimization computers, the results imply that quantum optimizers could obtain very different types of solutions to problems such as the traveling salesman problem when compared with conventional annealing techniques, a finding which will affect both the design and use of quantum optimization systems.
Figure: Schematic of final result after optimization with strong quantum annealing. For the travelling salesman problem, the arrows correspond to binary digits in the representation of the sequence of cities visited, with up and down arrows corresponding to ‘0’ and ‘1’ and respectively. For some regions, these digits are well-defined, while for others, particular pairs of spins are in quantum superpositions, similar to “Schrodinger’s cat” which is alive and dead simultaneously.