1 Introduction↩︎

Quantum error correction protects quantum information against decoherence and operational noise. Starting from the stabilizer formalism [1], several quantum-code families have been obtained by adapting classical coding notions to the quantum setting. CSS codes, for instance, are built from pairs of classical binary linear codes satisfying an orthogonality constraint [2], [3]. Nevertheless, not all quantum codes arise as adaptations of generic classical error-correcting codes. A particularly important example is given by triorthogonal codes. These quantum CSS codes were introduced in the context of MSD, a standard approach to implementing costly non-Clifford operators necessary to achieve fault-tolerant quantum computation [4]–[8]. Triorthogonal codes are especially relevant in this framework because they allow for transversal \(\mathsf{T}\) gates. This property follows from the pairwise and triple-wise overlap constraints that define triorthogonality [5], [8], [9]. The same structure that makes triorthogonal codes useful also makes their construction challenging, not only because of the aforementioned overlap conditions, but also because of additional row-weight constraints.

This paper studies the construction of binary triorthogonal codes with prescribed dual-distance properties. We derive an existence criterion for even-weight triorthogonal generator matrices by combining the overlap constraints with Krawtchouk-polynomial conditions derived from the MacWilliams identities. This yields an ILP formulation that can be used to search for triorthogonal matrices satisfying a target dual minimum distance. The proposed 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. This construction problem is related to, but distinct from, previous work on MSD and on the coding-theoretic structure of triorthogonal matrices. Bravyi and Haah introduced triorthogonal codes as a mechanism for low-overhead distillation of \(\mathsf{T}\)-type magic states [5], presenting notable \(\llbracket{15,1,3}\rrbracket\) and \(\llbracket{49,1,5}\rrbracket\) triorthogonal codes constructed from classical triply-even codes [10]. Subsequent works developed generalized triorthogonal constructions and alternative distillation protocols for \(\mathsf{T}\), controlled-\(\mathsf{S}\), Toffoli, and CCZ resources [6], [7]. More recently, Shi et al. studied triorthogonal matrices from a classical coding-theoretic perspective, constructing them from binary self-dual codes [11]. In contrast, the present work focuses on a complementary existence and design question: given a desired dual-distance target, we ask under which algebraic and enumerative conditions a triorthogonal matrix can be obtained. Our ILP formulation yields new nontrivial triorthogonal codes that are not necessarily generated by triply-even codes.

Finally, we evaluate triorthogonal codes over the dephasing channel, which is the relevant noise model for the MSD protocol since only phase-flip errors need to be considered [5]. We compare belief propagation (BP) plus ordered-statistics decoding (BP+OSD) [12], bounded-distance decoding, and GRAND [13], adapted to the quantum CSS setting. GRAND was previously used for random QSCs [14], while here it is applied to the classical code associated with a structured triorthogonal code.

2 Notation and Preliminaries↩︎

In this paper, \(\mathbb{F}_2\) denotes the binary field, \(\mathbb{Z}\) the set of integers, \(\mathbb{N}_{0} \triangleq\{0,1,2,\ldots\}\) the set of nonnegative integers, and \(\mathbb{C}\) the set of complex numbers. For a positive integer \(n\), we use the shorthand \([n]\triangleq\{1,2,\ldots,n\}\). Column vectors, e.g., \(\boldsymbol{a}\), and matrices, e.g., \(\mathsf{A}\), are denoted by bold lowercase letters and sans-serif uppercase letters, respectively. For a vector \(\boldsymbol{a}\), its \(i\)-th entry is denoted by \(a_i\) or \([\boldsymbol{a}]_i\). Similarly, for a matrix \(\mathsf{A}\), the entry in the \(i\)-th row and \(j\)-th column is denoted by \(a_{i,j}\) or \([\mathsf{A}]_{i,j}\). The transpose of a vector (matrix) is denoted as \(\boldsymbol{a}^{\mathrm{\textsf{\tiny T}}}\) (\(\mathsf{A}^{\mathrm{\textsf{\tiny T}}}\)). All-zero vectors and matrices are denoted by \(\boldsymbol{0}\) and \(\mathsf{0}\), respectively. Unless otherwise specified, operations involving binary vectors and binary matrices are performed over \(\mathbb{F}_2\). The inner product between two vectors \(\boldsymbol{a}\) and \(\boldsymbol{b}\) is denoted by \(\langle{\boldsymbol{a}},{\boldsymbol{b}}\rangle\), and the Hamming weight (or, simply, weight) of a vector \(\boldsymbol{a}\), i.e., the number of nonzero elements of \(\boldsymbol{a}\), is denoted by \(\operatorname{wt}(\boldsymbol{a})\). The rank of a binary matrix \(\mathsf{A}\) is denoted by \(\operatorname{rank}(\mathsf{A})\), while its column span is denoted by \(\operatorname{Col}(\mathsf{A})\).

