Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method

Abstract

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+\Delta$ with success probability $1/2+\zeta$. Using the multiplicative adversary method, we prove $\Omega \left(\max \left\{\zeta \sqrt{(N-M)(M+\Delta )}/\Delta ,\sqrt{\zeta N/\Delta }\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 complementing the input if necessary, we assume $M+\Delta \le N-M$. We use the Hamming-layer subspaces from the eigenspace method of Ambainis, Spalek, and de Wolf and compose their adjacent-layer unitary maps to relate the two nonadjacent promise layers. After fixing the queried coordinate, the analysis block-diagonalizes into four-dimensional subspaces. An exact calculation of the one-query progress ratio gives the first lower bound. The same estimate also implies ${\Vert (I-{\hat{\Pi }}_{\mathrm{bad}})|{\Psi }^T⟩\Vert }^2=O\left(T^2{\Delta }^2/((N-M)(M+\Delta ))\right)$ for the coherent input superposition used in the adversary argument. For the second term, we prove directly using a three-eigenvalue multiplicative adversary that unique OR on $n$ bits with success probability $1/2+\zeta$ requires $\Omega (\sqrt{\zeta n})$ queries, and then reduce unique OR to the two-weight counting problem.

18 pages