Quantum Approximate Counting with Bernoulli Oracles
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.07604
curl -X POST /api/v1/records/arxiv/2609.07604/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.07604/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'