*it has been only a decade since we learned that quantum computers could factor integers in polynomial time*.  In my (unbiased) opinion, the showdown that quantum computing has forced—between our deepest intuitions about computers on the one hand, and our best-confirmed theory of the physical world on the other—constitutes one of the most exciting scientific dramas of our time.

But why did this drama not occur until so recently?  Arguably, the main ideas were already in place by the 1960’s or even earlier.  I do not know the answer to this sociological puzzle, but can suggest two possibilities.  First, many computer scientists see the study of speculative models of computation as at best a diversion from more serious work; this might explain why the groundbreaking papers of Simon [@simon] and Bennett et al. [@bbbv] were initially rejected from the major theory conferences.  And second, many physicists see computational complexity as about as relevant to the mysteries of Nature as dentistry or tax law.

Today, however, it seems clear that there is something to gain from resisting these attitudes.  We would do well to ask: *what* *else* about physics might we have overlooked in thinking about the limits of efficient computation?  