Quantum lower bounds proven using classical moment matching method
Quantum Query Lower Bounds from Classical Moment Matching
Data Structures and Algorithms
Summary
The paper shows how a classical mathematical technique called moment matching, which helps prove limits on how well algorithms can identify differences in data, can be adapted for quantum algorithms. This means they figured out how to prove lower limits on the number of queries a quantum computer must make to solve certain problems reliably. The authors present two versions with different strengths and use a combination of proof techniques to achieve these results. They also apply their findings to improve known limitations in several computational problems.
What this means in practice
- •For quantum algorithm designers: Understand the fundamental query limits for testing properties like k-distinctness and planarity under quantum models to guide efficient algorithm development.
- •For classical algorithm developers: Use quantum lower bound insights to better evaluate whether quantum approaches can outperform classical methods in property testing scenarios.
A theory result. No direct application yet.
Authors
Chandrima Kayal, Frédéric Magniez, Sayantan Sen, Dániel Szabó
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.