Linear-Time Encodable Quantum Codes near the CSS GV Bound

arXiv:2610.01277 · quant-ph · Submitted 2026-10-01 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai, and with me are Mira and Lev, guest researcher.

Mira: Today's paper: "Linear-Time Encodable Quantum Codes near the CSS GV Bound".

Kai: The gist: This work constructs quantum CSS codes with an extremely efficient encoder whose rate-distance tradeoff lies near the quantum CSS GV bound,

Mira: First, who's behind it and why it matters.

Paper summary: Kai: So we're talking about this paper now called "Linear-Time Encodable Quantum Codes near the CSS GV Bound," and it’s from Rachel Yun Zhang at UC Berkeley. Mira, can you give us the quick rundown on what they actually claim?

Mira: Sure. This paper constructs quantum CSS codes with a rate-distance tradeoff that approaches the CSS GV bound, which is basically the theoretical limit for how good a code can be for a given rate and distance <ref:2610.01277#pg1>. The authors suggest this can be done using a quantum circuit with logarithmic depth and only a linear number of gates <ref:2610.01277#pg1>.

Kai: Linear number of gates is really interesting for hardware because it means the encoding and decoding operations don't blow up as you go. So, what's the main idea behind this construction?

Mira: The construction is inspired by a previous work by Brehm and Resch and they view this new code as a quantum version of classical repeat multiple accumulate codes <ref:2610.01277#pg1>. They define an outer code C0, and then use an amplified code C which involves applying a classical operator L iteratively, which includes random permutations and accumulation steps <ref:2610.01277#pg3>.

Kai: So the structure itself is pretty simple, I guess? Does that mean the complexity stays low for this type of code?

Mira: The encoder for the final code C has three main parts: first, there's a constant-size circuit for C0 which needs 2s minus three CNOTs <ref:2610.01277#pg2>, then there's an accumulation operator A that runs in log(n) depth and O(n) gates <ref:2610.01277#pg3>, and finally, a derivative operator D which is just the inverse of A <ref:2610.01277#pg3>.

Kai: That sounds like a lot of classical processing layered on top of the quantum part. How does that translate to actual circuit depth?

Mira: The total encoding circuit has a depth of 2s minus three plus four m ceiling log two(n) <ref:2610.01277#pg3>, and it uses O(n) CNOT gates overall <ref:2610.01277#pg3>.

Kai: Okay, so we're looking at a linear time encoder with logarithmic depth, which is pretty efficient for what you're doing. But what about the distance? How close does this code get to that theoretical bound you mentioned?

Paper summary: Mira: The analysis focuses on the classical codes derived from this amplified code, specifically Ps(AD)m and Ps(DA)m codes <ref:2610.01277#pg3>. As the number of accumulation rounds m grows, the relative distance of our code approaches the CSS GV bound >

Lev: From a hardware standpoint, if we look at this as a practical setup, what are we really trying to achieve with these Ps(AD)m and Ps(DA)m codes?

Kai: Well, what we're trying to show is that for any even s greater than or equal to four and any small epsilon, there exists a quantum CSS code with rate R = one minus two/s that also has both X-distance and Z-distance greater than deltaCSS-GV (R) minus epsilon * n <ref:2610.01277#pg2>.

Mira: And they show that for any even s >= four and any small epsilon, there's some m greater than or equal to three such that the quantum code C has rate one minus two/s and also has both X-distance and Zdistance greater than h-one(one/s) minus epsilon * n with a probability of at least one minus Oe(n two-m) over the choice of uniformly random Pi1 <ref:2610.01277#pg2>...Pi2m <ref:2610.01277#pg3>.

Kai: So, the convergence seems pretty robust, even when we look at it from the perspective of random choices in those accumulation rounds. What's the catch there? Where does this construction stop working or what are its limitations?

Lev: The paper points out that while the relative distance approaches deltaCSS-GV as m grows, they don't actually give an explicit characterization of how fast that convergence happens <ref:2610.01277#pg4>.

Mira: And they characterize this convergence behavior by a sequence of thresholds delta(m) where delta(m) greater than or equal to delta(m-one) for all m greater than zero, which they prove from r(m)A equals zero <ref:2610.01277#pg4>.

Kai: And what about the expected number of codewords that are good enough? Does it get sparse quickly?

Mira: They show that the expected number of codewords with weight below (delta(m) minus epsilon)n is an inverse polynomial function, which means it decays to zero as n gets bigger <ref:2610.01277#pg5>. Specifically, for m greater than or equal to two the expected number of codewords of a Ps(DA)m code that have weight equal to three is bounded by O˜(n(two-m)) <ref:2610.01277#pg5>.

