Checkpoint: Estimate Algorithm Resources

This checkpoint asks you to do what every quantum software engineer eventually must: take an algorithm and a hardware model and produce a concrete resource estimate. You will chain the three skills from this module — counting algorithmic repetitions, converting them to a $T$ -count, and reasoning about the fault-tolerant cost model — into a single end-to-end number.

The estimation pipeline

A fault-tolerant resource estimate flows through four stages, each feeding the next:

\text{problem size} \;\to\; \text{logical operation count} \;\to\; \text{T-count} \;\to\; \text{physical qubits \& runtime}.

This lesson walks the first three stages explicitly for Grover's search and leaves the last as commentary, because the $T$ -count is the number that drives everything below it.

Stage 1 — how many iterations?

Grover over $N = 2^n$ items with one marked entry needs

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

iterations (the result from the Resource Estimation lesson). For $n = 8$ , $N = 256$ , so $\sqrt{N} = 16$ and $k = \lfloor (\pi/4)\cdot 16 \rfloor = \lfloor 12.566\ldots \rfloor = 12$ . The quadratic speedup is already vivid: 12 iterations to search 256 items, versus 128 expected classical probes.

Stage 2 — T-count per iterate

Each Grover iterate is an oracle followed by the diffusion operator, and both are built largely from Toffoli gates (the multi-controlled phase flips). For this estimate we model each iterate as 5 Toffoli gates, and from the Counting T-Gates lesson each Toffoli costs 7 $T$ gates in the Clifford+T set. So

T_{\text{iterate}} = 5 \times 7 = 35.

The Clifford gates ( $H$ , CNOT, $X$ ) in the iterate are free in the fault-tolerant cost model, so they do not enter the headline number.

Stage 3 — total T-count

Multiplying the per-iterate $T$ -count by the number of iterates gives the algorithm's leading $T$ -count:

T_{\text{total}} = k \times T_{\text{iterate}} = 12 \times 35 = 420.

That single number — 420 $T$ gates — is the dominant fault-tolerant cost of this Grover instance, and it is what your solution returns.

Stage 4 — what 420 T gates implies (commentary)

The $T$ -count then drives the physical estimate from the Logical vs Physical lesson:

Magic states. Each $T$ consumes one distilled magic state, so 420 distillations must be scheduled; the distillation factories often dominate the physical qubit budget.
Physical qubits. With $n = 8$ data qubits plus diffusion ancillas encoded at a code distance $d$ chosen so the logical error rate over all $\sim$ 420 $T$ operations stays acceptable, the width is $\approx (\text{logical qubits}) \times 2d^2$ plus factory overhead.
Runtime. $\approx (\text{logical depth}) \times d \times (\text{cycle time})$ .

Each of those follows mechanically once the $T$ -count and the target error budget are fixed — which is exactly why $T$ -count is the number engineers fight to minimise.

Try it

Produce the end-to-end estimate: for an $n = 8$ Grover search, compute the iteration count $k = \lfloor(\pi/4)\sqrt{N}\rfloor$ , multiply by the per-iterate $T$ -count ( $5$ Toffolis $\times\,7$ $T$ each $= 35$ ), and return the total $T$ -count as an integer. The grader checks the value and that it is a whole number.

Run your code to see the quantum state.