Quantum Query Lower Bounds from Classical Moment Matching
Abstract
We prove a quantum analogue of the classical moment matching method, a popular framework used to prove lower bounds in property testing. For two random variables X0 and X1 whose moments match up to the first r−1 moments, the classical moment matching method says that no classical algorithm can reliably distinguish between input instances of length N constructed from X0 and X1, respectively, unless it performs at least Ω(N1−1/r) queries. While this method has been widely explored since its inception in the seminal work of Raskhodnikova, Ron, Shpilka, and Smith (STOC 2007) to prove lower bounds for symmetric properties, it has remained an open question whether a quantum analogue of it could be proved. We prove two variants of this quantum moment matching method, which are incomparable. Our first quantum query lower bound scales as Ω(N1/2−1/(2r)), while our second moment matching theorem yields a sharper lower bound of Ω(N1/2−1/(2(2r−1))), albeit for smaller parameter ranges. Our results combine a new continuous hybrid argument with the polynomial method. The continuous hybrid argument compares two hard input distributions generated from i.i.d. samples by continuously varying both distributions, keeping them identically distributed at every intermediate stage. It reduces the comparison to the effect of changing the distribution of a single sample. The polynomial method then cancels the terms determined by the matched moments. We apply these moment matching theorems to prove new optimal lower bounds on k-distinctness, k-star-freeness, planarity and outerplanarity testing, as well as to improve prior lower bounds on image size testing and K-junta testing by logarithmic factors. A key advantage of our framework is its simplicity: it reduces quantum lower bound proofs to the construction of suitable moment-matching distributions.
Related
- Tight bounds for hybrid quantum-classical query algorithms
- Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points
- Quantum lower bounds for convex optimization and real matrix-vector query problems
- Improved Quantum Query Bounds for Boolean Matrix Product Verification
- Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model
BibTeX
@misc{kayal2026quantum,
title = {{Quantum Query Lower Bounds from Classical Moment Matching}},
author = {Chandrima Kayal and Frédéric Magniez and Sayantan Sen and Dániel Szabó},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05117},
eprint = {2611.05117},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05117},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Query Lower Bounds from Classical Moment Matching
AU - Chandrima Kayal
AU - Frédéric Magniez
AU - Sayantan Sen
AU - Dániel Szabó
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05117
UR - https://arxiv.org/abs/2611.05117
AB - We prove a quantum analogue of the classical moment matching method, a popular framework used to prove lower bounds in property testing. For two random variables X_0 and X_1 whose moments match up to the first r−1 moments, the classical moment matching method says that no classical algorithm can reliably distinguish between input instances of length N constructed from X_0 and X_1, respectively, unless it performs at least Ω(N^1−1/r) queries. While this method has been widely explored since its inception in the seminal work of Raskhodnikova, Ron, Shpilka, and Smith (STOC 2007) to prove lower bounds for symmetric properties, it has remained an open question whether a quantum analogue of it could be proved. We prove two variants of this quantum moment matching method, which are incomparable. Our first quantum query lower bound scales as Ω(N^1/2−1/(2r)), while our second moment matching theorem yields a sharper lower bound of Ω(N^1/2−1/(2(2^r−1))), albeit for smaller parameter ranges. Our results combine a new continuous hybrid argument with the polynomial method. The continuous hybrid argument compares two hard input distributions generated from i.i.d. samples by continuously varying both distributions, keeping them identically distributed at every intermediate stage. It reduces the comparison to the effect of changing the distribution of a single sample. The polynomial method then cancels the terms determined by the matched moments. We apply these moment matching theorems to prove new optimal lower bounds on k-distinctness, k-star-freeness, planarity and outerplanarity testing, as well as to improve prior lower bounds on image size testing and K-junta testing by logarithmic factors. A key advantage of our framework is its simplicity: it reduces quantum lower bound proofs to the construction of suitable moment-matching distributions.
ER -