Controversial quantum computer beats factoring record

Physics 13 April 2012

Is this a record for a quantum computer? A group of physicists in China have used a process called adiabatic computing to find the prime factors of the number 143, beating the previous record for a quantum computer of 21. However, there are doubts about the quantum nature of this method, and its potential to scale up any further.

Rather than bits, quantum computers use quantum bits, or qubits, which can exist in multiple states at once. In theory, these superpositions should allow the machines to complete some calculations, including factorisation, much faster than conventional or classical computers.

That could be a boon to some types of computation, but it could also pose a threat: encryption schemes rely on the fact that factorising large numbers is hard for classical computers. As yet, though, no one has built a quantum machine big enough to harness this power.

The Chinese experiment, led by Jiangfeng Du at the University of Science and Technology in Hefei, China, is based on well-established technology called liquid-phase NMR. The qubits in this set-up are the spins of hydrogen nuclei in molecules of 1-bromo-2-chlorobenzene. Each spin is a quantum magnet that can be manipulated using bursts of radio waves.


Qubit pool

While this hardware is conventional, its use in this case is not. Adiabatic quantum computing does away with the circuits and separate components found in other quantum and classical computers, which are based on switches and logic gates. Instead, a pool of qubits is encouraged to find the answer collectively.

The technique relies on a pool of qubits always seeking its lowest overall energy state; the trick is to adjust the system so that the lowest-energy state gives the answer to the problem. It is a bit like putting a lightweight ball in the middle of a stretched out blanket, and then moving the blanket’s edges to manoeuvre the ball into the right spot. Only the right moves will coax it into position; similarly, only the right quantum algorithm will enable a pool of qubits to solve a given problem.

In 2006, Ralf Schützhold and Gernot Schaller at the Dresden Technical University in Germany worked out an adiabatic algorithm to factorise a number using a pool of qubits. Now Du and colleagues have simplified that algorithm, and used it to factorise the number 143. (It’s 13 x 11, in case you were wondering.)

Though that is a leap of an order of magnitude, it is still a small enough number that ordinary computers can do the calculation in a flash.

The researchers’ computer has just four qubits and it is hard to scale up liquid-phase NMR further. That means that to factorise larger numbers, different hardware would be required such as trapped ions or superconducting circuits – or perhaps a hybrid of the two. But “the algorithm could be used in other quantum-computing architectures”, says Du.

Entanglement clue

Most groups are taking a different approach, trying to beat classical computers at factorisation via another quantum algorithm called Shor’s algorithm.

There is mathematical proof that Shor’s algorithm will be much faster than any classical algorithm for factorising large numbers, but will the same be true of the adiabatic algorithm? Maybe not, says Scott Aaronson, a quantum physicist at the Massachusetts Institute of Technology.

“It doesn’t ‘know’ about the special mathematical properties of factoring that make that an easy problem for quantum computers,” Aaronson says. “In contrast to Shor’s algorithm, we have no reason to think it would be able to factor 10,000 digit numbers in less than astronomical amounts of time.”

Du acknowledges that there is no mathematical proof for his team’s algorithm, but he says there is strong evidence from numerical simulations that it will be fast for large numbers.

Aaronson also questions the quantum nature of the calculation. “I didn’t see any evidence that quantum behaviour played a role in finding the factors of 143,” he says. Rather, the experiment might have reached the conclusion in a classical way, he suggests.

Du responds that the system starts from a superposition of all possible quantum states, and that qubits are linked in a uniquely quantum manner called entanglement. “No classical algorithms could handle the computing task in this way.”

Journal Reference: Physical Review Letters, DOI: 10.1103/PhysRevLett.108.130501

More on these topics: