# Quantum computing

By Shaun Hendy 06/10/2010

On Thursday evening, I will be talking about quantum computing on Bryan Crump’s radio show (Nights, Radio New Zealand National, 8.42pm, 7 October).

Bryan and I have had several conversations on the workings of contemporary computing technologies, from quantum mechanics to transistors, and then on to how transistors are assembled into integrated circuits

This week, I want to take a look at what might be on the horizon in computing, thanks to some of the more exotic quirks of quantum mechanics and recent breakthroughs in quantum technologies.

Quantum computers promise to be very good at doing things like breaking codes.  Conventional computers were developed to crack codes in World War II, and they played a decisive role in helping the Allies to their eventual victory.

Any modern code must designed to exploit the weaknesses of conventional computers or it won’t stay a code for long.  One drawback of conventional computers are that they are relatively slow at breaking numbers down into their prime factors (e.g. 12 = 2 x 2 x 3) — this makes it possible to build strong codes that are based on factoring large numbers.  It turns out that this something at which quantum computers would excel.

Two bits or qubits

Let’s just remind ourselves that modern computers work by turning transistors on and off.  You can obviously use the on/off state of a transistor to store information:  e.g. if you assign the value 1 to ’on’ and 0 to ’off’ to a single transistor you can represent one ’bit’ of information.  If you have two transistors, you can represent four binary numbers, 00, 01, 10 and 11 by their on/off states.  So with two transistors, you could store a single number between zero and three.

Quantum computers, however, store information using qubits (pronounced ’kewbits’) rather than bits.  Like a bit, a qubit can be on or off, but curiously, it can also be both on and off at the same time.  While this may seem pretty strange, it is certainly useful, since with just two qubits we can store four numbers between zero and three.  In fact, with qubits, a quantum computer can store exponentially more than a traditional computer with the same number of bits.

Quantum superposition

But how can this be?  In quantum mechanics, when an object seems to be in more than one state simultaneously, we say that it is in a superposition of states.  It is a strange sort of thing, but the fact that this can happen appears to be a fundamental property of the universe we live in.

There must be a catch.  In fact, there are several.  The first is that it is very, very hard to keep a qubit in a quantum superposition for even a short period of time.  A slight thermal vibration, a collision with a stray photon or any attempt to read the qubit will destroy the superposition.  There are only a few reliable technologies that have been developed that can keep qubits in a superposition long enough to do something useful with them.

A second problem is that when we want to read the state of a collection of qubits, we can only access one of the many numbers that are stored in the superposition.  And it gets worse — we can only select one of these numbers at random, we can’t choose which one we want to access.  Although Einstein famously wrote that God does not play dice, quantum mechanics certainly does.

A superposition of problems

These problems are as challenging as they sound.  Luckily, there appear to be some ways around them.

First, if there is only one number you want from your computation, then only being able to access a single number stored in a qubit array is fine, provided it’s the right number.  Algorithms can be developed so that the chance is high that the number that is read from a qubit array is the right answer.  And even if you have to run your computation over and over again to ensure you are getting the right answer, it could still be faster to use the qubit computer rather than a conventional computer.

But how do you compute things in the first place if the numbers you need to compute with are stored in a superposition of states in a qubit array?  It turns out that superposed states in a qubit array can interact with each other, if the qubits are entangled.

Entanglement

Entanglement is another peculiar feature of quantum mechanics, where the state of one quantum system depends on the state of another.  What is peculiar about systems that are entangled is that a change in the state of one system can effect the state of the other, even when the systems are some distance apart.

In an age of wireless communication, this may seem mundane, but there is something quite different about entangled systems.  They don’t communicate any change in state using signals like a wireless device; rather, their states are intrinsically linked by what Einstein called spooky action at a distance.  Changes in the state of one system are instantly reflected in changes in state of the other.

This may have spooked Einstein, but for our purposes, it means that entanglement between qubits can be used to perform quantum computations.

So what can be done?

Any practical quantum computer would need to keep its qubits entangled for long enough to do such a computation.  Many of the approaches that have been suggested for doing this use arrays of single atoms as qubits, and to keep them in entangled states you need to keep them very, very still.  A single tiny vibration will destroy the quantum superpositions.

But recently a team of physicists from the University of Otago took an important step by capturing an atom dead still in something called an ’optical trap’.  Using lasers, they were able to show that they could repeatedly suspend single rubidium atoms and hold them very still in the beam for long enough that a computation should be possible.

To build a viable quantum computer, the Otago team would still need to put a large array of trapped atoms in close contact.  Theoretical arguments suggest that it would then be possible to perform some simple computing tasks faster than a conventional computer.  Many people will have taken notice of the Otago team’s progress as they work towards a full quantum computer.

And where do I get one?

Well, I for one am keen to get a quantum computer, as it has been shown that they would be very good at doing quantum chemistry, something that people in my research team are very much involved in.

However, I may have to wait a while before I can pick one up at Dick Smith’s.  While there are many promising approaches to quantum computing, including the route being pursued by the Otago group, and some simple computations have even been carried out, it is likely to be a few decades before Apple puts a ‘must-have’ qPod on the market.