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 $p_1,\dots,p_m$ and a gap parameter $\Delta$, the goal is to estimate the fraction $\rho$ of \emph{positive} distributions ($p_i\ge1/2+\Delta$) to within additive error $\epsilon$. We prove an upper bound of $\tilde{O}\!\big(\frac{\sqrt{\rho}}{\Delta\epsilon}+\frac{1}{\Delta\sqrt{\epsilon}}\big)$ queries, achieving a quadratic speedup over the classical sample complexity. % of $\Theta(\rho/\Delta^2\epsilon^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 $\Omega(\sqrt{\rho}/(\Delta\epsilon))$ 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 $\Delta=\Theta(1)$, which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to $\tilde{O}\big(\frac{\sqrt{\rho}}{\epsilon}+\frac{1}{\sqrt{\epsilon}}\big)$ and $\Omega(\frac{\sqrt{\rho}}{\epsilon})$, thereby characterizing the query complexity of quantum counting with bounded-error oracles.

arXiv:2609.07604 [quant-ph]

(or arXiv:2609.07604v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.07604 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.