Deutsch - computers may use matter that outdoes the brain

I shall now try to describe Deutsch's scheme for building a quantum computer. He does not actually try to use some wierd new form of matter like my hypothetical halting crystal. Instead, he exploits quantum phenomena that exist everywhere, but which are usually invisible at a macroscopic scale.

Before I can do so, I must delve into quantum physics. Most of Deutsch's papers on this are very technical, and you're only likely to be able to read them if you start working on such things professionally (but if you do, it will provide - albeit not for ten or fifty years, perhaps - a major advance in computation.) There's a comparatively non-technical account in Mind, Brain and the Quantum by Lockwood (PSY AA:L 081), chapter 14.

Summary of what you must know in order to build a quantum computer.

• Consider an electron or a nucleus in a magnetic field. You can imagine it as a ball spinning about its axis of rotation. Electrons and nuclei have an electric charge. Because they're spinning, this causes a magnetic field which points along the axis.

  The axis of rotation can point in various directions. But - first wierdness - unlike in everyday experience, the directions are quantised. Only a finite number of directions is allowed. This number depends on the particle's electric charge.

  The simplest possibility is that the particle could be pointing ``up'', or ``down'', but nowhere in between. In this case, we say that the particle is either ``spin up'' or ``spin down''. I will ignore particles with more than two possible spin directions in the rest of these notes.

• As I said in the 6th week lecture, today's computers represent numbers in binary. Each number is represented as a series of binary digits or bits. For example, the number 3 would be represented as binary 11, and the number 8 as binary 1000. We can encode instructions in binary too. Each bit is stored in a separate memory cell.

• In conventional computers, these cells are built from cross-coupled transistors. But if we can find some way to make electrons or nuclei hold still, we could use a single particle to represent a bit. Use an electron with spin up to represent a 0; an electron with spin down to represent a 1. It would be possible to read out the state of a bit, or to change it, using a method related to nuclear magnetic resonance. We could then build an entire computer memory out of cells, each of which holds a spin-up or spin-down particle.

• In everyday physics, any object can exist in only one state at a time. You can't have a door that's both open and closed, or a ball that's spinning both clockwise and anticlockwise. But in quantum physics - second wierdness - you can. Particles can exist in a superposition of states, also called a mixed state. So you can have an electron that's both spin-up and spin-down at the same time.

• Actually, each component state has a probability associated with it. So our mixed electron is not just spin-up+spin-down, but is (say) 40% spin-up + 60% spin-down, or perhaps 27% spin-up + 73% spin-down. You can also have pure states: it's possible, even in quantum physics, for our electron to be 100% spin-up + 0% spin-down.

• This means that we could prepare our computer memory so that some or all of the cells are in mixed states. Think of such a memory as a collection of film strips lying on top of one another. Each strip is a memory in some particular collection of pure states. Each frame in the strip is one cell, one particle. The entire set of superimposed strips is a memory in a collection of mixed states.

• It's possible to build a CPU which, given a mixed state, processes it as though it were processing each of the component states independently. This gives us a kind of parallel processing. We put in a collection of memory cells in mixed states, and we get out a collection of cells in different mixed states. Our CPU is processing all the film strips at the same time.

• This gives us a form of parallel processing for free. If we'd built a conventional (non-quantum) parallel computer, we'd need one CPU for each strip. But here, we have one CPU which is, in effect, processing all the strips simultaneously.

• So far, what I've described is something which carries out a lot of computations in parallel. Since each of these can be done on a serial computer, the quantum machine can't do anything a Turing-equivalent computer can't do. But it can do so faster. So it is more powerful in a weak sense; it pushes back the limitations of complexity theory I described last week.