Quantum Computer a Reality

Physics Friday, February 9, 2007. Post by Chad

While a 16-qubit quantum computer is not that impressive, only being able to perform 65,536 computations in parallel, just the fact that they have a working quantum computer at all is a big deal. Given the absurd pace of technological development, can it be that long before we have a “real” quantum computer, capable of easily handling “unsolvable” NP-complete problems such as the travelling salesman problem? Of more concern is that a quantum computer of a few hundred bits would be capable of breaking the standard encryption schemes currently in use.

More details available here and here.

[Update 2007-02-13 by Chad]

Apparently I was wrong when I said that a quantum computer can easily solve NP-complete problems. More information at Nobel Intent. On the other hand, this article, also at Nobel Intent, says that researchers have claimed to be able to solve NP-complete problems in polynomial time via adiabatic quantum computers (of which D-Wave is one)—so I’m not really sure what to believe at this point. I do know, however, that researchers have already created a quantum computer factoring algorithm that can break our encryption system in a reasonable amount of time.

• Previously on SciScoop: « Diamond White

• Next:Reversing Rett’s »