Separations in query complexity using cheat sheets
From MaRDI portal
Abstract: We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best such separation could only be quadratic (from Grover's algorithm). We also present a total function with a power 4 separation between quantum query complexity and approximate polynomial degree, showing severe limitations on the power of the polynomial method. Finally, we exhibit a total function with a quadratic gap between quantum query complexity and certificate complexity, which is optimal (up to log factors). These separations are shown using a new, general technique that we call the cheat sheet technique. The technique is based on a generic transformation that converts any (possibly partial) function into a new total function with desirable properties for showing separations. The framework also allows many known separations, including some recent breakthrough results of Ambainis et al., to be shown in a unified manner.
Recommendations
Cited in
(37)- On block sensitivity and fractional block sensitivity
- Query complexity of generalized Simon's problem
- Beyond quadratic speedups in quantum attacks on symmetric schemes
- Extended learning graphs for triangle finding
- Forrelation: a problem that optimally separates quantum from classical computing
- All classical adversary methods are equivalent for total functions
- Deterministic communication vs. partition number
- Forrelation: a problem that optimally separates quantum from classical computing
- scientific article; zbMATH DE number 6913819 (Why is no real title available?)
- Quantum query algorithms are completely bounded forms
- Low-sensitivity functions from unambiguous certificates
- Quantum query algorithms are completely bounded forms
- Time-Space Complexity Advantages for Quantum Computing
- A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
- Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
- Optimal separation and strong direct sum for randomized query complexity
- Query-to-communication lifting for BPP
- A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
- Algorithmic Polynomials
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- Nearly optimal separations between communication (or query) complexity and partitions
- Separation between deterministic and randomized query complexity
- Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
- An Optimal Separation of Randomized and Quantum Query Complexity
- Around the log-rank conjecture
- scientific article; zbMATH DE number 7758330 (Why is no real title available?)
- An optimal separation of randomized and Quantum query complexity
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- A direct reduction from the polynomial to the adversary method
- Average-case deterministic query complexity of Boolean functions with fixed weight
- Separations between combinatorial measures for transitive functions
- Proving unsatisfiability with hitting formulas
- An exponential separation between quantum query complexity and the polynomial degree
- Relations between monotone complexity measures based on decision tree complexity
- Quantum sabotage complexity
- Lifting to randomized parity decision trees
- Average-case query complexity of fixed-weight Boolean functions and k-CNFs
This page was built for publication: Separations in query complexity using cheat sheets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361886)
