Case Study: Designing an Early Fault-Tolerant Algorithm

Executive Summary

The first useful fault-tolerant machines will not have 6,000 logical qubits. They will have perhaps 50 to 200, with logical error rates around $10^{-8}$ — enough for something, but not for the textbook versions of the algorithms.

This creates a distinct design problem that has attracted its own research programme: early fault-tolerant quantum computing (EFTQC), where logical qubits are the scarcest resource and runtime is comparatively cheap. This case study redesigns a chemistry calculation for that regime, and the resulting algorithm looks quite different from either its NISQ or its full-fault-tolerant counterpart.

Skills applied

• Designing under a logical-qubit constraint rather than a depth constraint (§34.7).
• Trading runtime for qubit count.
• Reducing $T$-count as the dominant cost.
• Recognizing how optimal algorithm design shifts with the resource regime.

Phase 1: Three regimes, three different algorithms

The same scientific question — a molecular ground-state energy — yields three different algorithms depending on what is scarce:

VQE is designed for shallow circuits and dies on measurement cost (Chapter 19). Textbook QPE needs $t$ counting qubits plus a large system register plus ancillas — too many logical qubits. The early-FT question is what sits between them.

Phase 2: The constraint

Suppose 100 logical qubits at $10^{-8}$ logical error, with a total circuit budget of $\sim10^{7}$ logical operations before failure becomes likely.

The chemistry problem needs 60 qubits for the system. That leaves 40 for everything else — counting registers, ancillas, and magic-state injection.

Textbook QPE at 10 bits of precision needs 10 counting qubits plus ancillas for the controlled evolution — plausible. But controlled-$U^{2^j}$ for $j$ up to 10 means $2^{10}$ applications of the evolution operator, and each is expensive. The dominant cost is $T$-count, not qubits.

Phase 3: The design moves

Move 1: iterative QPE. Use one counting qubit reused $t$ times with classical feed-forward (Chapter 16), instead of $t$ counting qubits.

• Qubits: 10 → 1
• $U$ applications: unchanged
• Requires: mid-circuit measurement and feed-forward, which fault-tolerant architectures provide natively

Move 2: trade precision for repetitions. Rather than one high-precision run, take many low-precision runs and combine statistically. Bayesian phase estimation extracts more information per circuit than naive bit-by-bit readout, reducing the maximum circuit depth at the cost of more repetitions.

• Max depth: reduced ~4×
• Total runtime: increased ~2×
• Correct trade when qubits and coherence are scarcer than wall-clock

Move 3: qubitization instead of Trotterization. Better asymptotic scaling in the Hamiltonian's 1-norm, with a modest ancilla overhead.

• $T$-count: reduced ~5× for realistic chemistry Hamiltonians
• Ancillas: +$\log(\text{number of terms}) \approx 12$

Move 4: cheaper state preparation. Overlap dominates repetitions (Chapter 16). A matrix-product-state trial preparation improves overlap from ~0.1 to ~0.6, cutting repetitions ~6×, at a cost of ~15 extra qubits and a modest circuit.

Move 5: coarse rotation synthesis. Set rotation precision to the algorithm's error budget rather than machine precision — $\delta = 10^{-6}$ rather than $10^{-15}$ (Chapter 14). At $\sim3\log_2(1/\delta)$ $T$ gates per rotation, that is a 2.5× $T$-count saving for free.

Phase 4: The result

An honest result: the redesign fits the qubit budget comfortably and still exceeds the per-run operation budget by 30×. Total $T$-count went up, because repetitions were traded for depth.

That is the correct trade in this regime and it is not sufficient. Closing the remaining 30× requires either better Hamiltonian factorizations (tensor hypercontraction reduces the 1-norm substantially), a smaller active space, or a machine with a lower logical error rate.

The honest conclusion. Early fault-tolerant chemistry at useful scale is close but not yet within reach of a 100-logical-qubit, $10^{-8}$-error machine. The gap is one to two orders of magnitude in $T$-count — much smaller than the NISQ gap, and plausibly closable by algorithmic work alone.

Phase 5: What generalizes

Four design principles for the early-FT regime:

1. Qubits are scarcer than time. Reuse aggressively; iterative and Bayesian methods beat parallel ones.
2. $T$-count dominates. Every design decision should be evaluated in $T$ gates, not total gates.
3. Repetitions are cheap, depth is expensive. Per-run failure probability rises with depth, so many shallow runs beat one deep run — the opposite of the full-FT regime.
4. Precision should match the error budget. Over-precise rotation synthesis is one of the most common and most wasteful mistakes.

Note that principles 1 and 3 invert between the early-FT and full-FT regimes. An algorithm optimal for one is not optimal for the other, which is why EFTQC is a research programme rather than a subset of existing work.

Phase 6: Why this matters now

Early fault-tolerant machines are plausibly 5–12 years away — much sooner than the 6,000-logical-qubit machines that headline resource estimates describe. Algorithms designed for that regime determine whether those first machines do anything useful.

This is also where the highest-leverage work sits. As Chapter 15 showed, resource estimates fell ~50× from algorithmic advances with no hardware improvement. The early-FT regime is comparatively unexplored, so the remaining headroom is likely larger there than in the well-optimized full-FT algorithms.

The practical implication: if you are entering the field now, algorithm design for 50–200 logical qubits is a better-leveraged place to work than either NISQ heuristics or asymptotic full-FT analysis.

Discussion Questions

1. Total $T$-count rose while the design improved. Explain why that is the right trade here and wrong in the full-FT regime.
2. Principles 1 and 3 invert between regimes. What does that imply about porting algorithms between them?
3. The remaining gap is 30× in $T$-count. Which of the closing strategies would you pursue first?
4. Early-FT machines arrive before full-FT ones. Does that change which applications come first?

Your Turn: Extensions

• Estimate logical qubits and $T$-count for a 30-orbital active space under both textbook and early-FT designs.
• Compare Trotterization against qubitization $T$-counts for a Hamiltonian you construct.
• Compute the $T$ savings from relaxing rotation synthesis from $10^{-15}$ to $10^{-6}$.
• Read an EFTQC paper and identify which of the four principles it applies.

Key Takeaways

• Early fault tolerance — 50–200 logical qubits at $10^{-8}$ error — is a distinct design regime, not a waypoint between NISQ and full fault tolerance.
• Logical qubits are the scarce resource, so iterative and Bayesian methods that reuse qubits beat parallel ones.
• $T$-count is the cost metric; repetitions are cheap and depth is expensive, inverting the full-FT trade.
• The redesigned chemistry calculation fits the qubit budget but still exceeds the operation budget by ~30× — close, and not yet sufficient.
• Early-FT algorithm design is comparatively unexplored and therefore high-leverage, since algorithmic advances have historically moved resource estimates more than hardware has.