Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method
This research uses a multiplicative adversary method to establish fine-grained query lower bounds for distinguishing between two Hamming weights, M and M + Delta, in quantum approximate counting. The study recovers optimal asymptotic bounds by tracking progress through individual oracle queries, providing crucial limits for NISQ and post-quantum cryptography.