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