Source-linked AI summary
Asymptotically good binary triorthogonal codes and higher-level transversal gates
Rodrigo San-José
TL;DR
Asymptotically good binary triorthogonal codes with the desired single-qubit logical T action have remained elusive. This paper combines extension-field AG codes with an orthogonality-preserving alphabet reduction to construct such codes and higher-level diagonal-gate families. It also reports a correction-free construction with worse parameters and direct constant-overhead T-state block distillation from noisy inputs.
Problem
Asymptotically good triorthogonal codes over extension fields yield multi-qubit block gates after conversion to qubits, leaving asymptotically good binary codes with single-qubit transversal T and the desired logical action elusive.
Source: §1 · p. 2Method
Results
The first asymptotically good binary triorthogonal family achieves linear rate and linear distance simultaneously.
Source: §1 · p. 2Takeaways & Limitations
The binary T-gate families yield direct constant-overhead T-state block distillation from noisy T-state inputs.
Source: §1 · p. 2Whether increasing the extension degree improves the parameter trade-offs remains unclear because the parameters also depend on s and t; for h > 3, the distillation argument assumes ideal operations from C_{h−1}.
Source: §7.4 · p. 24, §7.6 · p. 26
Abstract
from arXiv · showhide
For each level of the Clifford hierarchy from the third level onward, we construct explicit asymptotically good binary CSS codes for which a strongly transversal diagonal rotation, followed by a correction from the preceding level, implements the corresponding logical rotation. We achieve this using algebraic geometry codes over binary extension fields and performing an alphabet reduction that translates orthogonality conditions over the extension field to binary overlap conditions. In particular, we obtain the first asymptotically good family of binary triorthogonal codes. We also give a stronger construction with worse parameters for which the strongly transversal physical rotation implements the desired logical rotation, with no subsequent correction. Finally, adapting an error-correction-based distillation protocol, our binary $T$-gate families yield direct constant-overhead $T$-state block distillation from noisy $T$-state inputs under sufficiently weak input noise and ideal stabilizer operations.
1. Introduction
The paper addresses the gap in asymptotically good binary codes that implement the desired single-qubit non-Clifford logical rotation, rather than merely preserving the code space. It constructs such families through algebraic-geometry codes and alphabet reduction, and extends the approach to higher hierarchy levels and direct T-state distillation.
1. Introduction
- CSS-T preservation alone does not guarantee a non-Clifford logical action; an asymptotically good binary CSS-T construction can implement the identity.Transversal gates are fault-tolerant in the limited sense that one physical-gate fault cannot spread within a code block.Source: §1 · p. 1
- Earlier extension-field codes become multi-qubit block gates after identifying each qudit with m qubits, rather than single-qubit transversal T gates.Finding asymptotically good binary triorthogonal codes therefore remains a distinct goal; prior constructions for single-qubit T had not achieved the desired logical action.Source: §1 · p. 2
- The first asymptotically good binary triorthogonal family achieves linear rate and linear distance simultaneously.The paper also gives a construction without subsequent correction, at the cost of worse parameters.Source: §1 · p. 2
- For every fixed h ≥3, the paper constructs asymptotically good binary CSS codes with strongly transversal diagonal rotations followed by a correction from the preceding hierarchy level.Its T-gate families also yield direct constant-overhead block distillation from noisy T-state inputs, adapting the protocol of.Source: §1 · pp. 2–3
- The construction shortens and punctures extension-field AG codes, then uses additive concatenation to translate Schur-orthogonality into binary overlap conditions.The resulting CSS codes meet weight and overlap conditions for the desired logical action, with distance controlled by the original AG code and its dual.Source: §1 · pp. 2–3
2. Preliminaries
The preliminaries establish the code-theoretic setting and the phase argument used to relate binary row-overlap conditions to logical diagonal rotations.
2.2. CSS codes, gates, and triorthogonal codes.
- Schur powers span coordinate-wise products of codewords, while triorthogonal binary rows give a CSS code whose transversal T implements logical T up to a diagonal Clifford correction.The paper generalizes this overlap condition to h-orthogonality, recovering triorthogonality when h = 3.Source: §2.1 · p. 3, §2.2 · pp. 4–5
2.1. Schur products and AG codes.
- AG evaluation codes arise by evaluating functions in a Riemann–Roch space at rational places, with dimension and distance bounds stated for 2g −1 ≤ deg G < n.Their Euclidean dual is also an AG code, with a stated lower bound on its minimum distance.Source: §2.1 · pp. 3–4
2.3. Diagonal phases.
- The diagonal-phase argument expands the phase into row-subset terms, with terms of size h vanishing modulo 2^(h−1).This provides the higher-level phase calculation underlying the correction construction.Source: §2.3 · p. 5
- For an h-orthogonal generator matrix with odd-weight logical rows, a computable correction in C_{h−1} converts the physical diagonal gate action into the logical one.At h = 3 the correction is diagonal Clifford; at h = 4 it lies in the third hierarchy level.Source: §2.3 · pp. 5–6
3. Asymptotically good AG codes over binary extension fields
The paper selects an explicit Galois tower of function fields over a binary extension field to obtain the AG-code families used in its constructions.
3. Asymptotically good AG codes over binary extension fields
- An explicit sequence of function fields over F_2^m is chosen from a Galois tower obtained from the Garcia–Stichtenoth construction.The tower has an increasing number of rational points and comes with genera and divisors used in the code construction.Source: §3 · p. 6
- The evaluation places are separated from the supports of the selected divisors, and a suitable canonical divisor is chosen for the dual-code relation.The text identifies that canonical divisor through a differential with simple poles and residue one at each evaluation place.Source: §3 · pp. 6–7
- The tower parameters are selected using a power of two τ with 4 ≤ τ ≤ ℓ/2.The stated inequalities use τ and ℓ to constrain the divisor choices in the construction.Source: §3 · p. 7
4. Alphabet reduction
Alphabet reduction uses additive maps from a binary extension field to a binary vector space to transfer extension-field orthogonality into binary overlap conditions.
4. Alphabet reduction
- The reduction is designed to preserve orthogonality through trace identities compatible with repeated factors in binary overlaps.For example, the trace expression for three inputs reduces to Tr(abc(a + b + c)), and the paper notes that a natural Tr(abc) alternative lacks the needed compatibility.Source: §4 · p. 8
- An additive map and a homogeneous polynomial of degree τ transfer the condition C⋆(τ−1) ⊂ C⊥ to orthogonality of the binary image.The polynomial is evaluated coordinate-wise, so its degree-τ terms correspond to Schur products.Source: §4 · pp. 8–9
- For every j ≥2, an additive injective map exists with the required identity and homogeneity conditions at τ = 2j−1.The general length bound is not intended to be optimal; explicit maps for the T-gate constructions are shorter and give better parameters.Source: §4 · p. 9
- The stated map choices use τ = 4 for T with a correction, τ = 8 for T without a correction, and τ = 2h−1 for R_h with a correction.Each construction's outer condition is C⋆(τ−1) ⊂ C⊥.Source: §4 · p. 10
5. Construction with a lower-level correction
The construction separates the distance analysis from the two code constructions, using puncturing, shortening, and an additive binary map. A blockwise adjoint map is introduced to bound the Z-distance.
5. Construction with a lower-level correction
- The distance argument is shared by both constructions and begins by puncturing and shortening a classical code before applying an additive binary map.The puncture and shortening use selected coordinates, and the map applies ϕ coordinatewise.Source: §5.1 · p. 10
5.1. Bounds for the distances.
- Puncturing P coordinates can reduce distance by at most P, while each nonzero image block has weight at least d_in.Together these facts give the stated bound for the distance between C1 and C2.Source: §5.1 · p. 10
- The block-wise adjoint map is introduced as the key tool for bounding the quantum code’s Z-distance.The adjoint map is defined through the trace pairing between the binary image and the extension-field input.Source: §5.1 · p. 10
2. Consider
The section constructs binary CSS codes by puncturing and shortening extension-field codes, then transferring their orthogonality through an additive binary map. It gives asymptotically good families whose transversal rotations act logically with a correction from the preceding hierarchy level.
5.2. The puncturing construction.
- A compatible set of size one is always available for the stated maps, while larger compatible sets can improve the resulting quantum-code parameters.For size one, an element with trace one suffices.Source: §5.2 · pp. 11–12
- Puncturing P coordinates in an information set yields nested binary codes with an h-orthogonal generator matrix having exactly tP odd-weight rows, while its remaining rows span the smaller code.The construction chooses a compatible set for the additive map and punctures fewer than both the code dimension and its distance.Source: §5.2 · p. 12
- An additive concatenation map transfers the extension-field Schur-orthogonality conditions into binary overlap conditions for the punctured construction.The resulting binary image has products of up to h codewords of even weight.Source: §5.2 · p. 13
5.3. Asymptotic parameters.
- The asymptotic family is formed with length N_i = s(n_i−P_i) and dimension K_i = tP_i, for P_i = ⌊κn_i⌋.The construction uses 0 < κ < B(τ)/ℓ.Source: §5.3 · p. 14
- For each family member, a diagonal correction computable from its h-orthogonal matrix combines with the transversal physical rotation to implement the logical rotation.The correction belongs to C_(h−1).Source: §5.3 · p. 14
- For every fixed h ≥ 3, the construction gives explicit asymptotically good binary CSS code families with h-orthogonal generator matrices and a transversal rotation followed by a level-(h−1) diagonal correction acting logically.The general construction combines the algebraic-geometry codes with the puncturing construction.Source: §5.3 · p. 14
6. A correction-free construction
This section gives an explicit asymptotically good binary CSS family in which transversal rotations implement the desired logical gates without correction for every fixed level h ≥ 3. Its construction constants remain positive but deteriorate quickly as h grows; for the T gate, shorter explicit maps in the next section yield better parameters.
6.1. Weighted phases.
- The weighted-phase criterion makes R_h preserve a CSS code and enact the corresponding logical rotation when row weights and distinct-row overlaps satisfy specified divisibility conditions.The criterion allows arbitrary integer physical weights and logical gates R_h or R_h^-1.Source: §6.1 · p. 15
Then one can compute
- For h = 3, the construction uses the condition D⋆3 ⊂ D⊥ and divisibility moduli 8, 4, and 2 for one, two, and three factors to obtain a weighted transversal T gate without Clifford correction.These are the divisibility conditions used in Theorem 6.1.Source: Then one can compute · p. 16
6.2. The correction-free construction.
- Theorem 6.4 constructs codes with (2h−1)-orthogonal generator matrices and weighted physical rotations implementing the logical rotation up to global phase, without subsequent correction.The construction encodes K_i = ⌊κn_i⌋ qubits and selects P_i coordinates with K_i ≤ P_i ≤ (2h−1)K_i.Source: §6.2 · p. 16
- Repeating coordinates applies the same diagonal operator R_h on every physical qubit, producing CSS codes of length eN_i with N_i ≤ eN_i ≤ (2h−1)N_i and quantum distance eΔ_i ≥ Δ_i.The repeated generator matrix remains (2h−1)-orthogonal.Source: §6.2 · pp. 19–21
- For every fixed h ≥ 3, an explicit asymptotically good binary CSS family has (2h−1)-orthogonal generator matrices and transversal R_h^⊗N acts logically as R_h^⊗K, up to global phase, without correction.This result follows by repeating coordinates in the construction; the resulting codes retain the distance bounds.Source: §6.2 · p. 21
- Applying the construction at level h+1 with hierarchy lowering makes logical R_h rotations transversally addressable without correction [28, Rem. 1.3],.The parameters are those of the construction at level h+1.Source: §6.2 · p. 21
- The constants remain positive for each fixed h, but deteriorate quickly as h increases.Source: §6.2 · p. 21
- For the T gate, shorter explicit maps in the next section give better parameters.Source: §6.2 · p. 21
7. Explicit constructions for the T gate
The section specializes the constructions to T gates, giving explicit binary inner maps and compatible sets over F64 and F256. It also presents a correction-free F256 construction and shows that the corrected T-gate families support constant-overhead T-state distillation under stated noise and operation assumptions.
7. Explicit constructions for the T gate.
- The section specializes the general constructions to h = 3 by supplying explicit maps and compatible sets, with computations checked using SageMath.It introduces the cubic identity used in the constructions.Source: §7 · p. 21, §7.1 · pp. 21–22
7.1. The cubic identity and compatible sets.
- For h = 3, compatible elements satisfy trace-pairing orthogonality and a vanishing cubic tensor on triples of distinct elements.The section uses injective maps meeting the stated identities to specialize the construction to T gates.Source: §7.1 · p. 21
7.2. A construction over F64.
- The F64 corrected construction uses an inner binary code and yields an explicit CSS family with N_i = 14(n_i − P_i) and K_i = 4P_i.A computable diagonal Clifford correction makes physical T^⊗N_i act as logical T.Source: §7.2 · p. 22
7.3. A construction over F256.
- The F256 corrected construction uses an inner binary code and yields an explicit CSS family with N_i = 25(n_i − P_i) and K_i = 5P_i.A computable diagonal Clifford correction makes physical T^⊗N_i act as logical T.Source: §7.3 · p. 23
7.4. Further extension fields and limitations.
- For the bounds obtained, F256 has better relative parameters than F64 throughout the latter construction’s range, but the effect of increasing extension degree remains unclear.The trade-offs also depend on s and t.Source: §7.4 · p. 24
7.5. A correction-free construction over F256.
- The F256 correction-free construction has 4-orthogonal generator matrices and a Z-distance lower bound of 1/120 n_i − P_i, with no Clifford correction to the logical T gate.The family has K_i = ⌊κn_i⌋ for 0 < κ < 1/360, with K_i ≤ P_i ≤ 3K_i.Source: §7.5 · p. 25
7.6. Constant-overhead T-state distillation.
- Under ideal stabilizer operations and sufficiently weak input noise, either corrected T-gate family distills T states with constant input cost per output.For fixed admissible κ, the result holds for every fixed 0 < p < p0 and all sufficiently large family indices.Source: §7.6 · p. 26, §7.5 · p. 26
8. AI Usage
The authors disclose AI assistance in constructing the explicit inner maps, organizing drafts, clarifying proofs, and writing code to check results; they state that the author reviewed and verified all content, claims, and conclusions.
8. AI Usage
- ChatGPT 5.6 Sol assisted with explicit inner maps, draft organization, proof clarification, and code checks; the author says all claims and conclusions were reviewed and verified.The author retains responsibility for the content, claims, and conclusions.Source: §8 · p. 26
Appendix A. The general alphabet-reduction map
The appendix constructs an explicit alphabet-reduction map from a binary basis of the extension field. It derives the map from trace forms and a triangular system, yielding binary overlaps that match the forms on field inputs.
Appendix A. The general alphabet-reduction map
- The map ϕ is built from binary linear functionals selected by solving a triangular system over F2, making the construction explicit.Ordering subsets by decreasing cardinality gives a coefficient matrix with diagonal entries one and a unique solution.Source: Appendix A · pp. 27–28
- The polynomials H_j are symmetric, homogeneous of degree 2j−1, and additive in each variable in characteristic two.Their repeated-argument identity is H_j(X_1, …, X_{j−2}, Y, Y) = H_{j−1}(X_1, …, X_{j−2}, Y)^2.Source: Appendix A · p. 27
- The trace forms Γ_r are symmetric and multilinear over F2 and satisfy a collision identity that reduces repeated arguments to a lower-order form.This identity is used to establish the overlap relation for the binary image.Source: Appendix A · pp. 27–28
- The constructed map assigns binary coordinates so that overlaps on field inputs equal the corresponding trace forms, and nondegeneracy of the pairing makes ϕ injective.The construction also gives the r = 1 identity and the pairing case r = 2.Source: Appendix A · pp. 27–28
Appendix B. Higher-level odd completion
The appendix proves an odd-completion result by induction on the hierarchy level, starting from a self-orthogonal code and passing to its coordinate-wise square. The completion supplies odd coordinate weights while preserving the required congruences.
Appendix B. Higher-level odd completion
- The completion uses a vector with odd entries modulo 2^(h−1) and establishes the remaining congruences by induction on the number of codewords.The base case h = 2 assumes D ⊂ D⊥.Source: Appendix B · pp. 28–29
- The induction passes from D to P = D⋆2, using orthogonality of the requisite products to apply the lower-level completion result.The argument tests orthogonality to P through products generating P⋆(2h−2−1).Source: Appendix B · pp. 28–29
- Adding the new term makes the weighted sum of every word of D zero modulo 2^h while preserving the lower-modulus congruences for products of multiple words.The proof uses the weight identity and linearity on D.Source: Appendix B · p. 29
Appendix C. Z-error correction using the trace adjoint
The trace-adjoint map reduces Z-error correction for the binary CSS construction to decoding over an extension-field code. An extension-field decoder can therefore yield a binary Z decoder, with its correction radius and complexity determined by the AG code and construction choices.
Appendix C. Z-error correction using the trace adjoint
- A decoder for A2⊥ correcting symbol-weight-r errors induces a Z decoder correcting binary errors of weight at most r.The trace-adjoint map sends a binary error to extension-field syndrome coordinates; lifting the decoded vector back leaves an error differing by a Z stabilizer.Source: Appendix C · pp. 29–30
- The trace-adjoint map ρϕ is surjective with kernel I⊥, so a linear right inverse σ lifts decoded extension-field vectors back to binary vectors.For the inner maps in Theorems 7.2 and 7.4, Equation (35) permits σ = ϕ.Source: Appendix C · pp. 29–30
- For d* = deg G − P + 2 − 2g > 0, Proposition C.3 gives the binary code a Z decoder with a correction radius determined by d*.The proposition states the radius as a bound involving d* − 1.Source: Appendix C · p. 30
- The AG decoder of [11, Thm. 3] has complexity O(L^2.81), while total binary decoding is O(N^3) or O(N^2.81) with a precomputed right inverse.Constructing the actual AG codes is a separate step that can be done in polynomial time using standard Riemann–Roch-space algorithms [17, Alg. 13 and Rem. 14].Source: Appendix C · p. 30
- For the asymptotic families, the choice of P makes d* at least B(τ), with n − P positive as required by the Z-distance estimate.The appendix identifies n − P > 0 as corresponding to that distance estimate.Source: Appendix C · p. 30