CS Paper Radar

Local Quantum Fault Tolerance Without Expansion

David Ponarovsky

cs.CC quant-ph ·submitted 2026-10-28 20:31 UTC · v2
theory

Abstract

We study fault-tolerant quantum computation using a fixed, local error-correction rule and a geometrically simple code: the cubical $(d,d')$-Toric code with $d',d-d'\geq 2$, including the 4D Toric code. Under sufficiently weak local-stochastic Pauli noise, our construction uses noiseless, bounded-depth classical processing per physical time step. Its correction cycle acts only on the current syndrome, has constant depth, and is repeated unchanged during idle logical computation; it requires neither multiscale decoder states nor scale-dependent communication delays. Our proof treats errors and syndromes as chains in a cubical complex, combining geometric shrinking under the sweep rule with a space--time explanation-tree argument inspired by Toom's theorem. It does not rely on expansion. We establish three results: 1.Explicit higher-dimensional sweep rule. We give a local algorithm for choosing sweep corrections on cubical $(d,d')$-Toric complexes, resolving the local-existence question of Kubica and Preskill. 2. Fault-tolerant computation. We prove a circuit-level threshold theorem for noisy sweep cycles interleaved with logical gates. In particular, the 4D Toric code admits a fixed, constant-depth syndrome-based correction cycle without a multiscale decoder or expansion-based encoding. We do not claim constant total-depth overhead. 3. Ideal decoding under local-stochastic noise. For an initial local-stochastic Pauli error of rate $p$ below threshold, $n^{d+1}$ noiseless sweep cycles recover the encoded state on a side-length-$n$ $(d,d')$-Toric code with probability at least $1-O(\operatorname{poly}(n))p^{Ω(n)}$, extending earlier guarantees for independent errors.

Comment
[v2] - Fixed cross-referencing issues in the arXiv version. No changes to the results or proofs

Closest papers

Nearest neighbours by meaning across the whole index.

Fault-tolerant quantum computation cannot be achieved with constant spacetime overhead

cs.IT quant-ph ·2026-08-26 ·Kishor Bharti, Tobias Haug, Andrew Tanggara
theory similarity 0.69
Abstract · 40 pages

The threshold theorem states that quantum computations can be made reliable below a physical error threshold, at the cost of additional physical qubits and circuit depth. Recent work has reduced these space and time overheads to polylogarithmic or nearly logarithmic scalings, but whether the cumulative spacetime overhead can be constant has remained unclear. Here, we show that even for the simplest task of preserving quantum information in a quantum memory, under an optimistic noise model and allowing general adaptive protocols, there is an unavoidable logarithmic contribution to the cumulative spacetime overhead. This additional cost can nevertheless be shared among many logical qubits, so sufficiently wide computations, including standard implementations of Shor's algorithm, may still achieve constant relative overhead. We further give a positive-rate CSS code construction that attains the memory bound, identify sufficient conditions under which the same scaling extends from quantum memory to fault-tolerant circuit implementations, and derive circuit-size bounds for subsystem spacetime codes. Our work establishes fundamental limits on the resources required for quantum fault tolerance.

0.26

Parametric Proof-Carrying Compilation for Quantum Error-Correction

cs.PL quant-ph ·2026-11-08 ·John Zhuoyang Ye, Jens Palsberg
theory similarity 0.68
Abstract

We present PC-QEC, a proof-carrying compilation framework for quantum error correction parameterized by both code distance and syndrome-extraction scheme. It covers all four schemes---Standard, Flag, Shor and Knill---with circuit-level distance guarantees for every legal code distance in each proved family under the declared error and readout contracts. The circuit-level model permits single-wire Pauli errors at every operation's qubit operands, capturing data errors, readout errors and ancilla errors that propagate into multi-qubit hook errors. For each family and scheme, supplied code-algebra and invariant proofs combine with proved scheme-specific propagation lemmas into a finite symbolic certificate whose size is independent of code distance. We demonstrate family-wide guarantees for five code families across all four schemes. For rotated Surface code, one Standard Scheme certificate proves a distance lower bound $d$ for every odd $d\ge3$ and checks in 214\,s on average. Lean 4 mechanizes the metatheory and exact circuit-level distances for canonical rotated Surface, unrotated Surface and Toric code families.

0.30

Fault-Tolerant Quantum Computation with Adversarial Errors

cs.CC quant-phcs.IT ·2026-08-17 ·Nikolas P. Breuckmann, Louis Golowich, Umesh Vazirani
theory similarity 0.68
Abstract · v2: minor edits to exposition, updated funding acknowledgments

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.

0.10

Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes

cs.CC quant-ph ·2026-08-17 ·Louay Bazzi, Georges Khater
similarity 0.66
Abstract · Added author contributions and AI use statements

Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for topological quantum codes. For surface codes under the depolarizing channel, we consider Minimum-Weight decoding, which seeks a minimum-weight Pauli error consistent with both the $X$- and $Z$-syndromes. For color codes under independent $X$- and $Z$-error models, we consider Separate Minimum-Weight decoding. Assuming $P\neq NP$, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the toric code and the $4.8.8$ color code on the torus, there exists a constant $c>0$ such that no polynomial-time algorithm can always produce a solution whose weight is within $cN^{1/14}$ of the optimum, where $N$ is the number of qubits, unless $P=NP$. For the planar surface code, we obtain an $Ω(N^{1/18})$ gap. Our inapproximability results use Håstad's hardness of approximation for MAX-3SAT. Our reduction develops a general, modular framework for embedding logical constraints into coupled primal--dual join problems on a lattice. A key ingredient is a localization argument that controls unintended interactions between different parts of the construction.

0.34

Towards Block-Level Fault-Tolerant Quantum Simulation on Small High-Rate Non-CSS Codes

cs.IT quant-ph ·2026-09-14 ·Zhuangzhuang Chen, Narayanan Rengaswamy
similarity 0.66
Abstract · 29 pages, 21 figures

Small high-rate non-CSS stabilizer codes provide compact platforms for encoded quantum computation, but mixed-Pauli checks and limited native transversal logical gates complicate fault-tolerant dynamics. Block-level constructions offer an alternative by mapping an entire logical block to a physical circuit rather than compiling separately protected logical gates. We investigate this approach using the high-rate [[8,3,3]] non-CSS code and logical Trotter circuits as a testbed. We construct flagged syndrome-extraction circuits and establish a circuit-level memory pseudo-threshold near \(1.5\times10^{-3}\). We then apply our symplectic-transvection construction, which maps a logical Trotter circuit to a physical circuit with the same block pattern for any stabilizer code. Although this mapping preserves the intended unitary algebraically, encoded Trotter circuits exhibit asymmetry between logical-\(X\) and logical-\(Z\) failure channels. Single-fault analysis identifies the mechanism: a fault on the shared parity ancilla can propagate through the uncomputation network into an undetectable logical operator, reducing the effective circuit distance in the affected sector. We evaluate flag-conditioned recovery, biased-noise decoding, CliNR resource verification, flag postselection, and asymmetric gate-noise models. These methods suppress propagated faults but do not simultaneously suppress both logical sectors in the realistic configurations studied. A diagnostic protected limit removing the identified malignant first-order locations restores pseudo-threshold behavior in both sectors, approaching memory performance. These results demonstrate the potential of block-level logical constructions for non-CSS codes without rich native transversal gate sets and the joint protection of the parity network, analog rotation, and recovery required to preserve fault-tolerant distance.

0.09

Constant-Overhead Injection into Quantum Codes

cs.IT quant-ph ·2026-09-30 ·Louis Golowich, Venkatesan Guruswami
similarity 0.64
Abstract

We construct the first known fault-tolerant scheme for injecting states into quantum error-correcting codes with constant space and time overhead. That is, we construct a family of constant-rate quantum error-correcting codes for which a set of bare physical qubits can be injected, i.e. fault-tolerantly encoded, into a code block. Similarly, a code state can be ejected, i.e. fault-tolerantly decoded, back into bare physical qubits. We show that these injection and ejection procedures succeed under circuit-level locally stochastic noise, while incurring just a small constant probability of corrupting each qubit, which is unavoidable for bare physical qubits. We also show how to perform fault-tolerant error correction and code-state preparation under locally stochastic noise. All of our gadgets can be implemented with constant quantum circuit depth (i.e. are single-shot), and with a number of physical qubits growing linearly with the number of logical qubits, assuming the ability to run polynomial-sized noiseless classical circuits on the side. We construct our quantum codes by taking a high-dimensional hypergraph product of classical LDPC codes, which in turn are a simplified version of Spielman's linear-time encodable codes (STOC'95). As our resulting product codes are only resilient to physical errors occurring with non-uniform probabilities across qubits, we then show how to concatenate with inner codes of various sizes to obtain fault-tolerance against uniform noise.

