Speaker: Andris Ambainis
Affiliation: UC, Berkeley
Date: 4/5/01
Time and Location: 4:15 PM, B11 Kimball Hall
Title: Lower Bounds on Quantum Computing
Abstract: 

Quantum computation is an exciting new field which touches on the foundations of both computer science and quantum mechanics. It provides a new model of computation that is both physically reasonable and more powerful than conventional (classical) computing.

Shor gave a polynomial time quantum algorithm for factoring integers, a problem which is suspected to be very hard classically. Since most of public key cryptography is based on hardness of factoring, building a quantum computer would undercut the foundations of today's cryptography. Another major achievement is Grover's quantum algorithm which can speed up the solution of  an arbitrary exhaustive search problem. Given those developments, it is very important to understand the limitation of quantum computing.

This can be done in the quantum query model where we restrict the algorithm to accessing the input by queries and count the number of queries needed to solve the problem. Almost all known quantum algorithms can be analyzed in this model, including Grover's algorithm and a key part of Shor's factoring algorithm.

In this talk, I will present a new `quantum adversary' method for proving lower bounds on quantum algorithms in the query model. Using this method, I will show that Grover's algorithm is optimal both for the original search problem considered by Grover and several other related problems. Besides giving better lower bounds, the new method also allows to unify a number of results that were previously shown using a variety of different techniques.