An upper bound of $\tilde{O}\!\big(\frac{\rho}}{\Delta\epsilon}+\frac{1}{\Delta\sqrt{\epsilon}}\big)$ queries is proved for quantum counting with bounded-error oracles, achieving a quadratic speedup over the classical sample complexity.
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.
A multiplicative-adversary derivation that tracks the progress produced by individual oracle queries and proves that unique OR on bits with success probability $1/2+\zeta$ requires $\Omega(\sqrt{\zeta n})$ queries, and reduces unique OR to the two-weight counting problem.
Entropy estimation of discrete probability distributions is a fundamental problem in statistical inference and quantum property estimation. In this paper, we study the problem of estimating R\'enyi entropy $H_\alpha(\mathbf{p})$ for any distribution $\mathbf{p} = (p_i)_{i=1}^n$ given its purified quantum query-access....
The argument reduces any $N$-query circuit to the approximation of $e^{it\theta}$ by a trigonometric polynomial with degree bounded by $O(N)$ by a trigonometric polynomial with degree bounded by $O(N)$ together with Remez inequality to establish a matching lower bound for arbitrary query algorithms.
A. Liu, Adam Wesołowski, Jayne Thompson et al.· 0 citations
We prove the first quantum-classical separation for a sampling problem over a continuous domain. For a class of Gibbs states $p\propto e^{-\beta E}$ on the torus $\mathbb{T}^d$ with smooth ($s$-Gevrey) potential and barrier amplitude $\alpha=e^{\beta\Delta}$, where $\Delta = \max E-\min E$, every classical algorithm qu...
Enrico Olivucci, Mariia Sobchuk, Sehmimul Hoque et al.· 1 citation
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation...
A. Ambainis, A. Gilyén, M. Kokainis· 2 citations· ⚡1
We give a quantum algorithm for stochastic $2$-player games. Their game trees are the expectiminimax trees of classical game search: $m$ adversarial layers alternate with $m$ chance layers, every node has $deg$ children, and the leaf values lie in an interval of length $N$. The algorithm estimates the value of the game...
M. Raat, Merlin Incerti-Medici, James R. Wootton et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.