Quantum Approximate Counting with Bernoulli Oracles
Abstract
Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given m Bernoulli distributions with unknown biases p1,…,pm and a gap parameter Δ, the goal is to estimate the fraction ρ of \emph{positive} distributions (pi≥1/2+Δ) to within additive error ε. We prove an upper bound of Õ (√ρ/Δε+1/Δ√ε) queries, achieving a quadratic speedup over the classical sample complexity. % of Θ(ρ/Δ2ε2). Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of Ω(√ρ/(Δε)) via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap Δ=Θ(1), which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to Õ(√ρ/ε+1/√ε) and Ω(√ρ/ε), thereby characterizing the query complexity of quantum counting with bounded-error oracles.
Related
- Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method
- Approximate Counting for Mixed p-Spin Glasses in Weak External Fields via Cluster Expansion
- How to make quantum cheese: efficient geometry oracles for exponentially many pseudorandom microstructures
- Spectral theory of energy-selective quantum search with Ising Hamiltonian phase oracles
- Modeling and Resource Optimization for Quantum Oracles
BibTeX
@misc{gao2026quantum,
title = {{Quantum Approximate Counting with Bernoulli Oracles}},
author = {Chengshen Gao and Yongzhen Xu and Lvzhou Li},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07604},
eprint = {2609.07604},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07604},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Approximate Counting with Bernoulli Oracles
AU - Chengshen Gao
AU - Yongzhen Xu
AU - Lvzhou Li
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07604
UR - https://arxiv.org/abs/2609.07604
AB - Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given m Bernoulli distributions with unknown biases p_1,…,p_m and a gap parameter Δ, the goal is to estimate the fraction ρ of \emph{positive} distributions (p_i≥1/2+Δ) to within additive error ε. We prove an upper bound of Õ (√ρ/Δε+1/Δ√ε) queries, achieving a quadratic speedup over the classical sample complexity. % of Θ(ρ/Δ^2ε^2). Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of Ω(√ρ/(Δε)) via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap Δ=Θ(1), which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to Õ(√ρ/ε+1/√ε) and Ω(√ρ/ε), thereby characterizing the query complexity of quantum counting with bounded-error oracles.
ER -