Thesis
Shor's algorithm for 2048-bit RSA demands 10⁶–10⁸ physical qubits and billions of T-gate cycles when naively mapped to surface codes — a regime physical qubit count alone cannot unlock. The decisive bottleneck is the full fault-tolerant software stack: codes that exponentially suppress logical error with distance, magic-state factories that produce the non-Clifford gates universal circuits need, real-time decoders that keep up with sub-microsecond syndrome cycles, and compilers that translate high-level quantum programs into hardware-native fault-tolerant sequences. Recent milestones — Google Willow's sub-threshold operation, IBM's Gross code (10× overhead reduction over surface codes), Gidney et al.'s magic-state cultivation (~CNOT-cost T states), Higgott–Gidney Sparse Blossom decoders, and Quantinuum's Guppy/Selene/Helios stack — collectively compress the practical threshold for cryptographically-relevant quantum computation by orders of magnitude. Without these advances, raw qubit count is necessary but wholly insufficient.
Scoring
Compresses physical qubit estimates by 10²–10³× and enables every algorithm above ~10³ logical-qubit-depth. Vulnerable to the post-quantum-crypto pivot if NIST PQC rollout outpaces FTQC. Strongest concrete engineering momentum across Google, IBM, Microsoft, Quantinuum.
Open problems
- ·Real-time decoders for general QLDPC codes (MWPM is surface-code only).
- ·Magic-state cultivation/distillation adapted to non-planar QLDPC geometries.
- ·Topological qubit reproducibility and scale-up beyond 8-qubit demos.
- ·NP-hard scheduling of T gates and lattice-surgery patches; current compilers leave 2–10× overhead.
- ·ASIC/FPGA decoder co-processors with I/O bandwidth for >10⁶ physical qubits.
- ·Threshold analysis under realistic correlated noise (crosstalk, leakage, cosmic rays).
Demo · pre-computed on the Selene emulator
Fault-tolerant resource estimates
| Algorithm | Logical qubits | T-count | Reference |
|---|---|---|---|
| Shor factor RSA-2048 | 6,189 | 1.4e+10 | Gidney & Ekerå 2021 |
| Regev factor RSA-2048 (space-efficient variant) | 1,730 | 1.0e+10 | Ragavan-Vaikuntanathan 2024 |
| QSVT Hamiltonian sim (50-spin FeMoco) | 4,000 | 1.0e+10 | Lee et al. 2021 |
| QTDA Betti numbers (n=30 simplicial complex) | 60 | 1.0e+9 | McArdle et al. 2022 |
| HHL 1024x1024 sparse solve | 25 | 5.0e+8 | Childs-Kothari-Somma 2017 |
Order-of-magnitude estimates; conventions vary by paper. The QEC + compilation stack is the lever that turns these from impossible to merely large.
Key papers (8)
arXiv:2408.13687Willow demonstrates exponential suppression of logical error from d=3 to d=7 — first empirical confirmation of sub-threshold superconducting operation.
arXiv:1808.02892Canonical space-time trade-off framework for surface-code FTQC; T-factories shown to dominate Shor's circuit volume.
arXiv:2308.07915The Gross code [[144,12,12]]: 12 logical qubits at distance 12 on 288 physical qubits — ~10× overhead reduction vs surface codes.
arXiv:2409.17595Distillation-free magic state preparation at ~100 physical qubit-rounds per T state — 3–5× cheaper than the best prior factories.
arXiv:2303.15933MWPM decoder fast enough for real-time surface-code decoding at superconducting syndrome rates; ships in PyMatching v2.
arXiv:2401.09549Substrate behind Majorana 1: topological qubit parity readout via Majorana interferometry — hardware-level error protection.
arXiv:2510.12582Production type-safe, fault-tolerant compilation DSL with mid-circuit measurement and classical control. Powers the demos in this app.
arXiv:2510.11420The 'LLVM moment' for quantum compilation: hierarchical IR with linearity types, interoperating with OpenQASM3 and QIR.