Quantum method finds better limits on approximate counting queries
Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method
Computational Complexity
Summary
The paper tackles a quantum computing problem where you have to tell if a list of bits has a certain number of ones or just a few more. The authors used a mathematical method called the multiplicative adversary to figure out how many times a quantum algorithm must look at the list to decide this reliably. They improved our understanding by tracking each query’s progress, giving new lower bounds on the number of steps needed. This helps clarify the limits of quantum approximate counting.
What this means in practice
- •For quantum algorithm designers: Know the minimal number of oracle queries required when building quantum algorithms for approximate counting tasks under two-weight distinctions.
- •For quantum hardware engineers: Use the proven query lower bounds to estimate the minimum operation counts needed for quantum processors handling approximate counting or decision subroutines.
A theory result. No direct application yet.
Authors
Albert Lin, Han-Hsuan Lin
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+Δ$ 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 complementing the input if necessary, we assume $M+Δ\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 $\left\|(I-\widehatΠ_{\mathrm{bad}})\lvertΨ^T\rangle\right\|^2=O\left(T^2Δ^2/((N-M)(M+Δ))\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+ζ$ requires $Ω(\sqrt{ζn})$ queries, and then reduce unique OR to the two-weight counting problem.