Paper summary: Lev: So, if you were running this on real hardware, what does that mean for the feasibility of achieving these distance bounds? Is it something we can actually implement with current noise levels?

Kai: It means the complexity of encoding and unencoding is low, with linear gates and logarithmic depth <ref:2610.01277#pg1>, which makes it much more viable than codes that require exponential resources for those operations. The paper suggests this structure is highly desirable for tasks like running error correction at the logical level <ref:2610.01277#pg3>.

Mira: And they bound the boundary contribution terms by negl(n), which means the expected number of nonzero codewords with certain weights stays very small after m-one rounds and stays below negl(n) after m rounds <ref:2610.01277#pg5>. This suggests the code structure is well-behaved even near its limits.

Lev: So, to sum up, this paper presents a construction of a quantum CSS code with a linear time encoder and logarithmic depth that gets very close to the CSS GV bound as you run more accumulation rounds <ref:2610.01277#pg4>.

Kai: It’s really about showing that you can get near the best theoretical limits using a structure that is simple enough to actually build with manageable resources <ref:2610.01277#pg3>. Where does this leave us for future work on these codes?

Mira: The authors focused on proving convergence and bounding contributions, but they don't give an explicit characterization of the rate at which the relative distance approaches deltaCSS-GV as m grows <ref:2610.01277#pg4>. That would be a natural next step for further theoretical analysis.

Lev: I think that makes sense; understanding exactly how fast that convergence happens is crucial for predicting performance in noisy environments. It connects the abstract bound to something more concrete about practical performance on real hardware <ref:2610.01277#pg4>.

Kai: So, we've seen a construction with linear time encoding and logarithmic depth that targets the CSS GV bound by using iterative accumulation layers, and the key is how those rounds m affect the distance convergence <ref:2610.01277#pg3>. That’s what they’re showing us about this paper.

Conclusion: Kai: So we're wrapping up this look at the paper "Linear-Time Encodable Quantum Codes near the CSS GV Bound."

Mira: Basically, they’ve built a quantum code where you can encode and decode it in a linear number of gates and with only logarithmic depth.

Lev: That’s the main thing to pull out: linear time encoding for quantum error correction.

Kai: The authors are showing how you can get right near that CSS GV bound, which is the theoretical limit for how well a code can do at a certain rate.

Mira: They achieve this by using an iterative accumulation process with these random permutations they call the operator L.

Lev: What this means practically is that we're looking at a construction that’s feasible in terms of circuit complexity, not just theoretical bounds.

Kai: It's about showing that you don't need exponentially growing resources for the encoding part if you use these accumulation rounds correctly.

Mira: The convergence to the bound happens as you increase those accumulation rounds m, which is what they call the number of times you apply this L operator.

Lev: But there’s a catch, because they don't give us a precise formula for *how fast* that convergence actually speeds up.

Kai: That’s the missing piece we need to figure out, how quickly these rounds m translate into distance improvement on real hardware.

Mira: So, the authors have shown a very efficient way to build these codes, but they haven't fully mapped out the speed of that convergence yet.

Rachel Yun Zhang

UC Berkeley

quant-ph

Submitted: 2026-10-01

Updated: 2026-10-01

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 81/100

The gist: The gist: This work constructs quantum CSS codes with an extremely efficient encoder whose rate-distance tradeoff lies near the quantum CSS GV bound, achievable by a linear number of gates and

Key concepts

Outer Code C0: This is the initial CSS code constructed on n qubits with k logical qubits, where k is determined by s (an even integer >= 4). It serves as the base structure upon which the final amplified code C is built, defining its fundamental properties.
Amplified Code UL C0: The final quantum code C is formed by applying an operator UL to the outer code C0. This operator involves iteratively applying random permutations, accumulation, and derivatives multiple times (m rounds), which enhances the code's distance properties.
Accumulation Operator (A) and Derivative Operator (D): The encoding circuit uses these two operators. The Accumulation Operator computes running prefix-sums in log(n) depth with O(n) gates, while the Derivative Operator is its inverse, implemented by running the prefix circuit backwards. This structure allows for a linear time encoding circuit.
CSS GV Bound: This bound represents the theoretical limit on how well a quantum CSS code can achieve distance relative to its rate. The paper shows that their constructed code's relative distance approaches this bound as the number of accumulation rounds (m) increases.

