Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.39345

Constant-Overhead Injection into Quantum Codes

Louis Golowich, Venkatesan Guruswami

quant-phcs.ITSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

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.

AI Summary

The paper asks whether bare quantum data can be fault-tolerantly encoded into, and decoded from, quantum error-correcting codes with constant space and quantum-time overhead. It constructs a code family with parameters $[[n=\Theta(k),k,d=\mathrm{poly}(k)]]$ supporting injection, ejection, logical $|0\rangle^{\otimes k}$ and $|+\rangle^{\otimes k}$ preparation, transversal blockwise CNOT, and error correction. Each gadget uses $O(k)$ physical qubits and $O(1)$ quantum depth under circuit-level locally stochastic noise, assuming polynomial-sized noiseless classical computations can run within each timestep. Operations other than injection and ejection have failure probability $2^{-\mathrm{poly}(k)}$. The construction takes high-dimensional hypergraph products of hierarchical classical LDPC codes adapted from linear-time-encodable expander codes. Four-dimensional products supply syndrome redundancy for single-shot state preparation. Decoding combines pushing errors into selected sectors with a high-dimensional small-set-flip decoder. Ejection uses physical Pauli measurements and classical corrections; injection teleports through encoded–physical Bell pairs. The initial analysis assumes level-dependent noise rates $p^{2^{\Omega(\ell)}}$. Concatenation with differently sized inner codes converts uniform physical noise into this profile while retaining constant overhead. Injection and ejection necessarily introduce errors on bare data. The guarantees allow correlated errors: except with small constant probability, only a small fraction of data qubits are corrupted, yielding low marginal error probabilities on a large fraction of positions once the noise distribution is fixed. Locally stochastic output errors are not established. A complete universal fault-tolerance scheme and practical finite-size performance remain open.

No sign of AI-generated textAI use disclosedStrong assumptions
ChatGPT 6 Astra was used to find references, make figures, and check over the final draft.

Central claim may not hold: The abstract's small corruption probability for every data qubit is not established by the body's weaker, explicitly acknowledged guarantee of low marginal probabilities only for a large fraction of positions identified after fixing the fault distribution. The written lossless-expansion definitions lack a restriction on the size of the expanded set, making the stated expander existence lemma false when applied to the entire left vertex set.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Fault-tolerant quantum computation with constant overhead for general noise

Matthias Christandl, Omar Fawzi, Ashutosh Goswami

Fault-tolerant quantum computation traditionally incurs substantial resource overhead, with both qubit and time overheads scaling polylogarithmically with the size of the computation. While prior work by Gottesman showed that constant qubit overhead is achievable under stochastic noise using quantum low-density parity-check (QLDPC) codes, it has remained an open question whether similar guarantees hold under more general, non-stochastic noise models. In this work, we address this question by considering a general circuit-level noise model defined via the diamond norm, which captures both stochastic and non-stochastic noise, including coherent and amplitude damping noise. We prove that constant qubit overhead fault-tolerant quantum computation is achievable in this general setting, using QLDPC codes with constant rate and linear minimum distance. To establish our result, we develop a fault-tolerant error correction scheme and a method for implementing logic gates under general circuit noise. These results extend the theoretical foundations of fault-tolerant quantum computation and offer new directions for fault-tolerant architectures under realistic noise models.

quant-pharXiv:2512.02760•PRX Quantum•Dec 3, 2025•4 citations

Fault-tolerant interfaces for quantum LDPC codes

Matthias Christandl, Omar Fawzi, Ashutosh Goswami

The preparation of a quantum state using a noisy quantum computer (gate noise strength $δ$) will necessarily affect an O($δ$)-fraction of the qubits, no matter which protocol is used. Here, we show that fault-tolerant quantum state preparation can be achieved with constant space overhead improving on previous constructions requiring polylogarithmic overhead. To achieve this, we add to the toolbox of fault-tolerant schemes for circuits with quantum input and output. More specifically, we construct fault-tolerant interfaces that decrease the level of protection for quantum low-density parity-check (LDPC) codes. When information is encoded in multiple code blocks, our interfaces have constant space overhead. In our decoder construction that change the level of protection by an arbitrary amount, we circumvent bottlenecks to error pileup and overhead by gradual lowering of the level of encoding at the same time as we increase the number of blocks on which decoding is carried out simultaneously.

