Published October 19, 2013
An experimental computer made by a Canadian company has proved its ability to solve increasingly complex mathematical problems. But the question remains — just how much of this calculating power is actually due to the strange properties of quantum mechanics?
In theory, quantum computers can perform calculations far faster than their classical counterparts to solve incredibly complex problems. They do this by storing information in quantum bits, or qubits.
At any given moment, each of a classical computer's bits can only be in an “on” or an “off” state. They exist inside conventional electronic circuits, which follow the 19th-century rules of classical physics. A qubit, on the other hand, can be created with an electron, or inside a superconducting loop. Obeying the counterintuitive logic of quantum mechanics, a qubit can act as if it’s “on” and “off” simultaneously. It can also become tightly linked to the state of its fellow qubits, a situation called entanglement. These are two of the unusual properties that enable quantum computers to test multiple solutions at the same time.
But in practice, a physical quantum computer is incredibly difficult to run. Entanglement is delicate, and very easily disrupted by outside influences. Add more qubits to increase the device's calculating power, and it becomes more difficult to maintain entanglement.
Instead of struggling to keep ever-larger numbers of qubits in balance, D-Wave Systems invested in a different kind of quantum computer, where entanglement is not as crucial. They aimed to create an “adiabatic” computer, in which the qubits begin in a simple low-energy state and are slowly nudged towards a state that represents the best possible solution. This enabled the company to incorporate 512 qubits into its current model, the D-Wave Two.
The D-Wave uses a limited form of adiabatic quantum computing called quantum annealing, in which the qubits exist in a bath of noise, or random electrical fluctuations, that can disrupt their delicate states, explained Daniel Lidar, who oversees the use of a D-Wave Two device at the University of Southern California.
It helps to compare a computer using quantum annealing to an explorer seeking the lowest point in a landscape of mountains and valleys. “Think of the height of the landscape as the energy of the problem we’re trying to solve,” Lidar suggested. “We’ve solved the problem once we’ve minimized the energy, or arrived at the deepest valley.”
A "classical" explorer would have to cover the terrain alone, which would take a long time. But a quantum expedition could survey the entire landscape with multiple walkers simultaneously. “You have multiple copies of this landscape and lots of random walkers walking all at once, but for the price of one,” Lidar explained.
Quantum annealing is one method to solve optimization problems, in which you need to find the best of all possible solutions, such as determining the most efficient path between multiple travel destinations. When you give the D-Wave an optimization problem, it then uses quantum annealing to reach the best solution.
In an attempt to apply an adiabatic algorithm to a practical problem, researchers, in collaboration with D-Wave, have used this method to calculate Ramsey numbers. Ramsey numbers indicate when order will appear in a disordered system. For example, they quantify how many people you need to invite to a party in order to ensure that at least some of the guests will be mutual friends.
The scientists transformed the Ramsey number calculation into an optimization problem, and ran it using 84 qubits of a 128-qubit D-Wave device. As they discuss in Physical Review Letters, the D-Wave returned the correct values for two known Ramsey numbers. In the future, the algorithm may also be able to calculate unknown Ramsey numbers by incorporating more qubits.
“We were just trying to get a proof of principle of the algorithm, and test it on the hardware,” said study author Frank Gaitan, from the University of Maryland. “Maybe down the road as the chips get bigger we can get a new Ramsey number, but at this point, it’s unrealistic.”
Although the work certainly proves the D-Wave can solve this type of problem, it doesn't prove that the machine used quantum methods to do so.
Scientists have been debating D-Wave's quantumness since the company announced its first device in 2004. It is an argument that continues both online, in blog posts and forums, and in scientific journals.
One side argues there is too much noise in the D-Wave system, which prevents consistent entanglement. But in an adiabatic device, certain types of entanglement are not as vital as they are in the traditional model of a quantum computer.
Some researchers are attempting to solve this conundrum by proving the presence or absence of entanglement. If they show entanglement is absent, that would be the end of the discussion. On the other hand, even if some of D-Wave's qubits are entangled, this doesn't mean the device is taking advantage of it.
Another way to prove D-Wave's quantumness would be to confirm it is indeed performing quantum, and not classical, annealing. Lidar has published work to this effect, but that triggered opposition, and then a counter-point. The debate continues.
Even the D-Wave's speedy calculations don't serve as proof of a quantum origin. One researcher did find D-Wave performed 3600 times faster than a classical device. However, other classical algorithms seriously reduced the scale of this speed-up.
"We believe the device is definitely a quantum computer.” said Colin Williams, a Ph.D. scientist at D-Wave who serves as its director of business development and strategic partnerships. “Little by little we're adding more and more evidence of the quantumness of the device."