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
three results in quantum computing 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 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.

Third, 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.

I'll end by discussing how skepticism of quantum computing can be
addressed scientifically through the notion of a "Sure/Shor separator":
a class of quantum states, with reasonable closure properties, that
includes all the states that experimentalists have already prepared but
not the states arising in Shor's factoring algorithm.

No quantum computing background will be assumed.