quant-pharXiv:2602.16948•Feb 20, 2026•1 citation

Fault-Tolerant Quantum Computation with Adversarial Errors

Nikolas P. Breuckmann, Louis Golowich, Umesh Vazirani

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.

quant-pharXiv:2608.16857•Aug 18, 2026•0 citations

Constant-Overhead Addressable Gates via Single-Shot Code Switching

Louis Golowich, Kathleen Chang, Guanyu Zhu

It is a major challenge to perform addressable and parallel logical operations on constant-rate quantum LDPC (qLDPC) codes. Indeed, the overhead of targeting specific logical qubits represents a crucial bottleneck in many quantum fault-tolerance schemes. We introduce fault-tolerant protocols for performing various addressable as well as parallel logical operations with constant space-time overhead, on a family of constant-rate and polynomial-distance qLDPC codes. Specifically, we construct gadgets for a large class of permutations of logical qubits. We apply these logical permutations to construct gadgets for applying a targeted Hadamard (or $CNOT$) gate on any chosen logical qubit (pair). We also construct gadgets for preparing logical code states, and for applying Hadamard gates on all logical qubits in a codeblock. All of our gadgets use constant quantum space-time overhead along with polynomially bounded classical computation. Prior protocols for such operations required larger overhead, or else relied on codes with certain symmetries that lack known asymptotic constructions. Our codes are given by tensor products of classical codes constructed from lossless expander graphs. Our core technical contribution is a constant-overhead code-switching procedure between 2- and 3-dimensional product codes, which generalizes Bombin's dimensional jump (arXiv:1412.5079). We prove that all of our gadgets exhibit a constant threshold under locally stochastic noise. Along the way, we develop a small-set flip decoder for high-dimensional product codes from lossless expanders. Our techniques yield additional interesting consequences, such as single-shot state preparation of 2-dimensional product codes with constant space-time overhead. We also propose a method for performing parallel non-Clifford gates by extending our techniques to codes supporting transversal application of such gates.

arXiv:2510.06760•Oct 8, 2025•22 citations

Constant-space-overhead fault-tolerant quantum input/output and communication

Paula Belzig, Hayata Yamasaki

Fault-tolerant capacities quantify the ability of a quantum channel to reliably transmit information when every component of the encoding and decoding procedure is noisy. Earlier work analyzed achievable communication rates under such noise using fault-tolerant implementations based on concatenated codes with a single logical qubit. In this work, we develop an alternative approach using concatenations of quantum Hamming codes, which offer constant space overhead by encoding many logical qubits simultaneously. We introduce modular techniques for implementing fault-tolerant circuits with quantum input/output interfaces using the concatenated quantum Hamming code. These tools enable an analysis of fault-tolerant entanglement-assisted communication that is not only simpler, but also yields substantially higher achievable communication rates than previous methods, owing to the limited noise correlations in syndrome qubits of high-rate quantum Hamming codes.

quant-pharXiv:2602.09103•Feb 11, 2026•3 citations

Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation

Hayata Yamasaki, Masato Koashi

Abstract Scaling up quantum computers to attain substantial speedups over classical computing requires fault tolerance. Conventionally, protocols for fault-tolerant quantum computation demand excessive space overheads by using many physical qubits for each logical qubit. A more recent protocol using quantum analogues of low-density parity-check codes needs only a constant space overhead that does not grow with the number of logical qubits. However, the overhead in the processing time required to implement this protocol grows polynomially with the number of computational steps. To address these problems, here we introduce an alternative approach to constant-space-overhead fault-tolerant quantum computing using a concatenation of multiple small-size quantum codes rather than a single large-size quantum low-density parity-check code. We develop techniques for concatenating different quantum Hamming codes with growing size. As a result, we construct a low-overhead protocol to achieve constant space overhead and only quasi-polylogarithmic time overhead simultaneously. Our protocol is fault tolerant even if a decoder has a non-constant runtime, unlike the existing constant-space-overhead protocol. This code concatenation approach will make possible a large class of quantum speedups with feasibly bounded space overhead yet negligibly short time overhead.

