PaperlayerView exact revision on arXiv

Source-linked AI summary

Cyclic triorthogonal codes in prime dimension

Shiroman Prakash

arXiv:2610.08012v1quant-phcs.ITmath.IT

TL;DR

Small explicit triorthogonal-code examples, particularly for qudits, are comparatively scarce despite their role in magic-state distillation. This paper uses spectral-support sumset criteria to search cyclic codes and characterize triply-even cyclic codes; it finds qudit codes that improve on named Reed–Muller and Reed–Solomon comparisons, along with an infinite family for primes p ≥ 7.

  • Problem

    Small explicit triorthogonal-code examples are comparatively scarce, particularly for qudits, though these codes underlie magic-state distillation protocols.

    Source: §1 · p. 1

  • Method

    For cyclic codes of length coprime to p, the paper translates triorthogonality into spectral-support sumset conditions and searches two constructions, using a definition for odd p that does not require self-orthogonality.

    Source: §1 · pp. 1–2

  • Results

    The [[19, 1, 3]]3 and [[7, 1, 3]]7 codes improve on the shortest Reed–Muller and Reed–Solomon codes in overhead exponent and distillation threshold.

    Source: §1 · p. 2

  • Takeaways & Limitations

    For every prime p ≥ 7, the criteria also yield an infinite family of [[p, 1, 2⌊p/6⌋+1]]p codes.

    Source: §9 · p. 16

    The reported thresholds assume depolarizing noise, and single-round thresholds and γ do not by themselves determine full-protocol overhead.

    Source: §8 · p. 16

Abstract

from arXiv · show

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.

1 Introduction

Cyclic triorthogonality can be tested through sumsets of spectral supports, enabling systematic searches for small codes in prime dimensions. The paper characterizes triply-even cyclic codes for qubits and finds qudit codes and families with strong distance and distillation results.

1 Introduction

  • For cyclic codes of length coprime to p, triorthogonality reduces to checking whether 0 lies in specified sumsets of the spectral support.Coordinatewise products of cyclic codes correspond to sums of their frequencies.Source: §1 · p. 1
  • For odd p, the paper's triorthogonality definition does not require self-orthogonality, allowing the [[19, 1, 3]]3 code; imposing it would raise the shortest cyclic distance-3 qutrit code to length 39.The two constructions use 0 ∉ S ∪ 2S ∪ 3S and 0 ∉ 3S, respectively.Source: §1 · p. 2
  • For odd-length cyclic binary codes, triply even is equivalent to classical triorthogonality, characterized by 0 ∉ 3S; the paper determines all such codes up to length 763.The resulting transversal T gate acts exactly, with no Clifford correction.Source: §1 · p. 2
  • The search covers p = 3 through length 121 and p = 5, 7 through length 96, and finds [[19, 1, 3]]3 and [[7, 1, 3]]7 codes that improve on the shortest Reed–Muller and Reed–Solomon codes in overhead exponent and distillation threshold.For p = 5, cyclic codes provide no advantage over recursive use of the [[4, 1, 2]]5 Reed–Solomon code.Source: §1 · p. 2
  • For every prime p ≥ 7, the criteria yield an infinite family of [[p, 1, 2⌊p/6⌋+1]]p codes, beginning with [[7, 1, 3]]7.The paper reports that this family had not previously been identified as triorthogonal, to the authors' knowledge.Source: §1 · p. 2
  • The paper focuses on small codes for small primes, distinct from cyclic quadratic-residue protocols that distill Clifford-eigenstate magic states and asymptotically good constructions targeting overhead.The codes studied here distill states produced by a transversal non-Clifford gate; earlier searched cyclic-column-symmetry examples were all distance 3.Source: §1 · pp. 2–3

2 Preliminaries: Cyclic codes over Fp and spectral support

For lengths coprime to p, cyclic codes can be described by their spectral supports, sets of frequencies that determine which vectors belong to the code. In this description, coordinatewise products and coordinate-sum conditions become support operations and tests.

