<h5>3.1-1 <span class="Heading">What it does?</span></h5>
<p>In the simplest possible terms, we are given a pair of matrices <span class="Math">P</span> and <span class="Math">Q</span> with orthogonal rows, <span class="Math">PQ^T=0</span>. The matrices have entries in a finite field <span class="Math">F=\mathop{\rm GF}(q)</span>, where <span class="Math">q</span> is a power of a prime. The goal is to find the smallest weight of a non-zero vector <span class="Math">c</span> over the same field <span class="Math">F</span>, such that <span class="Math">c</span> be orthogonal with the rows of <span class="Math">P</span>, <span class="Math">Pc^T=0</span>, and linearly independent from the rows of <span class="Math">Q</span>.</p>
<p>We first construct a generator matrix <span class="Math">G</span> whose rows form a basis of the <span class="Math">F</span>-linear space of all vectors orthogonal to the rows of <span class="Math">P</span>. At each step, a random permutation <span class="Math">S</span> is generated and applied to the columns of <span class="Math">G</span>. Then, Gauss' elimination with back substitution renders the resulting matrix to the reduced row echelon form, after which the inverse permutation S^{-1} is applied to the columns. Rows of the resulting matrixG_S that are linearly independent from the rows of Q are considered as candidates for the minimum weight vectors. Thus, after N steps, we are getting an upper bound on the distance which is improving with increasing N.
<p>The intuition is that each row of <span class="Math">G_S</span> is guaranteed to contain at least <code class="code">rank</code><span class="Math">(G_S)-1</span> zeros. Thus, we are sampling mostly lower-weight vectors from the linear space orthogonal to the rows of <span class="Math">P</span>. Further, it is easy to see that any vector obtained this way is <em>irreducible</em> <a href="chapBib.html#biBDumer-Kovalev-Pryadko-bnd-2015">[DKP15]</a>, i.e., it cannot be decomposed into a pair of zero-syndrome vectors with non-overlapping supports.</p>
<p>Furthermore, the eventual convergence is guaranteed. Indeed, if <span class="Math">c</span> is a minimum-weight codeword of weight <span class="Math">d</span>, consider a permutation <span class="Math">S</span> which places one position from its support into the 1st column, and the remaining positions into the last <span class="Math">d-1</span> columns. Vector <span class="Math">c</span> being the lowest-weight non-trivial vector, no pivot column may be in the block of last <span class="Math">d-1</span> columns. This guarantees that vector <span class="Math">c</span> is obtained as the first row of <span class="Math">G_S</span>. (This argument is adapted to degenerate quantum codes from <a href="chapBib.html#biBCuellar-etal-2020">[CGLN21]</a>).</p>
<h5>3.1-4 <span class="Heading">CSS version of the algorithm</span></h5>
<p>The described version of the algorithm is implemented in the function <code class="code">DistRandCSS</code> (<a href="chap4.html#X826856C47F9890F3"><span class="RefLink">4.1</span></a>). It applies to the case of Calderbank-Shor-Steane (CSS) codes, where the matrices <span class="Math">P=H_X</span> and <span class="Math">Q=H_Z</span> are called the CSS generator matrices, and the computed minimum weight is the distance <span class="Math">d_Z</span> of the code. The number of columns <span class="Math">n</span> is the block length of the code, and it encodes <span class="Math">k</span> qudits, where <span class="Math">k=n-</span><code class="code">rank</code><span class="Math">(H_X)-</span><code class="code">rank</code><span class="Math">(H_Z)</span>. To completely characterize the code, we also need the distance <span class="Math">d_X</span> which can be obtained by calling the same function with the two matrices interchanged. The conventional code distance <span class="Math">d</span> is the minimum of <span class="Math">d_X</span> and <span class="Math">d_Z</span>. Parameters of such a <span class="Math">q</span>-ary CSS code are commonly denoted as <spanclass="Math">[[n,k,(d_X,d_Z)]]_q</span>, or simply <span class="Math">[[n,k,d]]_q</span> as for a general <span class="Math">q</span>-ary stabilizer code.</p>
<h5>3.1-5 <span class="Heading">Generic version of the algorithm</span></h5>
<p>CSS codes are a subclass of general <span class="Math">F</span>-linear stabilizer codes which are specified by a single stabilizer generator matrix <span class="Math">H=(A|B)</span> written in terms of two blocks of <span class="Math">n</span> columns each. The orthogonality condition is given in a symplectic form,</p>
<p class="pcenter"> A B^T-B A^T=0, </p>
<p>or, equivalently, as orthogonality between the rows of <span class="Math">H</span> and the symplectic-dual matrix <span class="Math">\tilde H=(B|-A)</span>. Non-trivial vectors in the code must be orthogonal to the rows of <span class="Math">P=\tilde H</span> and linearly independent from the rows of <span class="Math">Q=H</span>. The difference with the CSS version of the algorithm is that we must minimize the <em>symplectic</em> weight of <span class="Math">c=(a|b)</span>, given by the number of positions <span class="Math">i</span>, <span class="Math">1\le i\le n</span>, such that either <span class="Math">a_i</span> or <span class="Math">b_i</span> (or both) be non-zero.</p>
<p>The parameters of such a code are denoted as <span class="Math">[[n,k,d]]_q</span>, where <span class="Math">k=n-</span><code class="code">rank</code><span class="Math">H</span> is the number of encoded qudits, and <span class="Math">d</span> is the minimal symplectic weight of a non-trivial vector in the code. It is easy to check that a CSS code can also be represented in terms of a single stabilizer generator matrix. Namely, for a CSS code with generators <span class="Math">H_X</span> and <span class="Math">H_Z</span>, the stabilizer generator matrix has a block-diagonal form, <spanclass="Math">H=</span><code class="code">diag</code><span class="Math">(H_X,H_Z)</span>.</p>
<p>A version of the algorithm for general <span class="Math">F</span>-linear stabilizer codes is implemented in the function <code class="code">DistRandStab</code> (<a href="chap4.html#X826856C47F9890F3"><span class="RefLink">4.1</span></a>).</p>
<p><em>Important Notice</em>: In general, here one could use most general permutations of <span class="Math">2n</span> columns, or restricted permutations of <span class="Math">n</span> two-column blocks preserving the pair structure of the matrix. While the latter method would be much faster, there is no guarantee that every vector would be found. As a result, we decided to use general permutations of <span class="Math">2n</span> columns.</p>
<p>Representation of quantum codes in terms of linear spaces is just a convenient map. In the case <span class="Math">q=2</span> (qubits), the details can be found, e.g., in the book of Nielsen and Chuang, <a href="chapBib.html#biBNielsen-book">[NC00]</a>. Further details on the theory of stabilizer quantum error correcting codes based on qubits can be found in the Caltech Ph.D. thesis of Daniel Gottesman <a href="chapBib.html#biBgottesman-thesis">[Got97]</a> and in the definitive 1997 paper by Calderbank, Rains, Shor, and Sloane <a href="chapBib.html#biBCalderbank-1997">[CRSS98]</a>. Theory of stabilizer quantum codes based on qudits (<span class="Math">q</span>-state quantum systems) was developed by Ashikhmin and Knill <a href="chapBib.html#biBAshikhmin-Knill-2001">[AK01]</a> (prime fields with <span class="Math">q</span> prime) and by Ketkar, Klappenecker, Kumar, & Sarvepalli <a href="chapBib.html#biBKetkar-Klappenecker-Kumar-Sarvepalli-2006">[KKKS06]</a> (extension fields with <span class="Math">q</span> a non-trivial power of a prime).</p>
<p>In the binary case (more generally, when <span class="Math">q</span> is a prime), <span class="Math">F</span>-linear codes coincide with <em>additive</em> codes. The <em>linear</em> codes [e.g., over <span class="Math">\mathop{\rm GF}(4)</span> in the binary case <a href="chapBib.html#biBCalderbank-1997">[CRSS98]</a>] is a different construction which assumes an additional symmetry. A brief summary of <span class="Math">F</span>-linear quantum codes [where <span class="Math">F=\mathop{\rm GF}(q)</span> with <span class="Math">q=p^m</span>, <span class="Math">m>1</span> a non-trivial power of a prime] can be found in the introduction of Ref. <a href="chapBib.html#biBZeng-Pryadko-hprod-2020">[ZP20]</a>. The construction is equivalent to a more physical approach in terms of a lifted Pauli group suggested by Gottesman <a href="chapBib.html#biBGottesman-prime-power-2014">[Got14]</a>.</p>
<p>The algorithm <a href="chap3.html#X7C198D417DA58DFD"><span class="RefLink">3.1-2</span></a> is closely related to the algorithm for finding minimum-weight codewords in a classical linear code as presented by Leon <a href="chapBib.html#biBLeon-1988">[Leo88]</a>, and a related family of <em>information set</em> (IS) decoding algorithms <a href="chapBib.html#biBKruk-1989">[Kru89]</a> <a href="chapBib.html#biBCoffey-Goodman-1990">[CG90]</a>.</p>
<p>Consider a classical linear <span class="Math">q</span>-ary code <span class="Math">[n,k,d]_q</span> encoding <span class="Math">k</span> symbols into <span class="Math">n</span>, specified by a generator matrix <span class="Math">G</span> of rank <span class="Math">k</span>. Using Gauss' algorithm and column permutations, the generator matrix can be rendered into a systematic form, G=(I|A), where the two blocks are I, the size-k identity matrix, and a k by n-k matrix A. In such a representation, the first k positions are called the information set of the code (since the corresponding symbols are transmitted directly) and the remaining n-k symbols provide the redundancy. Any k linearly-independent columns of G can be chosen as the information set, which defines the systematic form of G up to a permutation of the rows of A.
<p>The IS algorithm and the original performance bounds <a href="chapBib.html#biBLeon-1988">[Leo88]</a> <a href="chapBib.html#biBKruk-1989">[Kru89]</a> <a href="chapBib.html#biBCoffey-Goodman-1990">[CG90]</a> are based on the observation that for a long random code a set of <span class="Math">k+\Delta</span> randomly selected columns, with <span class="Math">\Delta</span> of order one, are likely to contain an information set. ISs are (approximately) in one-to-one correspondence with the column permutations, and a random IS can thus be generated as a set of <em>pivot</em> columns in the Gauss' algorithm after a random column permutation. Thus, if there is a codeword c of weight d, the probability to find it among the rows of reduced-row-echelon form G_S after a column permutation S can be estimated as that for a randomly selected set of k columns to hit exactly one non-zero position in c.
<p>The statistics of ISs is more complicated in other ensembles of random codes, e.g., in linear <em>low-density parity-check</em> (LDPC) codes where the check matrix <span class="Math">H</span> (of rank <span class="Math">n-k</span> and with rows orthogonal to those of <span class="Math">G</span>) is additionally required to be sparse. Nevertheless, a provable bound can be obtained for a related <em>covering set</em> (CS) algorithm where a randomly selected set of <span class="Math">s\ge k-1</span> positions of a putative codeword are set to be zero, and the remaining positions are constructed with the help of linear algebra. In this case, the optimal choice <a href="chapBib.html#biBDumer-Kovalev-Pryadko-IEEE-2017">[DKP17]</a> is to take <span class="Math">s\approx n(1-\theta)</span>, where <span class="Math">\theta </span> is the erasure threshold of the family of the codes under consideration. Since <span class="Math">\theta\ge R</span> (here <span class="Math">R=k/n</span> is the code rate), here more zeros must be selected, and the complexity would grow (assuming the distance <span class="Math">d</span> remains the same, which is usually <em>not</em> the case for LDPC codes).</p>
<p>Note however that rows of <span class="Math">G_S</span> other than the last are not expected to contain as many zeros (e.g., the first row is only guaranteed to have <span class="Math">k-1</span> zeros), so it is <em>possible</em> that the performance of the IS algorithm on classical LDPC codes is actually closer to that on random codes as estimated by Leon <a href="chapBib.html#biBLeon-1988">[Leo88]</a>.</p>
<p>Case of <em>quantum CSS codes</em></p>
<p>In the case of a random CSS code (with matrices <span class="Math">P</span> and <span class="Math">Q</span> selected randomly, with the only requirement being the orthogonality between the rows of <span class="Math">P</span> and <span class="Math">Q</span>), the performance of the algorithm <a href="chap3.html#X7C198D417DA58DFD"><span class="RefLink">3.1-2</span></a> can be estimated as that of the CS algorithm, in terms of the erasure threshold of a linear code with the parity matrix <span class="Math">P</span>, see <a href="chapBib.html#biBDumer-Kovalev-Pryadko-IEEE-2017">[DKP17]</a>.</p>
<p>Unfortunately, such an estimate fails dramatically in the case of <em>quantum LDPC codes</em>, where rows of <span class="Math">P</span> and <span class="Math">Q</span> have weights bounded by some constant <span class="Math">w</span>. This is a reasonable requirement since the corresponding quantum operators (supported on <span class="Math">w</span> qudits) have to actually be measured frequently as a part of the operation of the code, and it is reasonable to expect that the measurement accuracy goes down (exponentially) quickly as <span class="Math">w</span> is increased. Then, the linear code orthogonal to the rows of <span class="Math">P</span> has the distance <span class="Math">\le w</span> (the minimal weight of the rows of <span class="Math">Q</span>), and the corresponding erasure threshold is exactly zero. In other words, there is a finite probability that a randomly selected <span class="Math">w</span> symbols contain a vector orthogonal to the rows of <span class="Math">P</span> (and such a vector would likely have nothing to do with non-trivial <em>quantum</em> codewords which must be linearly independent from the rows of <span class="Math">Q</span>).</p>
<p>On the other hand, for every permutation <span class="Math">S</span> in the algorithm <a href="chap3.html#X7C198D417DA58DFD"><span class="RefLink">3.1-2</span></a>, the matrix <span class="Math">G_S</span> contains exactly <span class="Math">k=n-</span><code class="code">rank</code><span class="Math">(P)-</span><code class="code">rank</code><span class="Math">(Q)</span> rows orthogonal to rows of <span class="Math">P</span> and linearly independent from rows of <span class="Math">Q</span> (with columns properly permuted). These vectors contain at least <span class="Math">s</span> zeros, where <span class="Math">[1-\theta_*(P,Q)] n\le s\le n-</span><code class="code">rank</code><span class="Math">(Q)</span>, where <span class="Math">\theta_*(P,Q)</span> is the erasure threshold for <span class="Math">Z</span>-like codewords in the quantum CSS code with <span class="Math">H_X=P</span> and <span class="Math">H_Z=Q</span>.</p>
<p><em>What is it that we do not understand?</em></p>
<p>What missing is an understanding of the statistics of the ISs of interest, namely, the ISs that overlap with a minimum-weight codeword in one (or a few) positions.</p>
<p>Second, we know that a given column permutation <span class="Math">S</span> leads to the unique information set, and that every information set can be obtained by a suitably chosen column permutation. However, there is no guarantee that the resulting information sets have equal probabilities. In fact, it is easy to construct small matrices where different information sets are obtained from different numbers of column permutations (and thus have <em>different</em> probabilities). It is not clear whether some of the ISs may have vanishingly small probabilities in the limit of large codes; in such a case the algorithm may take an excessively long time to converge.</p>
<h4>3.3 <span class="Heading">Empirical estimate of the success probability</span></h4>
<p>The probability to find a codeword after <span class="Math">N</span> rounds of the algorithm can be estimated empirically, by counting the number of times each codeword of the minimum weight was discovered. We <em>expect</em> the probability <span class="Math">P(c)</span> to discover a given codeword <span class="Math">c</span> to depend only on its (symplectic) weight <code class="code">wgt</code><span class="Math">(c)</span>, with the probability a monotonously decreasing function of the weight. If, after <span class="Math">N</span> steps, codewords <span class="Math">c_1</span>, <span class="Math">c_2</span>, <span class="Math">\ldots</span> , <span class="Math">c_m</span> of the same (minimal) weight <span class="Math">w</span> are discovered <span class="Math">n_1</span>, <span class="Math">n_2</span>, <span class="Math">\ldots</span> , <span class="Math">n_m</span> times, respectively, we can estimate the corresponding Poisson parameter as</p>
<p>Then, the probability that a codeword <span class="Math">c_0</span> of the true minimal weight <span class="Math"> d < w </span> be <em>not</em> discovered after <span class="Math">N</span> steps can be upper bounded as (the inequalities tend to saturate and become equalities in the limit of small <span class="Math">\lambda_w</span>)</p>
<p>Thus, the probability to fail is decreasing as an exponent of the parameter <span class="Math">\langle n\rangle</span>, the <em>average number of times a minimum-weight codeword has been found.</em></p>
<p>The hypothesis about all <span class="Math">P(c_i)</span> being equal to <span class="Math">\lambda_w</span> is testable, e.g., if one considers the distribution of the ratios <span class="Math">x_i=n_i/N</span>, where <span class="Math">N=\sum_{i=1}^m n_i</span> is the total number of codewords found. These quantities sum up to one and are distributed according to multinomial distribution<a href="chapBib.html#biBSteel-1953">[Ste53]</a>. Further, under our assumption of all <span class="Math">P(c_i)</span> being equal, we also expect the outcome probabilities in the multinomial distribution to be all equal, <span class="Math">\pi_i=1/m</span>, <span class="Math">1\le i\le m</span>.</p>
<p>This hypothesis can be tested using Pearson's \chi^2 test. Namely, in the limit where the total number of observations N diverges, the quantity
<p>is expected to be distributed according to the <span class="Math">\chi^2_{m-1}</span> distribution with <span class="Math">m-1</span> parameters, see <a href="chapBib.html#biBChernoff-Lehmann-1954">[CL54]</a> <a href="chapBib.html#biBCramer-book-1999">[Cra99]</a>.</p>
<p>In practice, we can approximate with the <span class="Math">\chi^2_{m-1}</span> distribution as long as the total <span class="Math">N</span> be large compared to the number <span class="Math">m</span> of the codewords found (i.e., the average <span class="Math">\langle n\rangle</span> must be large, which is the same condition as needed for confidence in the result.)</p>
<p>With <code class="code">debug[4]</code> set (binary value 8) in <code class="code">DistRandCSS</code> and <code class="code">DistRandStab</code> (<a href="chap4.html#X826856C47F9890F3"><span class="RefLink">4.1</span></a>), whenever more than one minimum-weight vector is found, the quantity <span class="Math">X^2</span> is computed and output along with the average number of times <span class="Math">\langle n\rangle</span> a minimum-weight codeword has been found. However, no attempt is made to analyze the corresponding value or calculate the likelihood of the null hypothesis that the codewords be equiprobable.</p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