0.18

Improved Quantum Codes with Transversal T Gates

cs.IT quant-ph ·2026-08-25 ·Adam Wills
theoryhighly cited similarity 0.61
Abstract

In this work, we study quantum CSS codes with transversal $T$ gates. Here, $T$ gate transversality is meant in the strongest sense; the application of physical $T$ to every physical qubit yields logical $T$ on every logical qubit, without Clifford corrections. Despite the importance of the $T$ gate in fault-tolerant quantum computation, the parameters of asymptotic families of such codes have not been improved since the work of Hastings and Haah in 2017, and Haah in 2018. In this work, we significantly broaden the achievable parameters of quantum code families with transversal $T$ gates, both expanding the regime of achievable polynomial rate and distance, and constructing such codes with constant rate and growing distance; this is the first time the latter has been achieved, even when allowing Clifford corrections after the transversal $T$ gate. These are also the first codes achieving $γ\to 0$ for a code with a transversal $T$ gate, where $γ$ is the overhead exponent of magic state distillation. To do this, we develop a framework of divisible decreasing monomial codes, punctured at a downward-closed set on the Boolean hypercube to create logical qubits. We prove a closed-form expression for the distance of such a code punctured at such a set, which may be of independent interest. We first instantiate this with an explicit construction based on weighted Reed-Muller codes, puncturing at low Hamming-weight points, and then with a randomised construction, where a small random set of points is protected from the puncturing to save quantum code distance, achieving improved parameters.

0.28

Linear-time erasure recovery for quantum expander codes

cs.IT quant-ph ·2026-11-04 ·Anirudh Krishna, Christopher A. Pattison
similarity 0.61
Abstract

Erasures are used to model faults at a subset of known locations in various platforms used to construct fault-tolerant quantum computers. Beyond the utility in erasure recovery, efficient decoders for erasures are useful to both understand error decoders and as a subroutine for error decoding. Classical expander codes, which belong to the family of low-density parity-check (LDPC) codes, can be equipped with the Peeling decoder which works in linear time. Our main result is the algorithm Small-Set-Peeling, a quantum generalization of the classical Peeling decoder for erasures, that applies to quantum expander codes (Tillich, Zémor, IEEE T-IT 2013; Leverrier, Tillich, Zémor, FOCS 2015). This decoder can correct up to $D-1$ erasures, where $D$ is the (design) distance of the code and, importantly, is the first decoder that is guaranteed to do so in linear time. Combining with the erasure-conversion algorithm Small-Set-Find (Krishna, Livni-Navon, Wootters, SODA 2024), our result also implies the existence of a novel graph-local linear-time decoder for Pauli errors.

0.22