Monday, June 20, 2011

No quantum factoring

The quantum computer folks brag that their greatest accomplishment is quantum factoring, and the proof is the experiment that factored the number 15. But those claims are bogus, as Nature magazine reports:
The notion that quantum computing can be done only through entanglement was cemented in 1994, when Peter Shor, a mathematician at the Massachusetts Institute of Technology in Cambridge, devised an entanglement-based algorithm2 that could factorize large numbers ...

Clues that entanglement isn't essential after all began to trickle in about a decade ago, with the first examples of rudimentary quantum computation. In 2001, for instance, physicists at IBM's Almaden Research Center in San Jose and Stanford University, both in California, used a 7-qubit system to implement Shor's algorithm5, factorizing the number 15 into 5 and 3. But controversy erupted over whether the experiments deserved to be called quantum computing, says Carlton Caves, a quantum physicist at the University of New Mexico (UNM) in Albuquerque.

The trouble was that the computations were done at room temperature, using liquid-based nuclear magnetic resonance (NMR) systems, in which information is encoded in atomic nuclei using an internal quantum property known as spin. Caves and his colleagues had already shown6 that entanglement could not be sustained in these conditions. "The nuclear spins would just be jostled about too much for them to stay lined up neatly," says Caves. According to the orthodoxy, no entanglement meant no quantum computation.

The NMR community gradually accepted that they had no entanglement, says Jiangfeng Du, an NMR-computing specialist at the University of Science and Technology of China, in Hefei. [Published online 1 June 2011 | Nature 474, 24-26 (2011) | doi:10.1038/474024a]
The article argues that the factoring of 15 was still legitimate, even if it did not use quantum computing. But a primitive 1940s computer could factor 15. If no entanglement was used, then the result is trivial and the whole thing is a hoax.

1 comment: