Sharp quantum versus classical query complexity separations
From MaRDI portal
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.
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
Cited in
(17)- Quantum algorithms for algebraic problems
- Quantum and classical query complexities of local search are polynomially related
- Quantum vs. classical proofs and subset verification
- Improved bounds on the union complexity of fat objects
- Minimum-cost load-balancing partitions
- The quantum query complexity of learning multilinear polynomials
- Forrelation: a problem that optimally separates quantum from classical computing
- Approximate unions of lines and Minkowski sums
- Kinetic collision detection for convex fat objects
- Superpolynomial Speedups Based on Almost Any Quantum Circuit
- Forrelation: a problem that optimally separates quantum from classical computing
- Approximate range searching in external memory
- scientific article; zbMATH DE number 7561499 (Why is no real title available?)
- Preprocessing imprecise points for Delaunay triangulation: simplified and extended
- Separations in query complexity using cheat sheets
- Quantum algorithm for multivariate polynomial interpolation
- Fourier 1-norm and quantum speed-up
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)
