The Limits of Quantum Computers - University of Virginia ...

1 INFORMATION. TECHNOLOGY. THE. LIMITSOF. Quantum By Scott Aaronson Quantum Computers would be exceptionally fast at a few speci c tasks, but it appears that for most problems they would outclass today's Computers only modestly. This realization may lead to a new fundamental physical principle H. aggar Physicists Develop Quantum Slacks,' read a headline in the satirical weekly the Onion. By exploiting a bizarre Schr dinger's Pants duality, the article explained, these non-Newtonian pants could paradoxically behave like formal wear and casual wear at the same time. Onion writers were apparently spoo ng the breathless articles about Quantum computing that have lled the popular science press for a decade.

2 A common mistake see for instance the February 15, 2007, issue of the Economist is to claim that, in principle, Quantum Computers could rapidly solve a particularly dif cult set of mathematical challenges called NP-complete problems, which even the best existing Computers cannot solve quickly (so far as anyone knows). Quantum Computers would supposedly achieve this feat not by being formal and casual at the same time but by having hardware capable of processing every pos- sible answer simultaneously. If we really could build a magic computer capable of solving an NP- ILLUSTRATIONS BY DU AN PETRIC IC . complete problem in a snap, the world would be a very different place: we could ask our magic computer to look for whatever patterns might exist in stock-market data or in recordings of the weather or brain activ- ity.

3 Unlike with today's Computers , nding these patterns would be com- pletely routine and require no detailed understanding of the subject of the problem. The magic computer could also automate mathematical creativ- 62 March 2008. 2008 SCIENTIFIC AMERIC AN, INC. Computers ity. Given any holy grail of mathematics such Quantum computer and its environment, which as Goldbach's conjecture or the Riemann hy- introduces errors). In particular, the bounds on pothesis, both of which have resisted resolution what it is mathematically possible to program a for well over a century we could simply ask our computer to do would apply even if physicists computer to search through all possible proofs managed to build a Quantum computer with no and disproofs containing up to, say, a billion sym- decoherence at all.

4 Bols. (If a proof were much longer than that, it is not clear that we would even want to read it.) Hard, Harder, Hardest If Quantum Computers promised such godlike How is it that a Quantum computer could pro- mathematical powers, maybe we should expect vide speedups for some problems, such as break- KEY CONCEPTS. them on store shelves at about the same time as ing codes, but not for others? Isn't a faster com- Quantum Computers would warp-drive generators and antigravity shields. puter just a faster computer? The answer is no, exploit the strange rules of But although we should not accept the usual and to explain why takes one straight to the intel- Quantum mechanics to process hype, in my view it is equally misguided to dis- lectual core of computer science.

5 For computer information in ways that are miss Quantum computing as science ction. In- scientists, the crucial thing about a problem is impossible on a standard stead we should nd out what the Limits of quan- how quickly the time needed to solve it grows as computer. tum Computers are and what they could really the problem size increases. The time is measured They would solve certain specif- do if we had them. in the number of elementary steps required by ic problems, such as factoring In the 26 years since physicist Richard Feyn- the algorithm to reach a solution. For example, integers, dramatically faster man rst proposed the idea of Quantum comput- using the grade school method, we can multiply than we know how to solve ing, computer scientists have made enormous two n-digit numbers in an amount of time that them with today's Computers , progress in guring out what problems Quantum grows like the number of digits squared, n2 (an but analysis suggests that for Computers would be good for.)

6 According to our amount of time said to be a polynomial in n ). most problems Quantum com- current understanding, they would provide dra- But for factoring a number into primes, even the puters would surpass conven- matic speedups for a few speci c problems most advanced methods known take an amount tional ones only slightly. such as breaking the cryptographic codes that of time that grows exponentially with the num- Exotic alterations to the known are widely used for monetary transactions on ber of digits (in particular, like 2 to the cube root laws of physics would allow the Internet. For other problems, however such of n power).

7 Thus, factoring seems intrinsically construction of Computers that as playing chess, scheduling airline ights and harder than multiplying and when we get up to could solve large classes of hard proving theorems evidence now strongly sug- thousands of digits, this difference matters much problems ef ciently. But those gests that Quantum Computers would suffer more than the difference between a Commodore alterations seem implausible. In the real world, perhaps the im- from many of the same algorithmic limitations 64 and a supercomputer. possibility of ef ciently solving as today's classical Computers . These limitations The kind of problems that Computers can these problems should be taken are completely separate from the practical dif - solve in a reasonable amount of time, even for as a basic physical principle.

8 Culties of building Quantum Computers , such as large values of n, are those for which we have an decoherence (unwanted interaction between a algorithm that uses a number of steps that grows The Editors w w w. S c i A m . c o m SCIENTIFIC AMERICAN 63. 2008 SCIENTIFIC AMERIC AN, INC. what better than trying every possible solution Quantum Computing 101 are known for these problems, no algorithm is known that is fundamentally better. Every known P hysicists are hotly pursuing the construction of Quantum Computers , which would harness the quirks of Quantum mechanics to perform certain computations more ef ciently than a conventional computer.)

9 Algorithm will take an amount of time that in- creases exponentially with the problem size. It turns out that the three problems I just list- ed have a very interesting property: they are all . 1 The fundamental feature of a Quantum computer is that it the same problem, in the sense that an ef cient uses qubits instead of bits. A qubit may be a particle such as an electron, with spin up (blue) representing 1, spin down algorithm for any one of them (red) representing 0, and Quantum states called super- would imply efficient algo- positions that involve spin up and spin down simultane- rithms for all the others.

10 Ste- ously (yellow). 1 phen A. Cook of the University of Toronto, Richard Karp of the . 2 A small number of particles in superposition University of California, Berkeley, states can carry an enormous amount of informa- and Leonid Levin, now at Boston tion: a mere 1,000 particles can be in a superpo- University , arrived at this remarkable sition that represents every number from 1 to conclusion in the 1970s, when they de- 21,000 (about 10300 ), and a Quantum comput- . 2. veloped the theory of NP-completeness. er would manipulate all those numbers in NP stands for nondeterministic poly- parallel, for instance, by hitting the parti- nomial time.