2.1 Classical and Quantum Codes↩︎

A classical binary linear code of length \(n\), dimension \(k\), and minimum Hamming distance \(d\) is denoted by \([n,k,d]\) and is a subspace \(\mathscr{C}\subseteq \mathbb{F}_2^{n}\). The vectors \(\boldsymbol{c} \in \mathscr{C}\) are called codewords, and the minimum Hamming distance \(d\) of \(\mathscr{C}\) is the minimum weight of its nonzero codeword(s). Then, its error-correcting capability is \(t = \left\lfloor\frac{(d-1)}{2} \right\rfloor\). A code can be represented as the kernel of a PCM \(\mathsf{H}\in \mathbb{F}_2^{m \times n}\) or as the row span of a (full-rank) GM \(\mathsf{G} \in \mathbb{F}_2^{k \times n}\), namely \(\mathscr{C} \triangleq\left\{\boldsymbol{c}\in\mathbb{F}_2^n \mid \mathsf{H}\boldsymbol{c} = \boldsymbol{0}\right\} =\left\{\mathsf{G}^{\mathrm{\textsf{\tiny T}}}\boldsymbol{m}\mid \boldsymbol{m}\in\mathbb{F}_2^k\right\}\). The redundancy of \(\mathscr{C}\) is \(r=n-k=\operatorname{rank}(\mathsf{H})\leq m\). We denote by \(\mathscr{C}^{\perp} \subseteq \mathbb{F}_2^{n}\) the \([n,n-k,{d}^\perp]\) dual code of \(\mathscr{C}\), defined as \(\mathscr{C}^{\perp} \triangleq \left\{ \boldsymbol{x}\in\mathbb{F}_2^n \mid \langle{\boldsymbol{x}},{\boldsymbol{c}}\rangle=0, \, \forall \, \boldsymbol{c}\in\mathscr{C} \right\}.\) Then, \({\mathscr{C}}^\perp=\operatorname{Col}(\mathsf{H}^{\mathrm{\textsf{\tiny T}}}).\) A code \(\mathscr{C}\) satisfying \(\mathscr{C}\subseteq\mathscr{C}^{\perp}\) is called self-orthogonal. A binary classical code is called triply-even if every codeword has Hamming weight divisible by \(8\).

QSCs are the quantum counterpart of classical binary linear codes [1]. An \(\llbracket n,k,d \rrbracket\) QSC is a \(2^k\)-dimensional subspace \(\mathscr{C}\subseteq(\mathbb{C}^2)^{\otimes n}\) with minimum distance \(d\).In this paper, we focus on CSS codes, i.e., QSCs whose stabilizer generators are either pure \(\mathsf{X}\)-type or pure \(\mathsf{Z}\)-type operators [2], [3], [15].

The dimension of the CSS code \(\mathscr{C}\) turns out to be \(k = k_\textrm{X} + k_\textrm{Z}-n\). The structure of CSS codes allows us to carry out the correction of \(\mathsf{Z}\)-type errors and \(\mathsf{X}\)-type errors independently at the decoder level. In particular, the classical code \(\mathscr{C}_{\textrm{X}}\) is used to correct \(\mathsf{Z}\)-type errors, whereas the other classical code, \(\mathscr{C}_{\textrm{Z}}\), is employed to correct \(\mathsf{X}\)-type errors. It is important to mention that the (quantum) minimum distance of the \(\llbracket n, k, d \rrbracket\) CSS code \(\mathscr{C}\) is computed as \(d \triangleq\min\{d_{\textrm{X}}, d_{\textrm{Z}}\}\), where

It follows that \(d \geq \delta \triangleq\min\{ d_0, d_1 \}\). If \(d > \delta\), the CSS code \(\mathscr{C}\) is called highly-degenerate, and if \(d_{\textrm{X}} > d_0\) (\(d_{\textrm{Z}} > d_1\)), it is called \(\mathsf{X}\)-degenerate (\(\mathsf{Z}\)-degenerate). The capability of correcting \(\mathsf{Z}\)-type and \(\mathsf{X}\)-type errors is \(t_{\textrm{X}} = \left\lfloor\frac{(d_{\textrm{X}}-1)}{2} \right\rfloor\) and \(t_{\textrm{Z}} = \left\lfloor\frac{(d_{\textrm{Z}}-1)}{2} \right\rfloor\), respectively.

