Introduction

Imagine you have a massive database of NN items and you want to know how many of them are marked — without enumerating every one. Classically, the best you can do is sample: check O(N)O(N) items and estimate. There is no shortcut.

Quantum counting changes that. Introduced by Brassard, Høyer, and Tapp in 1998, it estimates the number of marked items MM using only O(N)O(\sqrt{N}) quantum operations — a quadratic speedup over any classical survey.

The trick is elegant: quantum counting is not really about searching. It is about measuring a rotation angle. Every call to Grover's oracle rotates a quantum state by an angle θ\theta that encodes MM. By measuring θ\theta with quantum phase estimation, you read off MM — without ever listing a single marked item.

Try It

Below is a simulation of the quantum counting idea. Choose how many items are marked out of a database of N=64N = 64 items, then watch how the phase angle θ\theta is estimated and converted back to a count M^\hat{M}.

<!-- Quantum Counting demo — phase estimation on the Grover operator -->
<p class="hint">Choose how many items are <b>marked</b> out of 64, then click <b>Estimate Count</b>. Phase estimation reads the Grover rotation angle θ where sin²θ = M/N, recovering M in O(√N) oracle calls instead of O(N).</p>
<div class="controls">
  <label for="marked-slider">Marked items M = <strong id="marked-val">8</strong> / 64</label>
  <input type="range" id="marked-slider" min="1" max="63" value="8" step="1">
</div>
<div class="controls">
  <label for="ancilla-slider">Ancilla qubits t = <strong id="ancilla-val">6</strong></label>
  <input type="range" id="ancilla-slider" min="3" max="8" value="6" step="1">
</div>
<button id="run-btn" type="button">Estimate Count</button>
<div id="result-area" class="result-area" aria-live="polite"></div>
<div id="chart-area" class="chart-area"></div>

