Element distinctness revisited

DOI10.1007/S11128-018-1930-XzbMATH Open1451.81179arXiv1711.11336OpenAlexW2774040291MaRDI QIDQ1993785FDOQ1993785

Authors: R. Portugal 

Publication date: 5 November 2018

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

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.

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

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
• Quantum complexities of ordered searching, sorting, and element distinctness

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)

Cites Work

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

Cited In (7)

• Quantum Walk Algorithm for Element Distinctness
• Models in quantum computing: a systematic review
• 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)