#### Theory Seminar

# Polynomial approximations and quantum lower bounds

Add to Google Calendar

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'.