Quantum Computers

Quantum computers are a generalisation of conventional computers (otherwise known as classical computers) that use features of quantum mechanics to perform operations.

One way to think of a classical computer is as a physical system that can be in any one of a finite number of discrete states. Imagine, for example a computer with just 8 bits of memory so that it can store numbers from 0 to 255. We can write the complete state of such a computer as |n> where n is the number stored in it. Suppose this computer is hard wired with a very simple circuit so that it just counts. At each tick of the clock the number gets incremented - and when n=255 it gets reset to zero. We can describe such a computer as follows:

|0>->|1>
|1>->|2>
...
|255>->|0>

In effect any classical computer is just a more complex version of this: There is a notion of a current state and rules for making transitions.

Reversible Computers

Before we get onto quantum computers it is worth discussing reversible computers. Note how in the example above it is easy to find out what state came before the current state. For some computers this is not the case. Suppose we are programming in C and the computer executes
x = 0;

then whatever was stored in x before this is now lost. You can't reverse this step. The line

x = x-37;

is reversible. In fact we can reverse it by writing

x = x+37;

A reversible computer is one in which every step is reversible. In fact making sure that it logs at every stage enough information to reconstruct the previous state can make any computer program reversible. You can do this, for example, by using, in C or C++, the += operator rather than simply +.

Probabilistic Computers

We will consider one more kind of computer before getting onto quantum computers: probabilistic computers. These are computers for which the transition rules involve probabilities. For example imagine a variant of our counter that is unreliable so that it has a 0.9 chance of incrementing but also a 0.1 chance of decrementing. We can introduce a new notation to describe states of such machines: we write p|n>to mean a probability p of being in state |n>. We can then use addition to represent 'or' so, for example 0.15|3>+0.75|7>. means we have a 0.25 chance of being in a state with value 3 and a 0.75 chance of having a value of 7. In any given expression the sum of the coefficients should equal 1 as probabilities should always sum to 1. Representing probabilities algebraically in this way pays off as I will show. Write the transition rules for our faulty counter as follows:
|0>->0.1|255>+0.9|1>
|1>->0.1|0>+0.9|2>
...
|255>->0.1|254>+0.9|0>
Suppose we start in the state |2>. Apply the above rules for one step and we get 0.1|1>+0.9|3>. Applying these rules again we find

0.1(0.1|0>+0.9|2>)+0.9(0.1|2>+0.1|4>) = 0.01|0>+0.18|2>+0.81|4>

Using this algebra of computer states works and gives correct probabilities.

One obvious question is "Can we do more with probabilistic computers than with classical computers?" One approach might be like this: Let's say we have a function f and we know one of f(0), f(1), ... , f(255) equals zero but we don't know which. The problem is to find which it is supposing that computing f is very expensive. Well first we can describe the computer we need by the following simple rules:

|0>->|f(0)>
|1>->|f(1)>
...
|255>->|f(255)>
Now lets set our computer up at the outset in the state
(|0>+|1>+|2>+...+|255>)/256

If we now let the computer run we get

(|f(0)>+|f(1)>+|f(2)>+...+|f(255)>)/256

in just one step. In a way what we have is a bit like parallel computing - the operation f acts on all states simultaneously and gives a state that is a kind of mixture containing our answer. But think about what this really means - what we have described is the same as simply tossing 8 coins to decide what number we're going to test. So what do we get from using a probabilistic computer? Well we only had to evaluate f once so that's an improvement. Unfortunately we only have a 1/256 chance of finding the answer to our question. That's not much of an improvement. (Under some circumstances this might be an improvement of course - if your life depended on knowing which value of f was zero and you only have one time unit to spare!)

Quantum Computers

Quantum computers are generalisations of reversible computers. They are very like the probabilistic computer above except that in quantum mechanics the coefficients are allowed to be complex numbers. So suppose we have a state like a|0>+b|1> what does it mean? With probabilistic machines a and b are simply probabilities. With quantum computers a and b are called 'probability amplitudes'. They are converted to probabilities by taking the square of the modulus of the amplitude. (In order that the probabilities after summing and squaring total to one we must impose certain conditions on what operations can be performed. Operations that preserve probability and are reversible are called unitary.) Unlike probabilistic machines however a state like a|0>+b|1> doesn't mean "either 0 or 1" but is a kind of mixture. When we actually try to read the state of a quantum computer we must convert the coefficients to probabilities but if we don't try to read the state then quantum computers act a bit like they are in both states at the same time.

It's all very well having this kind of theoretical model but can these things really be built? The answer appears to be "yes!" because this is how the universe actually behaves at a microscopic level. You'll have to refer to a quantum mechanics primer for more details on that.

Having probability amplitudes that are complex numbers gives quantum computers vastly more power than probabilistic computers. One reason is this: adding two states together can make coefficients smaller. This can't happen with probabilities which are always positive (or zero). This means that it is possible to add two states and have a term suddenly become insignificant (or even zero). This forms the basis for many interesting quantum algorithms. For example Peter Shor of AT&T devised a quantum algorithm for rapid factorisation of integers. This exploits the fact that states corresponding to non-factors cancel out by summing to nearly zero leaving only states corresponding to factors. This phenomenon is called 'interference' - in this example destructive interference removes non-factors and constructive interference gives us our answer.

A quantum operation

One example of a quantum operation that cannot easily be performed on a classical computer is the 'square root of NOT' operation. It is the square root in the sense that if you apply it twice to 0 you get 1 and if you apply it twice to 1 you get 0. Here is the transition table for it:
|0>->a|0>+a|1>
|1>->a|0>-a|1>
where 'a' is 1/sqrt 2. (This value ensures that the probabilities sum to 1). This is a kind of halfway state between 0 and 1.

Notice how if you perform a sqrt(NOT) operation on a definite state you end up with a superposition of two states. Do two sqrt(NOT) operations, one on each of a pair of bits, and you end up with a superposition of 4 states. As you perform sqrt(NOT) operations the number of states you are superimposing goes up exponentially. This makes even simple quantum computers with this one operation computationally expensive to simulate.

Quantum Protocols

As interesting as quantum algorithms are quantum protocols. A protocol is an algorithm that requires 2 or more participants - for example a method of sending encrypted data to a co-conspirator. There are a number of interesting quantum encryption techniques that have actually been tested in practice - in principle making messages completely impossible to eavesdrop on.

Quantum Computers are Hard to Build

One or two bit quantum computers already exist - in fact you can imagine some standard physics experiments as hardware implementations of simple quantum computer programs. However in order to get quantum computers we generally need to build a device that has no interaction with its environment. If it did interact with the environment than you'd get a quantum mechanical effect called decoherence appearing and this would tend to make the quantum computer act more like a classical computer. Unfortunately implementing a multibit quantum computer looks like it's probably very hard, if not impossible. It can be shown that a non-reversible operation must produce heat as a by-product. This heat is an interaction with the environment - so this is part of the reason why quantum computers need to be reversible. But to build a large machine that has no interaction whatsoever with the environment is immensely difficult - even if all of its instructions are reversible. So maybe quantum computers are just a fantasy after all.

On the other hand there have been some very interesting attempts to deal with decoherence. In particular the construction of error-correcting quantum codes that could potentially fix errors caused by decoherence. Another related approach is that of decoherence free subspaces where decoherence effects are made to exactly cancel each other out leaving components that can be modelled exactly as if they were decoherence free.