No article text was recorded for this version.
quantum query complexity lower bounds
Version 1 of 1241 papers408 conceptsfrozen 2026-10-04
Papers in this version
- Blog: Separations in query complexity using cheat sheets
- Blog: All Quantum Adversary Methods are Equivalent
- Blog: Quantum algorithms and lower bounds for convex optimization
- Blog: Quantum lower bounds for the collision and the element distinctness problems
- Blog: Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem
- Blog: Optimal quantum query bounds for almost all Boolean functions
- Blog: Quantum Implications of Huang's Sensitivity Theorem
- Blog: The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
- Blog: Quantum Lower Bounds by Entropy Numbers
- Blog: Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions
- Blog: A note on quantum lower bounds for local search via congestion and expansion
- Blog: On a problem in quantum summation
- Blog: Quantum Algorithms for Element Distinctness
- Blog: Lower Bounds in the Quantum Cell Probe Model
- Blog: Quantum interpolation of polynomials
- Blog: Tight Bounds on Communication Complexity of Symmetric XOR Functions in One-Way and SMP Models
- Blog: Two QCMA-complete problems
- Blog: Quantum query complexity of graph connectivity
- Blog: Quantum Algorithm for Lexicographically Minimal String Rotation
- Blog: The space "just above" BQP
- Blog: Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss
- Blog: Tight Bound for Quantum Unitary Time-Reversal
- Blog: On the Exponential Sample Complexity of the Quantum State Sign Estimation Problem
- Blog: Quantum Lower Bounds by Sample-to-Query Lifting
- Blog: Lower bounds for predecessor searching in the cell probe model
- Blog: Quantum Approximation II. Sobolev Embeddings
- Blog: Quantum Formulas: a Lower Bound and Simulation
- Blog: Classical-Quantum Separations in Minimal Query Complexity of Boolean Functions
- Blog: Quantum Integration in Sobolev Classes
- Blog: A note on quantum divide and conquer for minimal string rotation
- Blog: No quantum speedup over gradient descent for non-smooth convex optimization
- Blog: On the Quantum Complexity of Closest Pair and Related Problems
- Blog: Query complexity of generalized Simon's problem
- Blog: Quantum algorithms for the ordered search problem via semidefinite programming
- Blog: Quantum speedups for stochastic optimization
- Blog: Quantum Lower Bounds by Sample-to-Query Lifting
- Blog: An Exact Quantum Query Algorithm Beyond Parity using Maiorana-McFarland (MM) type Bent functions
- Blog: Open Problems Related to Quantum Query Complexity
- Blog: The Need for Structure in Quantum Speedups
- Blog: Quantum property testing in sparse directed graphs
- Blog: Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
- Blog: Exact quantum query complexity of weight decision problems
- Blog: A Note on Quantum Divide and Conquer for Minimal String Rotation
- Blog: Quantum exploration algorithms for multi-armed bandits
- Blog: Quantum Algorithms for Solving Dynamic Programming Problems
- Blog: Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies
- Blog: Limitations of Quantum Advice and One-Way Communication
- Blog: On estimating the trace of quantum state powers
- Blog: Quantum approximate optimization algorithms for maximum cut on low-girth graphs
- Blog: Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss
- Blog: Fractional Certificates for Bounded Functions
- Blog: Quantum Exploration Algorithms for Multi-Armed Bandits
- Blog: (Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids
- Blog: Quantum Certificate Complexity
- Blog: Two New Results About Quantum Exact Learning.
- Blog: Quantum Query Complexity of State Conversion
- Blog: Quantum integration in Sobolev classes
- Blog: On the Role of Entanglement and Statistics in Learning
- Blog: Lower Bounds for Local Search by Quantum Arguments
- Blog: Quantum Query Complexity of Entropy Estimation
Showing 60 of 241 papers.
History & citation
Current · Permanent link
- Bridging Upper and Lower Bounds in Quantum Query Complexity merged into this direction (73% overlap)
- Quantum Query Lower Bounds via the Adversary Method merged into this direction (83% overlap)
- Quantum Query Complexity of Boolean Functions merged into this direction (73% overlap)
Cite this direction
Latest version (a living page):
@misc{lacuna_quantum_query_complexity_lower_bounds_c56b954a,
title = {quantum query complexity lower bounds},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/quantum-query-complexity-lower-bounds/rdr_c56b954a4c48453ea0cdc4fafcd89b21},
note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}This exact version (version 1, frozen text):
@misc{lacuna_quantum_query_complexity_lower_bounds_c56b954a_v1,
title = {quantum query complexity lower bounds},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/quantum-query-complexity-lower-bounds/rdr_c56b954a4c48453ea0cdc4fafcd89b21/v/1},
note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}