AI summaryⓘ
The authors prove a new way for quantum computers to keep working correctly even when many parts are being badly corrupted in a very strong and tricky way by an adversary. They build a fault-tolerant method that handles almost as many errors as the number of physical quantum bits, greatly improving on past methods that only handled small or random errors. Their approach uses special quantum codes with good error correction features and can perform important quantum operations safely. This work helps solve big open problems in quantum computing theory and shows fault tolerance can survive even highly correlated and worst-case noise. They also develop techniques to simplify their complex construction to practical quantum systems.
quantum fault toleranceadversarial noisequantum error correctionsubsystem product codestransversal gatessingle-shot error correctiontensor codesquantum PCPcode switchingFloquet procedure
Abstract
We prove a fault-tolerance theorem for quantum computation against adversarial noise. For every quantum circuit on $\bar{N}$ logical qudits of depth $\bar{T}$, we construct a fault-tolerant circuit on $N=\text{poly}(\bar{N})$ physical qudits of depth $\bar{T}\cdot\bar{N}^{o(1)}$, which is robust against an adversary who may arbitrarily choose and corrupt an almost-linear number $N^{1-o(1)}$ of physical qudits at each time step. This robustness significantly improves upon prior fault-tolerance theorems, which assumed corruptions were either local and stochastic, or else only act on a polynomially vanishing fraction of qudits. Our fault-tolerance scheme addresses a key bottleneck towards constructing quantum PCPs via the circuit-to-Hamiltonian mapping of Anshu, Breuckmann, and Nguyen (STOC'24). More fundamentally, our result demonstrates that fault-tolerant quantum computation remains possible under noise models that are global, worst-case, and non-Markovian over the full duration of the computation, directly countering concerns that correlated noise could fundamentally undermine quantum fault tolerance. Our construction is based on a new family of subsystem product codes we develop, which have large dimension and distance along with low-weight parity-checks, and which support transversal non-Clifford gates. We show how to perform single-shot fault-tolerant error correction on these codes using a Floquet-like procedure based on the local testability of classical tensor codes. We then obtain a universal fault-tolerance scheme using repeated code switching in a hypercubic qudit architecture. Finally, we recursively compose our scheme with itself to reduce an initially exponential qudit dimension down to a constant.