⚛️ quantum physics

Improved Quantum Codes with Transversal T Gates

This paper introduces a new framework of divisible decreasing monomial codes that constructs the first quantum CSS codes with transversal T gates achieving both constant rate and growing distance, significantly improving upon previous asymptotic parameters and magic state distillation overheads.

Original authors: Adam Wills

Published 2026-08-26

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Adam Wills

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

Building a large-scale quantum computer requires solving a problem that seems almost paradoxical: how to protect fragile information without destroying it. In the quantum world, the very act of checking for errors can scramble the data you are trying to save. To avoid this, scientists rely on a strategy called fault tolerance, where information is spread out across many physical particles, known as qubits, so that if one fails, the others can hold the line. The most efficient way to perform calculations on this distributed information is through "transversal" operations. Imagine a choir where every singer performs a specific note at the exact same time; in a quantum code, this means applying a simple gate to every physical qubit simultaneously to create a complex logical operation on the encoded data. This method is naturally safe because an error on one physical qubit cannot spread to many others during the operation. However, a fundamental law of physics, known as the Eastin-Knill theorem, dictates that no quantum code can support a complete set of universal operations using only these simple, safe transversal methods. Scientists must therefore find a way to include at least one difficult operation that breaks this rule, or find a code that supports a specific, crucial gate transversally while handling the rest through other means.

The gate at the heart of this new research is the T gate, a specific type of quantum operation that is essential for making quantum computers powerful enough to solve real-world problems. While many quantum codes can handle a set of simpler operations called Clifford gates transversally, adding the T gate has proven to be a significant hurdle. For years, the best-known families of quantum codes that could support a transversal T gate were stuck with poor performance metrics. They either had to sacrifice the amount of information they could store for the sake of error protection, or they could only protect a small amount of data. These limitations meant that to build a useful computer, one would need an impractical amount of physical hardware, creating a massive overhead that made large-scale construction seem distant. The central question for researchers has been whether it is possible to design a family of quantum codes that maintains a high rate of information storage while also growing stronger as the system gets larger, all while supporting this critical T gate without needing complex, error-prone corrections.

In this work, a researcher at the Massachusetts Institute of Technology and IBM Research has developed a new framework that significantly expands the possibilities for these codes. The study introduces a method for constructing quantum codes that support the transversal T gate with parameters that were previously thought unattainable. The researcher achieved this by adapting a class of mathematical structures known as decreasing monomial codes. These codes are built from polynomials evaluated over a grid of points, and the researcher's innovation involved carefully selecting which points to keep and which to remove, a process called puncturing. By choosing to remove points in a specific, structured pattern, the researcher was able to create logical qubits that are protected by the remaining structure. Crucially, the study proves that by using a specific type of weighted polynomial code and puncturing it at a carefully chosen set of points, one can create quantum codes that not only support the T gate but also achieve a constant rate of information storage while their error-correcting distance grows as the system scales up. This is the first time such a combination has been achieved for codes supporting the T gate without requiring additional correction steps.

The paper details two main approaches to building these codes. The first is an explicit construction, meaning the steps to build the code are clearly defined and can be followed by a computer algorithm. This method uses a variation of a well-known mathematical object called the Reed-Muller code, but with a twist: the researcher assigns different "weights" to the variables in the polynomial, effectively making some parts of the code heavier or more significant than others. By tuning these weights and the pattern of removed points, the researcher demonstrated that it is possible to create codes that store information at a steady rate while their ability to detect and correct errors improves as the system gets larger. This result is significant because it breaks a long-standing barrier where previous codes could only achieve this growth at the cost of their storage rate. The second approach is a randomized construction, which uses probability to show that even better parameters are possible, even if the specific steps to build them are not as straightforward to write down. This method involves protecting certain points from being removed by using a structure similar to a hypergraph, which acts as a shield for specific parts of the code, ensuring that the most critical information remains intact.

One of the most profound implications of these findings relates to the efficiency of magic state distillation, a process required to turn noisy quantum operations into the high-fidelity T gates needed for computation. In previous work, the efficiency of this process was limited by a specific exponent that determined how much physical resource was needed to create a single high-quality logical gate. The new codes constructed in this study allow this exponent to approach zero, meaning that the overhead required to create these essential gates becomes negligible as the system scales. This represents a dramatic improvement over the best previous results, where the overhead remained a significant fraction of the total resources. The researcher also notes that while the codes are not necessarily low-density parity-check codes, which are a popular target for hardware implementation, they can serve as a powerful logical layer on top of other codes or be used directly in architectures where the physical constraints are less rigid. The work provides a closed-form mathematical expression for the distance of these punctured codes, a result that may be useful in other areas of classical and quantum communication theory.

