Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method

Albert Lin, Han-Hsuan Lin

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+ζ…