The Limits of Quantum Computers

Scott Aaronson

University of Waterloo

Friday, March 2nd, 2007, 3:30 pm

Wean Hall 7220

Abstract

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.