## A Smidgen of Quantum Computing

- Details
- Published on Monday, 05 March 2012 11:22
- Written by Douglas Eadline
- Hits: 9755

### Article Index

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.

- << Prev
- Next