Quantum walk algorithm for element distinctness

By Andris Ambainis. 45th Annual IEEE Symposium on Foundations of Computer Science, 2003

948 citations recorded by the source corpus.

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/sup 2/3/) query quantum algorithm. This improves the previous O(N/sup 3/4/) quantum algorithm of Buhrman et al. and matches the lower bound by Shi. We also give an O(N/sup k/(k+1)/) query quantum algorithm for the generalization of element distinctness in which we have to find k equal items among N items.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems

View Paper: https://www.semanticscholar.org/paper/9b14f356f19766dd433bfa4b991128a871b06db7

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 Information Systems

Citations in the corpus

On the Relationship Between Continuous- and Discrete-Time Quantum Walk (2008, methodology): “Finally, I discuss limitations of the method for simulating Hamiltonians with negative matrix elements, and present two problems that motivate attempting to circumvent these limitations.”
Quantum algorithms for the triangle problem (2003, methodology): “The second algorithm uses O(n 13/m) queries, and it is based on a new design concept of Amhainis [6] that incorporates the benefits of quantum walks into Grover search [18].”
QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS (2003, neutral): “We describe the ﬁrst group in section 4 and the second group in section 5.”
Search via quantum walk (2006, methodology): “The firs t algorithm using quantum walks that goes beyond the capability of Grover Search is due to Ambainis [6] for Element Distinctness.”
Limits of quantum speedup in photosynthetic light harvesting (2009, methodology): “edu structured search [21], element distinctness [22] and evaluating AND-OR formulas [23].”
Universal Computation by Multiparticle Quantum Walk (2012, positive): “Applications of quantum walk include an example of exponential speedup over classical computation [6] and optimal algorithms for element distinctness [3] and formula evaluation [8].”
Universal computation by quantum walk. (2008, background): “By exploiting interference effects, quantum walks can outperform random walks at certain computational tasks: there are black-box problems for which quantum walk provides an exponential speedup over classical computation [4, 5], and many quantum walk algorithms achieve polynomial speedup over classi”
Efficient Quantum Algorithms for Simulating Sparse Hamiltonians (2005, background): “Such respresentations of Hamiltonians can arise as encodings of computational problems, such as simulations of quantum walks [6, 7, 8, 9, 10] or adiabatic quantum computations [11].”
Quantum Walk Based Search Algorithms (2008, methodology): “(n,r) is n/r(n− r) = Θ(1/r). If the set of marked vertices in J(n,r) is either empty, or it consists of vertices that contain a ﬁxed subset of constant size k≤ rthen ε= Ω(rk nk ). Theorem 3 (Ambainis [7]). Let Pbe the random walk on the Johnson graph J(n,r) where r= o(n), and let Mbe either empty, o”
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2018, methodology): “However, arguably the quantum walk algorithm of Ambainis [3] and Szegedy [53] together with the quantum linear systems algorithm of Harrow, Hassidim and Lloyd [30] are the most important other primitives that provide speed-ups relative to classical computing.”
Quantum walks: a comprehensive review (2012, methodology): “A variant of Definition 16, the element distinctness problem, was analyzed by Ambainis in [28]: Definition 21 Element distinctness problem [410].”