Resource Estimation

Before committing months of effort to a quantum algorithm, you want an answer to a blunt question: how big and how long? Resource estimation produces that answer — a count of qubits, gates, circuit depth, and (under a fault-tolerant model) physical resources and runtime. It is the quantum analogue of complexity analysis, but with constants that matter, because a factor of ten can be the difference between "runs tonight" and "runs in a decade".

Two regimes of estimate

A resource estimate lives in one of two regimes:

Asymptotic. Big- $O$ scaling: Grover searches $N$ items with $O(\sqrt{N})$ queries; Shor factors an $L$ -bit number with $O(L^3)$ gates. This tells you whether an algorithm is worthwhile but hides constants.
Concrete. Exact counts for a specific instance and a specific gate set: "factoring a 2048-bit RSA key needs roughly 6700 logical qubits and $2.7\times 10^9$ Toffoli gates" (illustrative figures from the literature). This is what you submit to a hardware budget.

This lesson works the concrete count for the cleanest example: Grover's search.

Counting Grover's iterations

Grover's algorithm searches an unstructured database of $N = 2^n$ items, with one marked item, by repeating a two-step Grover iterate: apply the oracle (which flips the phase of the marked state) then the diffusion operator (which reflects about the mean). Each iterate rotates the state vector by a fixed angle $\theta$ in the two-dimensional plane spanned by the marked and unmarked states, where

\sin\theta = \frac{1}{\sqrt{N}}, \qquad \theta \approx \frac{1}{\sqrt{N}} \text{ for large } N.

Starting from the uniform superposition (already at angle $\theta/2$ from the unmarked axis), we want to rotate as close as possible to the marked axis at $\pi/2$ . The optimal number of iterations is

k = \left\lfloor \frac{\pi}{4}\sqrt{N} \right\rfloor.

This is the famous quadratic speedup: $O(\sqrt{N})$ oracle calls instead of the classical $O(N)$ .

Qubits, gates, and depth

A complete Grover estimate has three numbers:

Width (qubits). $n$ data qubits to index $N = 2^n$ items, plus any ancillas the oracle and a multi-controlled diffusion phase need. The diffusion operator's $n$ -controlled $Z$ uses on the order of $n$ ancillas when decomposed into Toffoli gates.
Gate count. Each iterate costs (oracle gates) + (diffusion gates), and there are $k$ iterates, so the leading term is $k \times (\text{cost per iterate})$ . Because $k \sim \sqrt{N}$ , the total gate count scales as $\sqrt{N}$ times a per-iterate polynomial in $n$ .
Depth. Roughly the gate count divided by how much parallelism the iterate allows; for the serial multi-controlled gates inside diffusion, depth and gate count scale similarly.

Why the floor, and why it can be off by one

The exact optimum is a real number $(\pi/4)\sqrt{N} - 1/2$ ; rounding to the nearest integer maximises success probability. Using the floor of $(\pi/4)\sqrt{N}$ is the standard, slightly conservative choice and is exact when $N$ is large. The residual angle error means Grover's success probability is very close to but not exactly 1 — a subtlety a good resource estimate notes rather than hides.

Try it

Compute the optimal Grover iteration count for an $n = 10$ qubit search ( $N = 2^{10} = 1024$ items, one marked) and return it as an integer. The grader checks the value and that it is a whole number.

Run your code to see the quantum state.