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:2603.04543

Linear-Time Encodable and Decodable Quantum Error-Correcting Codes

Adam Wills, Ting-Chun Lin, Rachel Yun Zhang, Min-Hsiu Hsieh

quant-phSubmitted Mar 4, 2026• Announced Mar 6, 2026• 2 citations
v1 · Mar 4, 2026v2 · Jun 22, 2026
arXivHTMLPDF

Abstract

Recent years have seen rapid development in the subject of quantum coding theory, with breakthroughs on many exciting classes of codes, including quantum LDPC codes, quantum locally testable codes, and quantum codes with interesting transversal gates. However, a natural class of quantum codes, which has been well-studied classically, has not yet been treated: those which can be quickly encoded and decoded. This problem concerns the channel capacity setting, where a noise channel sits between perfect encoding and unencoding/decoding operations; this is the setting that is relevant for communication between fault-tolerant quantum computers. In this work, we construct asymptotically good quantum codes that can be encoded and unencoded by quantum circuits of logarithmic depth and consisting of a linear total number of gates. The classical decoding algorithms also run in logarithmic depth and use $\mathcal{O}(n \log n)$ gates, or alternatively a linear number of gates but with higher depth. We further construct explicit and asymptotically good quantum codes whose encoding, unencoding and decoding all use a linear number of gates, and additionally whose encoding and unencoding may be run in logarithmic depth.

Related papers

Fault-Tolerant Coding for Quantum Communication

Matthias Christandl, Alexander Müller‐Hermes

Designing encoding and decoding circuits to reliably send messages over many uses of a noisy channel is a central problem in communication theory. When studying the optimal transmission rates achievable with asymptotically vanishing error it is usually assumed that these circuits can be implemented using noise-free gates. While this assumption is satisfied for classical machines in many scenarios, it is not expected to be satisfied in the near term future for quantum machines where decoherence leads to faults in the quantum gates. As a result, fundamental questions regarding the practical relevance of quantum channel coding remain open. By combining techniques from fault-tolerant quantum computation with techniques from quantum communication, we initiate the study of these questions. We introduce fault-tolerant versions of quantum capacities quantifying the optimal communication rates achievable with asymptotically vanishing total error when the encoding and decoding circuits are affected by gate errors with small probability. Our main results are threshold theorems for the classical and quantum capacity: For every quantum channel$T$and every$\epsilon >0$there exists a threshold$p(\epsilon,T)$for the gate error probability below which rates larger than$C-\epsilon $are fault-tolerantly achievable with vanishing overall communication error, where$C$denotes the usual capacity. Our results are not only relevant in communication over large distances, but also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise than affecting the local gates.

arXiv:2009.07161•IEEE Transactions on Information Theory•Apr 21, 2022•20 citations

Design, decoding, and fault-tolerant implementation of quantum error-correcting codes

Diego Forlivesi

Quantum computation promises to revolutionize information processing by exploiting superposition and entanglement, enabling applications such as quantum simulation, combinatorial optimization, and secure quantum communication. Beyond individual processors, the quantum internet aims to connect quantum nodes through entanglement distribution, enabling distributed computation. However, quantum states are fragile: environmental interactions, imperfect gate operations, and measurement errors can quickly degrade encoded information. Reliable quantum computation therefore requires carefully designed quantum error-correcting codes and fault-tolerant protocols. Unlike classical redundancy schemes, quantum error correction must preserve delicate phase relationships and relies on indirect error detection through syndrome extraction with ancillary qubits, enabling error identification without collapsing encoded states. Topological codes, in particular, emerged early as the preferred choice for many architectures due to their planar structure, local interactions, and natural support for fault-tolerant logical operations. Color codes, for instance, allow transversal implementation of all Clifford gates, whereas non-Clifford operations require magic-state injection. More recent constructions, including quantum low-density parity-check codes, offer higher encoding rates and reduced resource overhead, but require long-range qubit connectivity and more complex protocols. Despite experimental progress, several challenges remain. Many platforms exhibit biased noise, motivating codes that exploit channel asymmetry. Real-time decoding remains a critical bottleneck, as fault-tolerant computation requires low-latency processing of rapidly generated syndrome data. Fault-tolerant logical state initialization also remains resource-intensive and scales poorly with code distance. Addressing these challenges, this thesis develops a unified framework spanning theory and experiment. It provides precise performance analysis of quantum error-correcting codes in the low physical error-rate regime, introduces codes tailored to biased noise, develops fast low-complexity decoding algorithms for real-time operation, and presents modular and efficient protocols for fault-tolerant state preparation of CSS codes. The latter is demonstrated experimentally through the preparation of a logical zero state of the Golay code on the Quantinuum H2 trapped-ion quantum computer.

