Name
Abstract | ||
|---|---|---|
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 Θ(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 Ω(n/log n) lower bound on the quantum query complexity of AC0. The best previous lower bound known for any AC0 function was the Ω((n/log n)2/3) bound given by Aaronson and Shi's Ω(n2/3) lower bound for the element distinctness problem [1]. |
Year | Venue | Keywords |
|---|---|---|
2010 | Quantum Information & Computation | element distinctness problem,ac0 function,quantum query complexity,input function,log n,quantum algorithm,computational complexity,quantum physics,lower bound |
DocType | Volume | Issue |
Journal | 12 | 7-8 |
Citations | PageRank | References |
3 | 0.39 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Beame | 1 | 2234 | 176.07 |
| Widad Machmouchi | 2 | 19 | 2.69 |