A Constant Rate Quantum Computer on a Line

Craig Gidney, Thiago Bergamaschi · 2025

Read A Constant Rate Quantum Computer on a Line by Craig Gidney, Thiago Bergamaschi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-16132.txt.

Introduction

Craig Gidney and Thiago Bergamaschi wrote a paper in two thousand twenty-five on building a fault-tolerant quantum computer in the shape of a line. Their qubits, the basic units of the machine, sit in a row and link only to their nearest neighbors. A known limit had suggested that good error-correcting codes need a denser layout than a line allows.

The authors show by construction that the limit does not extend to full circuits. Their design keeps a coding rate above five percent, with time costs that grow slowly. It builds on a tower of Hamming codes and uses a variant of a known method to check the qubits.

Catalog record

CREATORCraig Gidney, Thiago Bergamaschi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE113 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-16132

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Constant Rate Quantum Computer on a Line Craig Gidney, Thiago Bergamaschi Abstract We prove by construction that the Bravyi-Poulin-Terhal bound on the spatial density of stabilizer codes does not generalize to stabilizer circuits. To do so, we construct a fault tolerant quantum computer with a coding rate above 5 % \% and quasi-polylog time overhead, out of a line of qubits with nearest-neighbor connectivity, and prove it has a threshold. The construction is based on modifications to the tower of Hamming codes of Yamasaki and Koashi (Nature Physics, 2024), with operators measured using a variant of Shor’s measurement gadget. 1 Introduction A “stabilizer code” is a simple way of describing a quantum error correction strategy [ Got97 ] . A stabilizer code specifies a list of stabilizers (a set of commuting Pauli product operators) as well as a list of logical qubits (each an anticommuting pair of Pauli product operators). The intent is that, by measuring the stabilizers, you can catch errors and thereby protect quantum information encoded into the logical qubits. Stabilizer codes can’t describe many forms of quantum fault tolerance. The stabilizers of a stabilizer code must all commute [ Bac06 ] , so stabilizer codes can’t represent the Bacon-Shor code [ Bac06 ] . The observables of a stabilizer code can’t change, so stabilizer codes can’t represent the Honeycomb code [ HH21 ] . Stabilizer codes don’t include information about how to measure the stabilizers, so they can’t describe concepts like “measurement qubits” [ FMMC12 ] , “flag qubits” [ CR18 ] , “hook errors” [ FMMC12 ] , or measuring expensive operators less often [ GB23 , GNBJ23 ] . Individually, these limitations can be fixed by extending the definition of a stabilizer code. But attempting to simultaneously include all the extensions necessary to fix these limitations, would destroy the simplicity that makes stabilizer codes so useful as a language for quantum error correction. A “stabilizer circuit” is a quantum circuit built out of operations that can be efficiently analyzed using the stabilizer formalism [ Got97 , AG04 ] . Stabilizer circuits can use Hadamard gates ( H ), controlled-not gates ( C_{X} ), phase gates ( S ), measurement gates ( M_{Z} ), reset gates ( R_{Z} ), and classical feedback. This allows stabilizer circuits to implement arbitrary Clifford operations and arbitrary Pauli product measurements, but isn’t sufficient for universal quantum computation without some additional ingredient (such as the ability to produce magic states [ BK05 ] ). Although they are strictly more complicated than stabilizer codes, stabilizer circuits can represent a wider variety of fault tolerant constructions [ Gid21 , MBG23 , DP23 , BLN+24 ] . Bounds on quantum error correction are often proved first for stabilizer codes. For example, in a seminal result, Bravyi, Poulin, and Terhal proved a bound on the rate and distance of stabilizer codes whose stabilizers are local on a two dimensional grid. In particular, they proved that 2D [[n,k,d]] stabilizer codes must satisfy kd^{2}=O(n) [ BPT10 ] . 1 1 1 Where n is the number of physical qubits, k is the number of logical qubits, and d is the code distance. In 2010, Bravyi extended this work to gauge codes [ Bra11 ] . Crucially, he showed that the [ BPT10 ] bound didn’t apply to gauge codes. Instead, gauge codes are restricted by the looser bound of kd=O(n) . This naturally raises the question: does this bound continue to loosen as more possibilities are considered? In particular, How do these bounds on spatial density generalize from 2D local codes to 2D local circuits ? Quantum circuits can use a series of local gates to measure non-local stabilizers, so this isn’t a trivial question. Unfortunately, the true limits of the space & time overheads of noisy stabilizer circuits still remain much less well understood. Recently, Baspin, Fawzi, and Shayeghi extended Bravyi et al’s work to certain families of stabilizer circuits [ BFS23 ] . They proved that any stabilizer circuit in 2D of logical error rate \delta - with a shallow decoding circuit (cf. Section 1.2 ) - must have a spatial overhead (an inverse rate) of at least \Omega(\sqrt{\log\delta^{-1}}) . Conceptually, their argument is based on the fact that high-rate quantum error correcting codes must be highly entangled. Any error-correction circuit must create and maintain this long-range entanglement, but a geometrically-local, noisy quantum circuit is limited in how quickly and reliably it can do so. In this paper, we prove that the [ BPT10 ] bound cannot fully generalize to stabilizer circuits. To do so, we construct a constant-rate quantum memory, whose operations can be fully realized using nearest-neighbor gates in 1 dimension (on a line). Our construction is built on the concatenated “tower of Hamming codes” of Yamasaki and Koashi [ YK24 ] , and leverages multi-scale error correction to bypass the no-go result of [ BFS23 ] . By further combining our memory with a magic state distillation protocol, we show how to achieve fault-tolerant quantum computation, with a constant space overhead, in 1D. 1.1 Our Contributions A technical statement of our contributions follows. We refer the reader to Section 2 for formal definitions. Ultimately, our main result is the following theorem. Theorem 1.1 (A Constant Rate Quantum Memory) . There exists an infinite family of quantum memories M_{n} , such that 1. M_{n} uses n physical qubits to implement more than n/20 logical qubits. 2. M_{n} is implemented by a stabilizer circuit using nearest-neighbor gates on a line, while subjected to local stochastic noise. 3. Below some local stochastic noise threshold p independent of n , the per-circuit-cycle logical error rate of M_{n} is \exp(-\exp(\Omega(\log^{1/3} n))). We assume that M_{n} is decoded by an efficient (polynomial-time bounded) classical control system, that uses long range communication and perfect operations. Only the quantum part of the memory is local and noisy. However, we emphasize that no classical feedback is required for the purposes of simply maintaining the logical quantum information as in Theorem 1.1 . We simply use the classical control system to store and update syndrome measurements. To operate on our memory M_{n} , we design fault-tolerant gadgets to perform arbitrary Pauli-product measurements. This enables us to measure stabilizers, logical information, and more generally to perform arbitrary Clifford gates. To achieve a universal set of gates, we combine our memory with a magic state distillation protocol [ BH12 ] . Ultimately, we prove the following theorem on the fault-tolerant simulation of 1D quantum circuits, with a constant space overhead and quasi- \mathrm{polylog} time overhead. Theorem 1.2 (Fault-Tolerant Computation) . Let C be a quantum circuit on m qubits configured on a line, which can be implemented using d alternating layers of nearest neighbor, two qubit gates. Then, for any desired target accuracy \varepsilon bounded by \varepsilon\geq d\cdot\exp(-\exp(O(\log^{1/3} m))), (1) there exists a fault-tolerant simulation C_{\varepsilon} of C , satisfying 1. C_{\varepsilon} uses \leq 20\cdot m physical qubits to implement m logical qubits. 2. C_{\varepsilon} is implemented by a depth d\cdot\exp(O(\log^3\log\frac{m\cdot d}{\epsilon})) stabilizer circuit using nearest neighbor gates on a line, while subjected to local stochastic noise. 3. Below some threshold noise rate p independent of m , the logical error rate of

Read the complete text