•Jun 29, 2026•0 citations

Constant-Overhead Injection into Quantum Codes

Louis Golowich, Venkatesan Guruswami

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.

quant-pharXiv:2609.39345•Oct 1, 2026•0 citations

Fault-Tolerant Coding for Entanglement-Assisted Communication

Paula Belzig, Matthias Christandl, Alexander Müller‐Hermes

Channel capacities quantify the optimal rates of sending information reliably over noisy channels. Usually, the study of capacities assumes that the circuits which the sender and receiver use for encoding and decoding consist of perfectly noiseless gates. In the case of communication over quantum channels, however, this assumption is widely believed to be unrealistic, even in the long-term, due to the fragility of quantum information, which is affected by the process of decoherence. Christandl and Müller-Hermes have therefore initiated the study of fault-tolerant channel coding for quantum channels, i.e. coding schemes where encoder and decoder circuits are affected by noise, and have used techniques from fault-tolerant quantum computing to establish coding theorems for sending classical and quantum information in this scenario. Here, we extend these methods to the case of entanglement-assisted communication, in particular proving that the fault-tolerant capacity approaches the usual capacity when the gate error approaches zero. A main tool, which might be of independent interest, is the introduction of fault-tolerant entanglement distillation. We furthermore focus on the modularity of the techniques used, so that they can be easily adopted in other fault-tolerant communication scenarios.

arXiv:2210.02939•IEEE Transactions on Information Theory•Jan 15, 2024•10 citations

Fault-Tolerant Coding for Entanglement-Assisted Communication

Paula Belzig, Matthias Christandl, Alexander Müller‐Hermes

Channel capacities quantify the optimal rates of sending information reliably over noisy channels. Usually, the study of capacities assumes that the circuits which sender and receiver use for encoding and decoding consist of perfectly noiseless gates. In the case of communication over quantum channels, however, this assumption is widely believed to be unrealistic, even in the long-term, due to the fragility of quantum information, which is affected by the process of decoherence. Christandl and Müller-Hermes have therefore initiated the study of fault-tolerant channel coding for quantum channels, i.e. coding schemes where encoder and decoder circuits are affected by noise, and have used techniques from fault-tolerant quantum computing to establish coding theorems for sending classical and quantum information in this scenario. Here, we extend these methods to the case of entanglement-assisted communication, in particular proving that the fault-tolerant capacity approaches the usual capacity when the gate error approaches zero. A main tool, which might be of independent interest, is the introduction of fault-tolerant entanglement distillation. We furthermore focus on the modularity of the techniques used, so that they can be easily adopted in other fault-tolerant communication scenarios.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2023•2 citations

Quantum Codes with Addressable and Transversal Non-Clifford Gates

Zhiyang He, Vinod Vaikuntanathan, Adam Wills +1 more

The development of quantum codes with good error correction parameters and useful sets of transversal gates is a problem of major interest in quantum error-correction. Abundant prior works have studied transversal gates which are restricted to acting on all logical qubits simultaneously. In this work, we study codes that support transversal gates which induce $\textit{addressable}$ logical gates, i.e., the logical gates act on logical qubits of our choice. As we consider scaling to high-rate codes, the study and design of low-overhead, addressable logical operations presents an important problem for both theoretical and practical purposes. Our primary result is the construction of an explicit qubit code for which $\textit{any}$ triple of logical qubits across one, two, or three codeblocks can be addressed with a logical $\mathsf{CCZ}$ gate via a depth-one circuit of physical $\mathsf{CCZ}$ gates, and whose parameters are asymptotically good, up to polylogarithmic factors. The result naturally generalizes to other gates including the $\mathsf{C}^{\ell} Z$ gates for $\ell \neq 2$. Going beyond this, we develop a formalism for constructing quantum codes with $\textit{addressable and transversal}$ gates. Our framework, called $\textit{addressable orthogonality}$, encompasses the original triorthogonality framework of Bravyi and Haah (Phys. Rev. A 2012), and extends this and other frameworks to study addressable gates. We demonstrate the power of this framework with the construction of an asymptotically good qubit code for which $\textit{pre-designed}$, pairwise disjoint triples of logical qubits within a single codeblock may be addressed with a logical $\mathsf{CCZ}$ gate via a physical depth-one circuit of $\mathsf{Z}$, $\mathsf{CZ}$ and $\mathsf{CCZ}$ gates. In an appendix, we show that our framework extends to addressable and transversal $T$ gates, up to Clifford corrections.

