Element distinctness revisited

DOI10.1007/S11128-018-1930-XMaRDI QIDQ1993785zbMATH OpenOpenAlexFDO

Authors R. Portugal

Publication date 5 November 2018

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.11336

zbMATH Keywords

quantum algorithmquantum computingquantum walkstaggered quantum walkelement distinctnesscollision problem

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Quantum computation (81P68) (2)-body potential quantum scattering theory (81U05)

Abstract: The element distinctness problem is the problem of determining whether the elements of a list are distinct, that is, if $x=(x_1,\mathrm{...},x_N)$ 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(N^{2/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(N^{1/(k+1)})$, quickly approaching 1. The specification of the exact running time and success probability is important in practical applications of this algorithm.

Recommendations

• Quantum Walk Algorithm for Element Distinctness
• Quantum Algorithms for Element Distinctness
• Quantum lower bounds for the collision and the element distinctness problems
• scientific article; zbMATH DE number 5320343
• Quantum complexities of ordered searching, sorting, and element distinctness

Cites work

• scientific article; zbMATH DE number 5899233 (Why is no real title available?)
• scientific article; zbMATH DE number 5320343 (Why is no real title available?)
• scientific article; zbMATH DE number 1478494 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• A lower bound for randomized algebraic decision trees
• Coins make quantum walks faster
• Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
• Graph Classes: A Survey
• On the relationship between continuous- and discrete-time quantum walk
• Quantum Algorithms for Element Distinctness
• Quantum Algorithms for the Triangle Problem
• Quantum Walk Algorithm for Element Distinctness
• Quantum Walk Based Search Algorithms
• Quantum adversary lower bound for element distinctness with small range
• Quantum attacks against iterated block ciphers
• Quantum cryptanalysis of hash and claw-free functions
• Quantum lower bound for the collision problem with small range
• Quantum lower bounds for the collision and the element distinctness problems
• Quantum walks and search algorithms
• The staggered quantum walk model
• Time-efficient quantum walks for 3-distinctness
• Time-space trade-off lower bounds for randomized computation of decision problems

Cited in

(7)

• Models in quantum computing: a systematic review
• Quantum Walk Algorithm for Element Distinctness
• The role of tessellation intersection in staggered quantum walks
• How significant are the known collision and element distinctness quantum algorithms?
• Optimal deterministic quantum algorithm for the promised element distinctness problem
• Time-efficient quantum walks for 3-distinctness
• Deterministic quantum search with adjustable parameters: implementations and applications

This page was built for publication: Element distinctness revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1993785)