Polynomial approximations and quantum lower bounds

The approximation degree of a Boolean function is the smallest degree of
polynomials that approximate the function on 0/1 inputs. It has been shown
that the approximation degree is a lower bound for the "black-box" quantum
complexity, a connection discovered by Beals, Buhrman, Cleve, Mosca,
and de Wolf [FOCS'98]. Except for the case of symmetric Boolean functions,
proving approximation degree lower bounds remains a challenging task
in general.

In this talk I will use this "polynomial method" to prove a quantum
lower bound on the number of oracle accesses for solving the Collision
Problem: given a two-to-one function f on 1, 2, …, n, find two distinct
indices i and j such that f(i)=f(j). I will show that the technique of
Aaronson [STOC'02] can be extended to improve his Omega(n^{1/5}) lower bound
to Omega(n^{1/3}), which is asymptotically tight. Our lower bound also
implies an Omega(n^{2/3}) lower bound on the number of queries to the input
for Element Distinctness, which is to decide whether or not n input numbers
are all distinct. The previous best quantum lower bound is Omega(sqrt(n)),
by a simple reduction from Grover's search problem, while the best known
quantum upper bound is O(n^{3/4}log(n)), due to Buhrman et al.[CCC'01].

This is a result to appear in FOCS'02 under the title "Quantum lower bounds
for the collision and the element distinctness problems'.