/* Base layout and controls */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.controls { display: flex; align-items: center; gap: .7rem; margin: .4rem 0; flex-wrap: wrap; }
.controls label { font-size: .9rem; min-width: 14rem; }
input[type=range] { flex: 1; min-width: 120px; accent-color: #1d3557; }
button { font: 600 14px system-ui; padding: .45rem 1rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; margin-top: .4rem; }
button:hover { background: #2b4d73; }
.result-area { margin: .7rem 0 .3rem; font-size: .95rem; min-height: 2.4em; }
.result-area .row { margin: .15rem 0; }
.ok { color: #0a7d33; font-weight: 600; }
.formula { font-family: ui-monospace, monospace; font-size: .85rem; color: #555; }
/* Bar chart comparing query counts */
.chart-area { margin-top: .5rem; overflow-x: auto; }
.chart-area svg { display: block; }
.bar-exact { fill: #1d3557; }
.bar-estimate { fill: #e63946; }
.axis { stroke: #bbb; stroke-width: 1; }
.tick-label { font-size: 10px; fill: #666; }
.legend { font-size: 11px; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Quantum Counting (Brassard–Høyer–Tapp 1998):
// Run phase estimation on Grover operator G = -H I_0 H I_f.
// G has eigenphases ¹2θ where sin²(θ) = M/N.
// Measuring θ via QPE gives M in O(sqrt(N)/epsilon) queries.

const N = 64; // database size — fixed for this demo

// Compute the exact Grover rotation angle from M and N
function exactTheta(M, N) {
  return Math.asin(Math.sqrt(M / N));
}

// Simulate QPE measurement: the ideal output is theta/pi as a t-bit fraction.
// We add small Gaussian-like noise to model finite precision.
function simulatePhaseEstimation(M, t) {
  // Grover eigenphase
  const theta = exactTheta(M, N);
  // QPE measures the closest t-bit fraction to theta/pi
  // phase eigenvalue of G is exp(±2i*theta); QPE measures k/2^t ≈ theta/pi
  const trueFrac = theta / Math.PI;
  // Add finite-precision noise proportional to 1/2^t
  const noise = (Math.random() - 0.5) * (0.6 / Math.pow(2, t));
  const measFrac = Math.max(0, Math.min(0.5 - 1e-9, trueFrac + noise));
  return measFrac;
}

// Convert measured fraction back to an integer count
function fracToM(frac, N) {
  const theta = frac * Math.PI;
  return Math.round(N * Math.sin(theta) * Math.sin(theta));
}

// Classical sample complexity to count with relative error eps
function classicalQueries(N, M, eps) {
  // classical: O(N / (M * eps^2)) — proportional to N/M
  return Math.ceil(N / (M * eps * eps));
}

// Quantum query complexity for counting
function quantumQueries(N, M, eps) {
  // quantum: O(sqrt(N) / eps) — independent of M
  return Math.ceil(Math.sqrt(N) / eps);
}

function drawChart(M, Mest) {
  const area = document.getElementById('chart-area');
  const W = Math.min(area.clientWidth || 400, 460);
  const H = 110;
  const pad = { l: 50, r: 10, t: 20, b: 30 };
  const innerW = W - pad.l - pad.r;

  // Build bar chart comparing quantum vs classical query counts
  const eps = 0.1;
  const qQ = quantumQueries(N, M, eps);
  const cQ = classicalQueries(N, M, eps);
  const maxQ = Math.max(qQ, cQ, 1);
  const scale = innerW / maxQ;

  let svg = `<svg width="${W}" height="${H}" viewBox="0 0 ${W} ${H}" xmlns="http://www.w3.org/2000/svg">`;
  // Draw axes
  svg += `<line class="axis" x1="${pad.l}" y1="${pad.t}" x2="${pad.l}" y2="${H - pad.b}"/>`;
  svg += `<line class="axis" x1="${pad.l}" y1="${H - pad.b}" x2="${W - pad.r}" y2="${H - pad.b}"/>`;

  // Quantum bar (blue)
  const bH = 22, gap = 8;
  const y1 = pad.t + 4;
  svg += `<rect class="bar-exact" x="${pad.l + 1}" y="${y1}" width="${Math.max(2, qQ * scale)}" height="${bH}"/>`;
  svg += fmt('<text class="tick-label" x="%v%" y="%v2%" dominant-baseline="middle">Quantum (%qQ%)</text>', { v: pad.l + Math.max(2, qQ * scale) + 4, v2: y1 + bH - 6, qQ: qQ });

  // Classical bar (red)
  const y2 = y1 + bH + gap;
  svg += `<rect class="bar-estimate" x="${pad.l + 1}" y="${y2}" width="${Math.min(innerW, Math.max(2, cQ * scale))}" height="${bH}"/>`;
  svg += fmt('<text class="tick-label" x="%v%" y="%v2%" dominant-baseline="middle">Classical (%cQ%)</text>', { v: pad.l + Math.min(innerW, Math.max(2, cQ * scale)) + 4, v2: y2 + bH - 6, cQ: cQ });

  // Label x-axis
  svg += `<text class="tick-label" x="${pad.l}" y="${H - 4}">0</text>`;
  svg += fmt('<text class="tick-label" x="%v%" y="%v2%">queries →</text>', { v: W - pad.r - 30, v2: H - 4 });
  svg += '</svg>';
  area.innerHTML = svg;
}

function run() {
  const M = parseInt(document.getElementById('marked-slider').value, 10);
  const t = parseInt(document.getElementById('ancilla-slider').value, 10);

  const frac = simulatePhaseEstimation(M, t);
  const Mest = fracToM(frac, N);
  const theta = frac * Math.PI;
  const thetaDeg = (theta * 180 / Math.PI).toFixed(2);

  const area = document.getElementById('result-area');
  area.innerHTML =
    fmt('<div class="row">True M: <strong>%M%</strong> &nbsp;|&nbsp; Estimated M̂: <strong class="ok">%Mest%</strong></div><div class="row formula">θ ≈ %thetaDeg%° &nbsp;(sin²θ = %v%, M/N = %v2%)</div><div class="row formula">Quantum oracle calls needed: ~%ceil% &nbsp;(classical would need ~%N%)</div>', { M: M, Mest: Mest, thetaDeg: thetaDeg, v: (Math.sin(theta) ** 2).toFixed(4), v2: (M / N).toFixed(4), ceil: Math.ceil(Math.sqrt(N)), N: N });

  drawChart(M, Mest);
  console.log('Quantum counting run:', { M, Mest, thetaDeg, t });
}

// Sync slider display values
document.getElementById('marked-slider').addEventListener('input', function() {
  document.getElementById('marked-val').textContent = this.value;
});
document.getElementById('ancilla-slider').addEventListener('input', function() {
  document.getElementById('ancilla-val').textContent = this.value;
});
document.getElementById('run-btn').addEventListener('click', run);
run(); // Run once on load
Result
Console

Notice that the estimate converges rapidly — you need only O(N)O(\sqrt{N}) oracle queries, not O(N)O(N). With N=64N = 64, that is roughly 8 queries instead of 64. The classical approach has no such shortcut: it must inspect items one by one until the count is reliable.

The Real Complexity

The core of quantum counting is quantum phase estimation applied to the Grover operator GG.

  • The Grover operator G=−H⊗nI0H⊗n⋅IfG = -H^{\otimes n} I_0 H^{\otimes n} \cdot I_f alternates between an oracle reflection IfI_f (which flips the sign of marked states) and a diffusion reflection I0I_0 (which inverts about the mean). Together they rotate the search subspace by angle 2θ2\theta where sin⁥2 ⁣θ=M/N\sin^2\!\theta = M/N.
  • Phase estimation prepares a superposition of eigenvalues of GG, applies GG repeatedly in a controlled fashion, and reads the phase θ\theta via an inverse quantum Fourier transform. With tt ancilla qubits, you get tt bits of precision.
  • The speedup: estimating MM to additive error Îľ\varepsilon takes O(N/Îľ)O(\sqrt{N}/\varepsilon) quantum oracle calls — versus O(N/Îľ2)O(N/\varepsilon^2) classically. The quantum query complexity is provably Θ(N/M)\Theta(\sqrt{N/M}) for finding one solution; counting is comparable.
  • Where it sits: quantum counting lives in BQP (efficient quantum) and extends Grover's search. Classically, even randomised algorithms need Ί(N/M)\Omega(N/M) queries to count — a provable quadratic gap.

The result is one of the cleanest quantum speedups: a single angle measurement, combined with the quantum Fourier transform, replaces an exhaustive survey.

Where It Matters

Counting how many things satisfy a condition is surprisingly central to computing:

  • Amplitude estimation: the same phase-estimation trick generalises to estimate the expected value of any boolean function — the foundation of quantum Monte Carlo integration.
  • Counting hard problems: many problems in #P ask "how many solutions exist?" rather than "does a solution exist?". Quantum counting provides a sub-linear survey for unstructured instances.
  • Database analytics: future quantum databases could answer aggregate COUNT queries in O(N)O(\sqrt{N}) rather than O(N)O(N) time, useful when NN is astronomical.
  • Quantum speedups for optimisation: knowing how many near-optimal solutions exist helps configure the number of Grover iterations needed before committing to a search.

Quantum counting is also a pedagogical bridge: it shows how Grover's search and Shor's algorithm share the same underlying quantum Fourier transform machinery.

Conclusion

Quantum counting distils a deep idea: you do not need to see every item to know how many satisfy a property. By treating the Grover operator as a clock whose hands rotate at a rate set by M/NM/N, phase estimation reads that rate — and with it, the count — in O(N)O(\sqrt{N}) steps.

The result is a provable quadratic advantage over any classical method, sitting comfortably inside BQP while the best classical algorithms require Ω(N)\Omega(N) queries. It is also a reminder that quantum algorithms are most powerful not when they enumerate, but when they interfere — turning global structure into a single, measurable phase.

Explore the related ideas in Grover's search and Shor's factoring algorithm to see how phase and interference thread through the most celebrated quantum speedups.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/quantum-counting/Content licensed under CC BY-NC 4.0.