A Little (q)bit of Quantum Computing

I noticed a press release recently which states, D-Wave Systems sells its first Quantum Computing System to Lockheed Martin Corporation. After reading the press release and some other material on exactly what this quantum computer does, I decided it was time to discuss this topic. At least in this universe anyway.

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 it break into two installments. The first installment will cover some background on QM and Quantum Computing, while the second will talk about 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 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

When you look at the image, what state do you see?

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.

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. In the next column, I’ll talk about some of the practical issues and what kind of machine D-Wave is actually selling.