2.2 Noise Model↩︎

We focus on the dephasing error model, where each qubit undergoes a \(\mathsf{Z}\)-type, or phase-flip, error with dephasing probability \(p\). Equivalently, the error pattern is generated by a binary symmetric channel. For CSS codes, this allows us to use a binary decoder based only on the \(\mathsf{X}\)-type stabilizer checks, represented by \(\mathsf{H}_{\textrm{X}}\in\mathbb{F}_2^{m_{\textrm{X}}\times n}\). After syndrome measurement, the decoder receives \(\boldsymbol{s}_{\textrm{X}}=\mathsf{H}_{\textrm{X}}\boldsymbol{e}_{\textrm{Z}}\in\mathbb{F}_2^{m_{\textrm{X}}}\), where \(\boldsymbol{e}_{\textrm{Z}}\in\mathbb{F}_2^n\) identifies the qubit positions affected by phase-flip errors.

2.3 Triorthogonal Codes↩︎

We first recall some basic facts regarding triorthogonal matrices and codes, both in the classical and quantum settings [5].

Next, we particularize Definition 1 for a triorthogonal code.

3 Construction of Even-Weight Triorthogonal Matrices with Odd Lengths↩︎

In this section, our first goal is to construct suitable even-weight triorthogonal matrices \(\mathsf{H}_{\textrm{X}}\) of odd length \(n\). Then, we append an all-ones row of length \(n\) to obtain \(\llbracket n, 1, d \rrbracket\) triorthogonal codes. This follows the standard approach in the literature [5], [9].

3.1 Weight Enumerators and MacWilliams Theorem↩︎

For a binary linear \([n,k, d]\) code \(\mathscr{C}\), we denote by \(A_j\) the number of codewords of weight \(j\) in \(\mathscr{C}\), i.e., \(A_j \triangleq |\{\boldsymbol{c}\in \mathscr{C} \, | \, \operatorname{wt}(\boldsymbol{c})=j\}|\), for \(j\in \{0\}\cup [n]\). Thus, the weight enumerator of \(\mathscr{C}\) is given by \(W_{\mathscr{C}}(y)=\sum_{j=0}^{n}A_jy^j\). Similarly, for the dual code \({\mathscr{C}}^\perp\), we denote by \(B_j\) the number of codewords in \({\mathscr{C}}^\perp\) of weight \(j\in \{0\}\cup [n]\). The relationship between the coefficients \(A_j\) and \(B_j\) is characterized by the celebrated MacWilliams theorem.

3.2 Integer Linear Programming (ILP) Formulation for Triorthogonal Codes↩︎

Inspired by the construction of self-orthogonal codes in [17], we propose a general construction of binary linear codes whose GMs are triorthogonal and have only even-weight rows, while imposing the dual-distance constraint \(d({\mathscr{C}}^\perp)\geq {d}^\perp\).

Before presenting the ILP formulation, we introduce the following notation. Define \(\mathcal{V}\triangleq\mathbb{F}_2^k\setminus\{\boldsymbol{0}\}\) as the set of all nonzero binary column types, and let \(N\triangleq|\mathcal{V}|=2^k-1\). We enumerate the elements \(\boldsymbol{v}_1,\ldots,\boldsymbol{v}_N\in\mathcal{V}\). For each \(\boldsymbol{v}_i\in\mathcal{V}\), the variable \(x_i\in\mathbb{N}_0\) denotes the multiplicity of the column type \(\boldsymbol{v}_i\) in the GM. Thus, the multiplicity vector \(\boldsymbol{x}=(x_1,\ldots,x_N)^{\mathrm{\textsf{\tiny T}}}\) specifies the multiset of columns of the desired GM.

We next define three matrices that encode the constraints in our formulation. First, let \(\mathsf{M}\in\{0,1\}^{N\times N}\) be the incidence matrix indexed by the nonzero vectors in \(\mathcal{V}\), such that \[\mathsf{M}_{i,j} = \begin{cases} 1, & \textrm{if } \langle{\boldsymbol{v}_i},{\boldsymbol{v}_j}\rangle=0, \\ 0, & \textrm{otherwise}.\label{eq:Mk95weights95codewords} \end{cases}\tag{1}\] This matrix is used to compute the weights of the nonzero codewords generated by the chosen column multiplicities.

