⚛️ quantum physics

Quantum Approximate Counting with Bernoulli Oracles

This paper introduces a quantum algorithm for approximate counting using Bernoulli oracles with unknown biases, achieving a quadratic speedup over classical methods by combining Quantum Singular Value Transformation with adaptive amplitude estimation and establishing near-matching query complexity bounds.

Original authors: Chengshen Gao, Yongzhen Xu, Lvzhou Li

Published 2026-09-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Chengshen Gao, Yongzhen Xu, Lvzhou Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computing, there is a fundamental task known as counting. Imagine a vast room filled with thousands of people, some wearing red hats and others wearing blue. A computer's job is to figure out what fraction of the crowd is wearing red. In the classical world, the only way to do this is to walk around and ask people one by one, or to take a random sample of the crowd and count the hats within that group. This method works, but it is slow; to get a very precise answer, you often have to check a huge number of people.

Quantum computing offers a different path. By using the strange laws of physics that govern the very small, quantum computers can process information in a way that allows them to find the answer much faster than classical machines. This speedup is not just a little bit faster; for counting problems, it is a massive leap, allowing the computer to find the answer with far fewer checks. However, this powerful speedup has traditionally relied on a very strict assumption: that the computer can ask a question and get a perfect, definite answer every time. If the computer asks, "Is this person wearing a red hat?" it expects a clear "yes" or "no." But in the real world, things are rarely so clear-cut. Sometimes the answer is fuzzy, or the person answering might be unsure, or the signal might be noisy. For years, scientists wondered if the quantum speedup could survive in this messy, uncertain reality.

A team of researchers has now answered that question with a definitive yes. They have developed a new method that allows quantum computers to count accurately even when the information they receive is probabilistic and imperfect. In their work, they tackled a scenario where the computer does not get a simple "yes" or "no" from each item it checks. Instead, each check returns a result that is more like a weighted coin flip. Some items are clearly "positive," meaning they are very likely to return a "yes," while others are clearly "negative," meaning they are very likely to return a "no." The challenge is to determine the overall fraction of positive items in the collection without knowing the exact bias of any single item.

The researchers proved that quantum computers can still achieve a quadratic speedup in this difficult setting. This means that even with the noise and uncertainty, the quantum approach requires significantly fewer checks than any classical method could ever hope to achieve. They designed an algorithm that first uses a sophisticated technique to sharpen the blurry signals. Instead of measuring each item immediately, which would destroy the quantum advantage, the algorithm gently amplifies the difference between the "positive" and "negative" items while keeping them all in a state of quantum superposition. This process acts like a filter that makes the clear signals clearer and the uncertain ones less confusing, all without collapsing the delicate quantum state.

Once the signals are sharpened, the algorithm performs a two-stage counting process. It first takes a rough look to see if the fraction of positive items is very small or substantial. Based on that initial glimpse, it then adjusts its precision for a second, more detailed run. This adaptive strategy ensures that the computer does not waste time looking for a needle in a haystack if there is no needle, or over-analyzing a situation that is already clear. The result is a highly efficient method that can estimate the fraction of positive items with high accuracy, even when the individual data points are unreliable.

To be certain that their method was truly the best possible, the researchers also proved a mathematical limit on how fast any quantum computer could possibly solve this problem. They showed that their new algorithm comes very close to this theoretical limit, meaning there is likely no way to make it significantly faster. This confirmation is crucial because it establishes that the speedup they found is not just a lucky trick, but a fundamental property of how quantum mechanics interacts with this type of uncertain data.

The implications of this work extend beyond just counting. The techniques they developed, particularly the way they handle uncertainty without losing quantum coherence, could be applied to many other problems where data is noisy or incomplete. Whether it is testing the reliability of a crowd-sourced answer, analyzing the performance of different options in a complex system, or inferring patterns from imperfect observations, the ability to count accurately in the face of uncertainty is a powerful tool. By showing that quantum speedup survives the messiness of the real world, this research opens the door for quantum computers to tackle practical problems that were previously thought to be too uncertain for them to handle efficiently.

The study also clarifies the relationship between different types of quantum oracles, or the ways a computer can access information. They showed that the problem of counting with noisy, bounded-error answers is a specific case of their more general problem involving Bernoulli distributions. This means that the solutions they found apply broadly, covering everything from perfectly clear data to data that is only slightly noisy. Their work provides a complete picture of the resources needed to solve these counting problems, mapping out exactly how the difficulty changes as the data becomes more uncertain or the required precision becomes higher.

