An Invitation to Quantum Computing

computing research as I perceived it at the recent AQIP'98 workshop on
quantum information processing.

After an introduction to the idea of quantum computing, I will take
the database search problem as an example for proving upper and lower
bounds on the power of quantum computers.

Given a function f:{0,..,N-1}->{0,1}, the database search problem asks
to find an x such that f(x)=1. Assume there is only one such x. A
(probabilistic) classical algorithm then needs an average number of
N/2 evaluations of f to find x. On a quantum computer, x can be
determined with an average of O(sqrt(N)) evaluations, but not faster.