Lower Bounds

Given that we can theoretically attain exponential speedup through quantum parallelism, it is tempting to hope that quantum computing could offer exponential speedup to large classes of problems. Shor's algorithm seems to validate that hope. The optimality of Grover's algorithm, on the other hand, essentially establishes that a quantum computer can offer at most quadratic speedup to the brute force solution of a problem that exhaustively searches all possible solutions.

To answer questions surrounding the power of the quantum computer, we
study lower bounds for quantum algorithms. Lower bounds on large
classes of functions allow us to make quantitative comparisons between
quantum and classical computers. It is very difficult to prove a
lower bound on a particular problem in any general model of
computation, as one has to argue how quickly any possible algorithm
can solve the problem. Throughout this thesis we will consider a
restricted model of computation, the *oracle query model*, in
which we consider only algorithms whose input is provided in a black
box.

We will present a theorem by Andris Ambainis that enables us to easily prove lower bounds in the oracle query model [1]. The main strength of Ambainis' Theorem is its ability to prove lower bounds for a variety of Boolean functions, and thus allow us to compare the relative power of classical and quantum computers.