Second, let \(\mathsf{P}_k\in\{0,1\}^{\binom{k+1}{2}\times N}\) be the self-orthogonality constraint matrix. Let the rows be indexed by pairs \((a,b)\) with \(1\leq a\leq b\leq k\), then its entries are defined by \[[\mathsf{P}_k]_{(a,b),i}=[\boldsymbol{v}_i]_a[\boldsymbol{v}_i]_b.\label{eq:Pk95self-orthogonality}\tag{2}\] Therefore, for a certain multiplicity vector, we get that the entry \([\mathsf{P}_k\boldsymbol{x}]_{(a,b)}\) counts the weight of row \(a\) when \(a=b\), and the pairwise overlap between rows \(a\) and \(b\) when \(a<b\).

Similarly, we define the triorthogonality constraint matrix \(\mathsf{T}_k\in\{0,1\}^{\binom{k}{3}\times N}\). Let the rows be indexed by triples \((a,b,c)\) with \(1\leq a<b<c\leq k\), then its entries are defined by \[[\mathsf{T}_k]_{(a,b,c),i}=[\boldsymbol{v}_i]_a[\boldsymbol{v}_i]_b[\boldsymbol{v}_i]_c.\label{eq:Tk95tri-orthogonality}\tag{3}\] Therefore, \([\mathsf{T}_k\boldsymbol{x}]_{(a,b,c)}\) counts the triple overlap among rows \(a\), \(b\), and \(c\). These matrices allow the self-orthogonality, triorthogonality, and dual-distance requirements to be expressed as linear constraints in the ILP.

Theorem 2 provides an ILP formulation for deciding the existence of a triorthogonal matrix \(\mathsf{H}_{\textrm{X}}\) satisfying the prescribed dual-distance constraint, and for constructing one whenever the formulation is feasible. The proof is omitted due to space constraints. Instead, we illustrate the formulation by showing how it reconstructs the \(\llbracket 15,1,3 \rrbracket\) triorthogonal code of [5]. Note that, for the \(\llbracket 15,1,3\rrbracket\) and \(\llbracket 49,1,5\rrbracket\) triorthogonal codes presented in [5], the code generated by \(\mathsf{H}_{\textrm{X}}\) is triply-even.

3.3 Search for Nontrivial Triorthogonal Codes↩︎

Solving the ILP with all vectors in \(\mathcal{V}\) is computationally costly. To reduce the size of the formulation, we impose a prescribed symmetry on the column types, following the ideas of [17] and [18]. Specifically, we prescribe a group of automorphisms \(\Gamma\) acting on the binary column types in \(\mathcal{V}\). This group action partitions \(\mathcal{V}\) into orbits, and instead of assigning one variable to each vector in \(\mathcal{V}\), we assign one variable to each orbit under \(\Gamma\). This orbit-based reduction preserves the prescribed symmetry while substantially reducing the number of variables in the ILP. Due to space constraints, we do not report the full formulation here.

Based on the approach suggested in [18], we first restrict the orbit formulation to cyclic automorphism groups and vary \(k_0\) from \(6\) to \(10\). This provides a computationally tractable search space for nontrivial even-weight triorthogonal matrices with \({d}^\perp\geq 3\). The nontrivial triorthogonal codes obtained for odd lengths \(n\leq 80\) are listed in Table 1. Within this cyclic-symmetry search, all feasible solutions found have classical dual distance \({d}^\perp=3\). This indicates that cyclic symmetry alone may be too restrictive for obtaining higher-dual-distance instances, motivating the study of richer automorphism groups. Codes that are also triply-even are marked explicitly by “TE” in the table.

4 Numerical Results↩︎

In this section, we first introduce the decoders we employ, and then discuss their performance.

4.1 Decoding Methods↩︎

We consider three decoding strategies, all adapted to the quantum setting by decoding up to stabilizers: bounded-distance decoding (BDD), BP+OSD (BP2+OSD-E/CS-\(\lambda\)), and GRAND (qGRAND-Max_Query).

