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 $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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Quantum Physics

• arXiv preprint · 3 November 2026

  A Constant-Factor Approximation for Capacitated Facility Location with Outliers

  Rajni Dabas
• arXiv preprint · 4 November 2026

  Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics

  Yossi Azar, Junhao Gan, Shahar Lewkowicz and 2 others
• arXiv preprint · 3 November 2026

  Semidirect sums of tensors and the matrix multiplication exponent

  Baitian Li
• arXiv preprint · 4 November 2026

  Sublinear Metric Distortion for Matching

  Moses Charikar, Alireza Haqi, Jabari Hastings and 2 others
• arXiv preprint · 3 November 2026

  Incremental Open Addressing Has No Time-Space Tradeoff

  Martín Farach-Colton, Andrew Krapivin and William Kuszmaul

All new papers in Quantum Physics