Quantum fault tolerance with constant-space and logarithmic-time overheads

Understand

In a model of fault-tolerant quantum computation with quick and noiseless polyloglog-time auxiliary classical computation, we construct a fault tolerance protocol with constant-space and $\widetilde{O}(\log N)$-time overhead, where $\widetilde{O}(\cdot)$ hides sub-polylog factors.

• Our construction utilizes constant-rate quantum locally testable codes (qLTC), new fault-tolerant gadgets on qLTCs and qLDPC codes, and a new analysis framework.
• In particular, 1) we develop a new simple and self-contained construction of magic state distillation for qubits using qudit quantum Reed-Solomon codes with $(\log \frac{1}{\varepsilon})^{\gamma}$ spacetime overhead, where $\gamma \rightarrow 0$.
• 2) We prove that the recent family of almost-good qLTCs of Dinur-Lin-Vidick admit parallel single-shot decoders against adversarial errors of weight scaling with the code distance.