IF YOU’VE always wanted to have a quantum computer, what are you waiting for? You can already use your PC to harness the quantum world and do things no normal computer can manage.
OK, we’re not talking about a computer that uses quantum properties such as entanglement and superposition to perform myriad calculations at once – you may have to wait a while before you can buy one of those. But what if you could spruce up your computer’s performance using random numbers generated by the quantum world? Such quantum random number generators already exist; the big surprise is that they could allow us to compute things that have always been considered beyond reach.
Although the technology of the computer has marched onward and upward, the theoretical underpinning of today’s machines still rests on the model of computation set out in 1936 by the British mathematician Alan Turing. He invented the concept of a “Turing machine”, a sort of simplified calculator that can model any computer you like, but whose relatively transparent workings expose the inherent theoretical limitations of what any (real) computer can compute. If no Turing machine can solve a problem, then that problem is not computable at all. This wisdom is encapsulated in the Church-Turing thesis, and can be illustrated with the famous halting problem, the Philosopher’s Stone of computer science (see “Knowing when to stop”).
Advertisement
The problem is that the Turing limit leaves us at a rather frustrating impasse. Many problems in maths, such as solving Newton’s equations of gravity for three-body systems like the sun, Earth and moon, have no solution in terms of elementary functions, and so computers can never solve them either. At the moment, the best way to study such things is via computer simulations, but even the simulations themselves may be impractical, demanding enormous amounts of computational time and/or memory.
There are many other “impossible” problems awaiting better computing power, and researchers have poured vast amounts of money and effort into developing new models of computing, based on natural phenomena ranging from relativity and quantum theory to molecular biology. Some have raised high hopes, others have been dismissed as science fiction. What is surprising, though, is that a simple method offering as much promise as any other has passed virtually unnoticed.
That method involves, you guessed it, randomness. Leaving aside issues of computability, Turing machines have another well-known limitation: they cannot generate truly random bits. Because they obey rigid rules, they can generate only “pseudorandom” strings of bits created by following a specific algorithm. Pseudorandom bits look convincingly random, but are in principle predictable, because they are the result of following a definite set of rules. For many purposes, this makes no real difference, but it occasionally has dramatic implications, as any cryptographer will tell you. Cryptographic systems designed to provide protection against snooping and spoofing should, in principle, use secret genuinely random numbers. Anyone creating an encryption scheme that uses random numbers, for example, must ensure that adversaries have a very low probability of guessing or being able to determine the numbers involved. As the output of fixed rules, pseudorandom bits are inherently vulnerable to this.
But if we supplied, say, a PC with a source of truly random numbers, might we have a machine that could do things a Turing machine could not? The answer is yes, for reasons that we will explain shortly. And constructing such a machine is surprisingly easy. For example, a firm called id Quantique of Geneva in Switzerland markets a quantum mechanical random number generator called Quantis. This system generates random bits by looking at what happens when photons hit a half-silvered mirror. Each photon has a 50 per cent chance of transmission or reflection. The device can supply an arbitrarily long string of random bits fast enough for cryptographic applications. Plug this into your PC and you can, in theory at least, pass Turing’s barrier.
It has to be said that the true randomness of such numbers is not mathematically proven, and may not be provable. The quantum processes behind them are believed to be inherently random, but this is merely postulated and is not at all a mathematical consequence of the standard model of quantum mechanics. It may simply be an artefact of the particular mathematical apparatus we use to describe quantum phenomena. But being pragmatic, perhaps we can just accept this randomness because of the success of applications of quantum mechanics.
In any case, we know that quantum processes can’t be simulated on a rule-bound Turing-type machine. The reason, in physicist Richard Feynman’s words, is that “it is impossible to represent the results of quantum mechanics with a classical universal device”. So we can be confident that, whether or not they truly are random, plugging quantum “random” bits into a standard computer inevitably takes us beyond the capability of a Turing machine. That’s because the PC can be programmed to produce an arbitrarily long, but finite, quantum random string, whose information is then unleashed during a computation. The random string enables the computation to take a path not open to a standard Turing machine, and thus makes it superior to any standard computation.
Exactly how much more powerful such a machine could be is a fascinating open question. It looks unlikely to be able to solve the halting problem, but even this has yet to be proved. Such a device will outperform a standard Turing machine in tasks such as generating mathematical theorems from any given set of starting assumptions, but even this machine cannot generate all true statements of arithmetic. However, after decades of waiting, beating a Turing machine is not a bad place to start the random revolution.
Knowing when to stop
It is Turing’s most famous – perhaps infamous – problem, and one that could open a huge box of knowledge. Simply put, the challenge of the halting problem is to decide whether a Turing machine given some problem will ever find a solution and stop or grind through the computation for ever. Here’s an example: assume you want to know whether every even number greater than 4 is the sum of two primes.
We can see that 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 32 = 3 + 29, and so on. In fact, this is a famous puzzle known as the Goldbach conjecture, and has been verified computationally for numbers up to several million billion. But is it true for all numbers?
One can construct a Turing machine that checks each of the even numbers in turn to see whether it has this property, and stops only when it finds the first exception. Clearly, knowing before you start whether this machine will stop or not answers the original question. But Turing himself proved in 1936 that this is one example of a more general problem.
The halting problem is to decide whether an arbitrary program for a Turing machine halts after a finite number of steps for a given input. Using a hypothetical computer that could mimic the operation of any machine, Turing showed that there are no instructions you can give a computer that will enable it to decide in advance whether a given program will ever finish its task and halt. You just have to run it and wait.
That wait might be for more than a billion years. But even if we can use true randomness to step across the Turing limit, there is no guarantee of being able to solve the halting problem.