Resource Estimation for Fault-Tolerant Algorithms

Write the logical workload before the machine#

Define logical data and ancilla patches, operation counts by class, dependency depth, measurement and feed-forward steps, output success criterion, and total allowed algorithm failure. A thousand logical qubits used for a shallow Clifford workload is not the same request as a hundred logical qubits fed by billions of non-Clifford operations. Resource research repeatedly shows that code, factories, routing, workload, and failure target all matter [fault-tolerant roadmaps] [surface-code analysis].

The input schema distinguishes counts from schedules. Logical operation count estimates throughput demand; logical-cycle depth estimates elapsed protected time. A versioned SDK export may populate these fields, but the implementation and execution metadata must remain attached [Qiskit documentation].

Decompose the workload far enough to expose bottlenecks: Clifford layers, arbitrary rotations, T or Toffoli consumption, measurements, resets, classical reactions, and concurrent logical width. A total gate count cannot reveal whether one factory is starved by a burst of magic-state demand or mostly idle. Retain the dependency graph or a schedule summary that states maximum and average consumption per cycle.

Logical qubit count also needs a lifetime. Data patches may persist for the whole algorithm; temporary ancillas, routing patches, and factory buffers do not. Report peak patches, average patch-cycles, and the schedule that produces the peak. Multiplying peak width by total depth is a safe upper-bound ledger, not an automatically achievable space-time optimum.

Allocate failure probability across cycles#

If the workload lasts C relevant logical cycles and total allowed failure is ε, a conservative union-bound teaching target is $p_L\le\epsilon/C$ per cycle. The inequality labels an allocation, not an exact independence model. Different operation classes may receive different budgets; correlated failures can invalidate a naive sum.

For C=10⁹ and ε=10⁻², the teaching target is 10⁻¹¹ per declared cycle. Write “per syndrome cycle” or “per logical operation”; never leave the denominator implicit.

A complete budget has rows. Data-memory faults, logical operations, magic-state production, state injection, measurement, decoding failure, and classical-control failure can receive separate allocations whose sum does not exceed ε under the union bound. Moving budget from one row to another can change different code distances or factory protocols. Publish both the allocation rule and unused reserve.

The union bound does not require independent failures, but it can be loose. If an estimator instead uses $1-(1-p_L)^C$, it has introduced an independence and stationarity model. At small $Cp_L$, the two are close; near the budget boundary, the difference can matter. Name which relation selected distance and keep the alternative as a sensitivity case rather than blending them.

Solve distance in the companion model#

The companion model uses a named illustrative relation $p_L=A(p_{phys}/p_{th})^{(d+1)/2}$. Search odd distances until the allocated target is met. Suppression is conditional on the below-threshold error model; threshold is not a universal material constant [surface-code analysis] [Google Quantum AI below-threshold experiment].

Distance changes discretely. A small change in p_phys or ε can move d by two and physical area roughly with d². Report the grid, not only the most flattering cell.

Taking logarithms explains the search. With $r=p_{phys}/p_{th}<1$, the condition is $(d+1)/2\ge \log((\epsilon/C)/A)/\log r$; because $\log r<0$, the inequality reverses during division. Round upward to an integer exponent, translate to odd d, and then verify the original equation. Direct verification catches boundary and floating-point mistakes.

For the baseline values $p_{phys}=10^{-3}$, $p_{th}=10^{-2}$, $A=0.1$, and target $10^{-11}$, $d=19$ gives exactly $10^{-11}$ and therefore passes the declared inclusive comparison. The fixture parses the decimal inputs exactly and asserts this boundary. A float-only implementation can round the candidate infinitesimally above the target and incorrectly select $d=21$; this is why the record publishes comparison policy and witness cells.

Four independent perturbations have distinct effects. Doubling C halves the per-cycle budget; tightening ε does the same without changing runtime depth; improving p_phys changes the exponential base; changing A shifts the model normalization. Each can move d across a discrete boundary. A useful sensitivity report varies one while freezing the other three, then records why each distance step occurred.

Turn patches into qubits and cycles into seconds#

Under the companion geometry, $Q_{phys}=2Pd^2$ for P logical patches. This counts data and syndrome qubits in a simplified patch factor. Runtime is $T=Ct_{cycle}$ only if decoding and feed-forward sustain that cycle. Decoder latency belongs in seconds and must close the reaction deadline.

Detailed factoring estimates illustrate how physical-qubit and runtime conclusions move with factory and architectural assumptions [Gidney and Ekerå]. The calculation is useful because it is specific, not because its headline transfers to every architecture.

The formula $2Pd^2$ is a geometry convention. It does not include a chip’s disabled sites, couplers, readout resonators, communication links, or fabrication yield. Keep “physical code qubits” as its unit. Converting that count into packaged devices or cryostat footprint requires another architecture model and another evidence ledger.

Runtime branches at the schedule. If one logical layer consumes d syndrome cycles and measurement feed-forward takes additional cycles, C must already include them before multiplying by $t_{cycle}$. A 1 μs cycle over $10^9$ cycles gives 1,000 seconds of scheduled code time. Queueing, checkpointing, calibration, factory warm-up, and retries are separate wall-time terms, not hidden multipliers.

Decoder throughput imposes a stability condition: each round’s syndrome work must be processed quickly enough that the backlog does not grow without bound. Average throughput is insufficient when bursts exceed buffer capacity or a logical measurement needs a decision by a fixed reaction deadline. Report decoder latency percentiles, input bits per cycle, parallelism, and the deadline used by the logical schedule.

from decimal import Decimal
def decimal(value):
    return value if isinstance(value, Decimal) else Decimal(str(value))
