Quantum Query Lower Bounds from Classical Moment Matching
quant-ph, cs.DS
Submitted: 2026-11-03
Updated: 2026-11-03
Terminology
Sources
- Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing
- Quantum property testing for bounded-degree graphs
- Quantum property testing in sparse directed graphs
- Estimating Renyi Entropy of Discrete Distributions
- Quantum Lower Bound for the Collision Problem
- Quantum lower bounds for the collision and the element distinctness problems
- Quantum Algorithms for Learning and Testing Juntas
- Strengths and Weaknesses of Quantum Computing
- Quantum Lower Bounds by Polynomials
- Tight Quantum Lower Bound for k-Distinctness
- Quantum Property Testing
- The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
- (Quantum) complexity of testing signed graph clusterability
- Exploring the Gap between Tolerant and Non-tolerant Distribution Testing
- The Price of Tolerance in Distribution Testing
- Sharp Bounds for Generalized Uniformity Testing
- Quantum testers for hidden group properties
- A Survey of Quantum Property Testing
- The quantum complexity of approximating the frequency moments
- An Optimal Separation between Two Property Testing Models for Bounded Degree Directed Graphs
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements