We construct the first fully spatially local fault-tolerant quantum computer based on topological codes in fewer than four spatial dimensions. Our construction is a two-dimensional architecture that uses only geometrically local quantum and classical operations, bounded-speed classical communication and computation, and a constant density of quantum and classical resources. The core component is a new time-translation-invariant cellular-automaton decoder for the surface code. This decoder preserves logical information for a time stretched-exponential in the code distance and operates continuously during state injection, stabilizer-state preparation, lattice surgery, and transversal readout. We also prove that every translation-invariant topological Pauli stabilizer code is locally decodable under phenomenological noise.
Comments
118 pages, 19 figures, visualizations available at https://local-decoders.github.io/
We construct the first fully spatially local fault-tolerant quantum computer based on topological codes in fewer than four spatial dimensions. Our construction is a two-dimensional architecture that uses only geometrically local quantum and classical operations, bounded-speed classical communication and computation, and a constant density of quantum and classical resources. The core component is a new time-translation-invariant cellular-automaton decoder for the surface code. This decoder preserves logical information for a time stretched-exponential in the code distance and operates continuously during state injection, stabilizer-state preparation, lattice surgery, and transversal readout. We also prove that every translation-invariant topological Pauli stabilizer code is locally decodable under phenomenological noise.
We construct a local decoder for the 2D toric code using ideas from the hierarchical classical cellular automata of Tsirelson and Gács. Our decoder is a circuit of strictly local quantum operations preserving a logical state for exponential time in the presence of circuit-level noise without the need for non-local classical computation or communication. Our construction is not translation invariant in spacetime, but can be made time-translation invariant in 3D with stacks of 2D toric codes. This solves the open problem of constructing a local topological quantum memory below four dimensions.
Quantum error correction (QEC) normally requires active maintenance using measurements, classical processing and externally controlled correction schedules. Passive QEC, by contrast, was previously established only in unphysical spatial dimensions. Here, we give an explicit scheme for autonomous quantum error correction and computation in two dimensions, formulated as a dissipative quantum cellular automaton with a fixed, local and translation-invariant update rule. The construction uses hierarchical, self-simulating control elements based on ideas from the seminal classical results of Gács (1986, 1989) together with a measurement-free concatenated quantum code. We prove the existence of a nonzero noise threshold under a local noise model. Below this threshold, logical errors on encoded initial states are suppressed exponentially with increasing system size and the memory lifetime diverges in the thermodynamic limit. As an extension, we outline how this mechanism can also be implemented in continuous time by a time-independent, translation-invariant local Lindbladian. Quantum circuits can moreover be encoded in the automaton's initial state and executed fault-tolerantly with polylogarithmic overhead under the same circuit-independent rule. Our scheme thus realizes a self-correcting quantum computer capable of universal computation.
Two-dimensional topological translationally invariant (2D TTI) stabilizer codes lie at the heart of fault-tolerant quantum computation, but using them requires solving the decoding problem. Minimum-weight decoding of these codes was recently shown to be NP-hard, even in basic settings, such as the color code with Pauli Z errors and the toric code with Pauli X, Y and Z errors. Here, we prove that minimum-weight decoding of 2D TTI codes nonetheless admits a polynomial-time approximation scheme (PTAS), i.e., for any constant ε>0, a recovery operator of weight within a multiplicative factor of 1+ε of the minimum can be found in polynomial time. Our approach builds on Arora's PTAS for Euclidean problems, such as the traveling salesman problem, and applies when decoding can be cast in terms of point-like excitations connected by string-like errors. It therefore extends beyond two dimensions, covering certain higher-dimensional topological codes and quantum memories, including the toric code with phenomenological or circuit-level noise.
Active error decoding and correction of topological quantum codes—in particular the toric code—remains one of the most viable routes to large scale quantum information processing. In contrast, passive error correction relies on the natural physical dynamics of a system to protect encoded quantum information. However, the search is ongoing for a completely satisfactory passive scheme applicable to locally interacting two-dimensional systems. Here, we investigate dynamical decoders that provide passive error correction by embedding the decoding process into local dynamics. We propose a specific discrete time cellular-automaton decoder in the fault tolerant setting and provide numerical evidence showing that the logical qubit has a survival time extended by several orders of magnitude over that of a bare unencoded qubit. We stress that (asynchronous) dynamical decoding gives rise to a Markovian dissipative process. We hence equate cellular-automaton decoding to a fully dissipative topological quantum memory, which removes errors continuously. In this sense, uncontrolled and unwanted local noise can be corrected for by a controlled local dissipative process. We analyze the required resources, commenting on additional polylogarithmic factors beyond those incurred by an ideal constant resource dynamical decoder.
In fault-tolerant quantum computation, the preparation of logical states is a ubiquitous subroutine, yet significant challenges persist even for the simplest states required. In the present work, we present a unitary, scalable, distance-preserving encoding scheme for preparing Pauli eigenstates in surface codes. Unlike previous unitary approaches whose fault-distance remains constant with increasing code distance, our scheme ensures that the protection offered by the code is preserved during state preparation. Building on strategies discovered by reinforcement learning for the surface-17 code, we generalize the construction to arbitrary code distances and both rotated and unrotated surface codes. The proposed encoding relies only on geometrically local gates, and is therefore fully compatible with planar 2D qubit connectivity, and it achieves circuit depth scaling as O(d), consistent with fundamental entanglement-generation bounds. We design explicit stabilizer-expanding circuits with and without ancilla-mediated connectivity and analyze their error-propagation behavior. Numerical simulations under depolarizing noise show that our unitary encoding without ancillas outperforms standard stabilizer-measurement-based schemes, reducing logical error rates by up to an order of magnitude. These results make the scheme particularly relevant for platforms such as trapped ions and neutral atoms, where measurements are costly relative to gates and idling noise is considerably weaker than gate noise. Our work bridges the gap between measurement-based and unitary encodings of surface-code states and opens new directions for distance-preserving state preparation in fault-tolerant quantum computation.
Quantum computers are far more error-prone than their classical counterparts. Therefore, to build a quantum computer capable of running large-scale quantum algorithms, we must use the techniques of quantum error correction to ensure that the computer produces the correct output even when its components are unreliable. However, the resource requirements of building such a fault-tolerant quantum computer are currently prohibitive. Here, we examine the utility of using three-dimensional (3D) surface codes in a fault-tolerant quantum computer. This family of topological error-correcting codes is a generalization of the well-known 2D surface code to three spatial dimensions. We show that certain 3D surface codes have a transversal logical non-Clifford gate. In a quantum computing architecture, a non-Clifford gate is required to achieve computational universality. Transversal gates do not entangle qubits in different codes, so they are naturally fault tolerant because they do not spread errors. Next, we consider the problem of decoding 3D surface codes. In a quantum error-correcting code, we cannot observe the qubits directly, so we measure parity-check operators to gain information about the state of the code. Decoding is the problem of estimating what error has occurred given a list of unsatisfied parity checks. We observe that 3D surface codes offer asymmetric protection against bit-flip and phase-flip errors, but in both cases, we find that a threshold error rate exists below which we can suppress logical errors by increasing the size of the code. We use our results about logical gates and decoding to propose two fault-tolerant quantum computing architectures that utilize 3D surface codes. Finally, we compare the resource requirements of our architectures with the requirements of leading quantum computing architectures based on topological codes. We find that one of our architectures may be competitive with the leading architectures, depending on the properties of the physical systems used to build the qubits.