There is a sense in which quantum computers represent the triumph of the many-worlds interpretation to date. Not because the feasibility of quantum computers proves the reality of parallel worlds—that claim is hugely controversial, and we will scrutinize it later in this chapter. But what is inarguable is that the many-worlds viewpoint helped David Deutsch, back in 1985, have the key insight that made quantum computing possible.

Deutsch was not the first person to speculate about the possibility of quantum computing. A couple of years earlier, Richard Feynman had already published a paper on the subject. ¹ The ever-imaginative Feynman put forward a whole range of ideas for harnessing quantum to make computers smaller and more powerful. However, his real interest was in making computations of a type that I would call analog rather than digital.

The idea behind an analog computer is that a physical quantity, for example, the flow of electric current or the amount of charge on a capacitor, can be used to represent a numerical quantity to high precision. For example, if you can measure the charge or current to one part per thousand, you can use it to represent a quantity to about three decimal digits of precision. If you can improve the accuracy to one in a million, you get six decimal digits.

At first sight, this seems far more efficient than a digital computer, where the current or charge in a given component is allowed to have one of only two distinguishable values, on or off, representing a single binary bit. The advantage does not end there. You can build analog electrical components to add, multiply, and divide such currents in a single hardware operation, a job requiring hundreds of individual bit-operations in a digital computer. In a nonquantized world, there is in principle no limit to the amount of information you can store in a single analog quantity.

It occurred to Feynman that even in our quantized world, systems that can yield only a limited amount of information on measurement—like which one of two detectors a photon or electron ends up hitting—may nevertheless signal the outcome of an enormous amount of behind-the-scenes processing. In single-world terminology this processing is effectively done by the evolution of a probability wave, which can develop a very complex form and can be made to interfere with itself in intricate ways. Feynman realized that you could in principle make the probability wave do a large amount of analog computation before registering its simple zero-or-one outcome.

The main application he envisaged was the simulation of quantum systems themselves. In the macroscopic world, the behavior of a small physical model can be used as a kind of analog computer. For example, when a model of an airplane is placed in a wind tunnel and the fan is started, you are effectively using this system as a computer to calculate the forces on something quite different, a full-sized airliner moving through the real atmosphere at a much higher speed. Feynman thought that analogously, small and relatively easily controlled quantum systems might be used to predict the behavior of much larger and more intractable ones.

Unfortunately there is a fundamental problem with analog computing—the impossibility of achieving true precision. Whether you are working with macroscopic currents or quantum probability waves, in practice you can never make the amplitudes have exactly the values you wish, to infinite precision. Moreover, in most types of computation you might want to perform, any tiny initial errors rapidly multiply. In the early 1980s, I was occupied writing algorithms to verify

results obtained on a classical analog computer that could at that date still do certain calculations much faster than its digital cousins—but the analog computer never gave exactly the same result twice. I vividly remember that the analog machine gave different results on a warm day than on a cold one, despite being installed in a supposedly temperature-controlled room. Traditional analog computers simply cannot produce reliably repeatable answers and they have duly fallen out of use. Attempts to use quantum probability waves to calculate analog quantities would suffer the same problems.

David Deutsch’s many-worlds perspective led him to favor a subtly different approach. He could see the potential of something much more like a conventional digital computer, but one in which a single set of hardware could perform an enormous number of different computations at once—as he sees it, different versions of the computer in a sense simultaneously performing different calculations in different worlds. Using this idea, a relatively simple machine could do an enormous amount of processing. He called the technique “massive parallelism.” This concept, which he described in detail in a landmark 1985 paper, is the basis of all modern designs for quantum computers. ²

