Quantum lower bounds by quantum arguments

Andris Ambainis

Almost all known quantum algorithms can be analyzed in a query model where the algorithm accesses input by querying it in a specific position and the complexity of the algorithm is measured by the number of queries that it makes. The most famous such algorithm is Grover's algorithm for searching an unordered list of $n$ elements in $O(\sqrt{n})$ time. Another example is period-finding which is the basis of Shor's factoring algorithm. In my talk, I will show a new method for proving lower bounds on quantum query algorithms. Traditional methods use a classical adversary that runs the algorithm with one input and then modifies the input. We use a quantum adversary that runs the input with a superposition of inputs. Using this method, we give a new proof that Grover's algorithm is optimal and show $\Omega(\sqrt{n})$ lower bounds for 2 other problems (AND of ORs and inverting a permutation) for which only weaker bounds have been known before. Besides giving better bounds, our method also allows to treat all of these problems in a uniform way. (The previous results were proven via variety of different techniques.)

created Thu Mar 2 11:01:19 PST 2000