Project: Resource Estimate a Real Algorithm

Before anyone runs a "real" algorithm on hardware, they estimate its resources: how many physical qubits, how many cycles, how long it runs once you account for error correction. This capstone performs the central fault-tolerant calculation — turning a logical-qubit count and a target error rate into a physical-qubit budget — the kind of estimate behind headline results like factoring RSA-2048.

Why logical qubits are expensive

A fault-tolerant algorithm is written in logical qubits, but each logical qubit is encoded in a patch of many physical qubits running a quantum error-correcting code. The dominant code today is the surface code, whose logical error rate falls exponentially with the code distance $d$:

where $p$ is the physical error rate and $p_{\text{th}} \approx 1\%$ is the threshold. You pick $d$ large enough that $p_L$ times the total number of logical operations stays below your tolerated failure probability.

The qubit budget

A planar surface-code patch at distance $d$ uses roughly

physical qubits (data plus measurement ancillas). For an algorithm needing $Q$ logical qubits the data block costs

With $Q = 100$ logical qubits at $d = 15$:

What this leaves out

A full estimate adds two more terms. Magic-state factories distill the non-Clifford ($T$) states the algorithm consumes; for $T$-heavy circuits these can dominate the footprint. Runtime is set by the surface-code cycle time multiplied by the algorithm's logical depth — and the depth is inflated by $d$ rounds of syndrome extraction per logical step. Gidney & Ekerå's RSA-2048 estimate ($\sim$20 million physical qubits, $\sim$8 hours) is exactly this calculation carried out end-to-end on Shor's algorithm.

Try it

Implement physicalQubits(logicalQubits, d) returning the data-block footprint $Q \cdot 2d^2$. The grader checks you return $45{,}000$ for $Q = 100$, $d = 15$.

Sign in on the full site to ask questions and join the discussion.