Computing with Quantum Cats (24 page)

The essence of Shor's algorithm is that long strings of numbers contain periodicities—patterns of repetition—which may not be obvious at first sight but can be teased out by
mathematical analysis. The details are fascinating, and if you want them the best place to look is in Julian Brown's book
Minds, Machines and the Multiverse
, but what matters here is that periodic patterns can be probed using a technique known as Fourier analysis, which unpacks complicated wave patterns into their component parts. For example, the complicated sound wave corresponding to the sound of a group of musical instruments playing a chord together could be unraveled by Fourier analysis into a wave corresponding to a violin note, a wave corresponding to the cello, a wave corresponding to a clarinet and so on. Astronomers use the same sort of technique to do such things as, for example, analyze the variations in the output of light from a star and find underlying patterns of periodic variation which reveal details of the structure of the star.
¹⁶
Using a classical computer, it would be possible in principle to search for periodicities by considering each possibility in turn—looking for a pattern that repeats every two digits, then for one that repeats every three digits, then for one that repeats every four digits, and so on. But for numbers containing hundreds of digits this could take longer than the age of the Universe. A quantum computer using Shor's algorithm could set up a superposition with all the possible periods (waves) being examined simultaneously, and select the one that actually fit the number in question—which would take only a few minutes. The periodicity found in this way could then be used by a classical computer to reveal the factors of that number.

One particularly attractive feature of this procedure is that you know at once if you have gotten the right answer—you just multiply the factors together to see if they give you the right number. If there has been a glitch inside the computer
and you got the wrong answer (and the first quantum computers are likely to be at least as temperamental as the first classical computers were), you just run the problem again. Even if the quantum computer only works properly one time in a hundred, you can still solve the problem in a few hundred minutes: nothing compared with the age of the Universe.

Deutsch explains this in terms of a myriad identical computers in a myriad almost identical universes, each of which tests one of the possible periodicities, which then interfere so that each of them outputs the one correct answer. You might ask why the myriad codebreakers in all those universes bother to run their computers for our benefit. But FAPP those codebreakers are us; they also want to crack the code!

All of this provides Deutsch with his most powerful argument for the reality of the Multiverse. Bear in mind that a single 250-qubit “memory” contains more bits of information than there are atoms in the observed Universe. As Deutsch writes in
The Fabric of Reality
:

To those who still cling to a single universe world-view, I issue this challenge:
explain how Shor's algorithm works
.
¹⁷
I do not merely mean predict that it will work, which is simply a matter of solving a few uncontroversial equations. I mean provide an explanation. When Shor's algorithm has factorized a number, using 10
⁵⁰⁰
or so times the computational resources that can be seen to be present, where was the number factorized? There are only about 10
⁸⁰
atoms in the entire visible universe, an utterly minuscule number compared with 10
⁵⁰⁰
. So if the visible universe were the extent of physical reality, physical reality would not even remotely contain the resources required to factorize such a large number. Who did factorize it then? How, and where, was the computation performed?

“I have never,” Deutsch told me, “received a satisfactory answer to this question.” Or, as his colleague Artur Ekert, also of Oxford University, put it at that time: “The Many Worlds Interpretation of quantum mechanics is the least weird of all the weird interpretations of quantum mechanics.” These days, however, Ekert has told me, “I do not refer to the Many Worlds as an interpretation, for it is just quantum theory in its bare essentials.”
¹⁸

On its own, the codebreaking potential of the Shor algorithm would justify the effort now going into attempts to build quantum computers. It isn't just future codes that will be broken. You can be sure that government agencies, doubtless including GCHQ, are already stockpiling intercepted coded messages they suspect of being of long-term political significance in the hope and expectation of being able to read them in ten or twenty years' time.

