⚛️ quantum physics

Linear-Time Encodable Quantum Codes near the CSS GV Bound

This paper presents a construction of quantum CSS codes that approach the CSS GV bound with linear-time encodability, featuring a simple architecture inspired by Brehm and Resch that combines a constant-depth outer circuit with classical accumulation layers.

Original authors: Rachel Yun Zhang

Published 2026-10-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rachel Yun Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computing, information is often fragile. A single bit of data, a simple 0 or 1, can flip due to heat, radiation, or electrical noise, corrupting the message it carries. To protect against this, scientists use error-correcting codes, which act like a safety net, adding extra bits of information so that if some are lost or changed, the original message can still be recovered. This concept is vital for classical computers, but it becomes exponentially more difficult when applied to quantum computers. Quantum bits, or qubits, are far more sensitive than their classical counterparts, and the rules of quantum mechanics prevent them from being copied or measured directly without destroying their state. For quantum computers to become practical, they need codes that can not only protect this delicate information but also do so quickly, without requiring a massive amount of time or hardware to set up.

The challenge has been finding a balance between how much information a code can hold and how well it can protect that information. Theoretical limits, known as bounds, suggest that it is possible to have codes that are both efficient and highly protective, but creating a physical system that reaches these limits has been a stumbling block. Previous attempts at building fast quantum codes often resulted in systems that were either too weak to be useful or too complex to be built. The goal has long been to construct a quantum code that approaches the best possible theoretical performance while remaining simple enough to be encoded by a circuit that is both small and fast.

A researcher has now constructed a new type of quantum code that comes remarkably close to this ideal. Their work focuses on a specific family of quantum codes, which function by organizing information into two distinct layers of protection. The researcher designed a method to build these codes using a process that is surprisingly simple and fast. Instead of a complex, tangled web of operations, their system uses a straightforward sequence of steps: it starts with a basic block of information, repeats parts of it, and then shuffles and combines the data in a specific, repeating pattern. This pattern involves two main actions: one that adds up values in a running total, and another that calculates the difference between adjacent values. By alternating these actions with random shuffles, the system amplifies the code's ability to detect and correct errors.

The most significant finding is that this simple, repetitive process produces a code that is nearly as good as the best possible code allowed by the laws of physics. The researcher proved mathematically that as they increase the number of times they repeat this shuffling and combining process, the code's ability to resist errors improves rapidly, approaching the theoretical maximum limit. In practical terms, this means that with just a few rounds of this process, the code becomes incredibly robust. For example, after only four rounds of this encoding process, the code's ability to correct errors is within a tiny fraction of the absolute best possible performance. After six rounds, it is virtually indistinguishable from that perfect limit.

Crucially, this high level of protection does not come at the cost of speed or complexity. The researcher demonstrated that their code can be encoded using a quantum circuit that is both small and shallow. The circuit requires a number of basic operations that grows only linearly with the size of the data, meaning it does not explode in complexity as the data gets larger. Furthermore, the depth of the circuit, which corresponds to the time it takes to run, grows only logarithmically. This is a massive improvement over previous methods, which often required circuits that were too deep to be practical for large amounts of data. The entire system can be built using a standard set of quantum logic gates, making it a viable candidate for future quantum hardware.

The construction of this code was inspired by a similar technique used in classical computing, known as repeat-accumulate codes, but the researcher had to adapt the method significantly to work in the quantum realm. A direct translation of the classical method failed because it produced codes that were too weak to protect quantum information. The researcher solved this by interleaving the standard accumulation steps with a "derivative" step, which calculates the difference between adjacent bits. This addition ensures that the code remains strong even when viewed from the perspective of its dual, a necessary condition for quantum stability. They also replaced a simple repetition step with a more sophisticated parity check, which allows the code to carry more information while maintaining its protective strength.

The researcher did not stop at theoretical proofs; they also ran numerical simulations to verify their findings. These simulations confirmed that the code performs exactly as predicted, with the distance between valid and invalid states growing quickly as the number of encoding rounds increases. The results show that the code is not just a theoretical curiosity but a practical solution that can be implemented with current or near-future technology. The work represents a significant milestone, as the researcher is the first to prove that a quantum code with an iterated encoder can achieve good, near-optimal distance (specifically near the CSS GV bound) for a specific ensemble. This breakthrough suggests that the long-standing barrier of creating fast, high-performance quantum codes is surmountable for specific ensembles, opening the door to more reliable and scalable quantum computers. By proving that a simple, iterative process can achieve near-optimal protection, the researcher has provided a clear path forward for the engineering of quantum systems that can operate reliably in the real world.

Technical Summary: Linear-Time Encodable Quantum Codes near the CSS GV Bound

Problem Statement
The paper addresses the challenge of constructing quantum error-correcting codes that are both asymptotically good (approaching the optimal tradeoff between rate and distance) and efficiently encodable. While previous work by [WLZH26] demonstrated quantum codes with linear-time encoding, their rate-distance tradeoffs were suboptimal, depending heavily on the underlying expander graphs and remaining far from the Gilbert-Varshamov (GV) bound. The goal is to construct a Quantum CSS code that achieves a rate-distance tradeoff approaching the CSS GV bound while maintaining an encoding circuit of linear size and logarithmic depth.

