Fault-Tolerant Quantum Utility — Practically Useful Algorithms Beyond Classical Simulation

Foundational quantum algorithms establish that sufficiently capable quantum computers can offer asymptotic speedups for specified computational problems. Shor's 1994 algorithm gives polynomial-time quantum algorithms for integer factorisation and discrete logarithms; Grover's 1996 algorithm gives a quadratic query-complexity improvement for unstructured search; and Harrow, Hassidim and Lloyd's 2009 algorithm gives an exponential improvement in system size for preparing a state proportional to the solution of a sparse, well-conditioned linear system under restrictive input, conditioning and output assumptions. These are theoretical algorithmic results, not demonstrations of practical utility on fault-tolerant hardware, and their real-world advantage depends on end-to-end resource and data-access costs.

Kim et al. report accurate expectation values from a noisy 127-qubit superconducting processor at circuit volumes beyond brute-force classical computation and in regimes where the particular classical approximations tested in the paper break down. The result was presented as evidence for pre-fault-tolerant quantum utility, not as a general proof that classical simulation could not match the calculation. Subsequent tensor-network work, including Tindall et al., reproduced the relevant regime classically with greater accuracy, demonstrating that the classical comparison boundary was not settled by the original experiment. This evidence is contextual to the present fault-tolerant claim: it shows why 'beyond classical simulation' must be tested against evolving best classical methods.

Error-correction results tracked in FR-QE-0003 and FR-QE-0004 demonstrate material progress in the substrate required for fault-tolerant computation. Google's Willow work demonstrates below-threshold surface-code memories with logical error suppression as code distance increases, while Microsoft and Quantinuum reported four logical qubits with substantial circuit-level error suppression on trapped-ion hardware in 2024. These results do not establish a generic logical error rate below 10^-4 per gate, do not justify a general hundreds-to-thousands-of-gates executable-depth threshold, and do not demonstrate a practically useful fault-tolerant algorithm beyond classical simulation. They support the engineering path while leaving this record's application threshold unsatisfied.

Lee et al. provide a concrete fault-tolerant resource estimate for quantum simulation of the FeMoco active space using tensor hypercontraction. Their 2020 preprint, published in 2021, estimates 2,142 logical qubits and approximately 5.3×10^9 Toffoli gates for a representative calculation; under a specified surface-code architecture and physical-error assumptions, the analysis gives a representative implementation using roughly four million physical qubits and a runtime of days. The result is an architecture- and algorithm-dependent resource estimate, not a generic 1,000–4,000-logical-qubit threshold, and 10^-3 is a physical-error assumption rather than a claimed logical-gate error requirement. It nevertheless quantifies the large gap between small-scale logical demonstrations and a prominent candidate application.

The classical comparison boundary relevant to quantum utility can move materially after a quantum result is published. The 2023 IBM kicked-Ising experiment provides a directly documented example: the original work identified a regime beyond brute-force computation and beyond the classical approximations it tested, while subsequent tensor-network work reproduced the relevant calculations classically with improved accuracy. This does not establish that every proposed chemistry or materials target will become classically tractable. It establishes the narrower resistance mechanism needed by this record: any future useful-quantum claim must be evaluated against the best classical method available at the time of comparison.

A 107-qubit superconducting surface-code processor demonstrates composed logical Clifford operations — lattice-surgery merge/split, patch expansion and shrinkage, and logical CNOT, Hadamard, and phase gates — with multi-round syndrome extraction and neural-network decoding, without post-selection. This advances the fault-tolerant substrate but does not demonstrate a practically useful quantum algorithm beyond classical simulation: the demonstrated set is Clifford-only, the codes are distance-three, and the work supplies no target problem. No independent replication yet; peer review pending.

Proctor et al. introduce QUOPS, a cross-platform system-level benchmark of the largest computationally relevant universal circuits a processor can execute successfully and their execution rate. The authors measure QUOPS on physical processors from Quantinuum, Google and IBM and on a simple fault-tolerant logical processor using up to eight [[7,1,3]]-encoded logical qubits on Quantinuum Helios-1. Translating recognised challenge workloads into the same benchmark, they estimate a FeMoco workload at 1,459 logical qubits and approximately 10^9 Toffoli gates, corresponding to about 3.4×10^8 QUOPS, while present measured circuit-size capability remains about five orders of magnitude below utility-scale targets. The result is supportive as a quantified system-level map of the remaining utility gap, not a demonstration of practical quantum advantage. Challenge-workload conversions and future fault-tolerant projections depend on architecture, compilation and gate-decomposition assumptions, and the work is a preprint pending peer review.