There is another extremely useful algorithm that will enable quantum computers to perform rapidly a class of tasks that would take an interminably long time on classical computers. This is the seemingly mundane job of searching through large numbers of pieces of information to find the one that is required. The usual example is the problem of searching a printed telephone directory to find the name of somebody when you only have their telephone number. Starting at either end of the alphabet, you have to check each number against the corresponding name; since the name could be anywhere in the list, on average if N is the number of numbers in the list it will take N/2 steps to find it. In 1996 Lov Grover, another Bell Labs researcher, found an algorithm which reduces this number to roughly the square root of N, by starting with a superposition of all the pieces of
information and carrying out a series of operations which magnify (in a quantum sense) the one we are looking for. This is impressive, but not as impressive as Shor's algorithm, and not sufficient to displace classical computers as long as they remain cheap. The real importance of the discovery lay in providing evidence that quantum computing could be used for more than one thing, encouraging further investigation.

Remember, though, that “classical physics is false.” Perhaps the most important, and certainly the most profound, feature of a quantum computer is that it would be able to simulate physics
precisely
, not just approximately. No matter how good the approximations involved in simulating the Universe in a classical computer may be, they can never be perfect because the Universe is not classical. And remember how Deutsch got interested in quantum physics originally—through the search for a quantum theory of gravity. If we are ever to have a satisfactory “theory of everything” incorporating both quantum theory and gravity, it is almost certain that it will only be found with the aid of quantum computers to simulate the behavior of the Universe.
¹⁹

But if that is the long-term dream, we also have to face a harsher short-term reality. When they are good, quantum computers are very, very good. But…

THE BAD: LIMITS OF QUANTUM COMPUTATION

Ironically, Grover's algorithm, which stimulated interest in quantum computation in the late 1990s, also provides a neat example of the limitations of quantum computing. In 1997, the year after Grover published his discovery, the computer Deep Blue made headlines by defeating the human world chess champion, Gary Kasparov. This encouraged speculation
about how good a chess-playing quantum computer might be, if it were able to use Grover's algorithm to search for the best moves.

The argument is persuasively, but deceptively, simple. It goes like this. The computer chess program works by exploring all the possible moves as far ahead as possible in a set time. For each move by white, it considers each possible response by black, then for each possible response by black it considers each possible next move by white, and so on. From all these moves, it selects the first move that leads, assuming perfect play, to the most favorable situation for whichever color it is playing. There are about 10
¹²⁰
possible variations in a chess game, and if a computer could analyze a trillion (10
¹²
) possibilities every second, it would take 10
¹⁰⁰
years to analyze a whole game. For comparison, the time since the Big Bang is a few times 10
⁹
years, which is roughly a decimal point followed by 90 zeroes and a 1 times the time needed to analyze the number of possible variations in a chess game. In 1997, using 256 processors working in parallel, Deep Blue examined a mere 60 billion possibilities in the three minutes allowed between moves in the Kasparov game. Each of the processors considered about 25 million possibilities. So a naive understanding of Grover's algorithm suggests that a single quantum processor equivalent to one of Deep Blue's processors could handle 25 million squared possibilities in the same time, making the whole computer 600 million times more powerful than Deep Blue, and able to probe that much further into the web of chess possibilities in the time allowed.

Alas, this naive understanding is wrong. Richard Cleve, of the University of Calgary, pointed out that games like chess, in which there is a relatively small number of fixed choices
available at each move, do not lend themselves to speedup by Grover searching, and at best the process would be made slightly faster by a fixed amount. Don't just take my word for it—in a footnote to an article in
Frontiers
magazine in December 1998, David Deutsch said that “algorithms based on Grover-accelerated brute-force searching” are not suitable for speeding up chess-playing computers significantly—although, of course, there may be other algorithms that are more suited to the game.
²⁰

As this example demonstrates, there may be limitations on quantum computing that are quite separate from the practical problems of building a quantum computer. To see those limits, it is helpful to look in more general terms at the things computers (not just quantum computers) can do well, and the things they can't do. The key question that has to be considered is how quickly the time needed to solve a problem grows as the size of the problem increases. The time taken for factoring, our classic example, grows exponentially with the number of digits in the number; such problems can be solved efficiently if we have an algorithm that involves a number of steps that grows only by a fixed power, not exponentially, as the number increases, which is why Shor's algorithm works. Such algorithms are said to be “efficient,” and problems which can be solved by efficient algorithms belong to a category mathematicians call “complexity class P,”
²¹
or are said to be “in P.” Another class of problem, known as NP,
²²
are very difficult to solve but easy to check once you have the answer—such as the factorization problem. All problems in P are, of course, also in NP.

