Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Acta Applicandae Mathematicae

Quantum Counting: Algorithm and Error Distribution

Zijian Diao, Chunfeng Huang, Ke Wang

Published Feb 9, 2012• 26 citations
Publisher
DOI
10.1007/s10440-012-9682-6

Related papers

Influences of Gate Operation Errors in the Quantum Counting Algorithm

Qing Ai, Yansong Li, Gui‐Lu Long

Journal of Computer Science and Technology•Nov 1, 2006•15 citations

Distributed quantum approximate counting algorithm

Huaijing Huang, Daowen Qiu

•Jan 1, 2026•0 citations

Quantum Approximate Counting with Bernoulli Oracles

Chengshen Gao, Yongzhen Xu, Lvzhou Li

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 $Δ$, the goal is to estimate the fraction $ρ$ of \emph{positive} distributions ($p_i\ge1/2+Δ$) to within additive error $ε$. We prove an upper bound of $\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)$ 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 $Ω(\sqrtρ/(Δε))$ 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 $\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)$ and $Ω(\frac{\sqrtρ}ε)$, thereby characterizing the query complexity of quantum counting with bounded-error oracles.

quant-pharXiv:2609.07604•Sep 8, 2026•0 citations

Quantum Counting with Decoherence Errors

Jun Hasegawa, Fumitaka Yura

•Sep 1, 2003•0 citations

Generalized quantum counting algorithm for non-uniform amplitude distribution

Jianing Tan, Yue Ruan, Xi Li +1 more

Quantum Information Processing•Jan 25, 2017•3 citations

Quantum counting

Gilles Brassard, Peter Høyer, Alain Tapp

arXiv:quant-ph/9805082•Lecture notes in computer science•Jan 1, 1998•421 citations
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 mmm Bernoulli distributions with unknown biases p1,…,pmp_1,\dots,p_mp1​,…,pm​ and a gap parameter ΔΔΔ, the goal is to estimate the fraction ρρρ of \emph{positive} distributions (pi≥1/2+Δp_i\ge1/2+Δpi​≥1/2+Δ) to within additive error εεε. We prove an upper bound of O~ ⁣(ρΔε+1Δε)\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)O~(Δερ​​+Δε​1​) queries, achieving a quadratic speedup over the classical sample complexity. % of Θ(ρ/Δ2ε2)Θ(ρ/Δ^2ε^2)Θ(ρ/Δ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 Ω(ρ/(Δε))Ω(\sqrtρ/(Δε))Ω(ρ​/(Δε)) 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)Δ=Θ(1)Δ=Θ(1), which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to O~(ρε+1ε)\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)O~(ερ​​+ε​1​) and Ω(ρε)Ω(\frac{\sqrtρ}ε)Ω(ερ​​), thereby characterizing the query complexity of quantum counting with bounded-error oracles.