Quantum Counting

Fix a Boolean function $f : \{0,1\}^n \to \{0,1\}$ with oracle access via a phase oracle $O_f$, and let $M = |\{x : f(x) = 1\}|$ be the number of solutions among $N = 2^n$ items. Quantum Counting estimates $M$ (equivalently, the fraction $M/N$) to some target accuracy, using a number of oracle queries that scales like $\sqrt{N}$ rather than $N$. The construction leans entirely on the structure exposed in amplitude amplification. Define the uniform superposition state $|s\rangle = \frac{1}{\sqrt{N}}\sum_x |x\rangle$, decomposed as

where $|\text{good}\rangle$ is the uniform superposition over solutions and $|\text{bad}\rangle$ the uniform superposition over non-solutions. The Grover iterate $G = (2|s\rangle\langle s| - I)\, O_f$ acts within the two-dimensional real subspace $\mathrm{span}\{|\text{good}\rangle, |\text{bad}\rangle\}$ as a rotation by angle $2\theta$. Its eigenvalues on that subspace are $e^{\pm i 2\theta}$, with eigenvectors that are complex combinations of $|\text{good}\rangle$ and $|\text{bad}\rangle$. Quantum Phase Estimation, applied with $|s\rangle$ as input and $G$ as the unitary whose phase we estimate, returns (with high probability) an estimate $\hat\varphi$ of one of the two eigenphases $\varphi = \theta/\pi$ or $1-\theta/\pi$ (normalized to $[0,1)$), because $|s\rangle$ is an equal-weight superposition of the two eigenvectors of $G$ that live in the invariant subspace. Converting $\hat\varphi$ back to an angle $\hat\theta = \pi\hat\varphi$ and then computing $\hat M = N\sin^2\hat\theta$ produces the count estimate. This is the entire idea: rotation angle in, solution count out.

Step 1 — Set up the rotation. Build the Grover iterate $G = (2|s\rangle\langle s| - I) O_f$ exactly as in amplitude amplification, using $n$ "index" qubits initialized to $|s\rangle = H^{\otimes n}|0\rangle^{\otimes n}$.

Step 2 — Phase-estimate $G$. Attach $t$ ancilla "counting" qubits initialized to $|0\rangle^{\otimes t}$. Apply Hadamards to all $t$ ancillas, then apply controlled powers $G^{2^j}$ controlled on ancilla qubit $j$ (the standard phase estimation circuit), then apply the inverse quantum Fourier transform $\mathrm{QFT}_t^\dagger$ on the ancillas, then measure them in the computational basis to get an integer $y \in \{0, \dots, 2^t - 1\}$.

Step 3 — Convert to an angle. Compute $\hat\varphi = y / 2^t$, which estimates the eigenphase $\varphi$ of $G$ (in units of $2\pi$), and set $\hat\theta = \pi \hat\varphi$.

Step 4 — Convert to a count. Output $\hat M = N \sin^2 \hat\theta$, rounded to the nearest integer (or reported as an interval, since $\hat M$ is naturally an estimate rather than an exact value). ``` Algorithm QuantumCounting(oracle O_f, n, t):

# n = number of index qubits (search space size N = 2^n)

# t = number of precision qubits for phase estimation

# 1. Prepare index register in uniform superposition |s> index_register <- |0>^n apply H^{\otimes n} to index_register # now |s> = (1/sqrt(N)) sum_x |x>

# 2. Prepare counting register counting_register <- |0>^t apply H^{\otimes t} to counting_register

# 3. Build Grover iterate G = (2|s> -> (-1)^{f(x)} |x> apply H^{\otimes n} apply conditional phase flip on |0...0> (flip all states except |0...0>) apply H^{\otimes n}

# net effect: G = (2|s>

# 4. Controlled powers of G (phase estimation core) for j in 0 .. t-1: apply controlled-G^{2^j}, control = counting_register[j], target = index_register

# 5. Inverse QFT on counting register apply QFT_t^{\dagger} to counting_register

# 6. Measure counting register y <- measure(counting_register) # y in {0, ..., 2^t - 1}

# 7. Post-process phi_hat <- y / 2^t theta_hat <- pi phi_hat M_hat <- N sin(theta_hat)^2 return round(M_hat) ``` The controlled-$G^{2^j}$ blocks are the expensive part: implementing $G^{2^j}$ costs $2^j$ calls to $O_f$ (and $2^j$ reflections), so the total oracle query count across all $t$ rounds is $\sum_{j=0}^{t-1} 2^j = 2^t - 1$, i.e. $O(2^t)$ queries, all executed coherently inside superposition.

