Quantum complexities of ordered searching, sorting, and element distinctness
From MaRDI portal
Publication:1871829
DOI10.1007/s00453-002-0976-3zbMath1012.68071OpenAlexW2109924867WikidataQ56039270 ScholiaQ56039270MaRDI QIDQ1871829
Jan Neerbek, Peter Høyer, Yaoyun Shi
Publication date: 4 May 2003
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-002-0976-3
Searching and sorting (68P10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)
Related Items (8)
A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ Quantum and classical query complexities of local search are polynomially related ⋮ Lower bounds for predecessor searching in the cell probe model ⋮ Polynomial degree vs. quantum query complexity ⋮ On the power of Ambainis lower bounds ⋮ Quantum branch-and-bound algorithm and its application to the travelling salesman problem
This page was built for publication: Quantum complexities of ordered searching, sorting, and element distinctness
