In the popular imagination,
quantum computers would be almost magical devices, able to "solve
impossible problems in an instant" by trying exponentially many
solutions in parallel. In this talk, I'll describe four results in
quantum computing theory that directly challenge this view.
First, I'll show that any
quantum algorithm to decide whether a function f:[n]->[n] is one-to-one
or two-to-one needs to query the function at least n^{1/5} times. This
provides strong evidence that collision-resistant hash functions, and
hence secure electronic commerce, would still be possible in a world
with quantum computers.
Second, I'll show that in
the "black-box" or "oracle" model that we know how to analyze, quantum
computers could not solve NP-complete problems in polynomial time, even
with the help of nonuniform "quantum advice states."
Third, I'll show that
quantum computers need exponential time to find local optima -- and
surprisingly, that the ideas used to prove this result also yield new
classical lower bounds for the same problem.
Finally, I'll show how to
do "pretty-good quantum state tomography" using a number of measurements
that increases only linearly, not exponentially, with the number of
qubits. This illustrates how one can sometimes turn the limitations of
quantum computers on their head, and use them to develop new techniques
for experimentalists.
No quantum computing
background will be assumed.