Cyclic triorthogonal codes in prime dimension

AI summary

Overview

Research area: Quantum error correction and magic state distillation, specifically algebraic constructions of triorthogonal quantum codes from cyclic codes over prime fields.
Technical level: Advanced. The paper uses finite-field theory, cyclotomic cosets, spectral supports of cyclic codes, and CSS stabilizer formalism.
Scope: The paper characterizes cyclic triorthogonal codes in prime dimension via sumset conditions on their spectral support, enumerates small examples, proves a qubit classification theorem, and computes distillation thresholds and overhead exponents.

What This Paper Is About

Triorthogonal codes are CSS codes in which a transversal third-level diagonal gate implements a logical non-Clifford gate, making them central to magic state distillation. Small explicit examples are scarce, especially for qudits, so the paper asks whether cyclic codes in prime dimension can supply systematic constructions. The goal is to reduce triorthogonality for cyclic codes to a simple condition on Fourier frequencies, use that condition to search exhaustively for good small codes, and evaluate their distillation performance.

Key Contributions

1. A spectral sumset criterion for cyclic triorthogonality. For cyclic codes of length (n) with (p \nmid n), triorthogonality is expressed as a condition on the spectral support (S \subseteq \mathbb{Z}_n). Construction A requires (0 \notin S \cup 2S \cup 3S); construction B requires (0 \notin 3S). This makes exhaustive search over unions of cyclotomic cosets feasible.

2. A triorthogonality definition for odd (p) that does not require self-orthogonality. The paper gives a self-contained proof that this weaker definition still yields a transversal non-Clifford gate, separately for (p \geq 5) and (p = 3). The weaker definition matters: the ([[19,1,3]]_3) code is not self-orthogonal, and requiring self-orthogonality would raise the shortest cyclic distance-3 qutrit code to length 39.

3. Complete enumeration and new code families. The paper enumerates all maximal codes from the two constructions for (p=3) up to length 121 and for (p=5,7) up to length 96, certifying every distance exactly or as a rigorous lower bound. It identifies codes such as ([[19,1,3]]_3) and ([[7,1,3]]_7), the latter being the first member of an infinite family ([[p,1,2\lfloor p/6\rfloor+1]]_p) for every prime (p \geq 7).

4. A qubit classification theorem and a full determination of triply-even cyclic codes. For binary cyclic codes of odd length, the paper proves that being triply even is equivalent to being classically triorthogonal, equivalently (0 \notin 3S). It determines all such codes up to length 763.

Main Findings

• Triorthogonality becomes a sumset avoidance condition. For construction A, the stabilizer space is a cyclic code with the all-ones logical row, and triorthogonality holds exactly when (0 \notin S), (0 \notin 2S), and (0 \notin 3S). For construction B, a cyclic space is punctured at one coordinate, and triorthogonality holds exactly when (0 \notin 3S).

• The spectral criterion simplifies for small primes. For (p=2), construction A reduces to (0 \notin 3S); for (p=3), it reduces to (0 \notin 2S \cup 3S). For (p \geq 5), no such general inclusion holds.

• The weaker odd-(p) definition is sufficient for a transversal gate. For (p \geq 5), the transversal cubic gate implements (\bigotimes_i U^{\lambda_i}) exactly, with no correction. For (p=3), the transversal gate implements the logical gate up to a fixed Pauli correction and a logical Pauli.

• The ([[19,1,3]]_3) code improves on existing qutrit codes. It improves on the shortest Reed–Muller and Reed–Solomon codes in both overhead exponent and distillation threshold.

• The ([[7,1,3]]_7) code is much shorter than the comparable Reed–Muller code. It is less than a sixth of the length of ([[48,1,4]]_7), described as the shortest punctured Reed–Muller code with (d \geq 3).

• An infinite family exists for every prime (p \geq 7). The family is ([[p,1,2\lfloor p/6\rfloor+1]]_p), with ([[7,1,3]]_7) as its first member. The paper states that this family has not previously been identified as triorthogonal as far as the author knows.

• For (p=5), cyclic codes give no advantage. The paper finds that cyclic codes provide no advantage over recursive use of the ([[4,1,2]]_5) Reed–Solomon code.

• Qubit cyclic codes have a clean classification. A cyclic code of odd length is triply even if and only if it is classically triorthogonal, i.e., if and only if (0 \notin 3S). Every union of cyclotomic cosets with (0 \notin 3S) gives a triply-even code, and the transversal (T) gate acts exactly with no Clifford correction.