Going a step further, there are so-called NP-complete (or NP-hard) problems. An example is the problem of finding the shortest way to visit on foot all the islands in an archipelago
made up of thousands of islands, with every island connected to at least one other island by a bridge, on a tour which visits each island once, without retracing your steps.
²³
These are, in a sense, all different versions of the same problem, and it can be proven that if anyone ever found an efficient algorithm solution to one NP-complete problem, it would also solve not just the other NP-complete problems, but any NP problem. This would mean that all NP problems were really P problems, that P equals NP. But if anyone could prove that P is not equal to NP, we would be certain that there is no way to solve an NP problem in a reasonable time on a classical computer. A reward of a million dollars is on offer from the Clay Mathematical Institute in Cambridge, Massachusetts, for anyone who can prove P = NP; but few mathematicians believe that it will ever be won.

Unfortunately, the factoring problem is not NP-complete, so Shor's algorithm does not make him a candidate for the prize; and although it is not possible to prove that there is no quantum algorithm to solve NP-complete problems, there is no evidence that such an algorithm exists. This means that as far as we know, in spite of the hype sometimes associated with them, quantum computers are not going to be able to solve efficiently every interesting problem in the Universe, and it may even be possible to invent quantum codes that are as hard to crack using quantum computers as existing codes are using classical computers. The class of problems that quantum computers can solve efficiently is called BQP (bounded-error quantum polynomial). A quantum computer can solve efficiently any problem that a classical computer can solve efficiently, and certain other kinds of problems also, but it cannot solve efficiently all
problems that are intractable to classical computers. Quantum computers are not magic!

And there is another important insight. Because the physics of the Universe is quantum physics, a quantum computer is as good as it gets. Within the known laws of physics, we will never have a better kind of computer, and will never have an efficient way to solve NP-complete problems. We will doubtless develop more powerful quantum computers, just as more powerful classical computers have been developed since the 1940s, but they will only be able to tackle the same kinds of problems that the first generation of quantum computers will be able to tackle. Unless, of course, the laws of physics turn out to need modification in the light of future discoveries. But that way madness lies, and building the first generation of quantum computers is a tough enough task to be going on with.

THE UGLY: MAKING IT WORK

Putting all this into practice requires the construction of logic gates operating on quantum principles. These are analogous to the logic gates operating in classical computers, described in
Chapter 3
, but not identical, because quantum logic is not the same as classical logic. As an example, in a quantum computer it is possible to perform the operation NOT, just as in a classical computer, by poking an electron in an atom, which can exist in one of two states, either 0 or 1, with a judiciously chosen pulse of laser light. The right kind of pulse, known as a π-pulse, will flip the electron from one state to the other—from 0 to 1, or from 1 to 0. Poke it with another π-pulse and you will end up back where you started. But in a quantum computer, you might alternatively poke the electron
with an equally carefully selected but weaker pulse known as a π/2-pulse. This has the effect of putting the electron in a superposition of states 0 and 1. Now, if you poke it with another π/2-pulse it will settle into the
opposite
state from the one it started out in. Two π/2-pulses produce the same result as one π-pulse, but there is no classical equivalent of the effect of a single π/2-pulse. This operation is known as “Square Root of NOT.” The fundamental feature of this is that if we made a conventional measurement of the electron in its superposition we would get either the answer 0 or the answer 1 with equal probability; using Square Root of NOT we get one answer with 100 percent certainty. And we have a way of “negating” a value in a register (changing 0 to 1, or 1 to 0) by doing the same thing twice in succession, which is impossible in a classical computer.