Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0007016 · SIAM Journal on Computing

Quantum Algorithms for Element Distinctness

Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklós Sántha, Ronald de Wolf

Published Jan 1, 2005• 130 citations
arXivHTMLPDF

Abstract

We present several applications of quantum amplitude amplification for deciding whether all elements in the image of a given function are distinct, for finding an intersection of two sorted tables, and for finding a triangle in a graph. Our techniques generalize and improve those of Brassard, Hoyer, and Tapp [ACM SIGACT News, 28 (1997), pp. 14--19]. This shows that in the quantum world element distinctness is significantly easier than sorting, in contrast to the classical world.

DOI
10.1137/s0097539702402780

Related papers

Quantum algorithms for element distinctness

Harry Buhrman, Christoph Dürr, Mark Heiligman +4 more

We present several applications of quantum amplitude amplification to finding claws and collisions in ordered or unordered functions. Our algorithms generalize those of Brassard, Hoyer, and Tapp (1998), and imply an O(N/sup 3/4/ log N) quantum upper bound for the element distinctness problem in the comparison complexity model. This contrasts with /spl Theta/(N log N) classical complexity. We also prove a lower bound of /spl Omega/(/spl radic/N) comparisons for this problem and derive bounds for a number of related problems.

IEEE Conference on Computational Complexity (CCC)•Nov 13, 2002•95 citations

Quantum Walk Algorithm for Element Distinctness

Andris Ambainis

We use quantum walks to construct a new quantum algorithm for element distinctness and its generalization. For element distinctness (the problem of finding two equal items among N given items), we get an $O(N^{2/3})$ query quantum algorithm. This improves the previous $O(N^{3/4})$ quantum algorithm of Buhrman et al. [SIAM J. Comput., 34 (2005), pp. 1324–1330] and matches the lower bound of Aaronson and Shi [J. ACM, 51 (2004), pp. 595–605]. We also give an $O(N^{k/(k+1)})$ query quantum algorithm for the generalization of element distinctness in which we have to find k equal items among N items.

arXiv:quant-ph/0311001•SIAM Journal on Computing•Jan 1, 2007•836 citations

Quantum algorithms for intersection and proximity problems

Kunihiko Sadakane, Norito Sugawara, Takeshi Tokuyama

We discuss applications of quantum computation to geometric data processing. Especially, we give efficient algorithms for intersection problems and proximity problems. Our algorithms are based on Brassard et al.'s amplitude amplification method, and analogous to Buhrman et al.'s algorithm for element distinctness. Revealing these applications is useful for classifying geometric problems, and also emphasizing potential usefulness of quantum computation in geometric data processing. Thus, the results will promote research and development of quantum computers and algorithms.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•May 1, 2003•0 citations

A panoply of quantum algorithms

Bartholomew Furrow

This paper's aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover\cite{grover}. Grover's algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this paper is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grover's algorithm or similar techniques, which can be used as subroutines in many quantum algorithms.}{The tools we provide are carefully constructed: they are easy to use, and in many cases they are asymptotically faster than the best tools previously available. The tools we build on include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer.}{After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known deterministic classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible deterministic classical algorithm. These algorithms solve problems from the fields of graph theory and computational geometry, and some employ dynamic programming techniques. We discuss a breadth-first search that is faster than $\Theta(\text{edges})$ (the classical limit) in a dense graph, maximum-points-on-a-line in $O(N^{3/2}\lg N)$ (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.

arXiv:quant-ph/0606127•Quantum Information and Computation•Sep 1, 2008•11 citations

Quantum lower bounds for the collision and the element distinctness problems

Yaoyun Shi

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

arXiv:quant-ph/0112086•Annual Symposium on Foundations of Computer Science•Jun 26, 2003•122 citations

A panoply of quantum algorithms

Bartholomew Furrow

This thesis’ aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover. Grover’s algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this thesis is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grover’s algorithm or similar techniques, that can be used as subroutines in many quantum algorithms. The tools we provide are carefully constructed: they are easy to use, and they are asymptotically faster than the best tools previously available. The tools that we supersede include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer. After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible classical algorithm. These algorithms come from graph theory, computational geometry and dynamic programming. We discuss a breadth-first search that is faster than (edges) (the classical limit) in a dense graph, maximum-points-on-a-line in (N3/2 lgN) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.

Quantum Information and Computation•Jan 1, 2010•7 citations
We present several applications of quantum amplitude amplification for deciding whether all elements in the image of a given function are distinct, for finding an intersection of two sorted tables, and for finding a triangle in a graph. Our techniques generalize and improve those of Brassard, Hoyer, and Tapp [ACM SIGACT News, 28 (1997), pp. 14--19]. This shows that in the quantum world element distinctness is significantly easier than sorting, in contrast to the classical world.
We present several applications of quantum amplitude amplification to finding claws and collisions in ordered or unordered functions. Our algorithms generalize those of Brassard, Hoyer, and Tapp (1998), and imply an O(N/sup 3/4/ log N) quantum upper bound for the element distinctness problem in the comparison complexity model. This contrasts with /spl Theta/(N log N) classical complexity. We also prove a lower bound of /spl Omega/(/spl radic/N) comparisons for this problem and derive bounds for a number of related problems.
We use quantum walks to construct a new quantum algorithm for element distinctness and its generalization. For element distinctness (the problem of finding two equal items among N given items), we get an O(N2/3)O(N^{2/3})O(N2/3) query quantum algorithm. This improves the previous O(N3/4)O(N^{3/4})O(N3/4) quantum algorithm of Buhrman et al. [SIAM J. Comput., 34 (2005), pp. 1324–1330] and matches the lower bound of Aaronson and Shi [J. ACM, 51 (2004), pp. 595–605]. We also give an O(Nk/(k+1))O(N^{k/(k+1)})O(Nk/(k+1)) query quantum algorithm for the generalization of element distinctness in which we have to find k equal items among N items.
We discuss applications of quantum computation to geometric data processing. Especially, we give efficient algorithms for intersection problems and proximity problems. Our algorithms are based on Brassard et al.'s amplitude amplification method, and analogous to Buhrman et al.'s algorithm for element distinctness. Revealing these applications is useful for classifying geometric problems, and also emphasizing potential usefulness of quantum computation in geometric data processing. Thus, the results will promote research and development of quantum computers and algorithms.
This paper's aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover\cite{grover}. Grover's algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this paper is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grover's algorithm or similar techniques, which can be used as subroutines in many quantum algorithms.}{The tools we provide are carefully constructed: they are easy to use, and in many cases they are asymptotically faster than the best tools previously available. The tools we build on include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer.}{After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known deterministic classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible deterministic classical algorithm. These algorithms solve problems from the fields of graph theory and computational geometry, and some employ dynamic programming techniques. We discuss a breadth-first search that is faster than Θ(edges)\Theta(\text{edges})Θ(edges) (the classical limit) in a dense graph, maximum-points-on-a-line in O(N3/2lg⁡N)O(N^{3/2}\lg N)O(N3/2lgN) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.
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).
This thesis’ aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover. Grover’s algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this thesis is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grover’s algorithm or similar techniques, that can be used as subroutines in many quantum algorithms. The tools we provide are carefully constructed: they are easy to use, and they are asymptotically faster than the best tools previously available. The tools that we supersede include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer. After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible classical algorithm. These algorithms come from graph theory, computational geometry and dynamic programming. We discuss a breadth-first search that is faster than (edges) (the classical limit) in a dense graph, maximum-points-on-a-line in (N3/2 lgN) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.