arXiv:2207.08826•Nature Physics•Jan 16, 2024•75 citations
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.
The paper asks whether bare quantum data can be fault-tolerantly encoded into, and decoded from, quantum error-correcting codes with constant space and quantum-time overhead. It constructs a code family with parameters [[n=Θ(k),k,d=poly(k)]][[n=\Theta(k),k,d=\mathrm{poly}(k)]][[n=Θ(k),k,d=poly(k)]] supporting injection, ejection, logical ∣0⟩⊗k|0\rangle^{\otimes k}∣0⟩⊗k and ∣+⟩⊗k|+\rangle^{\otimes k}∣+⟩⊗k preparation, transversal blockwise CNOT, and error correction. Each gadget uses O(k)O(k)O(k) physical qubits and O(1)O(1)O(1) quantum depth under circuit-level locally stochastic noise, assuming polynomial-sized noiseless classical computations can run within each timestep. Operations other than injection and ejection have failure probability 2−poly(k)2^{-\mathrm{poly}(k)}2−poly(k).
The construction takes high-dimensional hypergraph products of hierarchical classical LDPC codes adapted from linear-time-encodable expander codes. Four-dimensional products supply syndrome redundancy for single-shot state preparation. Decoding combines pushing errors into selected sectors with a high-dimensional small-set-flip decoder. Ejection uses physical Pauli measurements and classical corrections; injection teleports through encoded–physical Bell pairs. The initial analysis assumes level-dependent noise rates p2Ω(ℓ)p^{2^{\Omega(\ell)}}p2Ω(ℓ). Concatenation with differently sized inner codes converts uniform physical noise into this profile while retaining constant overhead.
Injection and ejection necessarily introduce errors on bare data. The guarantees allow correlated errors: except with small constant probability, only a small fraction of data qubits are corrupted, yielding low marginal error probabilities on a large fraction of positions once the noise distribution is fixed. Locally stochastic output errors are not established. A complete universal fault-tolerance scheme and practical finite-size performance remain open.
Fault-tolerant quantum computation traditionally incurs substantial resource overhead, with both qubit and time overheads scaling polylogarithmically with the size of the computation. While prior work by Gottesman showed that constant qubit overhead is achievable under stochastic noise using quantum low-density parity-check (QLDPC) codes, it has remained an open question whether similar guarantees hold under more general, non-stochastic noise models. In this work, we address this question by considering a general circuit-level noise model defined via the diamond norm, which captures both stochastic and non-stochastic noise, including coherent and amplitude damping noise. We prove that constant qubit overhead fault-tolerant quantum computation is achievable in this general setting, using QLDPC codes with constant rate and linear minimum distance. To establish our result, we develop a fault-tolerant error correction scheme and a method for implementing logic gates under general circuit noise. These results extend the theoretical foundations of fault-tolerant quantum computation and offer new directions for fault-tolerant architectures under realistic noise models.
The preparation of a quantum state using a noisy quantum computer (gate noise strength δδδ) will necessarily affect an O(δδδ)-fraction of the qubits, no matter which protocol is used. Here, we show that fault-tolerant quantum state preparation can be achieved with constant space overhead improving on previous constructions requiring polylogarithmic overhead. To achieve this, we add to the toolbox of fault-tolerant schemes for circuits with quantum input and output. More specifically, we construct fault-tolerant interfaces that decrease the level of protection for quantum low-density parity-check (LDPC) codes. When information is encoded in multiple code blocks, our interfaces have constant space overhead. In our decoder construction that change the level of protection by an arbitrary amount, we circumvent bottlenecks to error pileup and overhead by gradual lowering of the level of encoding at the same time as we increase the number of blocks on which decoding is carried out simultaneously.
We prove a fault-tolerance theorem for quantum computation against adversarial noise. For every quantum circuit on Nˉ\bar{N}Nˉ logical qudits of depth Tˉ\bar{T}Tˉ, we construct a fault-tolerant circuit on N=poly(Nˉ)N=\text{poly}(\bar{N})N=poly(Nˉ) physical qudits of depth Tˉ⋅Nˉo(1)\bar{T}\cdot\bar{N}^{o(1)}Tˉ⋅Nˉo(1), which is robust against an adversary who may arbitrarily choose and corrupt an almost-linear number N1−o(1)N^{1-o(1)}N1−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.
It is a major challenge to perform addressable and parallel logical operations on constant-rate quantum LDPC (qLDPC) codes. Indeed, the overhead of targeting specific logical qubits represents a crucial bottleneck in many quantum fault-tolerance schemes. We introduce fault-tolerant protocols for performing various addressable as well as parallel logical operations with constant space-time overhead, on a family of constant-rate and polynomial-distance qLDPC codes. Specifically, we construct gadgets for a large class of permutations of logical qubits. We apply these logical permutations to construct gadgets for applying a targeted Hadamard (or CNOTCNOTCNOT) gate on any chosen logical qubit (pair). We also construct gadgets for preparing logical code states, and for applying Hadamard gates on all logical qubits in a codeblock. All of our gadgets use constant quantum space-time overhead along with polynomially bounded classical computation. Prior protocols for such operations required larger overhead, or else relied on codes with certain symmetries that lack known asymptotic constructions. Our codes are given by tensor products of classical codes constructed from lossless expander graphs. Our core technical contribution is a constant-overhead code-switching procedure between 2- and 3-dimensional product codes, which generalizes Bombin's dimensional jump (arXiv:1412.5079). We prove that all of our gadgets exhibit a constant threshold under locally stochastic noise. Along the way, we develop a small-set flip decoder for high-dimensional product codes from lossless expanders. Our techniques yield additional interesting consequences, such as single-shot state preparation of 2-dimensional product codes with constant space-time overhead. We also propose a method for performing parallel non-Clifford gates by extending our techniques to codes supporting transversal application of such gates.
Fault-tolerant capacities quantify the ability of a quantum channel to reliably transmit information when every component of the encoding and decoding procedure is noisy. Earlier work analyzed achievable communication rates under such noise using fault-tolerant implementations based on concatenated codes with a single logical qubit. In this work, we develop an alternative approach using concatenations of quantum Hamming codes, which offer constant space overhead by encoding many logical qubits simultaneously. We introduce modular techniques for implementing fault-tolerant circuits with quantum input/output interfaces using the concatenated quantum Hamming code. These tools enable an analysis of fault-tolerant entanglement-assisted communication that is not only simpler, but also yields substantially higher achievable communication rates than previous methods, owing to the limited noise correlations in syndrome qubits of high-rate quantum Hamming codes.
Abstract Scaling up quantum computers to attain substantial speedups over classical computing requires fault tolerance. Conventionally, protocols for fault-tolerant quantum computation demand excessive space overheads by using many physical qubits for each logical qubit. A more recent protocol using quantum analogues of low-density parity-check codes needs only a constant space overhead that does not grow with the number of logical qubits. However, the overhead in the processing time required to implement this protocol grows polynomially with the number of computational steps. To address these problems, here we introduce an alternative approach to constant-space-overhead fault-tolerant quantum computing using a concatenation of multiple small-size quantum codes rather than a single large-size quantum low-density parity-check code. We develop techniques for concatenating different quantum Hamming codes with growing size. As a result, we construct a low-overhead protocol to achieve constant space overhead and only quasi-polylogarithmic time overhead simultaneously. Our protocol is fault tolerant even if a decoder has a non-constant runtime, unlike the existing constant-space-overhead protocol. This code concatenation approach will make possible a large class of quantum speedups with feasibly bounded space overhead yet negligibly short time overhead.