The study does not claim to have solved the entire problem of building a universal quantum computer, nor does it suggest that these specific codes are the only path forward. It explicitly rules out the idea that previous constructions were optimal, showing that the boundaries of what is achievable have been pushed further. The researcher acknowledges that while the explicit constructions are a major step forward, the randomized constructions suggest that even better performance might be possible, though they are harder to implement directly. The work also clarifies that the transversal T gate property holds in the strongest sense: applying the physical gate to every qubit directly produces the logical gate on every logical qubit, without needing any additional correction steps, which simplifies the fault-tolerance protocol. This clarity is a key contribution, as previous works often relied on weaker notions of transversality that required extra operations to fix errors. By establishing these new parameters, the research opens up a wider regime of possibilities for quantum code design, suggesting that the trade-offs between storage rate and error protection are not as rigid as once believed.

Ultimately, this paper offers a new blueprint for how to organize quantum information to withstand the noise of the physical world while performing the most difficult operations required for computation. By rethinking how to puncture and weight mathematical codes, the researcher has shown that it is possible to have the best of both worlds: high information density and growing error protection, all while supporting the critical T gate. The results are proven mathematically, providing a solid foundation for future work in quantum error correction. As the field moves toward building larger and more complex quantum systems, these findings suggest that the overhead costs associated with fault tolerance may be lower than previously anticipated, bringing the dream of a large-scale, fault-tolerant quantum computer one step closer to reality. The work stands as a testament to the power of mathematical structure in solving physical problems, demonstrating that with the right arrangement of information, the limitations of the quantum world can be navigated with surprising efficiency.

Problem Statement

The paper addresses the construction of asymptotic families of quantum CSS codes that support a transversal T gate. The author defines transversality in the strongest sense: applying the physical $T$ gate to every physical qubit executes the logical $T$ gate on every logical qubit without the need for subsequent Clifford corrections.

While the T gate is fundamental to fault-tolerant quantum computation (enabling universality when combined with Clifford gates), constructing quantum codes with transversal T gates has been a significant bottleneck. Previous works, notably by Hastings and Haah (2017) and Haah (2018), established the best-known asymptotic parameters for such codes. However, these parameters had not been improved since then. Furthermore, existing constructions often relied on multi-qubit transversal gates (like CCZ) or allowed Clifford corrections, whereas this work focuses strictly on single-qubit T gates without corrections. The goal is to expand the achievable regime of code rate ( $k/n$ ) and distance ( $d$ ), specifically targeting:

Improved parameters in the polynomial rate and distance regime ( $k = \Omega(n^\alpha), d = \Omega(n^\beta)$ ).
The first construction of such codes with constant rate and growing distance (sub-polynomial distance scaling).

Methodology

The author develops a framework based on divisible decreasing monomial codes punctured at a downward-closed set (a "downset") on the Boolean hypercube.

1. Classical Divisibility and Quantum CSS Construction:
The construction relies on the "X-generator matrix" formalism. To obtain a quantum CSS code with a transversal T gate, one starts with a classical binary linear code $C$ that is 8-divisible (all codewords have Hamming weights divisible by 8). By selecting a set of coordinates $\Gamma$ to puncture, the author forms a generator matrix $G$ where the logical rows correspond to the punctured coordinates. The resulting quantum code $Q[G]$ has transversal T properties if $C$ is 8-divisible and the puncturing satisfies specific non-annihilation conditions.

2. Decreasing Monomial Codes and Downsets:
The author utilizes binary monomial codes $C(\Delta)$ , where $\Delta$ is a set of monomials. They restrict $\Delta$ to be a downset (if $A \in \Delta$ and $B \subseteq A$ , then $B \in \Delta$ ).

Key Technical Lemma: The author derives a closed-form expression for the distance of a decreasing monomial code punctured at a downset $\Gamma$ . If $\Delta$ and $\Gamma$ are downsets, the distance is:
$d(C(\Delta, \Gamma)) = \min_{A \in \Delta} |\{V \subseteq \bar{A} : V \in \bar{\Gamma}\}|$
This formula allows for precise distance analysis, which was previously difficult for punctured codes.

