2017/11/30 by Renato Portugal · 9 citations
Computer Science · Materials Science · Mathematics · Physics and Astronomy · #Computability, Logic, AI Algorithms #Element (criminal law) #History #Law #Machine Learning in Materials Science #Philosophy #Political science #Quantum Computing Algorithms and Architecture #cs.CC #math.CO #quant-ph
paper · pdf · doi:10.1007/s11128-018-1930-x
published in Quantum Information Processing 17(7) (Springer Science+Business Media) · 14 pages
openalex publication_date 2018/05/19 · arxiv created 2018/06/13 · arxiv updated 2018/11/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/09
The element distinctness problem is the problem of determining whether the elements of a list are distinct, that is, if x=(x1,...,xN) is a list with N elements, we ask whether the elements of x are distinct or not. The solution in a classical computer requires N queries because it uses sorting to check whether there are equal elements. In the quantum case, it is possible to solve the problem in O(N2/3) queries. There is an extension which asks whether there are k colliding elements, known as element k-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 1-O(N1/(k+1)), quickly approaching 1. The specification of the exact running time and success probability is important in practical applications of this algorithm.