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
(35)- Algorithmic Polynomials
- On block sensitivity and fractional block sensitivity
- Relations between monotone complexity measures based on decision tree complexity
- scientific article; zbMATH DE number 7758330 (Why is no real title available?)
- An Optimal Separation of Randomized and Quantum Query Complexity
- An optimal separation of randomized and Quantum query complexity
- Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
- A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
- Beyond quadratic speedups in quantum attacks on symmetric schemes
- Forrelation: a problem that optimally separates quantum from classical computing
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
- Deterministic communication vs. partition number
- Separations between combinatorial measures for transitive functions
- Query-to-communication lifting for BPP
- All classical adversary methods are equivalent for total functions
- Around the log-rank conjecture
- Forrelation: a problem that optimally separates quantum from classical computing
- Low-sensitivity functions from unambiguous certificates
- Quantum query algorithms are completely bounded forms
- A direct reduction from the polynomial to the adversary method
- scientific article; zbMATH DE number 6913819 (Why is no real title available?)
- Average-case deterministic query complexity of Boolean functions with fixed weight
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- An exponential separation between quantum query complexity and the polynomial degree
- Nearly optimal separations between communication (or query) complexity and partitions
- Query complexity of generalized Simon's problem
- Quantum query algorithms are completely bounded forms
- Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
- Quantum sabotage complexity
- Time-Space Complexity Advantages for Quantum Computing
- Proving unsatisfiability with hitting formulas
- Extended learning graphs for triangle finding
- Separation between deterministic and randomized query complexity
- Optimal separation and strong direct sum for randomized query complexity
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)
