Quantum Fault Tolerance with Constant-Space and Logarithmic-Time Overheads

In a model of fault-tolerant quantum computation with noiseless constant-time auxiliary classical computation per quantum operation, we construct a quantum fault tolerance protocol with constant-space and O(log N )-time overheads, where the notation O(•) hides sub-polylogarithmic factors. This significantly improves over the previous state-of-the-art protocol of Yamasaki and Koashi that achieved constant-space and quasi-polylogarithmic-time overhead. Our construction is obtained by using constant-rate quantum locally testable codes (qLTC) of appropriately chosen block size and developing new fault-tolerant gadgets on qLTCs and qLDPC codes. In particular, we obtain the following new technical results: (1) We develop a magic state distillation protocol with (log 1 ε ) γ spacetime overhead, where γ → 0 as ε → 0. This result differs from recent works in that we use a simple and self-contained construction using Reed-Solomon codes to obtain low spacetime overhead (rather than just space overhead as in recent works). We show a similar result for stabilizer state distillation. (2) We prove that quantum codes based on the cubical complex construction admit sequential and parallel single-shot decoders against adversarial errors of weight scaling with the code distance. In particular, our proof applies to a recent family of almost-good qLTCs of Dinur-Lin-Vidick and the good qLDPC codes of Dinur-Hsieh-Lin-Vidick. (3) Using the introduced distillation schemes, we develop fault-tolerant logical state preparation procedures with O(1)-spacetime overhead on qLTCs. Here, the qLTC property is used to quickly test if a state is too far from the codespace before proceeding. (4) We introduce the use of multiple resource states (from a small-sized set) to obtain addressable qLDPC logic that can be easily prepared using our state preparation schemes and transversal qLDPC gates. We obtain the main result by combining the above results with carefully chosen parameters. In doing so, we introduce a new weight enumerator formalism to prove fault tolerance in a composable way, which is of independent interest. To our knowledge, this gives the lowest spacetime overhead to date in the considered model of quantum fault tolerance, which, for the first time, matches that of classical fault tolerance up to sub-polylogarithmic factors. We conjecture this is optimal up to sub-polylogarithmic factors.