Does a real instant password cracking quantum computer exist, or are we just at the beginning of the next revolution in computing?
(Note: The first half of this article was published last year at Linux-mag.com, however the second half was never published. Both parts have been updated and are presented below.)
Recent news by IBM describes very good progress toward the creation of real quantum computer. The work helped solve the stability problem associated with many quantum computer designs. There have been other quantum computer announcements over the last year. In May of 2011 a press release by DWave Systems proclaimed D-Wave Systems sells its first Quantum Computing System to Lockheed Martin Corporation. The press release created a bit of a stir in the quantum computing world and as with any new technology there is often some confusing (some deliberate) around actual milestones and press releases.
Quantum computing is a complex topic because it brings in to play something most people find hard to understand -- quantum mechanics. Let me put you at ease. Eminent Physicist Richard Feynman expressed it this way; "I think I can safely say that nobody understands quantum mechanics." Fortunately, we can still use things we don't fully understand, but quantum mechanics (QM) is a strange beast. The physical reality suggested by QM does not sit well with how we perceive our slice of the universe. Be prepared, it is going to get a little weird.
Because this is a new topic for many people, I decided to provide some background on Quantum Computing and then address what D-Wave has accomplished and what quantum computing (if it is achieved) means for the rest of us.
The first step in understanding QM is to look at the picture below. What do you see? If you see a skull you are correct. If you see a man and a woman you are correct. Both images are in the picture, but you can only see one at a time. This picture is an loose example of "superposition of states," that is, something that exists in two (or more) states at the same time. It only takes on one of the two states when we look at it (or measure it with our eyes). This type of example was suggested by Dr. Boaz Tamir. Actually he used a better, but more complex example. Besides, I thought the skull was a bit more dramatic.
In the quantum world things can exist in two (or more) states at the same time. The particle wave duality is often taught in freshmen chemistry, as is the paradox of Schrödinger's cat and other such curiosities. In any case, quantum computing relies on this property to do parallel computation.
Keep in mind that measuring something that is in a superposition of states causes it to collapse into a definite state. The act of measuring creates an interaction of a measuring device (energy) with the quantum object. Thus, quantum objects are very fragile, and when they interact with other objects they exhibit "decoherence" and take on a definite state. The reason we exist in one state is that we are in constant interaction with our surroundings.
The next property is "entanglement." Consider again the picture above for a simplified description of quantum entanglement. If you are "entangled" with someone, then the minute your eyes see one view of the picture, their eyes will instantly see the alternate view. Your entangled partner could be in the next room, across the country, or anywhere in the universe and the effect would be the same. Curiously, entanglement "effects" can move faster than the speed of light, which lead Einstein to call it "spooky action at a distance." Books have been written about this topic, but for our purposes, we just need to understand that entanglement is real and can be created between two or more atoms (or quantum objects).
We are just about ready to build our quantum computer. First we need a way to store information. In a classical computer, like the one you are using, we use "bits" to store information. A bit has two states; a "0" or a "1" at any given time. In a quantum computer we use something called "qbits." A qbit is like a bit, but it is in a superposition between "0" and "1," but not ".5" or some other value. It is a superposition of two states, like the above picture before you look at it. There are no other pictures in between the two views (I bet you just looked and caused the picture to "decohere" into one of the two states).
Qbits are written as |0> (state "0") or |1> (state "1"). In a quantum computer however, a qbit is fully expressed as a|0> + b|1>, where a and b are "sort of" the probabilities of being in either state and (a^2 + b^2) = 1, which is the probability that the qbit must be in one state or another. Now consider a quantum computer with three qbits. There are eight possible states, a|000>, b|001>, c|010>, d|011>, e|100>, f|101>, g|110>, h|111>, where a,b,c,...,h are "sort of" probabilities of finding the three bits in any one of the states. In a quantum computer the three qbits are in all eight states at the same time, whereas in a classical computer, the bits can only be in one state at a time.
It is possible to add a number to the three qbits, which means all eight states will change at the same time. The ability to operate on all the states at the same time is why quantum computing can be so powerful. The number of simultaneous calculations (quantum parallelism) depends on the number of qbits, that is 2^N, where N is the number of qbits. For instance, with 32 qbits, you could have 4,294,967,296 parallel computations.
I have obviously skipped over some details, but the general principle is as described. By operating with qbits in superposition, all states are acted upon at the same time. Quantum logic gates can be constructed by using entanglement to link qbits. There are algorithms that have been devised to run using this type of system, but they are not easily programmed. Sorry no qperl or qFortran just yet. And, not all types of applications can use quantum parallelism. Finally, there are some difficulties in making all this work as well. The recent news by IBM helps stabilize quantum computing qbits, which should help with actually building a real device.
By using the superposition of states a quantum computer can, in theory, contain all solutions to a problem simultaneously. An easy way to understand this process is to use the Many Worlds interpretation of quantum mechanics. While I don't really endorse this interpretation (I lean more toward the Transactional interpretation), it does provide an easy way to understand what happens to all the quantum states when a quantum object "decoheres" into one particular state.
The many worlds interpretation basically says each time a quantum object takes on a definite state, each possible state splits off into it's own universe. Thus, if you consider the picture above as a quantum object, it will create one of two universes when it is measured or viewed. That is, we would look at it and see one or the other interpretation each occurring in its own universe, a bit heady when you think about how many alternate worlds there are with other versions of "you" in them.
If we leave out the head spinning issues of the many worlds interpretation, we can use it as a clever way to think about quantum computers. That is, the multiple solutions held in the superposition of states are each a separate universe. Thus, a quantum parallel calculation is like running the calculation in many universes at the same time, each one holding a solution (state) of the quantum computer. The ultimate parallel computer, to be sure.
One final topic that we need to cover is the Heisenberg Uncertainty Principle. In plain English, we can not know both position and momentum of a quantum object. The more we define one property, the less we know about the another. The wave/particle duality found in quantum objects is a good example. Consider the length or position of a standing wave: if we try and smash the wave into a point particle, the frequency increases to infinity. Thus, we can know the exact energy of a standing wave, but the position is smeared out. Conversely, we can know the exact position of the wave, but the energy has gone to infinity. This effect is used to explain quantum tunneling, where quantum objects are known to move through small but real barriers that would be impossible for classical objects. The tunnel diode is a commercial example of this effect.
Getting back to the original press release from D-Wave, is this a true quantum computer? The question is important, because if it is, there could be some problems for many well known cryptography systems. In 1995, Peter Shor surprised the cryptology community by proposing a quantum algorithm that can be used to rapidly factor large numbers.
Take for example, public/private key encryption such as RSA, which is used for encrypted web data (ssh) and many commercial transactions (SSL). To crack such a system, you would need the public key and a very fast computer to determine the private key, which is used to decrypt the message. Keys can be made stronger by increasing their size, thus, large keys are much harder to crack than small ones. With our current computer technology, cracking large keys is computational intractable (i.e. it will take too long even with all the computers on the planet).
All this changes with a quantum computer that can run Shor's algorithm. It has been shown that a quantum computer with a sufficient number of qbits can crack any commonly used RSA key in a mater of seconds. Large key values do not help much. All is not lost, however, there are some encryption methods that hold up better to quantum attacks (for now).
Someone possessing a true quantum computer would basically render much of the world's encryption mechanisms obsolete. Fortunately, that does not seem to be the case. The aforementioned press release states that Lockheed Martin has purchased a D-Wave quantum computer (I have emphasized quantum computer because D-Wave previously sold a system to Google, but did not call it a quantum computer). Specifically, D-Wave is calling it a quantum annealing processor, which requires a further bit of explanation. Simulated Annealing is an optimization algorithm for classical computers. One of the key issues with optimization is the trade off between computation time and the quality of solution. Some problems may even be computationally intractable and yet have a known solution. Simulated annealing is a method that allows optimization of hard problems within a reasonable time, but does not guarantee the best result (it will find an optimum solution, but it may not be the best solution).
Quantum simulated annealing uses the tunneling effect to find maxima that may otherwise may be harder to find using classical methods. In other words, using quantum tunneling it is possible to find better optimizations faster. The D-Wave system uses eight qbits to perform these optimizations. Thus, the interest from a company like Lockheed Martin, who spend a great deal of time maximizing and minimizing things.
When D-Wave announced the sale of their first quantum annealing computer, there were questions about whether their system actually exploits quantum annealing, or just performs classical simulated annealing. D-Wave recently published a paper in Nature that supports the quantum annealing effects, but there is a large amount of discussion as to whether it is a true quantum computer. Scott Aaronson, an Associate Professor of Electrical Engineering and Computer Science at MIT, has been critical of some of the claims made by D-Wave. There is also an interview in Forbes that will help shed some light on Aaronson's concerns.
Recently, in January of 2012, DWave announced the use of 84 qbits to solve a rather complicated math problem. You can balance the progress with further comments from Aaronson's blog. Hopefully, the background provide herein will allow you make some sense of these discussions now and in the future. There will undoubtedly be more developments in this field and the prospect of true quantum computers is a mind-boggling possibility. In summary, your silicon bits (and passwords) are safe for now. In my opinion, true quantum computing is still living happily in the future. At least in this universe.