Element Distinctness Revisited
arXiv:1711.11336 · doi:10.1007/s11128-018-1930-x
Abstract
The element distinctness problem is the problem of determining whether the elements of a list are distinct, that is, if is a list with elements, we ask whether the elements of are distinct or not. The solution in a classical computer requires queries because it uses sorting to check whether there are equal elements. In the quantum case, it is possible to solve the problem in queries. There is an extension which asks whether there are colliding elements, known as element -distinctness problem. This work obtains optimal values of two critical parameters of Ambainis' seminal quantum algorithm [SIAM J.~Comput., 37, 210-239, 2007]. The first critical parameter is the number of repetitions of the algorithm's main block, which inverts the phase of the marked elements and calls a subroutine. The second parameter is the number of quantum walk steps interlaced by oracle queries. We show that, when the optimal values of the parameters are used, the algorithm's success probability is , quickly approaching 1. The specification of the exact running time and success probability is important in practical applications of this algorithm.
arXiv comment14 pages
References in corpus (12)
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- On the relationship between continuous- and discrete-time quantum walk
- Quantum Algorithm for the Collision Problem
- Quantum lower bounds for the collision and the element distinctness problems
- The Staggered Quantum Walk Model
- Quantum Algorithms for Element Distinctness
- Staggered Quantum Walks on Graphs
- Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
- Quantum attacks against iterated block ciphers
- General framework for quantum search algorithms
- Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range