Terminology

Entanglement — 6× in this paper · explained in 4 episodes
CSS Codes — 4× in this paper · explained in 2 episodes
Ancilla Qubits — 2× in this paper · explained in 1 episode
Adam — 1× in this paper · explained in 2 episodes
Decode — 1× in this paper · explained in 2 episodes
Quantum Circuits — 1× in this paper · explained in 2 episodes
Verification — 1× in this paper · explained in 2 episodes

Summary

The gist: This work constructs quantum CSS codes with an extremely efficient encoder whose rate-distance tradeoff lies near the quantum CSS GV bound, achievable by a linear number of gates and logarithmic depth.

Code Construction and Encoder Structure

The construction begins by defining an outer code C0, which is a CSS code on n qubits with k = (1 − 2/s) · n logical qubits, where s is an even integer such that s >= 4. The outer encoder for C0 is defined using the parity code Ps of block length s, resulting in X and Z stabilizers Sx = LS0x and Sz = L−⊤S0z. The amplified code C is then defined as C = UL C0, where UL implements the classical operator L which iteratively applies a random permutation then an accumulation, then a random permutation then a derivative, and repeats m times.

Linear Time Encoding Circuit

The encoder for the final code C consists of three main parts:

Encoder for C0: This is implemented by a constant-size circuit consisting of 2s − 3 CNOTs.
Accumulation Operator (A): This operator computes running prefix-sums, which can be computed in log(n) depth and O(n) gates.
Derivative Operator (D): Defined as the inverse of A, it can be implemented by running the PREFIX(n) circuit backwards.

The total encoding circuit has a depth of 2s − 3 + 4m⌈log2(n)⌉ and consists of O(n) CNOT gates.

Distance Analysis and Convergence to GV Bound

The analysis focuses on the distance of classical codes derived from the amplified code, specifically Ps(AD)m and Ps(DA)m codes. The relative distance approaches the CSS GV bound as the number of accumulation rounds m grows.

)&Theorem 2.1 states that for any even s >= 4 and ε > 0, there is a quantum CSS code with rate R = 1 − 2/s and also has both X-distance and Z-distance >= (δCSS−GV (R) − ε) · n. The encoding circuit acts on (1 − 2/s)n logical qubits and n/s0⟩ and n/s+⟩ ancilla qubits, has depth O(log n), and consists of O(n) CNOT gates. Corollary 2.2 states that for any even s >= 4 and ε > 0, there is some m >= 3 such that the quantum code C has rate 1 − 2/s and also has both X-distance and Zdistance >= h−1(1/s) − ε · n with probability >= 1 − Oe(n 2−m) over the choice of uniformly random Π1,..., Π2m. The relative distance of our code approaches δCSS−GV as the number m of accumulation rounds grows, but we do not give an explicit characterization of the rate of convergence. In Figure 1, we numerically estimate the distances of our quantum code for a few code rates and number of encoding rounds. We see that after just 4 encoding rounds, the relative distance of our code is within 0.001 of the CSS GV bound; after 6, it is within 10−7.

Convergence Thresholds and Distance Bounds

The convergence behavior is characterized by a sequence of thresholds δ(m).

**)&Theorem 4.2 states that δ(m) >= δ(m-1) for all m > 0. The proof follows from r(m)A = 0. **

Expected Number of Codewords

The expected number of codewords with weight below (δ(m) − ε)n is shown to be an inverse polynomial function, decaying to 0 with n.

)&Theorem 5.1 states that for m >= 2, the expected number of codewords of a Ps(DA)m code that have weight = 3, the expected number of codewords of a Ps(AD)m code that have weight <= (δ(m) − ε)n after m rounds is <= O˜(n(2−m)).

Boundary Contribution Analysis

The boundary contribution terms are bounded by negl(n).

)&Theorem 5.2 states that let ε > 0 and m >= 1, and let τ = log2(n)/n. The expected number of nonzero codewords of a Ps(AD)m or Ps(DA)m code that have weight between τn and (1 − τ)n after m − 1 rounds and weight = (1 − δ(m) + ε)n after m rounds is <= negl(n).

This work provides a construction of a quantum CSS code with an extremely efficient encoder, whose rate-distance tradeoff lies near the quantum CSS GV bound, achievable by a linear number of gates and logarithmic depth. The distance analysis shows that the relative distance approaches the CSS GV bound as the number of accumulation rounds m grows. The construction is characterized by a linear time encoder, which is highly desirable for low complexity encoding and unencoding tasks.