The real temptation of the approach is the sheer number of computers you could in effect generate. The idea of parallel computing, using a large batch of small computers working together to solve a problem, is not new. As I write, the world’s largest parallel-processing supercomputer is Japan’s Earth Simulator, with 5,000 individual processors collectively capable of some 40 trillion calculations per second. Five thousand processors is by no means the limit, however. Ingenious scientists have found a few applications that allow thousands or even millions of processors to work on the same problem with very little communication required between them. This allows vast numbers of desktop computers to take part over the Internet by running screensaver programs—programs that work when the computer is otherwise idle, and normally just generate pretty patterns to amuse the user. Provided you have a computer that at least occasion-

ally connects to the Internet, so that the program can download data to work on and upload the results, you (or anyone else) can take part in a variety of worthwhile projects.

The most famous of these is the SETI@home project to process huge amounts of radio telescope data, to see if any signal from any part of the sky shows a pattern that might indicate that it is an intelligent signal from an alien race. The SETI project has already received plenty of publicity, but there are now a number of other distributed-screensaver projects to choose from. If you want to do something useful with your computer’s spare moments you might like to try the Screensaver Lifesaver Web site.³ This project involves screening millions of possible chemicals for useful biomedical effects, in particular against cancer, by calculating to what extent their shapes will cause them to dock with certain target molecules. It’s an extremely worthwhile cause and is likely to be the forerunner of an even more ambitious project as the Human Genome Project gives way to what has been called the Human Proteome Project, the huge task of identifying every biologically active molecule in the human body. Another interesting option is the Climate Prediction screensaver.⁴ This builds on the technique of ensemble weather forecasting. Nowadays, when a weather forecasting center makes a prediction, it is never the result of a single computer run. Forecasters are aware of the possibility of the butterfly effect: Would a tiny change in input parameters have produced a completely different forecast? They therefore run their model many times, each time with slightly different starting values because they know that their input data can never be perfectly accurate. If they get the same outcome every time, they know that they can forecast that weather with high confidence. If two or more significantly different results come from different runs, they know that they cannot be so sure. When a forecaster says that there is 33 percent chance of rain tomorrow, he may well be indicating that of 100 such simulations, about one-third ended in wet weather, the rest in dry.

The Climate Prediction screensaver takes the technique a bit further. When predicting what the climate will be like in 20 or 50 years, there are an enormous number of unknown variables governing feedback effects. How much sunlight will be reflected back into space by

clouds in a given scenario? By what percentage would a 1^°C temperature rise increase the melt rate of the Greenland ice shelf? How much will the Gulf Stream weaken per point of decrease in the salinity of the Northern Atlantic? And a thousand similar questions. The Climate Prediction project is building not a single forecast, but an ensemble of likelihoods. They already have one interesting result: A kind of butterfly effect affects the climate, not just the weather on some particular day. A very tiny change in parameters can give a whole region a markedly different temperature and rainfall over a long period. The Climate Prediction screensaver is beautiful and somewhat terrifying to watch, as a graphic of Earth shows the icecaps, deserts and forests shrink and grow in your particular slice of the future.

These kinds of distributed Internet projects might be able to recruit up to several million computers each. But obviously there is an upper limit. Even if you could persuade everyone on the planet to help you, there are only a billion or so computers available. That is nothing compared to the potential richness offered by quantum.

To understand the benefits of quantum computing, we will briefly review how a standard computer works. The heart of a computer is a device much like an old fashioned mechanical calculator, the kind that had a handle on the side that you could turn to add, subtract, or multiply numbers using wheels very similar to those in the odometer on your car dashboard. But a computer operates electrically, and it uses numbers based not on the decimal system, which has 10 different digits with successive columns representing units, tens, hundreds, and so on, but on the binary system, which has just two digits, zero and one, and in which successive columns represent units, twos, fours, eights, etc. Figure 11-1 illustrates a simple binary calculation.

Deutsch’s initial idea amounts to this. Suppose we could take a perfectly ordinary binary calculator and place it in Hilbert space, enclosed behind an impenetrable barrier like Schrödinger’s cat. We could then arrange the digits poised in unknown states, so that just as the cat’s Hilbert space would explore both the live-cat and dead-cat possi-

