To read all comments associated with this story, please click here.

In short, quantum computers are very good for solving problems which have lots of possible solutions through brute force, because they can test all possible solutions at once.

I don't see them replacing current desktop computers, at least not in the upcoming years. It's much harder to produce and program a quantum computer for a small benefit on everyday tasks (where for most people today's processors are already good enough). But there are several areas of computing which would benefit from those. Consider looking for something in a database, as an example...

A lost of current cryptography algorithms (like RSA) are going to be totally broken, because they are vulnerable to brute force attacks. Their authors did not expect that one day, computers would be able to test every single possible private key *at once*.

On the other hand, quantum mechanics have also major potential benefits in the information concealing area, because quantum information cannot be copied (to the best of physicists' knowledge at least), which means that communications based on quantum objects cannot be looked upon or otherwise altered without both parties knowing about it. That's the principle behind quantum cryptography.

*Edited 2011-01-23 18:20 UTC*

In this way, quantum computing (which is a completely different computing paradigm) would allow

**NP**problems to be solved in

**P**time on a quantum computing device. In order to confuse symbolic logicians everywhere, I propose

**P**time on a quantum computing machine be cannonicly called

**QP**(or maybe

**C3PO**).

*A lost of current cryptography algorithms (like RSA) are going to be totally broken, because they are vulnerable to brute force attacks. Their authors did not expect that one day, computers would be able to test every single possible private key *at once*.*

This is indeed REALLY scary. If you know the hash to someone's password it'll be a matter of seconds to find it out. And you can't really sign your applications or anything anymore since it's again just a matter of seconds of finding out the original key. The same goes for WPA2-PSK: no matter what kind of password you use, it'll be broken in seconds.

What's even worse though is that encrypting your files, using compressed, encrypted files, or even encrypting the whole filesystem will become useless if the algorithm is known! Basically, protecting your files will become almost impossible if the attacker has access to a quantum computer, and we can bet that there will be Amazon EC2-like service available sooner or later.

"A lost of current cryptography algorithms (like RSA) are going to be totally broken, because they are vulnerable to brute force attacks. Their authors did not expect that one day, computers would be able to test every single possible private key *at once*."

This is completely wrong. RSA and ECC will be broken due to Shor's algorithm, not due to instantaneous brute force attacks. Brute force approaches only get a O(n^2) speedup on quantum computers due to Grover's algorithm.

That's why hash functions, block ciphers and all the other primitives will still be secure (if we double their key/internal state sizes).

Fortunately, research in Cryptography already is studying problems which seem to be resistant to quantum computing power. The whole area is called Post-quantum Cryptography and they already have a stable conference. The primitives are normally built on top of NP-hard problems (which up to now only receive a quadratic speedup in a quantum computer).

Availability of quantum computing power does not imply that P = NP because until now no one could map any NP-hard problem for an efficient (polynomial) solution in a quantum computer.

True. I would just add one further point: all encryption methods are, from a mathematical point of view, vulnerable to brute force attack since they cannot use a key of infinite length. In practice this is less true due to implementations restricting how a user can determine if a key is valid or not.

With quantum cryptography the uncrackable one-time pad would still be secure. Even if you generated a complete super-key you have no way of knowing if its valid until you compared against all sub-keys. And since these are never reused, you could never know its valid until all the sub-keys were used up.

Using quantum cryptography to securely (as in it is impossible for 3rd parties to read the key without us knowing) transmit a one-time pad key, would still be 100% secure.

The current method used by financial companies that trade on the stock market is to transport a very large key (gigabytes in size) physically using a flash drive with security guards. This is the one-time pad, and each time a transaction is a made a piece of it is used as the key. This is also still 100% secure with quantum cryptography, because how can you ever know a quantum generated one-time pad is valid if the parts of it are never reused?

*Edited 2011-01-24 09:41 UTC*

It can also be used for nearly instantaneous communications of virtually unlimited data. I foresee entangled quantum arrays of even a small size ( even just a few dozen qubits ) being design to reflect a 'streaming' data stream from a given source.

Imagine TV signals without the need for transmission lines. Networking would become very quick, indeed.

To transmit data a group of qubits which are entangled with the master set are read at a specific rate. The master set is modified at the same specific rate, with a given duration per state held.

I do not see much in the way of providing master sets to the home user unless the entanglement can be dynamically altered on the silicon without fancy equipment. Which I am certain will be a goal.

A few qubits on a normal CPU will also permit massive gains in memory performance.

Unless I'm just missing something...

--The loon

Quantum entanglement does not work that way. You cannot use it to transmit information.

Although qubits can be in a lot of possible different states, those states cannot actually be read separately, even though they may affect intermediate computations. At best superdense coding ( https://secure.wikimedia.org/wikipedia/en/wiki/Superdense_coding ) can be used to get two bits out of a qubit.

Member since:

2005-11-18

It's my understanding that the applications for quantum computing are pretty specific, and it's unlikely we will have these machines in our homes? And our cryptography will be woefully broken?