Sharp quantum versus classical query complexity separations

DOI10.1007/S00453-002-0978-1zbMATH Open1012.68220arXivquant-ph/0011065OpenAlexW2139322641MaRDI QIDQ1871634FDOQ1871634

Richard Cleve, J. Niel de Beaudrap, John Watrous

Publication date: 4 May 2003

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We obtain the strongest separation between quantum and classical query complexity known to date -- specifically, we define a black-box problem that requires exponentially many queries in the classical bounded-error case, but can be solved exactly in the quantum case with a single query (and a polynomial number of auxiliary operations). The problem is simple to define and the quantum algorithm solving it is also simple when described in terms of certain quantum Fourier transforms (QFTs) that have natural properties with respect to the algebraic structures of finite fields. These QFTs may be of independent interest, and we also investigate generalizations of them to noncommutative finite rings.

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

zbMATH Keywords

quantum Fourier transformquantum algorithms

Mathematics Subject Classification ID

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

Cited In (14)

• Forrelation: A Problem That Optimally Separates Quantum from Classical Computing
• Quantum and classical query complexities of local search are polynomially related
• Optimal parallel quantum query algorithms
• Improved bounds on the union complexity of fat objects
• Minimum-cost load-balancing partitions
• The quantum query complexity of learning multilinear polynomials
• Approximate unions of lines and Minkowski sums
• Kinetic collision detection for convex fat objects
• Approximate range searching in external memory
• Title not available (Why is that?)
• Quantum vs Classical Proofs and Subset Verification
• Quantum algorithm for multivariate polynomial interpolation
• Preprocessing imprecise points for Delaunay triangulation: simplified and extended
• Quantum algorithms for algebraic problems

   Recommendations

• An optimal separation of randomized and Quantum query complexity 👍 👎
• On exact quantum query complexity 👍 👎
• k-forrelation optimally separates Quantum and classical query complexity 👍 👎
• Quantum and classical query complexities for generalized Deutsch-Jozsa problems 👍 👎
• Quantum and classical query complexities of local search are polynomially related 👍 👎
• Quantum and classical query complexities of local search are polynomially related 👍 👎
• Evaluation of exact quantum query complexities by semidefinite programming 👍 👎
• Exact Quantum Query Complexity of EXACT and THRESHOLD 👍 👎

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

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