def logical_error(p_phys, distance, threshold="0.01", prefactor="0.1"):
    p_phys, threshold, prefactor = map(decimal, (p_phys, threshold, prefactor))
    assert distance > 0 and distance % 2 == 1 and 0 < p_phys < threshold
    return prefactor * (p_phys/threshold) ** ((distance+1)//2)
def minimum_distance(p_phys, cycles, budget):
    target = decimal(budget)/decimal(cycles)
    for distance in range(1, 100, 2):
        if logical_error(p_phys, distance) <= target: return distance
    raise ValueError("distance search exhausted")
cells=[]
for p in ("0.001", "0.0005", "0.002"):
    d=minimum_distance(p, 10**9, "0.01")
    cells.append((p,d,2*100*d*d))
nominal_distance=minimum_distance("0.001", 10**9, "0.01")
worse_distance=minimum_distance("0.002", 10**9, "0.01")
assert logical_error("0.001", 19) == Decimal("1e-11")
assert nominal_distance == 19
assert [d for _,d,_ in cells] == [19,15,29]
assert all(d%2 for _,d,_ in cells) and worse_distance > nominal_distance
print(f"PASS: 43 resource estimate nominal_d={nominal_distance} worse_d={worse_distance} physical_qubits={[qubits for _,_,qubits in cells]}")

Factories, routing, and idle space are not free#

The patch model omits magic-state factory throughput and footprint, routing corridors, lattice-surgery scheduling, boundary effects, idle patches, spare capacity, injection failures, decoder compute, classical wiring, and manufacturing yield. A detailed factoring estimate shows how factories, schedules, decoding assumptions, and hardware timing couple to the algorithm [Gidney and Ekerå]. List each omission with direction: factory demand usually increases space and time; parallel factories trade space for time.

Model a factory with output interval $\tau_f$ cycles, accepted-state probability, footprint in patches, and required input fidelity. If the scheduled algorithm consumes T states faster than one factory supplies them, runtime stretches or parallel factory count rises. The buffer needed for bursty consumption occupies patches too. A single total T count cannot choose between these designs; the time profile is required.

Distillation can be recursive. Output error and acceptance at one level determine how many lower-level states and factories feed the next. Round every factory count upward, include failed attempts, and show the protocol boundary. Quoting a magic-state error without its production rate and footprint leaves the dominant resource path unaccounted.

Routing is likewise a schedule constraint, not a percentage surcharge. Moving or lattice-surgery operations occupy corridors and can block otherwise parallel interactions. An estimator should either schedule those conflicts or label routing as omitted. Adding twenty percent to patch count may be a scenario, but it is not a substitute for geometry.

A sensitivity surface, not a headline point#

Vary physical error, threshold/prefactor model, total budget, logical cycles, patches, factory policy, cycle seconds, and decoder deadline independently. Preserve input JSON, generated CSV, units, code revision, and warnings. Explain every step in d. False precision appears when an analyst reports seven-digit qubit counts from one-digit assumptions.

Use scenarios rather than probability distributions when inputs are not empirically characterized. A “hopeful,” “reference,” and “stress” row can make correlations explicit: an improved physical error rate may arrive with a slower gate, or a faster cycle may worsen control error. Cartesian grids are useful for local sensitivity, but their cells are not equally likely futures.

For every discontinuous distance change, print the previous distance’s logical error, the new distance’s logical error, and the target. For every factory-count jump, print demand rate and capacity on each side. These witness values turn a step plot from a mysterious cliff into an auditable integer decision.

Cross-check at three levels. Unit tests verify formulas and monotonicity. An independent spreadsheet or short script recomputes sampled cells. A domain review checks whether the workload, architecture, and failure categories correspond to the intended computation. Agreement at the arithmetic level cannot repair an omitted factory or a mismatched logical-operation denominator.

The six-cell exercise should expose at least four independent levers. Holding C, ε, A, and pth fixed while improving pphys changes the exponential ratio. Holding the error model fixed while tightening ε changes only the target. Changing cycle seconds moves wall time without changing distance. Changing P moves the simplified patch count without changing pL. If one code path changes several outputs at once, the fixture should explain the causal dependency rather than celebrate “sensitivity.”

Discontinuous distance selection deserves integer-safe arithmetic or a documented comparison tolerance. In the baseline decimal example, the mathematical boundary may land exactly on the target while binary floating-point evaluates infinitesimally above it. A robust implementation evaluates logarithms with a conservative policy or verifies candidate distances at controlled precision. The record must not silently spend two extra distance units because of representation error.

That numerical detail matters physically: moving d from 19 to 21 increases the simplified $2Pd^2$ count for P=100 from 72,200 to 88,200 code qubits, a 22 percent jump. The model uncertainty may dwarf floating error, but the implementation still needs a deterministic boundary rule. Scientific humility is not an excuse for avoidable arithmetic ambiguity.

End with a reconciliation table. One row carries peak physical code qubits, one patch-cycles, one factory footprint and output interval, one decoder throughput and deadline, and one scheduled wall time. Each value points to inputs and omitted costs. A reader can then change a workload or architecture assumption without reverse-engineering a headline number.

The estimator should reject nonphysical or structurally invalid inputs before search: nonpositive cycles or patches, budget outside (0,1), physical error at or above the model threshold, even or nonpositive candidate distance, and missing time units. An exhausted distance search is not evidence that the largest tried code works; it is an explicit failure to meet the target within the declared domain.

Preserve the exact input decimals as strings or controlled-precision values in the run record. Binary floats are fine for much of the grid, but boundary decisions need reproducible parsing and comparison. The generated CSV should include the raw ratio, exponent, pL, target, acceptance boolean, and software revision for every selected or rejected distance witness.