References

[AT11] Mamdouh Abbara and Jean-Pierre Tillich. The minimum distance of classical and quantum turbo-codes, 2011. 4

[BCF+25] Martijn Brehm, Binyi Chen, Ben Fisch, Nicolas Resch, Ron D. Rothblum, and Hadas Zeilberger. Blaze: Fast snarks from interleaved raa codes. In Advances in Cryptology – EUROCRYPT 2025: 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4–8, 2025, Proceedings, Part IV, page 123–152.

[BDMP98] S. Benedetto, D. Divsalar, G. Montorsi, and F. Pollara. Serial concatenation of interleaved codes: performance analysis, design, and iterative decoding. IEEE Transactions on Information Theory, 44(3):909–926.

[Bec75] William Beckner. Inequalities in fourier analysis. Annals of Mathematics, 102(1):159–182.

[BMS09] Louay Bazzi, Mohammad Mahdian, and Daniel A. Spielman. The minimum distance of turbo-like codes. IEEE Transactions on Information Theory, 55(1):6–15.

[BR26] Martijn Brehm and Nicolas Resch. Linear Time Encodable Binary Code Achieving GV Bound with Linear Time Encodable Dual Achieving GV Bound. In Shubhangi Saraf, editor, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:19.

[CS96] A. R. Calderbank and Peter W. Shor. Good quantum error-correcting codes exist. Phys. Rev. A, 54:1098–1105.

[DJM98] Dariush Divsalar, Hui Jin, and Robert J McEliece. Coding theorems for “turbo-like” codes. In Proceedings of the annual Allerton Conference on Communication control and Computing, 36:201–210.

[FR08] Fabio Fagnani and Chiara Ravazzi. Spectra and minimum distances of repeat multiple accumulate codes. In 2008 Information Theory and Applications Workshop, pages 77–86.

[HW13] Monireh Houshmand and Mark M. Wilde. Recursive quantum convolutional encoders are catastrophic: A simple proof. IEEE Transactions on Information Theory, 59(10):6724–6731.

[IAB09] Alexandre Graell I Amat and Raphael Le Bidan. Minimum distance and convergence analysis of hamming-accumulate-accumulate codes. IEEE Transactions on Communications, 57(12):3518–3523.

[IAR09] Alexandre Graell I Amat and Eirik Rosnes. Good concatenated code ensembles for the binary erasure channel. IEEE Journal on Selected Areas in Communications, 27(6):928–943.

[KFL01] F.R. Kschischang, B.

Improvements for AI systems

AI systems can be designed to execute quantum error-correcting encoding/decoding operations with linear time complexity and logarithmic depth using a circuit of O(n) CNOT gates for constructing quantum CSS codes.
The improved system can achieve a rate-distance tradeoff that approaches the CSS GV bound, enabling near-optimal performance for quantum codes based on an iterative encoder structure.
The system can leverage the structure of classical repeat multiple accumulate (RMA) codes, by utilizing interleaving of accumulation and derivative rounds to construct quantum codes with good distance properties, as seen in the analysis of Ps(AD)m and Ps(DA)m codes.
The system can perform high-speed encoding/decoding for logical qubits encoded in a code with rate R = 1 − 2/s, where s is an even integer greater than or equal to 4, with convergence to the GV bound demonstrated after just 4 encoding rounds numerically.
The AI can estimate the required number of encoding rounds 'm' needed for a desired relative distance (e.g., within 0.001 of the CSS GV bound), as suggested by Figure 1 in Section 4, providing practical guidance on circuit depth and gate count.
The system can analyze the spectral shape functions, such as r(m)AD(γ), to predict the asymptotic behavior of code distances, allowing for pre-computation of convergence rates based on the recursion defined in Definition 3.2.
The AI can determine a threshold distance δ(m) below which there are sub-exponentially many codewords in Ps(A)m codes, providing a metric to quantify the practical reliability of the code after 'm' rounds of iterative application.

Abstract

We construct quantum CSS codes with rate-distance tradeoff approaching the CSS GV bound, which can be encoded by a quantum circuit of logarithmic depth and a linear number of gates. Our construction is heavily inspired by a work of Brehm and Resch and can be viewed as a quantum analogue of classical repeat multiple accumulate codes. The encoder has a particularly simple structure, consisting of a single constant depth outer quantum circuit followed by several classical accumulation and inverse-accumulation layers.

Sources

Coding Theorems for Repeat Multiple Accumulate Codes