Quantum lower bounds for the collision and the element distinctness problems

By Yaoyun Shi. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., 2001

363 citations recorded by the source corpus.

Given a function f as an oracle, the collision problem is to find two distinct inputs i and j such that f(i)=f(j), under the promise that such inputs exist. In this paper, we prove that any quantum algorithm for finding a collision in an r-to-one function must evaluate the function /spl Omega/ ((n/r)/sup 1/3/) times, where n is the size of the domain and r|n. This lower bound matches, up to a constant factor, the upper bound of Brassard, Hoyer and Tapp (1997), which uses the quantum algorithm of Grover (1996) in a novel way. The previously best quantum lower bound is /spl Omega/ ((n/r)/sup 1/5/) evaluations, due to Aaronson (2002). Our result implies a quantum lower bound of /spl Omega/ (n/sup 2/3/) queries to the inputs for another well studied problem, the element distinctness problem, which is to determine whether or not the given n real numbers are distinct. The previous best lower bound is /spl Omega/ (/spl radic/n) queries in the black-box model; and /spl Omega/ (/spl radic/n log n) comparisons in the comparisons-only model, due to Hoyer Neerbek, and Shi (2001).

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/4beae9ab6774cac4190ba8ceb998370317c65d09

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Geometry and Topology

Citations in the corpus

Quantum algorithms for the triangle problem (2003, methodology): “The first polynomial lower bound for the 2-1 Collision Problem was shown by Aaronson and Shi [1] using the polynomial method of Beals, Buhrman, Cleve, Mosca and de Wolf [9].”
Quantum Computational Complexity (2008, background): “There is an oracle A such that SZK 6⊆ BQP [1, 6].”
Quantum walk algorithm for element distinctness (2003, background): “However, the only lower bound is theΩ(N2/3) lower bound for algorithms with unrestricted memory [1].”
The Sign-Rank of AC^O (2008, background): “Minsky and Papert’s observation has seen numerous uses in the literature [1,36,39].”
QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS (2003, methodology): “clear, because one of them uses coin registers and the other does not. 3. Improving k-distinctness, triangle and k-clique algorithms. The O(N2/3) element distinctness algorithm is known to be optimal [28]. However, the best lower bound for kdistinctness is only Ω(N2/3) [12] and the best lower bounds”
Quantum Walk Based Search Algorithms (2008, background): “This upper bound is tight, the Ω(n) lower bound is due to Aaronson and Shi [1].”
Search via quantum walk (2006, background): “In his seminal paper he resolved the quantum query complexity of the proble m, s ttling a difficult question that had been open for several years [12, 1].”