FIGURE 11-1 Binary numbers and arithmetic.

bilities, the calculator would explore a calculation in which the digits were in every possible combination of zeros and ones. If you imagine the computer sitting in a small cubicle with a human operator, then creating the impermeable barrier that separates the system from the outside world effectively creates a huge array of cubicles. I shall call this array the Dilbert Hotel, with apologies both to Scott Adams, cre-

ator of the excellent Dilbert cartoons, and to mathematicians familiar with the Hilbert Hotel, setting for David Hilbert’s famous thought experiments to illustrate the possibilities of infinities.

How many rooms has the Dilbert Hotel? Well, an 8-digit binary register can be set to 2⁸ = 256 possible combinations. So if we are multiplying every possible 8-bit number by every other possible 8-bit number, we are performing 256 × 256 = 2¹⁶ calculations in a hotel with 65,536 rooms. That might not sound vastly impressive, but modern computers have 32-bit or 64-bit registers. A 32-bit register can be set to just over 4 billion different combinations. In multiplying every possible 32-bit number by every other 32-bit number, we generate a hotel with more than 16,000,000,000,000,000,000 (16 billion billion) rooms—far more than the total number of computers ever built. This is beginning to sound promising.

However, the problem with this image is that it leads us to expect a great deal too much. You can whimsically imagine the operator in every cubicle doing his own thing, following a different line of thought, like in a real office block housing billions of computers and programmers. Unfortunately the reality is far more mundane. Each cubicle differs from its immediate neighbors by the setting of only one binary digit, and each worker must respond to the same sequence of commands shouted over some public announcement system. The workers are mannequins, all jerking about to the same string-pulls, as if following the steps of a formal and intricate dance.

A more accurate visualization would be to take a single cubicle and equip it with floors, walls, and ceilings that are perfect mirrors, thereby creating an illusion of a vast number of extra cubicles stretching off to right and left, upward and downward. In a sense we have created something extra—each extra cubicle is visible from a slightly different angle, so to speak—but we certainly have not created billions of independent worlds.

A major practical limitation is that collapsing the hotel at the end of the calculation leaves just one cubicle selected at random from the original array. Consider the task of dividing a very large number into its prime factors, a problem that arises in code breaking. You might naively think that one way of using the Dilbert Hotel would be to have

every operator try dividing a different number into the original. Soon, in just one of the vast array of cubicles a lucky Dilbert will be waving his arms over his head, shouting “I have cracked it! The remainder is zero, the number I was given to try is the answer to the problem!” But the chance that we will just happen to get that particular cubicle when we collapse the system is negligible.

To get a useful result from the Dilbert Hotel, we must arrange that every cubicle will hold a copy of the answer that we seek. That is possible, because the Dilberts are allowed to exchange information—to sneak notes between one another over the cubicle walls, so to speak. But they are only allowed to pass on such information (actually by interference effects) in a synchronized and stylized way, all moving to an invisible drumbeat. Then collapsing the system by a measurement at the right moment will give us a Dilbert who is certain, or at least reasonably probable, to be holding the correct answer. The Dilberts are, however, further constrained because time’s arrow must not be allowed to operate. For the cubicles to remain in contact with one another, no permanent recording of information can take place. It is as if each Dilbert is not allowed to write anything down, but merely to twist dials to and fro. So commanding him to do something can easily scramble an already useful result that he has found.

With all these restrictions, it is almost surprising to learn that it is, in principle, possible to arrange the rules of the dance so that the final position in every cubicle reflects the answer we are after. The problem is that the method is task dependent; it is entwined with the nature of the particular problem we are using the quantum computer to solve. For each different problem, an algorithm must be found that includes this last information-dissemination stage. This has turned out to be incredibly hard.

