**Efficient Computation in the Physical Universe**

*Quantum computing is revealing remarkable links between the central unsolved problems of theoretical computer science and the laws of physics. These links are already forcing a revision in our understanding of the physical world.*

**Summary**

What is the most powerful kind of computer compatible with the laws of physics? Which problems can computers ever solve within reasonable constraints of time and memory? These questions took on a new character fourteen years ago, with Peter Shor’s discovery that a quantum computer could factor integers in polynomial time, and thereby break the cryptographic codes on which most of the world’s electronic commerce depends. A quantum computer is a proposed device that would exploit the counterintuitive nature of quantum physics to solve certain problems exponentially faster than we know how to solve them with any computer today.

**Rationale**

In the wake of Shor’s algorithm, one can identify three basic questions:

(1) First, can quantum computers actually be built? Can they cope with realistic rates of decoherence — that is, unwanted interaction between a quantum computer and its external environment? Alternatively, can we find any plausible change to currently-accepted laws of physics such that quantum computing would *not* be possible?

(2) Second, what would the actual capabilities of quantum computers be? For example, could they efficiently solve NP-complete problems? Though quantum computers would break many of today’s cryptographic codes (including RSA), can other practical codes be found that are secure against quantum attacks?

(3) Third, does quantum computing represent the actual limit of what is efficiently computable in the physical world? Or could (for example) quantum gravity lead to yet more powerful kinds of computation?

Theoretical computer scientists have already contributed basic insights about all three of these questions. For example, they played a central role in proving and extending the Fault-Tolerance Theorem, which says that once a quantum computer’s noise rate falls below a certain critical point, decoherence can be corrected faster than it occurs, and hence arbitrarily long quantum computations are possible in principle. On the other hand, theoretical computer scientists also discovered evidence that quantum computers would face major limitations in solving NP-complete problems, as well as related tasks such as breaking cryptographic hash functions. Finally, they studied hypothetical models beyond quantum computing, for instance involving topological quantum field theories and closed timelike curves.

**Contributors and Credits**

Scott Aaronson, Bhaskar DasGupta, Richard Karp, Rocco Servedio, Diane Souvaine

## Leave a Reply