The Quantum Query Complexity of AC0

Details The Quantum Query Complexity of AC0 The Quantum Query Complexity of AC0

2010-08-14

arxiv.org/abs/1008.2422v2

Computer Science

Computational Complexity

Scientific paper

We show that any quantum algorithm deciding whether an input function $f$ from $[n]$ to $[n]$ is 2-to-1 or almost 2-to-1 requires $\Theta(n)$ queries to $f$. The same lower bound holds for determining whether or not a function $f$ from $[2n-2]$ to $[n]$ is surjective. These results yield a nearly linear $\Omega(n/\log n)$ lower bound on the quantum query complexity of $\cl{AC}^0$. The best previous lower bound known for any $\cl{AC^0}$ function was the $\Omega ((n/\log n)^{2/3})$ bound given by Aaronson and Shi's $\Omega(n^{2/3})$ lower bound for the element distinctness problem.

Affiliated with

Also associated with

No associations

Rating

The Quantum Query Complexity of AC0 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Quantum Query Complexity of AC0, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Quantum Query Complexity of AC0 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-42320