Quantum computing links two mysteries that have been with us since the
early twentieth century: the nature of quantum mechanics, and the ultimate
limits of computation. This thesis exploits that link by applying recent
progress in the theory of computing to foundational issues in physics. We
first demolish the idea that quantum computing equals exponential parallelism,
by showing that in the "black box" model, a quantum computer would need almost
as much time as a classical computer to find collisions in cryptographic hash
functions; to solve NP-complete problems (even aided by "quantum advice"); to
find local minima on a hypercube; or to evaluate total Boolean functions. We
then ask whether even the limited parallelism of quantum computing is
realized in Nature. After examining the arguments of skeptics such as Leonid
Levin and Stephen Wolfram, we propose a complexity classification of quantum
states as a way to answer this question. Finally, we show how a computer-science
perspective yields insights into holographic entropy bounds, the origins of the
quantum measurement rule, and stochastic hidden-variable interpretations of
quantum mechanics.

No quantum background is required or assumed.