In particular, for BDD, we plot its exact LER \(P_{\textrm{e, BDD}}=1-\sum_{w=0}^{t_{\textrm{X}}}\binom{n}{w}p^{w}(1-p)^{n-w}\), where \(p<\frac{1}{2}\) is the dephasing probability. For the BP+OSD decoder, we use the implementation of [12] in its min-sum variant, considering both the combination sweep (CS) and exhaustive (E) methods. We denote by \(\lambda\) the search depth parameter of the OSD post-processing procedure and consider \(\lambda \in \{ 0, 10, 60 \}\). For \(\lambda = 0\), corresponding to BP2+OSD-E-0, the decoder applies OSD-\(0\) whenever BP decoding fails. For \(\lambda \in \{ 10, 60 \}\), corresponding to BP2+OSD-CS-\(\lambda\), a failed BP decoding attempt is first followed by OSD-\(0\), and then by the CS procedure over \(\lambda\) bits [12]. The maximum number of BP iterations is \(100\). Although triorthogonal codes do not generally have a sparse PCM, we adopt this decoding strategy because the OSD post-processing stage remains effective beyond the strictly sparse regime. The third decoder considered here is based on GRAND. For classical codes, GRAND is well-suited to medium- and high-rate codes without a specific algebraic or sparse-graph structure [13], making it a natural candidate in our setting. Indeed, since we decode only \(\mathscr{C}_{\textrm{X}}\) using \(\mathsf{H}_{\textrm{X}}\), the problem reduces to decoding a classical binary linear code.

The proposed GRAND-based decoder works by generating candidate \(\mathsf{Z}\)-type error patterns according to their likelihoods. As the channel is memoryless, this corresponds to testing low-Hamming-weight error patterns first, since an error pattern of weight \(w\) has probability proportional to \(p^w(1-p)^{n-w}\). For each candidate error pattern \(\hat{\boldsymbol{e}}_{\textrm{Z}}\), the decoder computes the corresponding syndrome \(\hat{\boldsymbol{s}}_{\textrm{X}} = \mathsf{H}_{\textrm{X}} \hat{\boldsymbol{e}}_{\textrm{Z}}\). The first candidate satisfying \(\hat{\boldsymbol{s}}_{\textrm{X}}=\boldsymbol{s}_{\textrm{X}}\) is selected as the estimated error. If no such candidate is found after a predefined maximum number of guesses, denoted by \(\texttt{Max\_Query}\), the decoder declares a decoding failure. The estimated error vector \(\hat{\boldsymbol{e}}_{\textrm{Z}}\) defines the correction to be applied on the qubits indicated by its support. Since the code is quantum, successful decoding does not require \(\hat{\boldsymbol{e}}_{\textrm{Z}}\) to coincide with the physical error vector \(\boldsymbol{e}_{\textrm{Z}}\). Rather, it is sufficient that the residual error \(\tilde{\boldsymbol{e}}_{\textrm{Z}}= \boldsymbol{e}_{\textrm{Z}} + \hat{\boldsymbol{e}}_{\textrm{Z}}\) is either \(\boldsymbol{0}\) or corresponds to a \(\mathsf{Z}\)-type stabilizer, so that it acts trivially on the logical state. If the residual error is instead a nontrivial logical \(\mathsf{Z}\)-type operator, a logical error has occured.

4.2 Numerical Simulations↩︎

We assess the LER performance of two triorthogonal codes with \(d\geq 5\), obtained via the doubling construction [19], using Monte Carlo simulations over the dephasing channel. This setting is relevant because, in the MSD protocol, only \(\mathsf{Z}\)-type errors are encountered [5]. Each simulation point is obtained by collecting \(100\) logical errors, with a maximum of \(10^{9}\) transmitted frames. For the min-sum check-node update in the BP decoder, we use an optimized scaling factor of \(0.05\). For each simulated code, we also include the uncoded transmission curve as a reference, shown as a solid black line. Moreover, for each code whose minimum distance satisfies \(d_{\textrm{X}}=2t_{\textrm{X}}+1\) or \(d_{\textrm{X}}=2t_{\textrm{X}}+2\), we report an additional reference curve, shown as a dashed orange line, of the form \(y = a x^{t_{\textrm{X}}+1},\) for a suitable constant \(a\).

In Fig. [fig:triorto9549951955], the performance of the \(\llbracket 49, 1, 5 \rrbracket\) triorthogonal code of [5] is evaluated. We have numerically verified that this code is \(\mathsf{X}\)-degenerate, with \(d_{\textrm{X}} = 5\) and \(d_0 = 4\). In this case, BP2+OSD-E-0 (solid blue curve) shows poor performance, attributable to the nonsparse structure of the code. The best results are obtained by qGRAND-\(10^{6}\) and qGRAND-\(10^{7}\) (solid and dashed red curves, respectively), and BP2+OSD-CS-10 (dashed blue curve); all outperforming BDD (solid green curve). The improved performance of BP2+OSD-CS-10 with respect to BP2+OSD-E-0 is due to the larger OSD search depth, namely \(\lambda=10\) instead of \(\lambda=0\).