arXiv:2502.01864•Feb 3, 2025•34 citations
Recent years have seen rapid development in the subject of quantum coding theory, with breakthroughs on many exciting classes of codes, including quantum LDPC codes, quantum locally testable codes, and quantum codes with interesting transversal gates. However, a natural class of quantum codes, which has been well-studied classically, has not yet been treated: those which can be quickly encoded and decoded. This problem concerns the channel capacity setting, where a noise channel sits between perfect encoding and unencoding/decoding operations; this is the setting that is relevant for communication between fault-tolerant quantum computers.
In this work, we construct asymptotically good quantum codes that can be encoded and unencoded by quantum circuits of logarithmic depth and consisting of a linear total number of gates. The classical decoding algorithms also run in logarithmic depth and use O(nlog⁡n)\mathcal{O}(n \log n)O(nlogn) gates, or alternatively a linear number of gates but with higher depth. We further construct explicit and asymptotically good quantum codes whose encoding, unencoding and decoding all use a linear number of gates, and additionally whose encoding and unencoding may be run in logarithmic depth.
Designing encoding and decoding circuits to reliably send messages over many uses of a noisy channel is a central problem in communication theory. When studying the optimal transmission rates achievable with asymptotically vanishing error it is usually assumed that these circuits can be implemented using noise-free gates. While this assumption is satisfied for classical machines in many scenarios, it is not expected to be satisfied in the near term future for quantum machines where decoherence leads to faults in the quantum gates. As a result, fundamental questions regarding the practical relevance of quantum channel coding remain open. By combining techniques from fault-tolerant quantum computation with techniques from quantum communication, we initiate the study of these questions. We introduce fault-tolerant versions of quantum capacities quantifying the optimal communication rates achievable with asymptotically vanishing total error when the encoding and decoding circuits are affected by gate errors with small probability. Our main results are threshold theorems for the classical and quantum capacity: For every quantum channelTTTand everyϵ>0\epsilon >0ϵ>0there exists a thresholdp(ϵ,T)p(\epsilon,T)p(ϵ,T)for the gate error probability below which rates larger than$C-\epsilon arefault−tolerantlyachievablewithvanishingoverallcommunicationerror,whereare fault-tolerantly achievable with vanishing overall communication error, wherearefault−tolerantlyachievablewithvanishingoverallcommunicationerror,whereC$denotes the usual capacity. Our results are not only relevant in communication over large distances, but also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise than affecting the local gates.
Quantum computation promises to revolutionize information processing by exploiting superposition and entanglement, enabling applications such as quantum simulation, combinatorial optimization, and secure quantum communication. Beyond individual processors, the quantum internet aims to connect quantum nodes through entanglement distribution, enabling distributed computation. However, quantum states are fragile: environmental interactions, imperfect gate operations, and measurement errors can quickly degrade encoded information. Reliable quantum computation therefore requires carefully designed quantum error-correcting codes and fault-tolerant protocols. Unlike classical redundancy schemes, quantum error correction must preserve delicate phase relationships and relies on indirect error detection through syndrome extraction with ancillary qubits, enabling error identification without collapsing encoded states. Topological codes, in particular, emerged early as the preferred choice for many architectures due to their planar structure, local interactions, and natural support for fault-tolerant logical operations. Color codes, for instance, allow transversal implementation of all Clifford gates, whereas non-Clifford operations require magic-state injection. More recent constructions, including quantum low-density parity-check codes, offer higher encoding rates and reduced resource overhead, but require long-range qubit connectivity and more complex protocols. Despite experimental progress, several challenges remain. Many platforms exhibit biased noise, motivating codes that exploit channel asymmetry. Real-time decoding remains a critical bottleneck, as fault-tolerant computation requires low-latency processing of rapidly generated syndrome data. Fault-tolerant logical state initialization also remains resource-intensive and scales poorly with code distance. Addressing these challenges, this thesis develops a unified framework spanning theory and experiment. It provides precise performance analysis of quantum error-correcting codes in the low physical error-rate regime, introduces codes tailored to biased noise, develops fast low-complexity decoding algorithms for real-time operation, and presents modular and efficient protocols for fault-tolerant state preparation of CSS codes. The latter is demonstrated experimentally through the preparation of a logical zero state of the Golay code on the Quantinuum H2 trapped-ion quantum computer.
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.
Channel capacities quantify the optimal rates of sending information reliably over noisy channels. Usually, the study of capacities assumes that the circuits which the sender and receiver use for encoding and decoding consist of perfectly noiseless gates. In the case of communication over quantum channels, however, this assumption is widely believed to be unrealistic, even in the long-term, due to the fragility of quantum information, which is affected by the process of decoherence. Christandl and Müller-Hermes have therefore initiated the study of fault-tolerant channel coding for quantum channels, i.e. coding schemes where encoder and decoder circuits are affected by noise, and have used techniques from fault-tolerant quantum computing to establish coding theorems for sending classical and quantum information in this scenario. Here, we extend these methods to the case of entanglement-assisted communication, in particular proving that the fault-tolerant capacity approaches the usual capacity when the gate error approaches zero. A main tool, which might be of independent interest, is the introduction of fault-tolerant entanglement distillation. We furthermore focus on the modularity of the techniques used, so that they can be easily adopted in other fault-tolerant communication scenarios.
Channel capacities quantify the optimal rates of sending information reliably over noisy channels. Usually, the study of capacities assumes that the circuits which sender and receiver use for encoding and decoding consist of perfectly noiseless gates. In the case of communication over quantum channels, however, this assumption is widely believed to be unrealistic, even in the long-term, due to the fragility of quantum information, which is affected by the process of decoherence. Christandl and Müller-Hermes have therefore initiated the study of fault-tolerant channel coding for quantum channels, i.e. coding schemes where encoder and decoder circuits are affected by noise, and have used techniques from fault-tolerant quantum computing to establish coding theorems for sending classical and quantum information in this scenario. Here, we extend these methods to the case of entanglement-assisted communication, in particular proving that the fault-tolerant capacity approaches the usual capacity when the gate error approaches zero. A main tool, which might be of independent interest, is the introduction of fault-tolerant entanglement distillation. We furthermore focus on the modularity of the techniques used, so that they can be easily adopted in other fault-tolerant communication scenarios.
The development of quantum codes with good error correction parameters and useful sets of transversal gates is a problem of major interest in quantum error-correction. Abundant prior works have studied transversal gates which are restricted to acting on all logical qubits simultaneously. In this work, we study codes that support transversal gates which induce addressable\textit{addressable}addressable logical gates, i.e., the logical gates act on logical qubits of our choice. As we consider scaling to high-rate codes, the study and design of low-overhead, addressable logical operations presents an important problem for both theoretical and practical purposes. Our primary result is the construction of an explicit qubit code for which any\textit{any}any triple of logical qubits across one, two, or three codeblocks can be addressed with a logical CCZ\mathsf{CCZ}CCZ gate via a depth-one circuit of physical CCZ\mathsf{CCZ}CCZ gates, and whose parameters are asymptotically good, up to polylogarithmic factors. The result naturally generalizes to other gates including the CℓZ\mathsf{C}^{\ell} ZCℓZ gates for ℓ≠2\ell \neq 2ℓ=2. Going beyond this, we develop a formalism for constructing quantum codes with addressable and transversal\textit{addressable and transversal}addressable and transversal gates. Our framework, called addressable orthogonality\textit{addressable orthogonality}addressable orthogonality, encompasses the original triorthogonality framework of Bravyi and Haah (Phys. Rev. A 2012), and extends this and other frameworks to study addressable gates. We demonstrate the power of this framework with the construction of an asymptotically good qubit code for which pre-designed\textit{pre-designed}pre-designed, pairwise disjoint triples of logical qubits within a single codeblock may be addressed with a logical CCZ\mathsf{CCZ}CCZ gate via a physical depth-one circuit of Z\mathsf{Z}Z, CZ\mathsf{CZ}CZ and CCZ\mathsf{CCZ}CCZ gates. In an appendix, we show that our framework extends to addressable and transversal TTT gates, up to Clifford corrections.