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∈{0,1}N, distinguish |x|=M from |x|=M+Δ with success probability 1/2+ζ. Using the multiplicative adversary method, we prove Ω(max{ζ√((N−M)(M+Δ))/Δ,√(ζN/Δ)}). 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+Δ≤ 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 |(I−Π̂bad)lvertΨT⟩|2=O(T2Δ2/((N−M)(M+Δ))) 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 Ω(√(ζn)) queries, and then reduce unique OR to the two-weight counting problem.
Related
- Quantum Approximate Counting with Bernoulli Oracles
- Approximate Counting for Mixed p-Spin Glasses in Weak External Fields via Cluster Expansion
- High-Rank Encoding Can Improve Approximate Quantum Error Correction
- Approximate Synthetic Spectra of Quantum Systems Associated with Compact Lie Groups
- Depth analysis of the Quantum Approximate Optimization Algorithm with a Grover mixer
BibTeX
@misc{lin2026smallbias,
title = {{Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method}},
author = {Albert Lin and Han-Hsuan Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.09804},
eprint = {2609.09804},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09804},
}
RIS
TY - UNPB
TI - Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method
AU - Albert Lin
AU - Han-Hsuan Lin
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2609.09804
UR - https://arxiv.org/abs/2609.09804
AB - We study the two-weight decision version of quantum approximate counting: given oracle access to x∈{0,1}^N, distinguish |x|=M from |x|=M+Δ with success probability 1/2+ζ. Using the multiplicative adversary method, we prove Ω(max{ζ√((N−M)(M+Δ))/Δ,√(ζN/Δ)}). 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+Δ≤ 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 |(I−Π̂_bad)lvertΨ^T⟩|^2=O(T^2Δ^2/((N−M)(M+Δ))) 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 Ω(√(ζn)) queries, and then reduce unique OR to the two-weight counting problem.
ER -