home | forays | article

• What is classical computing?
• What is the Church-Turing thesis?
• What is decidability?
• Are neural networks any better than ordinary classical computers?
• What is quantum computing?
• What would a quantum neural network look like?
• Would the Church-Turing thesis apply to a QNN?

Every computer that has ever been built is a Von Neumann computer. They compute algorithms by following simple discrete instructions (the machine language codes) which are fully deterministic and serial. Their performance is implemented by finite state units of information known as ‘bits’, and logic gates that operate on these bits. This is called the Classical model of computation. Essentially Babbage’s Analytical Engine of 200 or 300 years ago, was as computationally powerful as today's most powerful supercomputers. There is no problem that the modern day computer could solve that the Analytical Engine could not also eventually solve, given enough time. This idea is summed up by the Church-Turing thesis.

The Church-Turing thesis is not really a theorem of Mathematics. I.e. it cannot be proven – it just seems intuitively correct. It was created independently by Alonzo Church and Alan Turing. Basically it says that all mechanisms for computing algorithms are inherently the same. It claims that no method we use in our head to solve some problem cannot be expressed as some sort of computer program. This seems true. For instance, if you were asked to multiply two numbers together, you would probably follow a simple algorithm which could be easily implemented as a computer program. If you were asked to factorise a number, you would also use some approach that could be written down as a program. The point is, there seems to be no algorithmic problem that can be solved by a person that can’t be solved by a computer. And the same is true in reverse. Any computer program could obviously be taken by a human, and executed with pencil and paper. More importantly though, the Church-Turing thesis claims that only partial recursive functions which terminate can be programmed. Termination is the central part of the thesis.

A Turing machine is an abstract computing device to which all existing computers can be reduced. It consists of a read/write head, and a long piece of tape. The head can read symbols from and write symbols to the tape. At each step, the machine can decide what to do next by following a very simple program consisting of conditional statements, read/write commands or tape shifts. The tape can be as long as we like to solve a particular problem, but it cannot be infinite, and this is the key point. If a problem can be solved, it can be solved on a Turing machine with some finite tape. It is the Turing machine which is used to illustrate whether or not an algorithm can be computed in finite time and space. If it cannot, then the algorithm is not decidable.

An axiomatic system is decidable whenever there is a Turing machine that can determine which statements of the axiomatic system are true and which are false. If a program can be created for a Turing machine that will take all statements of an axiomatic system, and determine their truth values, then the system is decidable. What that amounts to in essence, is finding a finite terminating algorithm for determining if a statement is true or false. Any algorithm that can do this is said to be computable. The Church-Turing thesis says that there is a level of computability which we cannot exceed. All computers use this level of computability. Therefore all computers are computationally equivalent. The question is really asking if quantum neural networks (or quantum computers in general) can use a level of computability above or beyond the Church limit.