3. Explicit Construction (Weighted Reed-Muller Codes):
To achieve high rates, the author moves beyond standard Reed-Muller codes to Weighted Reed-Muller (WRM) codes. They define a weight vector $s = (1, 1, \dots, 1, h)$ , where the last variable has a heavy weight $h$ .

By choosing $\Delta$ based on these weights and puncturing at a downset $\Gamma$ defined by low Hamming weight points (specifically subsets of the first $m-1$ variables), they construct codes that are 8-divisible.
This explicit construction allows for tuning the parameters to achieve constant rate with growing distance.

4. Randomized Construction with Protected Points:
To further improve parameters in the polynomial rate regime, the author introduces a randomized puncturing strategy.

They define a hypergraph $H$ on the first $m-1$ variables.
The puncture set $\Gamma$ is modified to "protect" certain points: a point is not punctured if it contains any hyperedge from $H$ .
This protection ensures that the distance of the dual code (and thus the quantum code) is maintained even when puncturing a large number of points, effectively preserving the code's distance while increasing the rate.
The author proves the existence of such hypergraphs with a small number of edges using probabilistic methods.

5. Concatenation:
For the randomized construction, the author concatenates their WRM-based codes with Haah's "divisible tower" codes to achieve the final optimal boundary of parameters in the polynomial regime.

Key Contributions and Results

1. Improved Polynomial Rate and Distance Regime:
The paper establishes new boundaries for the achievable exponents $(\alpha, \beta)$ where $k = \Omega(n^\alpha)$ and $d = \Omega(n^\beta)$ .

Explicit Constructions: The author derives a new function $\beta_{explicit}(\alpha)$ that strictly improves upon the Hastings-Haah boundary for $\alpha > H_2(1/6)$ .
Existential Constructions: By using the randomized construction and concatenation, they achieve a new boundary $\beta_{exist}(\alpha)$ that improves upon all prior known bounds for non-explicit families, particularly in the range $1/2 < \alpha < 1$ .

2. First Constant-Rate, Growing-Distance Codes:
The paper presents the first explicit family of quantum CSS codes with transversal T gates that achieve constant rate ( $R > 0$ ) and growing distance ( $d \to \infty$ as $n \to \infty$ ).

The distance scales as $d = \Omega(2^{(c_R + o(1))\sqrt{\log_2 n}})$ .
This is a significant breakthrough, as previous transversal T gate codes either had vanishing rate or constant distance.

3. Magic State Distillation Overhead:
The author demonstrates that the overhead exponent $\gamma = \frac{\log(n/k)}{\log(d)}$ for magic state distillation tends to zero ( $\gamma \to 0$ ) for their constructed codes.

This improves upon the previous best value of $\gamma \approx 0.678$ from Hastings and Haah.
This result holds even without allowing Clifford corrections after the transversal T gate.

4. New Mathematical Tools:

A closed-form expression for the distance of punctured decreasing monomial codes at a downset (Lemma 3.2).
A novel application of hypergraphs to "protect" points in puncturing schemes to preserve distance.

Significance and Claims

The paper claims to significantly broaden the achievable parameters for quantum codes with transversal T gates, a critical component for fault-tolerant quantum computing.

Theoretical Impact: It resolves the stagnation in parameters for transversal T gate codes that has persisted since 2017.
Practical Implications: While the codes constructed are not necessarily Low-Density Parity-Check (LDPC) codes (and thus may not be directly implementable at the physical level in all architectures), the author notes they can be used as logical-level codes for magic state distillation or as components in concatenated architectures.
Distinction from Prior Work: Unlike previous works that achieved $\gamma \to 0$ using multi-qubit gates (like CCZ), this work achieves it using single-qubit T gates. The author emphasizes that single-qubit transversal gates imply transversal addressability of lower-level Clifford hierarchy gates, a property not guaranteed by multi-qubit transversal gates.
Modesty: The author acknowledges that their explicit constructions do not improve parameters in the constant-rate regime compared to their randomized counterparts (though both are new), and that the randomized construction does not improve the constant-rate regime over the explicit one. They also note that relaxing the stabilizer code restriction might yield further improvements, but they restrict their scope to stabilizer codes due to the maturity of fault-tolerance procedures for them.

In summary, this work provides the first explicit and randomized families of quantum codes with transversal T gates that achieve constant rate with growing distance, and significantly improves the trade-off between rate and distance for polynomial regimes, thereby reducing the overhead for magic state distillation.

Problem Statement

Methodology

Key Contributions and Results

Significance and Claims

More like this