Correctness — why the eigenphase encodes $\theta$. Work in the two-dimensional real subspace $V = \mathrm{span}\{|\text{good}\rangle, |\text{bad}\rangle\}$, which is invariant under $G$. Choosing the orthonormal basis $|\text{good}\rangle, |\text{bad}\rangle$, the oracle $O_f$ acts as reflection through $|\text{bad}\rangle$ (flipping the sign of the good component), and $2|s\rangle\langle s| - I$ acts as reflection through $|s\rangle$. A composition of two reflections in a plane is a rotation, and the standard computation (identical to the one justifying Grover's algorithm) shows

a rotation by angle $2\theta$ where $\sin^2\theta = M/N$. This real rotation matrix has complex eigenvalues $e^{\pm i2\theta}$ with eigenvectors

and crucially $|s\rangle = \sin\theta|\text{good}\rangle + \cos\theta|\text{bad}\rangle$ is an equal-magnitude superposition of $|\psi_+\rangle$ and $|\psi_-\rangle$ (one checks $|s\rangle = \frac{e^{i\alpha}}{\sqrt2}|\psi_+\rangle + \frac{e^{-i\alpha}}{\sqrt2}|\psi_-\rangle$ for a phase $\alpha$ depending on $\theta$). Standard phase estimation theory says: feeding an eigenvector $|\psi\rangle$ of $G$ with eigenvalue $e^{2\pi i \varphi}$ into the phase estimation circuit yields, upon measurement, an estimate of $\varphi$ concentrated near the true value, exactly (with $t$ qubits, if $\varphi$ has a $t$-bit binary expansion) or with high probability otherwise (Nielsen & Chuang's phase estimation error bound). Since $|s\rangle$ is a superposition of only the two eigenvectors $|\psi_\pm\rangle$ with phases $\pm\theta/\pi \pmod 1$, the measured output $y$ concentrates near $y \approx 2^t\theta/\pi$ or $y \approx 2^t(1 - \theta/\pi)$, and both give the same $\sin^2$ value:

because $\sin(\pi - \theta) = \sin\theta$. This symmetry is precisely why the algorithm is well-defined despite the two-fold eigenphase ambiguity — the final count formula is insensitive to which of the two eigenphases was measured.

Precision analysis. With $t$ counting qubits, standard phase estimation guarantees that the measured $\hat\varphi = y/2^t$ satisfies

with probability at least $1 - \delta$ when a small number of extra qubits ($O(\log(1/\delta))$) are added beyond the target precision — or, more simply, the standard result:

for integer $k \ge 1$ (Nielsen–Chuang phase estimation bound). Taking $t = n_{\text{prec}} + \lceil \log_2(2 + 1/(2\delta))\rceil$ counting qubits gives $|\hat\varphi - \varphi| \le 2^{-n_{\text{prec}}}$ with probability $\ge 1-\delta$. Propagating this to the count estimate: since $M = N\sin^2(\pi\varphi)$, differentiating,

so an angle error $\Delta\varphi \approx 2^{-t}$ translates to a count error of at most roughly $N\pi \cdot 2^{-t}$ in the worst case, but importantly this bound is loose near $\varphi = 0, 1/2$ where the derivative is small (good, small relative error there) and tight near $\varphi = 1/4$ i.e. $M/N = 1/2$ (worst case, near half the items are solutions). A more careful multiplicative analysis shows that to estimate $M$ to additive accuracy $\epsilon N$ with constant probability, it suffices to take $t = O(\log(N/\epsilon))$ — more precisely $t \approx \log_2(1/\epsilon)$ suffices when $M \ll N$, and the standard tight statement is: > To estimate $M$ with additive error at most $\epsilon N$ (with probability $\ge 2/3$, boostable by repetition), $t = O(\log(1/\epsilon))$ counting qubits suffice.

Query complexity. The dominant cost is the controlled powers of $G$: the sum of oracle calls across all $t$ rounds of phase estimation is

using $O_f$ once per application of $G$. Combined with $N = 2^n$ index qubits, the total number of elementary oracle queries needed to reach additive count accuracy $\epsilon N$ is $O(1/\epsilon)$ — independent of $N$ in this normalized form, or equivalently $O(\sqrt{N}/\sqrt{\text{something}})$ when expressed relative to the classical sampling baseline below.

Classical comparison. Classically, to estimate $M/N$ to additive accuracy $\epsilon$ via random sampling requires $\Theta(1/\epsilon^2)$ samples (Chernoff bound for a Bernoulli estimator with success probability $M/N$). Quantum Counting achieves the same additive accuracy $\epsilon$ using $O(1/\epsilon)$ oracle queries — a quadratic speedup in the accuracy parameter, matching the general lower bound for amplitude estimation, which is provably optimal: no quantum algorithm can beat $\Omega(1/\epsilon)$ queries for this task (a consequence of the quantum query lower bound for amplitude estimation, related to the Amplitude Amplification optimality argument).

Space complexity. The algorithm uses $n$ index qubits plus $t = O(\log(1/\epsilon))$ ancilla qubits, so total space is $O(n + \log(1/\epsilon))$ qubits — modest, since no extra working memory beyond the oracle's own workspace and the counting register is required.

Honest tradeoffs. The speedup is in query complexity, not necessarily wall-clock time if the oracle itself is expensive to control coherently to high powers; implementing $G^{2^j}$ typically requires $2^j$ sequential (or parallel-with-ancilla) applications of $O_f$, so circuit depth still scales with $2^t$, meaning very high precision is costly in depth even though the qubit count stays low. Additionally, the estimate degrades in reliability of interpretation — not accuracy — when $M$ is very close to $0$ or $N$, discussed next.

Take $n = 4$, so $N = 16$ items, and suppose $f$ marks $M = 4$ of them (so $\sin^2\theta = 4/16 = 1/4$, giving $\theta = \pi/6$ radians, i.e. $30°$). We phase-estimate $G$ using $t = 4$ counting qubits. The true eigenphase is $\varphi = \theta/\pi = 1/6 \approx 0.16667$, so on a $4$-qubit counting register ($2^4 = 16$ levels) the ideal (real-valued) target is $y^\star = 16 \times 0.16667 \approx 2.667$. Since $2.667$ is not an integer, phase estimation cannot return it exactly; measurement will concentrate probability mass on the two nearest integers, $y = 2$ and $y = 3$, with smaller tails elsewhere.

Two features are visible and both are expected from the theory above. First, $y=2$ and $y=3$ dominate (they bracket the true non-integer target $2.667$), and rounding either $2.34$ or $5.35$ to the nearest integer near the true $M=4$ shows the estimate is in the right ballpark but not exact with only $t=4$ qubits — this is the ordinary phase-estimation discretization error, shrinking as $t$ grows. Second, $y = 13$ and $y = 14$ (i.e. $16 - y$ for the dominant outcomes) give identical $\hat M$ values to $y=3$ and $y=2$ respectively, exactly as predicted by the $\sin(\pi - \theta) = \sin\theta$ symmetry — confirming the algorithm's output is well-defined regardless of which of the two mirrored eigenphases gets measured. Repeating the entire circuit (fresh oracle queries each time) and taking a median or mode of several $\hat M$ values, plus increasing $t$, concentrates the estimate around the true value $M=4$; with $t = 8$ counting qubits the achievable resolution in $\hat M$ near $M/N=0.25$ shrinks to roughly $\pm 0.3$, and with $t=10$ to roughly $\pm 0.08$, illustrating the $O(2^{-t})$ angle-resolution to $O(N \cdot 2^{-t})$-ish count-resolution scaling derived above (exact factor depends on local slope of $\sin^2$).

Quantum Counting was introduced as a direct extension of Grover's algorithm once amplitude amplification's rotation-picture was understood, formalized together with the broader technique of amplitude estimation.

Quantum Counting is the standard tool whenever an algorithm needs to know $M$, the number of marked items, before running amplitude amplification optimally — since the ideal number of Grover iterations is $\Theta(\sqrt{N/M})$, and this quantity is otherwise unknown when $M$ is not given in advance. It converts "search when you don't know how many targets exist" into a two-stage pipeline: count first, then amplify with the now-known optimal iteration count. Beyond search, quantum counting is the ancestor of quantum amplitude estimation, which replaced binary "marked/unmarked" oracles with real-valued payoff oracles and became the leading quantum-advantage proposal for Monte Carlo pricing and risk estimation in computational finance, since option-pricing expectations are estimated with the same quadratic speedup in the number of oracle calls. It is also directly applicable to approximate model counting in formal verification and combinatorics — estimating the number of satisfying assignments of a Boolean formula — and to collision counting in cryptanalysis, where estimating how many colliding pairs exist in a hash-like function informs attack feasibility without exhaustively enumerating collisions. The technique also serves as a pedagogical bridge: because it composes exactly two previously-understood primitives, Amplitude Amplification and Quantum Phase Estimation, it is frequently the first "compositional" algorithm students see, illustrating how quantum primitives combine like ordinary subroutines while their error and cost analyses must be recombined carefully, a lesson reused throughout more advanced quantum algorithms built on Grover's Algorithm and its many generalizations.

Ask the tutor: How does the error in the count estimate change if I fix the number of counting qubits t but vary M from near 0 to near N/2?