Quantum Approximate Counting

Overview

Quantum approximate counting estimates how many items in a large set satisfy a condition, to within a chosen relative error, using only Grover-style iterations and measurements. It is a streamlined relative of quantum counting. The original method uses quantum phase estimation, which needs many extra qubits and a quantum Fourier transform. The approximate counting variants avoid phase estimation, which makes them easier to run on early fault-tolerant hardware.

The key result is that the number of queries needed is still on the order of the square root of N over M divided by the error, which is the same quadratic gain over classical sampling that the original method achieves.

The problem it solves

Quickly estimating roughly how many items in a large dataset satisfy a given condition, when an approximate answer is sufficient.

History and background

Brassard, Høyer, and Tapp introduced quantum counting in 1998. For many years, estimating amplitudes or counts needed the full phase estimation circuit. In 2019 and 2020, several groups found ways to remove the quantum Fourier transform. Suzuki, Uno, Raymond, Tanaka, Onodera, and Yamamoto proposed maximum likelihood amplitude estimation in 2020, Aaronson and Rall published Quantum Approximate Counting, Simplified in 2020, and Grinko, Gacon, Zoufal, and Woerner described iterative quantum amplitude estimation in 2021.

Aaronson and Rall's paper showed that a few lines of analysis suffice to prove that approximate counting can be done by running Grover iterations for various lengths and measuring the success probability, with the results combined by classical post-processing. These simplified methods are now the standard way to estimate amplitudes in practical resource estimates, for example in financial applications.

How it works

Uses simplified amplitude estimation circuits with fewer required qubits and gates than full quantum phase estimation, trading precision for practicality on near-term hardware.

The Grover iteration rotates the state by an angle of 2 theta, where the sine squared of theta equals the fraction of marked items. After k iterations, the probability of measuring a marked item is the sine squared of 2k plus 1 times theta. If you run the circuit with different values of k and record how often you see a marked item, the pattern of probabilities reveals theta.

Quantum counting reads theta using phase estimation. The simplified methods infer theta statistically instead. With small k, the probability changes slowly with theta, so the data gives a coarse estimate. With large k, the probability oscillates rapidly, so even a small change in theta shifts the outcome, which gives a fine estimate. By increasing k geometrically and combining the results, the algorithm zooms in on theta.

Because each run uses only the Grover circuit and a single measurement, the quantum hardware needs no counting register and no Fourier transform. The price is more repetitions and a classical statistics step, but the total number of Grover iterations still scales with the inverse of the error, which is the Heisenberg limit.

Step by step

1. Define the oracle that marks the items satisfying the condition, and the Grover operator built from it.
2. Choose a schedule of iteration counts, such as 0, 1, 2, 4, 8, and so on, up to a maximum determined by the desired precision.
3. For each iteration count, prepare the equal superposition, apply that many Grover iterations, and measure to record whether the result is marked.
4. Repeat each setting enough times to estimate its success probability.
5. Combine the results with maximum likelihood estimation or an adaptive confidence-interval method to obtain an estimate of theta.
6. Convert theta to a count estimate, N times the sine squared of theta, with the associated error bar.

A worked example

Suppose there are N = 1,000,000 items and an unknown number M of marked items, with true M equal to 4,000, so the marked fraction is 0.004. Running 0 Grover iterations gives a success frequency near 0.004. Running 1 iteration gives a frequency near the sine squared of 3 theta, about 0.036, and so on. Each of these gives a constraint on theta.

After a few dozen settings with a few hundred shots each, the combined likelihood pins down the fraction to about 1 percent. A classical random-sampling estimate of the same precision would need on the order of 100 over 0.004 squared samples, which is around ten million. The quantum version uses about a thousand Grover iterations in total.

Complexity and resources

What hardware it needs

• A reversible oracle that marks the solutions, and Grover iterations with enough coherence for the deepest run.
• Many repetitions of shorter circuits, which suits devices with limited coherence.
• Fast classical post-processing for the statistical combination.

Applications

• Estimating the number of solutions of a constraint problem before running Grover search.
• Amplitude estimation for Monte Carlo methods in finance and physics, in the form of iterative and maximum-likelihood variants.
• Estimating probabilities, expectation values, and volumes with a quadratic improvement over sampling.
• Benchmarking Grover circuits on early fault-tolerant hardware.

Limitations and caveats

• The Heisenberg-limited scaling needs deep circuits, so the speedup holds only if the hardware is coherent enough.
• With noise, the benefit decays, and the optimal depth depends on the error rate.
• The oracle cost dominates for complex conditions.

Common misconceptions

• Approximate counting does not count exactly. It gives an estimate with a confidence interval.
• It is not a different algorithm from amplitude estimation. It is the counting special case, in the same family of phase-estimation-free methods.

How it compares

• The original quantum counting algorithm uses phase estimation and a quantum Fourier transform.
• Amplitude estimation without phase estimation generalizes these methods to arbitrary state-preparation circuits.
• Classical sampling needs quadratically more samples.

Real-world impact

More practical for NISQ-era hardware than the full quantum counting algorithm, useful in statistical estimation tasks where approximate counts are acceptable.

Why it matters

These variants show that the quadratic advantage for estimation does not require the full machinery of phase estimation, which lowers the hardware bar for the first practical quantum Monte Carlo applications. They are what resource estimates for derivative pricing and risk analysis actually assume.

They also illustrate a broader trend: replacing coherent Fourier-transform subroutines with repeated short circuits and classical statistics, to match the capabilities of early fault-tolerant machines.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Counting
• Related algorithm: Quantum Amplitude Estimation
• Related algorithm: Quantum Mean Estimation
• Related algorithm: Quantum Monte Carlo Integration

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database