On Constructing and Decoding Quantum Triorthogonal Codes

The gist The proposed formulation casts the search for triorthogonal matrices with prescribed dual-distance properties as a constrained ILP problem, where overlap, row-weight, and distance conditions are handled jointly.

Construction and Existence Criterion

The work studies the construction of binary triorthogonal codes with prescribed dual-distance properties The criterion combines triorthogonality constraints with MacWilliams identities via Krawtchouk-polynomial conditions on the dual weight distribution, yielding an integer linear programming formulation for the construction problem This framework connects the algebraic constraints required for transversal non-Clifford gates with distance-oriented design criteria from classical coding theory, and is used to guide explicit constructions of triorthogonal codes The ILP formulation yields new nontrivial triorthogonal codes that are not necessarily generated by triply-even codes

Triorthogonal Code Structure

A binary classical code is called triply-even if every codeword has Hamming weight divisible by 8 Triorthogonal matrices are defined by satisfying simultaneous pairwise and triple-wise overlap constraints, as well as row-weight requirements A matrix A in F r×n 2 is called triorthogonal if and only if the supports of any pair and any triple of its rows have even overlap The structure of CSS codes allows us to carry out the correction of Z-type errors and X-type errors independently at the decoder level The dimension of the CSS code turns out to be k = kX+kZ−n

Decoding Performance Evaluation

The decoding performance of high-distance triorthogonal codes obtained via the doubling construction is then evaluated over the dephasing channel Three decoding strategies are compared: bounded-distance decoding (BDD), belief propagation plus ordered-statistics post-processing (BP+OSD), and a GRAND-based decoder adapted to the quantum setting For the dephasing error model, where each qubit undergoes a Z-type, or phase-flip, error with dephasing probability p, only X-type stabilizer checks are used for binary decoding

Numerical Results and Comparison

Monte Carlo simulations assess the LER performance of two triorthogonal codes with d ≥ 5, obtained via the doubling construction For the J49, 1, 5K triorthogonal code of [5], qGRAND-106 and qGRAND-107 show strong LER performance in the low-noise region relevant to MSD Simulations show that bypassing the BP stage and applying OSD directly gives the same performance as BP+OSD The average cost of BP2+OSD-CS-60 represents an upper bound because BP is always assumed to run for 100 iterations

Conclusion

The proposed formulation casts the search for triorthogonal matrices with prescribed dualdistance properties as a constrained ILP problem, where overlap, row-weight, and distance conditions are handled jointly Results on the decoding performance of codes obtained via the doubling construction indicate that qGRAND is a good match for the considered dephasing channel setting In fact, it achieves strong LER performance in the low-noise region relevant to MSD, while keeping the average decoding cost competitive The paper concludes that qGRAND is a promising option for decoding triorthogonal codes over the dephasing channel

Appendix A: Computational Complexity

The total cost of CS-λ becomes C(CS-λ) = C(sorting CS) + C(operations) + C(comparisons), and the total cost of the OSD-CS-λ post-processing routine becomes nOSD[C(OSD-0) + C(CS-λ)] The average cost per decoded (correctly decoded or not) frame becomes C(BP2+OSD-CS-λ) = nMCC(BP) + nOSD[C(OSD-0) + C(CS-λ)]/nMC The cost for qGRAND-Max Query is estimated as C(qGRAND-Max Query) = ng/nMC 2rn This cost is derived from the dense binary matrix-vector product between HX in F r×n 2 and the guessed error pattern, followed by the comparison with the measured syndrome The space complexity of this is proportional to n · Max Query This cost is derived from rn + r(n − 1) + r The total number of configurations considered by the CS method is nconf = k0/1 + λ squared = k0 + λ squared This cost is C(operations) = C(precomp CS) + nconf(rk0 + r(k0 − 1) + r) The total cost of the OSD-CS-λ post-processing routine becomes nOSD[C(OSD-0) + C(CS-λ)] This term is a lower bound on the total cost, since the complete decoder also includes the BP stage The average cost of BP2+OSD-CS-60 (solid cyan curve) represents an upper bound, because BP is always assumed to run for 100 iterations For p < 7·10−3, qGRAND-106 and qGRAND-107 require fewer binary operations than OSD-CS-60, while providing better decoding performance For p > 7·10−3, BP2+OSD-CS-60 becomes more favorable, requiring a smaller cost and achieving performance at least comparable to that of the GRAND-based decoders The total cost of CS-λ becomes C(CS-λ) = C(sorting CS) + C(operations) + C(comparisons) The total cost of the OSD-CS-λ post-processing routine becomes nOSD[C(OSD-0) + C(CS-λ)] The total cost for the OSD-0 routine becomes C(OSD-0) = C(sort OSD) + C(GE) + C(INV) + C(prod OSD) The cost for the BP decoding stage only is C(BP) = niter 4qne + ne + n The cost for the syndrome computation is C(syndrome) = rn + r(n − 1) + r The cost for computing the product between the syndrome sX in F r×n 2 and H˜−1 X,ssX is C(prod OSD) = r(2r − 1) The total cost of (5) is C(operations) = C(precomp CS) + nconf(rk0 + r(k0 − 1) + r) The total cost of CS-λ becomes C(CS-λ) = C(sorting CS) + C(operations) + C(comparisons) The total cost of the OSD-CS-λ post-processing routine becomes nOSD[C(OSD-0) + C(CS-λ)] The cost for computing the Hamming weight for each error pattern is nconf(n − 1) The cost of the comparison between all the Hamming weights of these vectors is (nconf − 1)<ref:

1. Bold Header: Transversal T Gate Implementation in Quantum Computation

The improved AI system can be designed to implement transversal T gates directly on quantum hardware by leveraging triorthogonal codes, as these codes allow for transversal T gates, a nonClifford logical operation useful for achieving universal faulttolerant quantum computation.

2. Bold Header: Efficient Triorthogonal Code Construction via ILP

The system can utilize the proposed integer linear programming formulation for the construction problem to search for new codes that are not necessarily generated by classical triply-even codes, enabling the design of specific quantum error-correcting structures based on desired dual-distance properties.

3. Bold Header: Optimized Decoding for Dephasing Channels

The AI can employ the GRAND-based decoder adapted to the quantum setting as a promising option, which is shown to be effective over the dephasing channel relevant to magic-state distillation protocols.

4. Bold Header: Performance Benchmarking of Quantum Decoders

The system can rigorously compare bounded-distance decoding, belief propagation plus ordered-statistics post-processing, and a GRAND-based decoder adapted to the quantum setting by evaluating their exact logical error rate (LER) against specific noise models like the dephasing channel.

5. Bold Header: Cost-Aware Decoder Selection

The AI can dynamically select the optimal decoding strategy based on operational constraints by calculating the average estimated number of binary operations per decoded frame for each decoder, as detailed in Appendix A, to balance performance against computational cost.