Quantum lower bounds for the collision and the element distinctness problems
Author:
- 15 December 2001
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 513-519
Abstract
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).Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Algorithms for quantum computation: discrete logarithms and factoring2002
- Quantum mechanical algorithms for the nonabelian hidden subgroup problem2001
- On the Power of Quantum ComputationSIAM Journal on Computing, 1997
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- A lower bound for randomized algebraic decision trees1996
- A fast quantum mechanical algorithm for database search1996
- Constructive Approximation1993
- On the degree of Boolean functions as real polynomials1992
- On the degree of polynomials that approximate symmetric Boolean functions (preliminary version)1992
- A lower bound of 12n2 on linear search programs for the Knapsack problemJournal of Computer and System Sciences, 1978