• The enumeration covers substantial ranges. For (p=3), all maximal construction-A and construction-B codes are enumerated up to length 121; for (p=5,7), up to length 96. All triply-even cyclic codes of odd length are determined up to length 763.

Methodology in Plain English

The paper works with cyclic codes, which are error-correcting codes invariant under cyclic shifts of their coordinates. Such a code can be described by its spectral support: the set (S) of Fourier frequencies at which codewords are allowed to be nonzero. Coordinatewise products of cyclic codes remain cyclic, and the spectral support of the (t)-fold product is the sumset (tS = S + \cdots + S).

Triorthogonality requires certain coordinate sums of products of codewords to vanish. A cyclic code has all coordinate sums equal to zero exactly when (0) is not in its spectral support. Therefore, triorthogonality reduces to checking that (0) avoids certain sumsets of (S), such as (S \cup 2S \cup 3S) or (3S).

Because every cyclic code is a union of cyclotomic cosets, the search space is finite and structured. The author enumerates all such unions satisfying the relevant sumset condition, computes the resulting code distances, and certifies each distance either exactly or with a rigorous lower bound. Distillation thresholds and overhead exponents are then computed from the resulting codes.

Why This Matters

This work gives a systematic way to find small triorthogonal codes, which are the building blocks of magic state distillation protocols for non-Clifford gates. By extending the analysis from qubits to prime-dimensional qudits, it opens a route to lower-overhead fault-tolerant quantum computation in qudit architectures.

Impact on research: The paper connects cyclic-code theory, spectral methods, and triorthogonality, and it supplies explicit small codes and infinite families that can be benchmarked against Reed–Muller and Reed–Solomon constructions. It also addresses the (q)-ary case left open in prior work on cyclic CSS-T codes.

Real-world applications:

• Fault-tolerant quantum computing: Magic state distillation is needed to implement non-Clifford gates fault-tolerantly; shorter codes reduce physical resource requirements.
• Qudit-based quantum processors: Codes such as ([[19,1,3]]_3) and ([[7,1,3]]_7) target qutrit and septit hardware, where higher-dimensional units can reduce overhead.
• Quantum architecture and resource estimation: Distillation thresholds and overhead exponents inform hardware design and compilation strategies.
• Error-correction code catalogs: The exhaustive enumeration provides a reference set of small cyclic triorthogonal codes for future protocol design.

Industry relevance: Quantum computing companies and research groups working on fault-tolerant architectures, especially those pursuing qudit platforms or magic-state factories, can use these codes and criteria to reduce distillation overhead.

Future Directions

• Prove converses and complete the classification. The paper states that a fuller treatment, including converses of the main transversal-gate theorems, will be given elsewhere.
• Extend the exhaustive search. Longer lengths, additional primes, and other cyclic or extended-cyclic constructions could yield further codes, especially for (p=5), where cyclic codes showed no advantage over recursive Reed–Solomon.
• Develop distillation protocols from the new codes. The threshold and overhead calculations can be turned into explicit injection and distillation circuits for the ([[19,1,3]]_3), ([[7,1,3]]_7), and infinite-family codes.
• Connect to broader code families. The spectral sumset approach may extend to matrix-product codes, concatenated codes, and other CSS-T constructions beyond the two considered here.

Target Audience

This paper is most useful to researchers and graduate students in quantum error correction, quantum information theory, and algebraic coding theory. It also benefits fault-tolerant quantum computing architects and engineers who need small, explicit codes for magic state distillation, particularly those working with qudit-based hardware.

Authors’ abstract

We study cyclic triorthogonal codes in prime dimension $p$, on which a transversal third-level diagonal gate acts as a logical non-Clifford gate. For odd $p$, we use a definition of triorthogonality that does not require self-orthogonality. For cyclic codes of length coprime to $p$, triorthogonality reduces to a sumset condition on the spectral support, which makes exhaustive search feasible: for two natural constructions, we enumerate all maximal codes of this kind for $p=3$ up to length $121$ and $p=5,7$ up to length $96$. For qubits, we prove that a cyclic code of odd length is triply even if and only if it is classically triorthogonal, giving a complete description of triply-even cyclic codes, and we determine all such codes up to length $763$. For qudits, we find codes such as $[[19,1,3]]_3$ and $[[7,1,3]]_7$, which improve on the shortest Reed-Muller and Reed-Solomon codes in both overhead exponent and distillation threshold. The latter is the first member of an infinite family of $[[p,1,2\lfloor p/6\rfloor+1]]_p$ codes.