What Are the Limits of Conventional Computing?

See allHide authors and affiliations

Science  01 Jul 2005:
Vol. 309, Issue 5731, pp. 96
DOI: 10.1126/science.309.5731.96

At first glance, the ultimate limit of computation seems to be an engineering issue. How much energy can you put in a chip without melting it? How fast can you flip a bit in your silicon memory? How big can you make your computer and still fit it in a room? These questions don't seem terribly profound.

In fact, computation is more abstract and fundamental than figuring out the best way to build a computer. This realization came in the mid-1930s, when Princeton mathematicians Alonzo Church and Alan Turing showed—roughly speaking—that any calculation involving bits and bytes can be done on an idealized computer known as a Turing machine. By showing that all classical computers are essentially alike, this discovery enabled scientists and mathematicians to ask fundamental questions about computation without getting bogged down in the minutiae of computer architecture.

For example, theorists can now classify computational problems into broad categories. P problems are those, broadly speaking, that can be solved quickly, such as alphabetizing a list of names. NP problems are much tougher to solve but relatively easy to check once you've reached an answer. An example is the traveling salesman problem, finding the shortest possible route through a series of locations. All known algorithms for getting an answer take lots of computing power, and even relatively small versions might be out of reach of any classical computer.

Mathematicians have shown that if you could come up with a quick and easy shortcut to solving any one of the hardest type of NP problems, you'd be able to crack them all. In effect, the NP problems would turn into P problems. But it's uncertain whether such a shortcut exists—whether P = NP. Scientists think not, but proving this is one of the great unanswered questions in mathematics.


In the 1940s, Bell Labs scientist Claude Shannon showed that bits are not just for computers; they are the fundamental units of describing the information that flows from one object to another. There are physical laws that govern how fast a bit can move from place to place, how much information can be transferred back and forth over a given communications channel, and how much energy it takes to erase a bit from memory. All classical information-processing machines are subject to these laws—and because information seems to be rattling back and forth in our brains, do the laws of information mean that our thoughts are reducible to bits and bytes? Are we merely computers? It's an unsettling thought.

But there is a realm beyond the classical computer: the quantum. The probabilistic nature of quantum theory allows atoms and other quantum objects to store information that's not restricted to only the binary 0 or 1 of information theory, but can also be 0 and 1 at the same time. Physicists around the world are building rudimentary quantum computers that exploit this and other quantum effects to do things that are provably impossible for ordinary computers, such as finding a target record in a database with too few queries. But scientists are still trying to figure out what quantum-mechanical properties make quantum computers so powerful and to engineer quantum computers big enough to do something useful.

By learning the strange logic of the quantum world and using it to do computing, scientists are delving deep into the laws of the subatomic world. Perhaps something as seemingly mundane as the quest for computing power might lead to a newfound understanding of the quantum realm.

View Abstract

Stay Connected to Science


Navigate This Article