{"id":"arxiv/2609.09804","url":"https://arxiv.org/abs/2609.09804","tags":["quant-ph","cs.CC"],"score":0,"title":"Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method","domain":"quant-ph","source":"arxiv","authors":["Albert Lin","Han-Hsuan Lin"],"reviews":0,"subject":"quant-ph","summary":"We study the two-weight decision version of quantum approximate counting: given oracle access to $x\\in\\{0,1\\}^N$, distinguish $|x|=M$ from $|x|=M+Δ$ with success probability $1/2+ζ$. Using the multiplicative adversary method, we prove $Ω\\left(\\max\\left\\{ζ\\sqrt{(N-M)(M+Δ)}/Δ,\\sqrt{ζN/Δ}\\right\\}\\right)$. The same parameter dependence follows from the polynomial-method characterization of the two-layer symmetric function by Podder, Yao, and Ye. Our contribution is a multiplicative-adversary derivation that tracks the progress produced by individual oracle queries. For the first term, after…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-09","reactions":{}}