Sharp quantum versus classical query complexity separations

DOI10.1007/s00453-002-0978-1zbMath1012.68220arXivquant-ph/0011065OpenAlexW2139322641MaRDI QIDQ1871634

Richard Cleve, J. Niel de Beaudrap, John Watrous

Publication date: 4 May 2003

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/0011065

zbMATH Keywords

quantum algorithmsquantum Fourier transform

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (13)

Approximate unions of lines and Minkowski sums ⋮ Minimum-cost load-balancing partitions ⋮ Quantum algorithm for multivariate polynomial interpolation ⋮ Forrelation: A Problem That Optimally Separates Quantum from Classical Computing ⋮ Optimal parallel quantum query algorithms ⋮ Approximate range searching in external memory ⋮ The quantum query complexity of learning multilinear polynomials ⋮ Preprocessing imprecise points for Delaunay triangulation: simplified and extended ⋮ Quantum vs Classical Proofs and Subset Verification ⋮ Improved bounds on the union complexity of fat objects ⋮ Unnamed Item ⋮ Quantum algorithms for algebraic problems ⋮ Kinetic collision detection for convex fat objects

This page was built for publication: Sharp quantum versus classical query complexity separations