Quantum Computers... so fast?

Last edition: 20/02/2007. I'm adding some links to the scientific terms.
---
Nobody (I mean, physicists) was expecting a commercial quantum computer so fast, but the firm D-Wave, founded by physicist Geordie Rose (who has his own blog) in 1999, claims that achieved just that.

Risking being repetitive, quantum computation becomes an attractive endeavour after P.W. Shor demonstrated in his paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. As prime factorization is a key element in todays public key cryptographic schemes because it is an NP problem for classical computers, i.e. the time necessary to factorize a prime number scales exponentially with the size of the number, a polynomial time algorithm, turning it into what is called a P problem, means a break down of our current electronic security.

Now, quantum computers are very elusive and that's because they relie on entanglement of quantum systems to make the miracle of transforming an NP problem into a P problem. More detailed explanations can be found in the book Quantum Computation and Information or in some sites in the internet:

The Quantum Computer, An Introduction by Jacob West
Lectures on Quantum Computers by David Deutsch
Quantum Computation. Mini-Course, by André Berthiaume

It is difficulty, although, to keep entanglement for a sufficient time to do any useful calculation, for entanglement is quickly lost as it is impossible to avoid interactions with the environment which causes entanglement to fade. D-Wave has just claimed it was successful in doing this for 16 qubits, which is a quantity of information that is already interesting.

Most of physicists, including me, are skeptical about that because D-Wave haven't released to much information about how the computer works and, as groups around the world have been trying it with a lot of different techniques without great results until now, it is surprising that they've achieved it so fast. Anyway, it would really be something exciting if they do that. Let us wait.

While you wait, a press release on PhysicsWeb

Firm claims first "commercial" quantum computer

and a YouTube video of D-Wave's presentation



Picture: taken from The Economist.

PS: I intend to edit this post a little more, adding some links, but I don't have too much time today and I'll do that during the next days.