2 Preliminaries: Cyclic codes over Fp and spectral support

  • A cyclic code of length n with p ∤ n is an ideal generated by a divisor of x^n − 1, and its spectral support is a union of p-cyclotomic cosets with size equal to the code dimension.The support consists of exponents j for which the generator polynomial does not vanish at α^j.Source: §2 · p. 3
  • The Fourier transform expresses codewords using frequencies in the support, and the span of all t-fold coordinatewise products has support tS.The sumset tS adds t frequencies from S.Source: §2 · p. 4
  • Every codeword has coordinate sum zero exactly when 0 is absent from its spectral support.This condition follows from the coordinate sum of a pure frequency.Source: §2 · p. 4
  • The dual cyclic code has support Zn \ (−S), the complement of the negated support of the original code.Source: §2 · p. 4
  • For p = 2, S ⊆ 2S ⊆ 3S; for p = 3, S ⊆ 3S, while for p ≥ 5 none of these inclusions holds in general.Source: §2 · p. 4
  • For p = 3 and n = 8, S = {1, 3} has dimension 2 and neither 2S nor 3S contains 0, yielding a triorthogonal code with the all-ones logical row and parameters [[8, 1, 2]]3.This is the punctured qutrit Reed–Muller code; the search finds a single maximal support at this length.Source: §2 · p. 4

3 Triorthogonal codes in odd prime dimension

The section defines triorthogonality for odd-prime CSS codes and shows how it controls transversal gates, treating qupits separately from qubits. It also gives weight and puncturing criteria for constructing one-logical-qudit codes.

3.1 The CSS code of a matrix

  • A matrix with independent logical and stabilizer rows defines a valid CSS code encoding k qudits without requiring orthogonality of the full row space.Its code states are uniform superpositions over stabilizer cosets.Source: §3.1 · p. 5

3.2 Triorthogonal matrices

  • For odd p, triorthogonality makes the weighted trilinear form vanish on triples involving stabilizer rows and nonidentical logical rows, while repeated logical rows may have nonzero λ.The definition imposes no pairwise-product condition.Source: §3.2 · p. 5

3.3 The case p ≥5

  • For p ≥5, a triorthogonal matrix makes the transversal gate implement the product of the corresponding logical gates exactly, without correction.Source: §3.3 · p. 6

3.4 The case p = 3

  • For p = 3, the transversal gate implements the logical gates up to a fixed Pauli correction and a logical Pauli.The proof uses integer lifts because carries do not affect cubes modulo 9.Source: §3.4 · p. 7
  • For p = 3, the definition needs no pairwise condition: the alternative gate differs by a diagonal Clifford, whose stabilizer-dependent phase may require pairwise orthogonality.Source: §3.4 · p. 8

3.5 Weights and puncturing

  • A space admits triorthogonal weights exactly when its triple-product span’s orthogonal complement contains a vector with no zero entries; puncturing then yields a one-logical-qudit code.The punctured logical parameter is λ = −c_s.Source: §3.5 · pp. 8–9

4 Cyclic constructions

The section translates cyclic triorthogonality into spectral-support conditions for two constructions and derives code families and examples. It also describes weight restrictions and a concatenation rule for construction-A codes.

4.1 Two constructions

  • Construction A requires 0 ∉ S ∪ 2S ∪ 3S, while construction B requires only 0 ∉ 3S for its cyclic space.Construction A uses cyclic stabilizers and an all-ones logical row; construction B punctures a cyclic space.Source: §4.1 · pp. 9–10
  • The ternary length-20 example has 0 ∈ 2S but 0 ∉ 3S, so construction B yields a [[19, 1, 3]]3 code that is not self-orthogonal.The authors verified its distance by brute force.Source: §4.1 · p. 10

4.2 Two MDS families

  • Construction A with n = p−1 yields [[p−1, 1, r+1]]p codes when S = {1, . . . , r} and 3r < p−1; construction B gives [[p, 1, 2r+1]]p when 6r < p+1.Both families are MDS in the sense that the relevant dual code meets the Singleton bound.Source: §4.2 · pp. 10–11
  • For p ≡1 (mod 6), the p-length family has distance (p+2)/3 versus (p−1)/3 at length p−1 for Reed–Solomon codes; for p ≡5 (mod 6), Reed–Solomon codes have the greater distance.The p-length family includes [[7, 1, 3]]7 and is the first member of the infinite family [[p, 1, 2⌊p/6⌋+1]]p.Source: §4.2 · p. 11

4.3 Weights and concatenation

  • The search considers unit weights; non-cube weights can change the transversal gate when p ≡1 (mod 3), and the authors do not know whether certain distance-one behavior holds generally.For p = 3 and n ≤44, spaces triorthogonal only under nonconstant weights have distance d = 1.Source: §4.3 · p. 11
  • Interleaved concatenations of construction-A codes remain construction-A codes, with support determined by the inner and outer supports and distance d1d2.The search found several records of this form.Source: §4.3 · p. 11

5 Qubits: triply-even cyclic codes

For odd-length cyclic binary codes, classical triorthogonality is equivalent to triply evenness, characterized by a spectral-support condition. This equivalence also yields an exact transversal T action for construction A.