Methodology
The author proposes a construction inspired by classical Repeat Multiple Accumulate (RMA) codes, specifically adapting the work of Brehm and Resch [BR26] on classical codes with interleaved accumulation and derivative rounds.

Code Structure (CSS Construction):
The code is a CSS (Calderbank-Shor-Steane) code defined by two sets of stabilizers:
- Outer Code ( $C_0$ ): A classical code constructed from $n/s$ blocks of an $s$ -parity code ( $P_s$ ), where $s \ge 4$ is an even integer. This outer code has rate $1 - 1/s$ .
- Amplification: The distance is amplified by applying a sequence of unitary operators corresponding to random permutations ( $\Pi_i$ ) and classical linear operators: Accumulation ( $A$ , a prefix-sum matrix) and Derivative ( $D$ , the inverse of $A$ ).
- Interleaving: The construction interleaves $m$ $m$ rounds of "permuted accumulation" and "permuted derivative" operations.
  - The $X$ -stabilizers correspond to a classical code $P_s(AD)_m$ , formed by applying $m$ rounds of $A$ then $D$ (with permutations) to the outer code.
  - The $Z$ -stabilizers correspond to a classical code $P_s(DA)_m$ , formed by applying $m$ rounds of $D$ then $A$ (with permutations).
- Quantum Encoding: The author demonstrates that the quantum code can be encoded by first applying a constant-depth quantum outer encoder (encoding the logical qubits into the coset superpositions of $C_0$ ) followed by the interleaved accumulation and derivative layers.
Distance Analysis:
The analysis focuses on the weight enumerators of the classical codes $P_s(AD)_m$ and $P_s(DA)_m$ .
- Spectral Shape Analysis: The author defines asymptotic spectral shape functions $r^{(m)}(\gamma)$ that bound the logarithm of the expected number of codewords of a given relative weight $\gamma$ .
- Recursion: They establish recursive relations for these spectral shapes based on the transition probabilities of the accumulation and derivative operators under random permutations.
- Convergence: They prove that as the number of rounds $m$ increases, the threshold $\delta(m)$ (below which the spectral shape is non-positive) converges to $\delta_{GV}$ , the relative distance satisfying the CSS GV bound equation $h(\delta_{GV}) = 1/s$ .
- Bounding Contributions: To show that the actual distance approaches $\delta(m)$ , the author splits the weight enumerator analysis into "middle" contributions (weights bounded away from 0 and $n$ ) and "boundary" contributions (weights very close to 0 or $n$ ). They prove that the expected number of low-weight codewords in both regions decays polynomially or exponentially with the block length $n$ .

Key Contributions

Construction of Near-Optimal Quantum Codes: The paper constructs a family of quantum CSS codes with rate $R = 1 - 2/s$ and relative distance approaching $\delta_{CSS-GV}(R) = h^{-1}((1-R)/2)$ .
Linear-Time Encodability: The encoding circuit has a size of $O(n)$ and a depth of $O(\log n)$ . Specifically, the depth is $O(s + m \log n)$ , and the gate count is $O(n)$ .
Generalization of Classical Results: The work extends the analysis of [BR26] from 2-repetition outer codes to $s$ -parity outer codes ( $s \ge 4$ ), enabling the construction of quantum codes with non-zero logical qubit rates.
Correction of Prior Proofs: The author identifies and corrects bugs in the proofs of [BR26] regarding the boundary contributions of the weight enumerators, providing rigorous bounds that account for ceiling and floor functions in the transition probabilities.

Results

Theorem 1.1: For any even $s \ge 4$ and $\epsilon > 0$ , there exists a quantum CSS code with rate $R = 1 - 2/s$ and both $X$ and $Z$ distances $\ge (\delta_{CSS-GV}(R) - \epsilon) \cdot n$ . The encoding circuit uses $O(n)$ CNOT gates and has depth $O(\log n)$ .
Convergence Speed: Numerical estimates presented in the paper suggest rapid convergence. For example, with $s=4$ and $m=4$ encoding rounds, the relative distance is within $0.001$ of the CSS GV bound; with $m=6$ , it is within $10^{-7}$ .
Probabilistic Guarantee: The distance guarantees hold with high probability ( $1 - e^{-\Omega(n^{k})}$ ) over the choice of random permutations, where $k$ depends on $m$ .

Significance
The paper claims to be the first to prove that a quantum code with an iterated encoder (specifically, one based on accumulation and derivative rounds) achieves a distance near the CSS GV bound. While previous attempts to quantize RMA codes failed due to poor dual code distances, this work successfully balances the $X$ and $Z$ stabilizer distances by interleaving accumulation and derivative operations. The result is a code that is not only asymptotically good but also practically efficient to encode, addressing a critical bottleneck in quantum error correction where low-complexity encoding is necessary to prevent overhead blowup in logical operations. The work does not address decoding complexity, noting that while belief propagation techniques exist for classical RMA codes, their extension to this quantum setting remains an open question.

Technical Summary: Linear-Time Encodable Quantum Codes near the CSS GV Bound

More like this