Fig. [fig:triorto9595951957] reports the performance of a \(\llbracket 95,1,7 \rrbracket\) triorthogonal code [9], [20]. We have also verified that this code is \(\mathsf{X}\)-degenerate, with \(d_{\textrm{X}}=7\) and \(d_0=4\). For this code, BDD outperforms both BP2+OSD-E-0 and BP2+OSD-CS-10, which can again be attributed to the nonsparse structure of the code. On the other hand, BP2+OSD-CS-60 (dashed cyan curve) achieves performance comparable to qGRAND-\(10^{7}\), especially for moderate and large \(p\), although the best overall performance is attained by qGRAND-\(10^{7}\).

Interestingly, for both codes, simulations show that bypassing the BP stage and applying OSD directly gives the same performance as BP+OSD. This is consistent with the very small optimized scaling factor used in the min-sum check-node update: larger values degrade performance, while such a small value strongly attenuates the BP messages. Hence, running BP before OSD does not provide any gain. We believe that this behavior is due to the dense structure of the codes.

For the \(\llbracket 95,1,7 \rrbracket\) triorthogonal code, Fig. [fig:costs] reports the estimated average number of binary operations per decoded frame for qGRAND (\(-10^{6}\) and \(-10^{7}\)) and BP2+OSD-CS-60. For the latter, an \(8\)-bit quantized implementation is assumed, so that reliability-domain arithmetic can be counted in binary-operation equivalents. We also report the cost contribution of OSD-CS-\(60\) (dotted cyan curve) within BP2+OSD-CS-\(60\). This term is a lower bound on the total cost, since the complete decoder also includes the BP stage. The BP cost is evaluated for a fixed number of iterations, set to \(100\), and is therefore independent of \(p\) (dotted gray curve). Hence, 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. We observe that for \(p<2\cdot 10^{-3}\), qGRAND-\(10^{6}\) and qGRAND-\(10^{7}\) require fewer binary operations than OSD-CS-60, while providing better decoding performance. For \(p>7\cdot 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.

5 Conclusion↩︎

This paper studied triorthogonal codes from both a construction and a decoding viewpoint. 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. 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.

6 Computational Complexity Estimation↩︎

In this appendix, we show in detail how we compute the average estimated number of binary operations per decoded frame for BP2+OSD-CS--\(\lambda\) and qGRAND, which is depicted in Fig. [fig:costs].

6.1 BP2+OSD-CS-\(\lambda\)↩︎

We account for a \(q\)-bit quantized implementation, so reliability-domain arithmetic can be counted in terms of binary-operation equivalents. Moreover, we set

• \(r = \operatorname{rank}(\mathsf{H}_{\textrm{X}})\) as the binary rank of the considered classical PCM,

• \(k_0 = n - \operatorname{rank}(\mathsf{H}_{\textrm{X}})\) as the dimension of the considered classical code,

• \(n_{\textrm{iter}}\) as the maximum number of BP iterations,

• \(n_{\textrm{MC}}\) as the number of transmitted frames, or Monte Carlo samples, simulated at a fixed value of the dephasing probability \(p\),

• \(n_{\textrm{OSD}}\) as the number of times (for a given value of \(p\)) for which the post-processing routine is called (both OSD-0 and CS-\(\lambda\)), and

• \(n_{\textrm{e}}\) as the number of edges in the Tanner graph of \(\mathsf{H}_{\textrm{X}}\).

According to [12], whenever the BP decoder fails after \(n_{\textrm{iter}}\) iterations, the corresponding OSD post-processing stage is invoked, namely OSD-0 for BP2+OSD-E-0 and OSD-0 followed, if needed, by CS-\(\lambda\) for BP2+OSD-CS-\(\lambda\). Therefore, \(n_{\textrm{OSD}}\) can be obtained from a BP2+OSD run by counting the number of such BP failures.

In the following, we denote by \(C(\texttt{BP})\) the cost of the BP decoding stage only, implemented through the min-sum check-node update rule. We use a worst-case estimate, assuming that all \(n_{\textrm{iter}}\) iterations are performed for every frame. This is in line with what we observed for the specific codes we have simulated. It would also be consistent with removing the early stopping criterion provided by intermediate syndrome checks. The resulting cost is \[C(\texttt{BP}) = n_{\textrm{iter}}(4 q n_{\textrm{e}} + n_{\textrm{e}} + n).\] The term \(4qn_{\textrm{e}}\) accounts for the reliability-domain operations associated with the message updates along the edges. For each edge, we count a constant number of \(q\)-bit operations, including the update of variable-to-check and check-to-variable messages, reliability additions/subtractions, and minimum/comparison operations. The term \(n_{\textrm{e}}\) accounts for the binary sign processing in the check-node updates, namely the propagation and combination of message signs along the edges. Finally, the term \(n\) accounts for the tentative hard decision on the \(n\) variable nodes, where a sign test is performed on each variable node to obtain the current binary estimate. Since these operations are performed at each iteration, the per-iteration cost is multiplied by \(n_{\textrm{iter}}\).

In the following, we denote by \(C(\texttt{OSD-0})\) the cost of the OSD-0 post-processing routine, after the BP decoding stage. In particular, according to [12], we first need to sort the soft-decision vector, i.e., the output of the BP decoding stage, and then re-order the columns of \(\mathsf{H}_{\textrm{X}}\) accordingly, obtaining \(\mathsf{H}_{\textrm{X,s}} \in \mathbb{F}_2^{r \times n}\), where the subscript “\(\textrm{s}\)” stands for “sorted”. The corresponding cost is \[C(\texttt{sort\_OSD}) = q (n \log_2(n)) + n.\] Next, we have to perform Gaussian elimination in order to find the first \(r\) linearly independent columns of \(\mathsf{H}_{\textrm{X,s}}\), which has an estimated cost of \[C(\texttt{GE}) = r (r-1) (3 n - r + 2) / 6.\] In this way, we obtain a full-rank matrix \(\tilde{\mathsf{H}}_{\textrm{X,s}} \in \mathbb{F}_2^{r \times r}\), and sorting the columns further we set, without loss of generality, \[\mathsf{H}_{\textrm{X,s}} = (\tilde{\mathsf{H}}_{\textrm{X,s}} \; \mathsf{H}_{\textrm{X,rem}}),\] where \(\mathsf{H}_{\textrm{X,rem}} \in \mathbb{F}_2^{r \times k_0}\) and the subscript “\(\textrm{rem}\)” stands for “remainder”.

Now, we can rewrite the error vector as \[\boldsymbol{e}_{\textrm{Z}} = \begin{pmatrix} \boldsymbol{e}_{\textrm{Z,s}} \\ \boldsymbol{e}_{\textrm{Z,rem}} \end{pmatrix} \in \mathbb{F}_2^{n},\] where \(\boldsymbol{e}_{\textrm{Z,s}} \in \mathbb{F}_2^{r}\) and \(\boldsymbol{e}_{\textrm{Z,rem}} \in \mathbb{F}_2^{k_0}\). As described in [12], the treatment of \(\boldsymbol{e}_{\textrm{Z,rem}}\) depends on the post-processing routine. In general, for a given choice of \(\boldsymbol{e}_{\textrm{Z,rem}}\), the corresponding \(\boldsymbol{e}_{\textrm{Z,s}}\) can be chosen so that the syndrome equation \(\boldsymbol{s}_{\textrm{X}}=\mathsf{H}_{\textrm{X,s}}\boldsymbol{e}_{\textrm{Z}}\) is satisfied. However, for OSD-0, \(\boldsymbol{e}_{\textrm{Z,rem}}\) is fixed to the all-zero vector, so that \(\boldsymbol{e}_{\textrm{Z,s}} = \tilde{\mathsf{H}}_{\textrm{X,s}}^{-1}\boldsymbol{s}_{\textrm{X}}\); hence, no additional cost is counted for computing \(\boldsymbol{e}_{\textrm{Z,rem}}\). In contrast, in the second post-processing stage, namely OSD-CS-\(\lambda\), nonzero configurations of \(\boldsymbol{e}_{\textrm{Z,rem}}\) are considered, and the corresponding cost will be accounted for later on.

In order to find \({\tilde{\mathsf{H}}_{\textrm{X,s}}}^{-1}\), we need to invert \(\tilde{\mathsf{H}}_{\textrm{X,s}}\), which has a cost of \[C(\texttt{INV}) = r (r-1)(3 r + 1) / 2,\] and the cost for computing the product between the syndrome \(\boldsymbol{s}_{\textrm{X}} \in \mathbb{F}_2^{r}\) and \(\tilde{\mathsf{H}}_{\textrm{X,s}}^{-1}\), namely \(\boldsymbol{e}_{\textrm{Z,s}} = \tilde{\mathsf{H}}_{\textrm{X,s}}^{-1} \boldsymbol{s}_{\textrm{X}}\), is \[C(\texttt{prod\_OSD})= r (2r - 1).\]

In summary, the total cost for the OSD-0 routine becomes

Next, let \(C(\texttt{CS-\lambda})\) denote the cost for the second post-processing routine, after OSD-0. According to [12], we first sort the entries of the remainder component \(\boldsymbol{e}_{\textrm{Z,rem}}\) according to the BP soft-decision reliabilities. This has a cost of \[C(\texttt{sorting\_CS}) = k_0.\] Then, we count the possible configurations considered by the CS method. In CS-\(\lambda\), we consider all weight-one configurations of \(\boldsymbol{e}_{\textrm{Z,rem}}\), together with all weight-two configurations supported on the first \(\lambda\) entries of \(\boldsymbol{e}_{\textrm{Z,rem}}\), where these entries are ordered according to the BP soft-decision reliabilities. Therefore, the total number of configurations is \[n_{\textrm{conf}} = \binom{k_0}{1} + \binom{\lambda}{2}=k_0+\binom{\lambda}{2}.\] For each of these configurations, we have to compute \[\label{eq:operations} \boldsymbol{e}_{\textrm{Z,s}} = \tilde{\mathsf{H}}_{\textrm{X,s}}^{-1} \boldsymbol{s}_{\textrm{X}} \, + \, \tilde{\mathsf{H}}_{\textrm{X,s}}^{-1} \mathsf{H}_{\textrm{X,rem}} \boldsymbol{e}_{\textrm{Z,rem}}.\tag{4}\] The product \(\tilde{\mathsf{H}}_{\textrm{X,s}}^{-1} \boldsymbol{s}_{\textrm{X}}\) is known from OSD-0, and the product \(\tilde{\mathsf{H}}_{\textrm{X,s}}^{-1} \mathsf{H}_{\textrm{X,rem}}\) needs to be computed only once (\(\texttt{precomp}\)), while the multiplication with \(\boldsymbol{e}_{\textrm{Z,rem}}\) and the summation must be calculated \(n_{\textrm{conf}}\) times. Hence, for \(\texttt{precomp}\), we have a cost of \[C(\texttt{pre}\texttt{comp\_CS}) = r^2 k_0 + r k_0 (r - 1) = r k_0 (2r-1),\] and the total cost of 4 is

The routine ends after having found the lowest-weight error pattern among all the configurations; hence, we have an additional cost of \[C(\texttt{comparisons}) = n_{\textrm{conf}} (n - 1) + (n_{\textrm{conf}} - 1),\] where \(n_{\textrm{conf}} (n - 1)\) is the cost to compute the Hamming weight for each error pattern and \((n_{\textrm{conf}} - 1)\) is the cost of the comparison between all the Hamming weights of these vectors, in order to find the lowest-weight vector.

In summary, the total cost of CS-\(\lambda\) becomes

and the total cost of the OSD-CS-\(\lambda\) post-processing routine becomes \[n_{\textrm{OSD}}[C(\texttt{OSD-0}) + C(\texttt{CS-\lambda})].\]

Finally, the average cost per decoded (correctly decoded or not) frame becomes

6.2 GRAND-Based Decoder↩︎

Here, we particularize the cost for the GRAND-based quantum decoder considered in this work, namely qGRAND-Max_Query. Our implementation is derived from the publicly available MATLAB code associated with [13], with the modifications required to support the QSCs and simulation settings considered in this work. In addition to what we already have set in the previous subsection, we denote by \(n_{\textrm{g}}\) the total number of guesses performed, for a fixed \(p\).

For each guessed error pattern, qGRAND-Max_Query performs the following operations:

1. it computes the binary syndrome associated with the guessed error pattern and compares it with the measured syndrome, returning the error pattern if the two syndromes are equal;

2. otherwise, it generates the next guessed error pattern, unless \(\texttt{Max\_Query}\) has been reached.

If no valid error pattern is found after \(\texttt{Max\_Query}\) guesses, the decoder stops without any additional cost being included in the present estimate.

For step 1), the syndrome computation is counted as a dense binary matrix-vector product between \(\mathsf{H}_{\textrm{X}}\in\mathbb{F}_2^{r\times n}\) and the guessed error pattern, followed by the comparison with the measured syndrome, and the corresponding cost becomes

Step 2) can be done with no computational cost, assuming the potential error patterns are loaded into memory. The space complexity of this is (proportional to) \(n\cdot\texttt{Max\_Query}\).

In summary, the average estimated cost per tested frame is therefore

References↩︎