In the end, this research demonstrates that the power of quantum computing is robust. It does not crumble when faced with the imperfect, probabilistic nature of real-world data. Instead, it adapts, using the unique properties of quantum mechanics to turn uncertainty into a manageable factor. The researchers have provided both a practical algorithm to solve these problems and a theoretical proof that their solution is nearly optimal. This dual achievement gives scientists and engineers a clear path forward for building quantum applications that can operate effectively in the complex, noisy environments where most real-world data lives.

Technical Summary: Quantum Approximate Counting with Bernoulli Oracles

1. Problem Definition

The paper addresses the problem of quantum approximate counting in a setting where the standard membership oracle is replaced by a Bernoulli oracle.

Standard Setting: In classical and standard quantum counting, a membership oracle deterministically labels elements of a set as 0 or 1. The goal is to estimate the fraction $\rho$ of elements labeled 1 within additive error $\epsilon$ . Quantum algorithms achieve a quadratic speedup over classical sampling, requiring $\Theta(\sqrt{\rho}/\epsilon)$ queries versus $\Theta(\rho/\epsilon^2)$ .
Bernoulli Oracle Setting: The authors consider a more realistic scenario where labels are probabilistic. The algorithm is given access to $m$ $m$ Bernoulli distributions $D = \{D_1, \dots, D_m\}$ $D = {D_{1}, \dots, D_{m}}$ with unknown biases $p_1, \dots, p_m \in [0, 1]$ $p_{1}, \dots, p_{m} \in [0, 1]$ .
- A distribution is positive if $p_i \ge 1/2 + \Delta$ .
- A distribution is negative if $p_i \le 1/2 - \Delta$ .
- The goal is to estimate the fraction $\rho$ of positive distributions within additive error $\epsilon$ .
- The quantum oracle $O$ acts on an index register $A$ and auxiliary registers $B, C$ as:
  $O |i\rangle_A |\vec{0}\rangle_{B,C} = |i\rangle_A \left( \sqrt{p_i} |1\rangle_B |\phi_{i,1}\rangle_C + \sqrt{1-p_i} |0\rangle_B |\phi_{i,0}\rangle_C \right)$

This model generalizes the bounded-error oracle (where each query returns the correct label with constant probability $p_e \ge 9/10$ , corresponding to $\Delta = 2/5$ ) and the standard membership oracle (where $\Delta = 1/2$ ).

2. Methodology

The paper establishes both upper and lower bounds on the query complexity, employing distinct techniques for each.

Upper Bound Techniques:
The primary challenge is that determining whether a specific distribution is positive or negative cannot be done perfectly with a bounded number of queries without collapsing the quantum superposition. Standard error reduction (repeating and taking the median) requires measurement, which destroys the coherence necessary for quantum amplitude estimation.

To resolve this, the authors propose a three-stage algorithm:

Coherent Error Reduction via QSVT: Instead of measuring, the algorithm uses Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap. By approximating a step function with a polynomial of degree $O(\frac{1}{\Delta} \log \frac{1}{\epsilon})$ $O (\frac{1}{Δ} lo g \frac{1}{ϵ})$ , the algorithm transforms the state such that:
- If $p_i \ge 1/2 + \Delta$ , the probability of measuring $|1\rangle$ becomes $\ge 1 - \epsilon$ .
- If $p_i \le 1/2 - \Delta$ , the probability of measuring $|1\rangle$ becomes $\le \epsilon$ .
  This subroutine, called RST (Robust Single Distribution Transform), performs error reduction entirely within the coherent layer, preserving the superposition over the index register.
Two-Stage Adaptive Amplitude Estimation: The RST subroutine is embedded into an adaptive amplitude estimation scheme.
- Stage 1: A coarse estimate of $\rho$ is obtained.
- Stage 2: If $\rho$ is non-negligible, the coarse estimate is used to calibrate the precision of a second, finer estimation run. This avoids wasting resources on high-precision estimation when $\rho$ is very small.
Confidence Boosting: The entire procedure is repeated $\Theta(\log(1/\delta))$ times, and the median is taken to boost the success probability to $1-\delta$ .