5 Qubits: triply-even cyclic codes

  • A binary cyclic code of odd length is triply even if and only if 0 ∉ 3S, equivalently if and only if it is classically triorthogonal.Source: §5 · p. 12
  • McEliece’s theorem gives the converse: when 0 ∉ 3S, all codeword weights are divisible by at least 8.Source: §5 · p. 12
  • For odd n, construction A gives an exact transversal T action with no Clifford correction when the stabilizer code is triply even.Source: §5 · p. 12
  • For the [[15, 1, 3]]2 code, S = {1, 2, 4, 8} has no three-term zero sum, but its four elements sum to 15, yielding a [15, 4, 8] simplex code.Source: §5 · p. 12

6 Search strategy

The search enumerates admissible unions of cyclotomic cosets, retains maximal supports up to multiplier equivalence, and certifies code distances with exhaustive and independent checks.

6 Search strategy

  • A support is admissible when 0 ∉ S ∪ 2S ∪ 3S for construction A, or 0 ∉ 3S for construction B.Source: §6 · p. 12
  • Depth-first search over coset unions prunes inadmissible branches and retains only maximal supports, since enlarging a support cannot decrease distance or increase output error under the stated setting.Source: §6 · p. 12
  • The reported counts are multiplier classes; permutation-equivalent cyclic codes not related by a multiplier may therefore be counted separately.Source: §6 · p. 13
  • An independent generalized Bron–Kerbosch search found the same maximal supports and dimensions up to multiplier equivalence across the tested lengths.Source: §6 · p. 13
  • Distances come from meet-in-the-middle searches with explicit minimum-weight witnesses; all p=3 and p=5 distances are exact, while some p=7 and p=2 cases remain lower bounds.Source: §6 · p. 13

7 Results

The search finds short cyclic qudit codes for several distances and dimensions, while the qubit results classify triply-even cyclic codes through length 763.

7 Results

  • The search covers p=3 through length 121, p=5,7 through length 96, and odd p=2 lengths through 763, finding 92/195, 248/395, and 624/1600 maximal supports for constructions A/B.Source: §7 · p. 13
  • For p=3, [[19, 1, 3]]3 is the shortest cyclic distance-3 code, and cyclic codes are shorter than Reed–Muller codes and concatenations for distances 3–8.Source: §7 · p. 13
  • For p=5, [[11, 1, 3]]5 is less than half the shortest Reed–Muller distance-3 length, but concatenation is shorter at larger distances.Source: §7 · p. 14
  • For p=7, cyclic codes are shorter than Reed–Muller codes and concatenations for distances 3–6; [[7, 1, 3]]7 is the shortest found.Source: §7 · p. 14
  • Among odd lengths 3–763, 84 admit nonzero triply-even cyclic codes, and every such code is a subcode of one of 879 listed maximal codes up to multiplier equivalence.Source: §7 · p. 14
  • Binary construction A records include [[85, 1, 5]]2 and [[223, 1, 9]]2; the cyclic codes are not competitive with the cited non-cyclic records.Source: §7 · p. 14

8 Distillation performance

The paper compares single-round distillation performance under twirled depolarizing noise, finding improved overhead exponent and threshold for selected p=3 and p=7 codes while identifying scope caveats.

8 Distillation performance

  • Table 2 reports overhead exponent, small-error output scaling, threshold, and acceptance probability at ε=0.01 under twirled depolarizing noise.Source: §8 · p. 15, Table 2 · p. 16
  • For p=3 and p=7, new codes improve on the shortest Reed–Muller and Reed–Solomon baselines in both overhead exponent and threshold.Source: §8 · p. 15
  • The [[7, 1, 3]]7 code has γ=1.77 and threshold 0.446, versus γ=2.58 and threshold 0.232 for [[6, 1, 2]]7.Source: §8 · p. 15
  • For the stated noise model, enlarging a support can improve output error but lowers acceptance probability, so single-round thresholds and γ do not alone determine full-protocol overhead.Source: §8 · p. 16
  • The reported performance assumes depolarizing noise; biased-noise thresholds may differ, and Lemma 17’s proof uses the depolarizing form.Source: §8 · p. 16

9 Conclusion

For cyclic codes of length coprime to p, triorthogonality becomes a spectral-support sumset condition, yielding qubit classifications and qudit code families. The approach is limited to two constructions and specified equivalences, while several extensions remain open.