The largest computers have always been needed for just two kinds of jobs, simulating the physical world and code breaking. Indeed, the first really big programmable calculating machines were built for just these purposes during World War II: In Britain, Colossus and its relatives at

Bletchley Park cracked the German Enigma code, while in America, computers at Los Alamos worked out exactly how to ignite a nuclear explosion. Since then, computers have been turned to all kinds of work. Many useful tasks can now be done on relatively tiny and inexpensive desktop computers, but the processing power ideally required for these two heavy-duty applications is still not available. In the case of code breaking, this is because of the arms-race element. More-powerful computers allow more-powerful codes to be generated in the first place. In the case of physical simulations, it is because of the inordinate complexity of the real world. Perfect simulation of anything beyond a medium-sized molecule is still beyond today’s computers. The best we can hope for with macroscopic systems like the weather is to achieve ever better approximations.

So, can we use a quantum computer to crack codes or perform physical simulations?

So far, in 20 years of searching by some of the world’s cleverest mathematicians, just one quantum algorithm fully capable of addressing a useful problem has been discovered.⁵ And even that case requires a slightly liberal definition of the term useful. The problem involves code breaking.

Nowadays, we all take the convenience of paying for goods and services by plastic for granted. Indeed, even physical plastic is no longer required—you can simply give your credit card details over the telephone, or type them into a form on a Web site. Yet I am old enough to remember the days when almost everything had to be paid for in cash. Even trying to pay for groceries by check earned you a suspicious look from the store manager, and often a surcharge. The transformation has come about largely because of a clever encoding technique that allows an organization such as a bank or a chain of stores to openly publish a key for sending it messages, which cannot be decoded or interfered with unless you have a second key that is kept secret. The point is not that your credit card details are particularly secret—many people, such as waiters, have plenty of opportunity to copy them, and

it does not take an Internet hacker. The point is that the transaction details cannot be falsified, so the recipient of such an electronic payment cannot be disguised. A fraudulent debit on your credit card can be traced to whomever it was paid to. The details need not concern us here; the important point is that the cipher system depends on the fact that it is much easier to multiply numbers than to divide them. Thus if I give a standard computer two large prime numbers to multiply, it can do so in a short time. But the reverse task—given the product, which two prime numbers divide it?—would take the computer thousands of years. The difficulty of factoring very large numbers is crucial to the security of modern commercial methods.

Peter Shor realized that a quantum computer could be made to perform this task of factoring very large numbers. His method is so clever that he was awarded the Fields Medal, then the nearest mathematical equivalent to the Nobel Prize, but we are not going to go into the details. The key step was to link the factoring task to the problem of finding the period of a function. The period simply means the interval in which the graph of a regular function repeats itself. For simple functions like sine waves, the period is immediately obvious to the human eye, but it can be much more difficult to spot with sharply discontinuous functions: Imagine a pattern like that of Figure 11-2 but extending for millions of miles. Using Shor’s method, factoring a large number becomes equivalent to spotting the periodicity hidden in a really enormous set of random-looking numbers, and this turns

FIGURE 11-2 A discontinuous function.

out to be something a quantum computer can do while staying within the rules of Dilbert Space.

If we could build a computer to run Shor’s algorithm, how useful would it be? Really secure messages, top-secret military and diplomatic communications, do not depend solely on these hard-to-factor products of primes. The main reason is that no one has ever proved that there is not a clever mathematical algorithm that could enable large numbers to be factored rapidly on a perfectly ordinary computer. The major use of the prime-number systems is to secure banking transactions.

The only significant result of quantum computers becoming available would therefore be to cause a meltdown of the developed world’s economy. That certainly stretches the meaning of the word useful. I am reminded of the tension that arises in commercial companies when a techie announces that he has discovered an interesting problem. He thinks it fascinating, but it probably represents a nightmare for everybody else, who find it interesting more in the sense of the ancient Chinese curse: “May you live in interesting times!”