Lower Bound Techniques:
The authors prove a lower bound by reducing the estimation problem to a composed decision problem: Count $\circ$ DD.

Outer Function (Count): A standard Boolean function determining if an $m$ -bit string has Hamming weight $\rho m$ or $(\rho + \epsilon)m$ .
Inner Function (DD): An average-case problem distinguishing between two unknown distributions $P$ and $Q$ given $R$ independent samples.

The authors introduce a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. Standard composition theorems handle Boolean-over-Boolean or average-case-over-Boolean, but this work addresses the reverse (Boolean outer, average-case inner).

Obstacle 1 (Inner Non-uniformity): Inner products across different blocks are not guaranteed to be equal. The authors construct specific inner adversary matrices where every block inner product equals 1, ensuring compatibility.
Obstacle 2 (Outer Misalignment): The uniform distribution vectors of the outer layer do not align with the principal eigenvectors of the adversary matrix for general Boolean functions. The authors show that for the specific "Count" function (a 0-1 matrix), the all-ones vector provides a sufficient lower bound on the spectral norm, resolving the misalignment.

3. Key Results

The paper provides a near-complete characterization of the query complexity for quantum counting with Bernoulli oracles.

Upper Bound (Theorem 1.2):
There exists a quantum algorithm that estimates $\rho$ within additive error $\epsilon$ with success probability $1-\delta$ using:
$\tilde{O}\left( \left( \frac{\sqrt{\rho}}{\Delta \epsilon} + \frac{1}{\Delta \sqrt{\epsilon}} \right) \log \frac{1}{\delta} \right)$
queries.

This achieves a quadratic speedup over the classical sample complexity of $\Theta(\frac{\rho}{\Delta^2 \epsilon^2})$ .
For the special case of the bounded-error oracle ( $\Delta = \Theta(1)$ ), the bound simplifies to $\tilde{O}(\frac{\sqrt{\rho}}{\epsilon} + \frac{1}{\sqrt{\epsilon}})$ .

Lower Bound (Theorem 1.3):
Any quantum algorithm estimating $\rho$ within additive error $\epsilon$ with success probability $2/3$ requires:
$\Omega\left( \frac{\sqrt{\rho}}{\Delta \epsilon} \right)$
queries.

This lower bound matches the upper bound up to logarithmic factors across the full range of $\Delta$ .
For the bounded-error oracle ( $\Delta = \Theta(1)$ ), the lower bound is $\Omega(\frac{\sqrt{\rho}}{\epsilon})$ .

Containment Chain:
The paper establishes a hierarchy of oracles: Membership $\subset$ Bounded-error $\subset$ Bernoulli.

The results for the Bernoulli oracle with $\Delta = 1/2$ recover the standard quantum counting bounds.
The results for $\Delta = 2/5$ characterize the complexity of quantum counting with bounded-error oracles, a problem previously studied but not fully characterized in this specific context.

4. Significance and Claims

The authors claim that this work provides an essentially complete characterization of the query complexity for quantum approximate counting under probabilistic labeling.

Generalization of Speedup: The work demonstrates that the quadratic speedup of quantum counting is robust even when the oracle returns probabilistic samples rather than deterministic labels, provided the bias gap $\Delta$ is known.
Coherent Error Reduction: The paper introduces a technique to perform error reduction coherently using QSVT, avoiding the collapse of superposition that typically prevents the composition of classical error reduction with quantum amplitude estimation.
New Composition Theorem: The derivation of the lower bound introduces a novel composition theorem for the quantum adversary method in the Boolean-over-average-case direction, overcoming specific structural obstacles (inner non-uniformity and outer misalignment) that previously hindered such analyses.
Bounded-Error Oracle Characterization: As a direct corollary, the paper settles the query complexity for quantum counting with bounded-error oracles, showing it scales as $\tilde{O}(\sqrt{\rho}/\epsilon)$ , matching the standard membership oracle scaling up to logarithmic factors.

The paper concludes by noting two open questions: whether the logarithmic factor in the upper bound can be removed, and how the complexity changes under the sampling model (where the algorithm receives random pairs of indices and samples) rather than the adaptive query model used here.

Technical Summary: Quantum Approximate Counting with Bernoulli Oracles

1. Problem Definition

2. Methodology

3. Key Results

4. Significance and Claims

More like this