9 Conclusion

  • The sumset criteria enable exhaustive searches and produce qudit codes that improve on punctured Reed–Muller codes in length and threshold, with an infinite family [[p, 1, 2⌊p/6⌋ + 1]]_p for every prime p ≥7.For p = 3 and p = 7 at distances 3 ≤ d ≤ 6, the codes are also shorter than concatenations of known codes; for p = 5, recursive use of [[4, 1, 2]]_5 remains better.Source: §9 · p. 16
  • For qubits, cyclic codes of odd length are triply even exactly when they satisfy 0 ∉ 3S, and all such codes are determined up to length 763.The classification gives a complete description of triply-even cyclic codes.Source: §9 · p. 16
  • The approach covers two unit-weight constructions, lengths coprime to p, and multiplier equivalence; some distances are only rigorous lower bounds.The authors note that non-cyclic constructions are shorter for qubits at d ≥ 5 and for qutrits at d = 3.Source: §9 · p. 16
  • Open directions include the smallest distance-3 qutrit code, multi-qudit gates via multiple punctures, and extending the criteria to abelian group and extended cyclic codes.The criteria also extend to higher Clifford-hierarchy levels; constacyclic families and multi-round overheads are proposed for further study.Source: §9 · pp. 16–17

A.1 Spectral description of concatenation

Interleaved concatenation of construction-A codes has a spectral-support description that preserves admissibility and multiplies the component distances. The proof identifies the concatenated stabilizer space with the cyclic code specified by that support.

A.1 Spectral description of concatenation

  • The construction uses k2 inner blocks of length k1, with outer stabilizers acting through inner logical operators.The spectral support is expressed using reduction modulo k1 and dilation of S2 by k1.Source: §A.1 · pp. 19–20
  • The concatenation has support S = π−1(S1) ∪ k1 · S2, is admissible for construction A, and has distance d1d2.Construction B concatenations are excluded because those codes are not cyclic.Source: §A.1 · p. 20
  • The concatenated stabilizer space lies in the cyclic code with support S, and equal dimensions establish that it is exactly that code.The two support pieces are disjoint, with dimensions adding to |S|.Source: §A.1 · p. 20
  • Admissibility follows by reducing a vanishing sum modulo k1 when it includes an element from π−1(S1), or dividing by k1 when all terms lie in k1 · S2.Both cases would contradict admissibility of S1 or S2.Source: §A.1 · p. 20
  • Orthogonality to block stabilizers and lifted outer stabilizers forces any nonzero-sum logical vector to have weight at least d1d2.Choosing a minimum-weight outer dual vector with nonzero sum and scaling an inner minimum-weight dual vector across blocks attains d1d2.Source: §A.1 · p. 20

A.2 Proof of Lemma 17

The proof reduces the lemma to a correlation inequality under a noise-dependent measure. It establishes the inequality through a pointwise bound, monotonicity, and the FKG inequality.

A.2 Proof of Lemma 17

  • Resampling represents noise by a random coordinate set R and uniform errors supported on R, then conditions on acceptance to define a measure μ.Each coordinate enters R with probability η = pϵ/(p − 1), giving error probability ϵ.Source: §A.2 · p. 21
  • Under μ, the probabilities of acting trivially, passing the smaller-code test, and satisfying both are expressed as expectations of f, g, and h.The lemma reduces to an inequality relating these expectations.Source: §A.2 · p. 21
  • For each R, h(R) ≥ f(R)g(R) follows from the subspace cardinality identity applied to the accepted-error spaces.The relevant spaces are VR ∩ L and VR ∩ V′.Source: §A.2 · p. 21
  • The functions f and g decrease as R grows, so the FKG inequality makes them positively correlated under μ and yields the lemma.When η = 1, the measure is a point mass and the inequality follows directly from Step 3.Source: §A.2 · p. 21

B Best code at each length

The appendix lists the best code among maximal supports at each length and provides spectral supports for selected codes. It specifies how to interpret the entries and the choice of primitive root.

B Best code at each length

  • Each table entry reports the largest distance among maximal supports, with the number of supports up to multiplier equivalence in parentheses; bounds and intervals indicate uncertified exact distances.The listed qubit entries give construction-A parameters and construction-B distances at length n − 1.Source: B Best code at each length · pp. 21–22
  • The qutrit and ququint searches report 92 and 248 construction-A maximal supports, and 195 and 395 construction-B maximal supports, respectively.These are total maximal-support counts, not code distances.Source: B Best code at each length · pp. 22–23
  • For p = 7, the search reports 624 maximal supports for construction A and 1600 for construction B.The table convention gives the best distance among those supports at each listed length.Source: B Best code at each length · pp. 21, 23

C Spectral supports of selected codes

  • Selected-code supports are indexed using the stated primitive root; changing the root changes S by a multiplier and gives an equivalent code.The table identifies columns for code, construction, length, and spectral support.Source: C Spectral supports of selected codes · pp. 23–24

Related papers

Loading 2610.08012v1…