It is a real pity that no one has yet found a good use for quantum computers, because—as so often in the world of computing—it is the software that has turned out to be far harder to implement than the hardware. When Deutsch first worked out the ground rules, quantum computers were pure science fiction. Since then, several techniques have been developed that can perform all the basic hardware functions needed, holding nontrivial numbers of bits in Hilbert space—in other words, so that they interact only with each other without being measured by the outside world. The most promising technology involves supercooled atoms suspended in electric fields. Other problems that Deutsch and others have solved include devising useful computer instruction sets that operate without erasing information—essential to keep the Hilbert space together—and even methods of detecting and correcting errors without prematurely reading the values that must remain hidden until the computation is complete. The latter task is tremendously hard.

As seen from the perspective of a single world, a quantum computer operates not on ordinary binary digits, called bits, but on more subtle entities called qubits. Each memory location contains not a 0 or a 1, but information that can be described by a vector, an arrow pointing to some point on the surface of the Bloch sphere shown on page 89. Thus a qubit can be physically stored in the polarization of a photon, or in the spin of an electron or a larger particle. But the whole point about a qubit is that you do not know where the vector is pointing. This absence of knowledge is what keeps it entangled with the other qubits in the computer, generating the multitude-of-Dilbert-cubicles effect, which can be thought of as a little bubble of Hilbert space. You are not allowed to read the qubit, and something called the quantum no-cloning theorem says that it is also not possible to duplicate the qubit, even without looking at it.

How can you possibly tell if some unwanted interaction with the environment, as is bound to happen occasionally, has corrupted the qubit’s value? The detailed answer is too technical to give here, but the analogous method for ordinary computers is shown in Figure 11-3. Without either copying or reading out the values of the central square of bits we can generate an extra row and column of information that enables us to correct single-bit errors. The corresponding technique for qubits is significantly more complicated, but has now been perfected.

So the architecture and hardware challenges of building a quantum computer are well on the way to being solved. What hope is there for the software problem?

I remain optimistic that quantum computers may turn out to have wonderful uses. In the early days of the laser, there seemed to be a very similar dearth of useful applications. Now optoelectronic devices based on lasers are ubiquitous in consumer gadgets, communications networks, and a host of other civilian and military applications. One hope is that quantum computers will be able to solve a very famous class of problems that mathematicians call NP-complete. This is a group of puzzles whose solution time grows exponentially as the system involved gets larger. The most famous is the traveling salesman problem: working out how to visit a group of towns with the least

FIGURE 11-3 Error correction.

total travel time. A fast method of solving problems like this would be of immense value to operational researchers, with practical applications in many fields. But it has not been proved that quantum computers can do this.

It remains possible that the “killer app” for quantum computers

will involve simulations of quantum systems themselves. It can be tremendously time-consuming to calculate the evolving waveform of even a simple quantum system on a classical computer, and the impossibility of calculating the quantum behavior of more complex entities is becoming an increasing vexation to materials scientists, among others. If quantum computers can be used to understand the behavior of quantum matter, we will have come full circle to Feynman’s original hope, but using digital rather than analog computation.

To give a flavor of what the future could hold, remember the cold fusion fiasco when Fleischmann and Pons claimed to be generating fusion power from a lump of palladium in a test tube of heavy water. Many reputable experimenters failed to repeat the result, and it was probably spurious. But the real lesson we should remember is that theorists could not dismiss the possibility that fusion was occurring, because the behavior of real solid matter at the nanoscale—where quantum effects become significant—remains far too complex for today’s computers to model. If we get working quantum computers, we might be able to get real insights into what is called condensed matter physics.

Quantum computers with viable architecture and hardware, capable of working with significant numbers of bits, will probably be with us soon. The example of Shor’s algorithm proves that they have the potential to be useful. What we vitally need, as ever in quantum, is better thinking tools that will make it more straightforward for humans to program them, to visualize what is going on in the little bubble of the multiverse in which they do their work.