A neural network is a structure that functions due to connections between nodes or neurons. It does not use any formal symbolic notation as do ordinary computer programs, it simply learns by example, to reproduce an output given an input. (I'm limiting myself to ordinary feed-forward networks here – the same argument can be extended to any kind of network). Does this mean that it has some extra inherent level of complexity beyond symbolic processing? The answer is clearly no. Most neural networks are simulated on standard classical architectures anyway, so there is no way that these could be more powerful. What about networks implemented in hardware? Again, the answer is no, since these use the same models as those implemented in software. We can say therefore, that a Turing machine could be constructed to represent and calculate like a neural network. If this is true, then no neural network could be more computationally powerful than an ordinary classical computer – indeed they are equivalent, at least in the decidable sense.

Whether a quantum neural network could be more powerful than an ordinary neural network is something I will leave until I have discussed the current theory on quantum computers.

A 'qubit' is a quantum bit, that can be thought of just like a digital bit in a computer, except for one important difference. Although in a digital computer a bit can only have the value 0 or 1, a qubit can have the value 0, 1 or both simultaneously. I’ll explain what is meant by that in a moment – first I’ll say how a qubit can be built.

We can construct a qubit with an atom of some element – let’s use hydrogen as an example. The hydrogen atom consists of a nucleus (which does not concern us), and an orbiting electron. This electron can exist in different energy levels, or orbits about the nucleus. These different orbits can be used to represent the binary 0 and 1 we are familiar with in digital computers. We could assume, for instance, that a hydrogen atom in its ground state (i.e. the state when the electron is in the lowest orbit) represents the value 0. Similarly we can say that such an atom in its first excitation level (or when the electron is in the next highest orbit) represents the value 1. To move the electron between excitation levels, we can subject it to a pulse of polarised laser light – essentially, we inject photons into the system. As photons are injected, the electron begins to move between one energy level and the next. So to flip a bit from 0 to 1, we just have to fire enough light at the atom to move the electron up an energy level. To flip from 1 to 0, we do the same thing, since overloading the electron will cause it to drop back down to its ground state. This is logically equivalent to a NOT gate, something that we require in a computer to do computation. Using similar ideas, we can construct AND gates and COPY gates which are the three basic components for building a computational device.

So far, there is no qualitative difference in using conventional bits to qubits, but something strange happens if we fire only enough light to move the electron half way between excitation levels. Since electrons cannot actually exist in the space between their excitation levels, they exist in BOTH levels simultaneously. This is known as ‘superposition’. This superposition allows us in theory to compute several possibilities at once, since a group of qubits can represent several numbers at once. If we take one ‘qubyte’, that is 8 qubits, then we can represent 256 numbers simultaneously. With more qubits, the quantity of representable numbers rises according to 2^n where n is the number of qubits.

To calculate things with the superpositional property, we can make a number of qubits, raise them to their superpositions, and then perform an algorithm on them. When the algorithm is finished, the superposition can be collapsed, and a true definite answer will result – i.e. all qubits will jump into either their 0 or 1 states. Basically, you can think of the algorithm as being run on all possible combinations of the definite qubit states (i.e. 0 and 1) in parallel, a trick known as quantum parallelism.

So, the real question here is if quantum computing as it stands offers anything not already achievable by ordinary classical computers. The answer is, of course, that it does. It provides enormous speed advantages. Consider a problem which takes an extremely long time to compute on a classical computer, such as factorising a 250 digit number. It is estimated that this would take approximately 800,000 years to factorise with 1400 present day classical computers working in parallel. Even as computers improve in speed and we learn ways of better integrating large scale parallelism, the problem is still exponentially expensive to compute. However, with a quantum computer, the complexity of the problem would be reduced to polynomial time rather than exponential. It would be possible for instance to factorise a 1000 digit number in just a few million steps. The central thrust here is that using the parallel nature of quantum effects (i.e. superposition), we can compute all possibilities simultaneously.

However! This is not the Holy Grail of computation. Quantum computing, at least in this incarnation, does NOT allow computations any more complex than can be performed on ordinary classical computers. The size of problems we can solve is limited to the number of qubits we use and we cannot compute problems without a terminating case in necessarily finite time. In this respect then, a quantum computer is nothing more than a quick Turing machine. Basically, the point is that a quantum computer in general is still subject to the constraints of the Church-Turing thesis. There are a couple of highly weird theories about how this may be circumvented, but I’ll bring them up at the end of my talk.

Whether the Church-Turing thesis holds true for all quantum computers is in some doubt. The QC’s mentioned so far operate in a very similar way to ordinary computers (i.e. with bits and logic gates and memory and so on), but there is no direct reason to assume that this means we cannot construct other types of QC’s that are inherently more powerful. One such model may be a quantum neural network. Although one could build a QNN using qubits and so on as described above, this would be analogous to constructing an ordinary neural network on a classical machine, and as such would only offer speed, not computability, advantages over ordinary neural networks. If we wish to construct a QNN that is not restrained by Church-Turing, we must think of a radically different approach to qubits and logic gates. This is of course very difficult, and has not been seriously attempted yet. Some proposals do exist though, which may begin the search for a new type of quantum computation.

There seem to be several research institutes around the world working on the concept of a quantum neural network, for instance Georgia Tech and Oxford University. Most however are reluctant to publish any of their work. This is probably because building a QNN is potentially much easier than an ordinary QC, and each institute wants to win the quantum race. Theoretically, it is simpler to build a QNN than a QC for one reason. Coherency. The superposition of many qubits decreases the resistance to noise in a QC, and noise can potentially collapse or decohere the superposition before a useful computation is achieved. However, since a QNN would not require very long periods or very many superpositions, per node, it would be less susceptible to noise, while still performing computation similar to, but many times faster (exponentially in fact) than a classical neural network.

A QNN would presumably gain its exponential speed advantage through superposition of values entering and exiting a node. But another advantage that could be gained is that since nodes can be used to calculate over many superpositional possibilities, the model may actually requires less hidden neurons to learn functions. This would lead to simpler networks with less nodes, and hence improved stability and reliability (i.e. there would be less ways in which the system could lose coherence).

With all this in mind however, would a QNN be any more powerful computationally than an ordinary network? At present, the answer seems to be no, since all quantum models rely on some finite number of qubits to perform their calculations and this is the limiting component.

I mentioned earlier that some very strange theories existed on how one might use a quantum computer to perform algorithms inherently more complex than those solvable by a Turing machine. Bear in mind that these are highly speculative (which I suppose the whole field of quantum computing is anyway). To perform a computation with no halting state (i.e. an algorithm which is not decidable) would not be possible on either a classical computer or our current model of a quantum computer. For instance, proving Goldbach’s conjecture by examining all cases simultaneously. Goldbach’s conjecture is this : "Every even number can be represented as a sum of two odd primes." One could write an algorithm (which doesn’t terminate) to solve this problem simply by taking each even number in turn, then searching the whole of the natural numbers to find the two odd primes that sum to it. If we could run this algorithm for an infinitely long time, then we could find the odd primes that sum to every even number. Of course, this is not possible on a Turing machine, because there is no terminating case. And since a quantum computer is computationally equivalent to a Turing machine, it cannot calculate the answer either.

One interesting solution to this problem suggests we use a wormhole to solve the problem. If we generated a wormhole in the form of a closed loop and used it as part of our quantum computer, we could have the infinite amount of time needed to compute the answer, simply by running the computation in the closed, infinite loop. Another suggestion is that we expand the wormhole into what is known as a ‘basement universe’ – essentially a new universe within our own – and then generate another basement universe inside that one, and so on ad infinitum. If we create these universes with a time dilation effect (through general relativity), then we can make each run at a slightly faster speed than its parent. All we have to do then is spawn a copy of our quantum computer off into these basement universes, and it into its child, and so on, and it will return the result of an infinitely long computation in a finite amount of time – in fact, immediately.

These theories are pretty crazy, but interesting nonetheless. They provide some way of escaping the decidability constraints of the Church-Turing thesis, something which our existing model of a quantum computer cannot do. If some plausible design for a quantum neural network that operates on different quantum principles was created, then it’s possible that it too would not be subject to the thesis. However, this seems very unlikely, as all models so far, quantum, classical, connectionist or otherwise, have basically analogous components and drawbacks.