{"id":"arxiv/2611.05117","url":"https://arxiv.org/abs/2611.05117","tags":["quant-ph","cs.DS"],"score":0,"title":"Quantum Query Lower Bounds from Classical Moment Matching","domain":"quant-ph","source":"arxiv","authors":["Chandrima Kayal","Frédéric Magniez","Sayantan Sen","Dániel Szabó"],"reviews":0,"subject":"quant-ph","summary":"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)…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}