Coduri CSS

Coduri liniare clasice

Codurile clasice de corectare a erorilor au fost studiate pentru prima dată în anii 1940 și, de atunci, sunt cunoscute multe tipuri diferite de coduri. Cele mai studiate și utilizate coduri se încadrează într-o categorie numită coduri liniare. Vom vedea exact ce înseamnă cuvântul „liniar" în acest context peste puțin timp, dar o modalitate foarte simplă de a descrie codurile liniare la acest punct este că sunt coduri Stabilizer care se întâmplă să fie clasice. Codurile CSS sunt, în esență, perechi de coduri liniare clasice combinate împreună pentru a crea un cod cuantic de corectare a erorilor. Astfel, pentru discuția care urmează, va trebui să înțelegem câteva lucruri de bază despre codurile liniare clasice.

Fie $\Sigma$ alfabetul binar pentru întreaga discuție de față. Când ne referim la un cod liniar clasic, înțelegem o mulțime nevidă $\mathcal{C}\subseteq\Sigma^n$ de șiruri binare de lungime $n,$ pentru un număr întreg pozitiv $n,$ care trebuie să satisfacă o singură proprietate de bază: dacă $u$ și $v$ sunt șiruri binare în $\mathcal{C},$ atunci șirul $u\oplus v$ se află de asemenea în $\mathcal{C}.$ Aici, $u\oplus v$ se referă la SAU-exclusiv pe biți al lui $u$ și $v,$ pe care l-am întâlnit de mai multe ori în cursul „Fundamentele algoritmilor cuantici".

În esență, când ne referim la un cod clasic de corectare a erorilor ca fiind liniar, ne gândim la șirurile binare de lungime $n$ ca la vectori $n$-dimensionali ale căror componente sunt fie $0,$ fie $1,$ și cerem ca însuși codul să formeze un subspațiu liniar. În loc de adunarea obișnuită a vectorilor peste numerele reale sau complexe, folosim însă adunarea modulo $2,$ care este pur și simplu SAU-exclusiv. Cu alte cuvinte, dacă avem două cuvinte de cod $u$ și $v,$ adică $u$ și $v$ sunt șiruri binare în $\mathcal{C},$ atunci $u + v$ modulo 2, adică $u\oplus v,$ trebuie să fie și el un cuvânt de cod în $\mathcal{C}.$ Observă, în special, că această implicație trebuie să fie adevărată chiar și atunci când $u = v.$ Aceasta implică faptul că $\mathcal{C}$ trebuie să conțină șirul format numai din zerouri $0^n,$ deoarece SAU-exclusiv pe biți al oricărui șir cu el însuși este șirul format numai din zerouri.

Exemplu: codul de repetiție pe 3 biți

Codul de repetiție pe 3 biți este un exemplu de cod liniar clasic. În particular, avem $\mathcal{C} = \{000,111\},$ deci, în ceea ce privește condiția de liniaritate, există doar două alegeri posibile pentru $u$ și două alegeri posibile pentru $v.$ Este un exercițiu trivial să parcurgi cele patru perechi posibile și să verifici că obținem întotdeauna un cuvânt de cod atunci când luăm SAU-exclusiv pe biți:

$$000 \oplus 000 = 000, \quad 000 \oplus 111 = 111, \quad 111 \oplus 000 = 111, \quad 111 \oplus 111 = 000.$$

Exemplu: codul Hamming $[7,4,3]$

Iată un alt exemplu de cod liniar clasic, numit codul Hamming $[7,4,3]$. A fost unul dintre primele coduri clasice de corectare a erorilor descoperite vreodată și constă din aceste 16 șiruri binare de lungime 7. (Uneori codul Hamming $[7,4,3]$ este înțeles ca reprezentând codul cu aceste șiruri inversate, dar noi îl vom considera ca fiind codul ce conține șirurile prezentate aici.)

$$\begin{array}{cccc} 0000000 & 1100001 & 1010010 & 0110011\\[1mm] 0110100 & 1010101 & 1100110 & 0000111\\[1mm] 1111000 & 0011001 & 0101010 & 1001011\\[1mm] 1001100 & 0101101 & 0011110 & 1111111 \end{array}$$

Există o logică foarte simplă în spatele selecției acestor șiruri, dar ea este secundară lecției și nu va fi explicată aici. Deocamdată, este suficient să observi că acesta este un cod liniar clasic: aplicând XOR oricăror două șiruri dintre acestea, vei obține întotdeauna un alt șir din cod.

Notația $[7,4,3]$ (cu paranteze drepte simple) are o semnificație analogă cu notația cu paranteze drepte duble pentru codurile Stabilizer menționată în lecția anterioară, dar aici este pentru codurile liniare clasice. În particular, cuvintele de cod au $7$ biți, putem codifica $4$ biți folosind codul (deoarece există $16 = 2^4$ cuvinte de cod), și se întâmplă să fie un cod cu distanța $3,$ ceea ce înseamnă că oricare două cuvinte de cod distincte trebuie să difere în cel puțin $3$ poziții — deci cel puțin $3$ biți trebuie inversați pentru a transforma un cuvânt de cod în altul. Faptul că acesta este un cod cu distanța $3$ implică faptul că poate corecta până la o eroare de tip inversare a unui bit.

Descrierea codurilor liniare clasice

Exemplele menționate mai sus sunt exemple foarte simple de coduri liniare clasice, dar chiar și codul Hamming $[7,4,3]$ pare oarecum misterios atunci când cuvintele de cod sunt pur și simplu enumerate. Există modalități mai bune și mai eficiente de a descrie codurile liniare clasice, inclusiv următoarele două.

1. Generatori. O modalitate de a descrie un cod liniar clasic este cu o listă minimă de cuvinte de cod care generează codul, adică prin luarea tuturor subseturilor posibile ale acestor cuvinte de cod și aplicând XOR asupra lor, obținem întregul cod.

   Mai în detaliu, șirurile $u_1,\ldots,u_m\in\Sigma^n$ generează codul liniar clasic $\mathcal{C}$ dacă

   $$\mathcal{C} = \bigl\{\alpha_1 u_1 \oplus \cdots \oplus \alpha_m u_m\,:\,\alpha_1,\ldots,\alpha_m\in\{0,1\}\bigr\},$$

   cu înțelegerea că $\alpha u = u$ când $\alpha = 1$ și $\alpha u = 0^n$ când $\alpha = 0,$ și spunem că această listă este minimală dacă eliminarea unuia dintre șiruri generează un cod mai mic. O modalitate naturală de a gândi o astfel de descriere este că mulțimea $\{u_1,\ldots,u_m\}$ formează o bază pentru $\mathcal{C}$ ca subspațiu, unde ne gândim la șiruri ca la vectori cu componente de valoare binară, ținând cont că lucrăm într-un spațiu vectorial unde aritmetica se face modulo $2.$

2. Verificări de paritate. O altă modalitate naturală de a descrie un cod liniar clasic este prin verificări de paritate — adică o listă minimală de șiruri binare pentru care șirurile din cod sunt exact cele al căror produs punct binar cu fiecare dintre aceste șiruri de verificare a parității este zero. (Similar cu SAU-exclusiv pe biți, produsul punct binar a apărut de mai multe ori în „Fundamentele algoritmilor cuantici".)

   Adică, șirurile $v_1,\ldots,v_r\in\Sigma^n$ sunt șiruri de verificare a parității pentru codul liniar clasic $\mathcal{C}$ dacă

   $$\mathcal{C} = \bigl\{ u\in \Sigma^n\,:\, u\cdot v_1 = \cdots = u \cdot v_r = 0 \bigr\},$$

   și această mulțime de șiruri este minimală dacă eliminarea unuia duce la un cod mai mare. Acestea se numesc șiruri de verificare a parității deoarece $u$ are produsul punct binar egal cu zero față de $v$ dacă și numai dacă biții lui $u$ de pe pozițiile unde $v$ are 1 au paritate pară. Deci, pentru a determina dacă un șir $u$ se află în codul $\mathcal{C},$ este suficient să verifici paritatea anumitor submulțimi de biți ai lui $u.$

   Un lucru important de observat este că produsul punct binar nu este un produs intern în sens formal. În special, atunci când două șiruri au produsul punct binar egal cu zero, asta nu înseamnă că sunt ortogonale în modul în care ne gândim de obicei la ortogonalitate. De exemplu, produsul punct binar al șirului $11$ cu el însuși este zero — deci este posibil ca un șir de verificare a parității pentru un cod liniar clasic să se afle el însuși în cod.

Codurile liniare clasice peste alfabetul binar conțin întotdeauna un număr de șiruri care este o putere a lui $2$ — și pentru un singur cod liniar clasic descris în cele două moduri tocmai prezentate, va fi întotdeauna adevărat că $n = m + r.$ În particular, dacă avem o mulțime minimală de $m$ generatori, atunci codul codifică $m$ biți și vom avea în mod necesar $2^m$ cuvinte de cod; și dacă avem o mulțime minimală de $r$ șiruri de verificare a parității, atunci vom avea $2^{n-r}$ cuvinte de cod. Deci, fiecare generator dublează dimensiunea spațiului codului, în timp ce fiecare șir de verificare a parității înjumătățește dimensiunea spațiului codului.

De exemplu, codul de repetiție pe 3 biți este un cod liniar, deci poate fi descris în ambele moduri. În particular, există o singură alegere pentru un generator care funcționează: $111.$ Putem descrie alternativ codul cu două șiruri de verificare a parității, cum ar fi $110$ și $011$ — care ar trebui să fie familiare din discuțiile noastre anterioare despre acest cod — sau am putea lua șirurile de verificare a parității ca $110$ și $101,$ sau $101$ și $011.$ (Generatorii și șirurile de verificare a parității nu sunt în general unici pentru un cod liniar clasic dat.)

Pentru un al doilea exemplu, considerăm codul Hamming $[7,4,3]$. Iată o alegere pentru o listă de generatori care funcționează.

$$\begin{array}{c} 1111000\\[1mm] 0110100\\[1mm] 1010010\\[1mm] 1100001 \end{array}$$

Și iată o alegere pentru o listă de verificări de paritate pentru acest cod.

$$\begin{array}{c} 1111000\\[1mm] 1100110\\[1mm] 1010101 \end{array}$$

Observă că, în acest caz, toate șirurile noastre de verificare a parității se află ele însele în cod.

O ultimă remarcă despre codurile liniare clasice, care le conectează la formalismul Stabilizer, este că șirurile de verificare a parității sunt echivalente cu generatorii Stabilizer care constau numai din matricele Pauli $Z$ și identitate. De exemplu, șirurile de verificare a parității $110$ și $011$ pentru codul de repetiție pe 3 biți corespund exact generatorilor Stabilizer $Z\otimes Z\otimes \mathbb{I}$ și $\mathbb{I}\otimes Z\otimes Z,$ ceea ce este consistent cu discuțiile despre observabilele Pauli din lecția anterioară.

Definiția codurilor CSS

Codurile CSS sunt coduri Stabilizer obținute prin combinarea anumitor perechi de coduri liniare clasice. Aceasta nu funcționează pentru două coduri liniare clasice arbitrare — cele două coduri trebuie să aibă o relație anume. Cu toate acestea, această construcție deschide multe posibilități pentru codurile cuantice de corectare a erorilor, bazate în parte pe peste 75 de ani de teorie clasică a codificării.

În formalismul Stabilizer, generatorii Stabilizer care conțin numai matricele Pauli $Z$ și identitate sunt echivalenți cu verificările de paritate, așa cum am observat tocmai pentru codul de repetiție pe 3 biți. Pentru un alt exemplu, considerăm următoarele șiruri de verificare a parității pentru codul Hamming $[7,4,3]$.

$$\begin{array}{c} 1111000\\[1mm] 1100110\\[1mm] 1010101 \end{array}$$

Aceste șiruri de verificare a parității corespund următorilor generatori Stabilizer (scrisi fără simboluri de produs tensorial), pe care îi obținem înlocuind fiecare $1$ cu un $Z$ și fiecare $0$ cu un $\mathbb{I}.$ Aceștia sunt trei dintre cei șase generatori Stabilizer pentru codul Steane de 7 qubiți.

$$\begin{array}{ccccccc} Z & Z & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] Z & Z & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} \\[1mm] Z & \mathbb{I} & Z & \mathbb{I} & Z & \mathbb{I} & Z \end{array}$$

Să numim generatori Stabilizer $Z$ generatorii de acest tip, adică cei care conțin doar Pauli $Z$ și factori tensoriali identitate — astfel, matricele Pauli $X$ și $Y$ nu apar niciodată în generatorii Stabilizer $Z$.

Putem considera și generatori Stabilizer în care apar ca factori tensoriali doar matricele Pauli $X$ și identitatea. Generatorii de acest fel pot fi priviți ca analogi ai generatorilor Stabilizer $Z$, cu deosebirea că descriu verificări de paritate în baza $\{\vert+\rangle,\vert-\rangle\}$ în loc de baza standard. Generatorii Stabilizer de această formă se numesc generatori Stabilizer $X$ — de data aceasta nu sunt permise matricele Pauli $Y$ sau $Z$.

De exemplu, să considerăm ceilalți trei generatori Stabilizer din codul Steane de 7 qubiți.

$$\begin{array}{ccccccc} X & X & X & X & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] X & X & \mathbb{I} & \mathbb{I} & X & X & \mathbb{I} \\[1mm] X & \mathbb{I} & X & \mathbb{I} & X & \mathbb{I} & X \end{array}$$

Urmează exact același tipar din codul $[7,4,3]$-Hamming ca și generatorii Stabilizer $Z$, cu excepția că de data aceasta substituim $X$ în loc de $1$, în loc de $Z.$ Ceea ce obținem doar din acești trei generatori Stabilizer este un cod care include cele 16 stări prezentate mai jos, pe care le obținem aplicând operații Hadamard stărilor din baza standard ce corespund șirurilor din codul $[7,4,3]$-Hamming. (Desigur, spațiul codului pentru acest cod include și combinații liniare ale acestor stări.)

$$\begin{array}{cccc} \vert {+++++++} \rangle \quad & \vert {--++++-} \rangle \quad & \vert {-+-++-+} \rangle \quad & \vert {+--++--} \rangle \\ \vert {+--+-++} \rangle \quad & \vert {-+-+-+-} \rangle \quad & \vert {--++--+} \rangle \quad & \vert {++++---} \rangle \\ \vert {----+++} \rangle \quad & \vert {++--++-} \rangle \quad & \vert {+-+-+-+} \rangle \quad & \vert {-++-+--} \rangle \\ \vert {-++--++} \rangle \quad & \vert {+-+--+-} \rangle \quad & \vert {++----+} \rangle \quad & \vert {-------} \rangle \end{array}$$

Putem acum defini codurile CSS în termeni foarte simpli.

Definiție

Un cod CSS este un cod Stabilizer care poate fi exprimat folosind doar generatori Stabilizer $X$ și $Z$.

Adică, codurile CSS sunt coduri Stabilizer pentru care avem generatori Stabilizer în care nu apar matrice Pauli $Y$, și pentru care $X$ și $Z$ nu apar niciodată în același generator Stabilizer.

Pentru a fi clar, conform acestei definiții, un cod CSS este unul pentru care este posibil să alegi doar generatori Stabilizer $X$ și $Z$ — dar trebuie să ținem minte că există libertate în modul în care alegem generatorii Stabilizer pentru codurile Stabilizer. Astfel, în general vor exista diferite alegeri pentru generatorii Stabilizer ai unui cod CSS care nu sunt generatori Stabilizer $X$ sau $Z$ (pe lângă cel puțin o alegere pentru care sunt).

Iată un exemplu foarte simplu de cod CSS care include atât un generator Stabilizer $Z$, cât și un generator Stabilizer $X$:

$$\begin{array}{cc} Z & Z \\[1mm] X & X \end{array}$$

Este clar că acesta este un cod CSS, deoarece primul generator Stabilizer este un generator Stabilizer $Z$, iar al doilea este un generator Stabilizer $X$. Desigur, un cod CSS trebuie să fie și un cod Stabilizer valid — adică generatorii Stabilizer trebuie să comute, să formeze o mulțime generatoare minimală și să fixeze cel puțin un vector de stare cuantică. Aceste cerințe sunt ușor de verificat pentru acest cod. Așa cum am menționat în lecția anterioară, spațiul codului pentru acest cod este spațiul unidimensional generat de starea Bell $\vert\phi^+\rangle$. Faptul că ambii generatori Stabilizer fixează această stare reiese considerând următoarele două expresii ale unui e-bit, împreună cu o interpretare a acestor generatori Stabilizer ca verificări de paritate în bazele $\{\vert 0\rangle, \vert 1\rangle\}$ și $\{\vert +\rangle, \vert -\rangle\}$.

$$\vert\phi^+\rangle = \frac{\vert 0\rangle\vert 0\rangle + \vert 1\rangle\vert 1\rangle}{\sqrt{2}} = \frac{\vert +\rangle\vert +\rangle + \vert -\rangle\vert -\rangle}{\sqrt{2}}$$

Codul Steane de 7 qubiți este un alt exemplu de cod CSS.

$$\begin{array}{ccccccc} Z & Z & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] Z & Z & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} \\[1mm] Z & \mathbb{I} & Z & \mathbb{I} & Z & \mathbb{I} & Z \\[1mm] X & X & X & X & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] X & X & \mathbb{I} & \mathbb{I} & X & X & \mathbb{I} \\[1mm] X & \mathbb{I} & X & \mathbb{I} & X & \mathbb{I} & X \end{array}$$

Avem aici trei generatori Stabilizer $Z$ și trei generatori Stabilizer $X$, și am verificat deja că acesta este un cod Stabilizer valid.

Iar codul Shor de 9 qubiți este un alt exemplu.

$$\begin{array}{ccccccccc} Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z\\[1mm] X & X & X & X & X & X & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I}& X & X & X & X & X & X \end{array}$$

De data aceasta avem șase generatori Stabilizer $Z$ și doar doi generatori Stabilizer $X$. Acest lucru este în regulă, nu trebuie să existe un echilibru sau o simetrie între cele două tipuri de generatori (deși adesea există).

Încă o dată, este esențial că codurile CSS sunt coduri Stabilizer valide, și în special fiecare generator Stabilizer $Z$ trebuie să comute cu fiecare generator Stabilizer $X$. Prin urmare, nu orice colecție de generatori Stabilizer $X$ și $Z$ definește un cod CSS valid.

Detecția și corectarea erorilor

În ceea ce privește detecția și corectarea erorilor, codurile CSS în general au o caracteristică similară cu codul Shor de 9 qubiți, și anume că erorile $X$ și $Z$ pot fi detectate și corectate complet independent; generatorii Stabilizer $Z$ descriu un cod care protejează împotriva inversărilor de bit, iar generatorii Stabilizer $X$ descriu un cod care protejează independent împotriva inversărilor de fază. Acest lucru funcționează deoarece generatorii Stabilizer $Z$ comută în mod necesar cu erorile $Z$, precum și cu operațiile $Z$ aplicate ca corecții, deci sunt complet insensibili la ambele, și la fel se întâmplă pentru generatorii Stabilizer $X$, erori și corecții.

Ca exemplu, să considerăm codul Steane de 7 qubiți.

$$\begin{array}{ccccccc} Z & Z & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] Z & Z & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} \\[1mm] Z & \mathbb{I} & Z & \mathbb{I} & Z & \mathbb{I} & Z \\[1mm] X & X & X & X & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] X & X & \mathbb{I} & \mathbb{I} & X & X & \mathbb{I} \\[1mm] X & \mathbb{I} & X & \mathbb{I} & X & \mathbb{I} & X \end{array}$$

Ideea de bază pentru acest cod este acum evidentă: este un cod $[7,4,3]$-Hamming pentru erorile de inversare a bitului și un cod $[7,4,3]$-Hamming pentru erorile de inversare a fazei. Faptul că generatorii Stabilizer $X$ și $Z$ comută este poate o fericită coincidență, deoarece acesta nu ar fi un cod Stabilizer valid dacă nu ar comuta. Dar există, de fapt, multe exemple cunoscute de coduri liniare clasice care produc un cod Stabilizer valid atunci când sunt utilizate într-un mod similar.

În general, să presupunem că avem un cod CSS pentru care generatorii Stabilizer $Z$ permit corectarea a până la $j$ erori de inversare a bitului, iar generatorii Stabilizer $X$ permit corectarea a până la $k$ erori de inversare a fazei. De exemplu, $j = 1$ și $k = 1$ pentru codul Steane, dat fiind că codul $[7,4,3]$-Hamming poate corecta o singură inversare de bit. Rezultă, prin discretizarea erorilor, că acest cod CSS poate corecta orice eroare pe un număr de qubiți de cel mult minimul dintre $j$ și $k.$ Aceasta se întâmplă deoarece, atunci când se măsoară sindromul, o eroare arbitrară pe acest număr de qubiți colapsează probabilistic într-o combinație de erori $X$, erori $Z$ sau ambele — iar apoi erorile $X$ și erorile $Z$ sunt detectate și corectate independent.

Pe scurt, dacă avem două coduri liniare clasice (sau două copii ale unui singur cod liniar clasic) care sunt compatibile, în sensul că definesc generatori Stabilizer $X$ și $Z$ care comută, codul CSS obținut prin combinarea lor moștenește proprietățile de corectare a erorilor ale celor două coduri, în sensul tocmai descris.

Observă că există și un cost, și anume că nu putem codifica la fel de mulți qubiți câte biți am fi putut codifica cu cele două coduri clasice. Aceasta deoarece numărul total de generatori Stabilizer pentru codul CSS este suma numărului de șiruri de verificare a parității pentru cele două coduri liniare clasice, iar fiecare generator Stabilizer înjumătățește dimensiunea spațiului codului. De exemplu, codul $[7,4,3]$-Hamming permite codificarea a patru biți clasici, deoarece are doar trei șiruri de verificare a parității, în timp ce codul Steane de 7 qubiți codifică un singur qubit, deoarece are șase generatori Stabilizer.

Spațiile codului pentru codurile CSS

Ultimul lucru pe care îl vom face în această discuție despre codurile CSS este să analizăm spațiile codului ale acestor coduri. Aceasta ne va oferi ocazia de a examina în mai mare detaliu relația care trebuie să existe între două coduri liniare clasice pentru ca ele să fie compatibile, în sensul că pot fi combinate pentru a forma un cod CSS.

Consideră orice cod CSS pe $n$ qubiți și fie $z_1, \ldots, z_s \in \Sigma^n$ șirurile de verificare a parității de $n$ biți care corespund generatorilor Stabilizer $Z$ ai acestui cod. Aceasta înseamnă că codul liniar clasic descris doar de generatorii Stabilizer $Z$, pe care îl vom numi $\mathcal{C}_Z,$ are următoarea formă.

$$\mathcal{C}_Z = \bigl\{ u \in \Sigma^n \,:\, u \cdot z_1 = \cdots = u \cdot z_s = 0 \bigr\}$$

Cu alte cuvinte, codul liniar clasic $\mathcal{C}_Z$ conține fiecare șir al cărui produs scalar binar cu fiecare șir de verificare a parității $z_1, \ldots, z_s$ este zero.

În mod similar, fie $x_1,\ldots,x_t\in\Sigma^n$ șirurile de verificare a parității de $n$ biți corespunzătoare generatorilor Stabilizer $X$ ai codului nostru. Astfel, codul liniar clasic corespunzător generatorilor Stabilizer $X$ are această formă.

$$\mathcal{C}_X = \bigl\{ u \in \Sigma^n \,:\, u \cdot x_1 = \cdots = u \cdot x_t = 0 \bigr\}$$

Generatorii Stabilizer $X$ singuri descriu prin urmare un cod similar cu acesta, dar în baza $\{\vert {+}\rangle,\vert {-}\rangle\}$ în loc de baza standard.

Vom introduce acum două noi coduri liniare clasice derivate din aceleași alegeri de șiruri, $z_1,\ldots,z_s$ și $x_1,\ldots,x_t,$ dar unde luăm aceste șiruri drept generatori în loc de șiruri de verificare a parității. Obținem în particular aceste două coduri.

$$\begin{aligned} \mathcal{D}_Z & = \bigl\{ \alpha_1 z_1 \oplus \cdots \oplus \alpha_s z_s \,:\, \alpha_1,\ldots,\alpha_s \in \{0,1\} \bigr\}\\[1mm] \mathcal{D}_X & = \bigl\{ \alpha_1 x_1 \oplus \cdots \oplus \alpha_t x_t \,:\, \alpha_1,\ldots,\alpha_t \in \{0,1\} \bigr\} \end{aligned}$$

Acestea sunt cunoscute drept codurile duale ale codurilor definite anterior: $\mathcal{D}_Z$ este codul dual al lui $\mathcal{C}_Z$, iar $\mathcal{D}_X$ este codul dual al lui $\mathcal{C}_X.$ S-ar putea să nu fie clar în acest moment de ce sunt relevante aceste coduri duale, dar ele se dovedesc a fi destul de relevante din mai multe motive, inclusiv cele două motive explicate în paragrafele următoare.

În primul rând, condițiile care trebuie îndeplinite pentru ca două coduri liniare clasice $\mathcal{C}_Z$ și $\mathcal{C}_X$ să fie compatibile, în sensul că pot fi asociate pentru a forma un cod CSS, pot fi descrise simplu prin referire la codurile duale. Mai precis, trebuie ca $\mathcal{D}_Z\subseteq\mathcal{C}_X,$ sau echivalent, că $\mathcal{D}_X\subseteq\mathcal{C}_Z.$ Cu alte cuvinte, codul dual $\mathcal{D}_Z$ include șirurile corespunzătoare generatorilor Stabilizer $Z$, iar includerea lor în $\mathcal{C}_X$ este echivalentă cu faptul că produsul scalar binar al fiecăruia dintre aceste șiruri cu cele corespunzătoare generatorilor Stabilizer $X$ este zero. Aceasta, la rândul ei, este echivalentă cu faptul că fiecare generator Stabilizer $Z$ comută cu fiecare generator Stabilizer $X$. Alternativ, inversând rolurile generatorilor Stabilizer $X$ și $Z$ și pornind de la includerea $\mathcal{D}_X\subseteq\mathcal{C}_Z,$ putem ajunge la aceeași concluzie.

În al doilea rând, prin referire la codurile duale, putem descrie cu ușurință spațiile codului pentru un cod CSS dat. În particular, spațiul codului este generat de vectori de următoarea formă.

$$\vert u \oplus \mathcal{D}_X\rangle = \frac{1}{\sqrt{2^t}} \sum_{v\in\mathcal{D}_X} \vert u \oplus v\rangle \qquad \text{(for all $u\in\mathcal{C}_Z$)}$$

Cu alte cuvinte, acești vectori sunt superpoziții uniforme peste șirurile din codul dual $\mathcal{D}_X$ al codului corespunzător generatorilor Stabilizer $X$, deplasate cu (cu alte cuvinte, XOR-ate bit cu bit cu) șiruri din codul $\mathcal{C}_Z$ corespunzător generatorilor Stabilizer $Z$. Trebuie precizat că alegeri diferite pentru deplasare — reprezentate de șirul $u$ în această expresie — pot produce același vector. Prin urmare, aceste stări nu sunt toate distincte, dar colectiv ele generează întregul spațiu al codului.

Iată o explicație intuitivă pentru motivul pentru care astfel de vectori se află atât în spațiul codului, cât și îl generează. Consideră starea din baza standard pe $n$ qubiți $\vert u\rangle,$ pentru un șir arbitrar de $n$ biți $u,$ și presupune că proiectăm această stare pe spațiul codului. Cu alte cuvinte, notând cu $\Pi$ proiecția pe spațiul codului al codului nostru CSS, consideră vectorul $\Pi\vert u\rangle.$ Există două cazuri:

• Cazul 1: $u\in\mathcal{C}_Z.$ Aceasta implică faptul că fiecare generator Stabilizer $Z$ al codului nostru CSS acționează trivial asupra $\vert u\rangle.$ Generatorii Stabilizer $X$, pe de altă parte, inversează pur și simplu unii dintre biții lui $\vert u\rangle.$ Mai precis, pentru fiecare generator $v$ al lui $\mathcal{D}_X,$ generatorul Stabilizer $X$ corespunzător lui $v$ transformă $\vert u\rangle$ în $\vert u\oplus v\rangle.$ Caracterizând proiecția $\Pi$ ca media peste elementele stabilizatorului (după cum am văzut în lecția anterioară), obținem această formulă:

  $$\Pi \vert u \rangle = \frac{1}{2^t} \sum_{v\in\mathcal{D}_{X}} \vert u \oplus v\rangle = \frac{1}{\sqrt{2^t}} \vert u \oplus \mathcal{D}_X\rangle.$$

• Cazul 2: $u\notin\mathcal{C}_Z.$ Aceasta implică faptul că cel puțin una dintre verificările de paritate corespunzătoare generatorilor Stabilizer $Z$ eșuează, adică $\vert u\rangle$ trebuie să fie un vector propriu cu valoarea proprie $-1$ al cel puțin unuia dintre generatorii Stabilizer $Z$. Spațiul codului al codului CSS este intersecția spațiilor proprii cu valoarea proprie $+1$ ale generatorilor Stabilizer. Astfel, ca vector propriu cu valoarea proprie $-1$ al cel puțin unuia dintre generatorii Stabilizer $Z$, $\vert u\rangle$ este ortogonal pe spațiul codului:

  $$\Pi\vert u\rangle = 0.$$

Și acum, parcurgând toate șirurile de $n$ biți $u$, eliminând pe cele pentru care $\Pi\vert u\rangle = 0$ și normalizând pe cele rămase, obținem vectorii descriși anterior, ceea ce demonstrează că ei generează spațiul codului.

Putem folosi și simetria dintre generatorii Stabilizer $X$ și $Z$ pentru a descrie spațiul codului într-un mod similar, dar diferit. Mai precis, este spațiul generat de vectori de forma următoare.

$$H^{\otimes n} \vert u \oplus \mathcal{D}_Z\rangle = \frac{1}{\sqrt{2^s}} \sum_{v\in\mathcal{D}_Z} H^{\otimes n}\vert u \oplus v\rangle \qquad \text{(for $u\in\mathcal{C}_X$)}$$

În esență, $X$ și $Z$ au fost interschimbate în fiecare loc în care apar — dar trebuie să interschimbăm și baza standard cu baza $\{\vert+\rangle,\vert-\rangle\}$, motiv pentru care sunt incluse operațiile Hadamard.

Ca exemplu, să considerăm codul Steane de 7 qubiți. Șirurile de verificare a parității atât pentru generatorii Stabilizer $X$, cât și pentru generatorii Stabilizer $Z$ sunt aceleași: $1111000,$ $1100110,$ și $1010101.$ Codurile $\mathcal{C}_X$ și $\mathcal{C}_Z$ sunt prin urmare identice; ambele sunt egale cu codul $[7,4,3]$-Hamming.

$$\mathcal{C}_X = \mathcal{C}_Z = \{0000000, 0000111, 0011001, 0011110, 0101010, 0101101, 0110011, 0110100, 1001011, 1001100, 1010010, 1010101, 1100001, 1100110, 1111000, 1111111\}$$

Codurile duale $\mathcal{D}_X$ și $\mathcal{D}_Z$ sunt prin urmare și ele identice. Avem trei generatori, deci obținem opt șiruri.

$$\mathcal{D}_X = \mathcal{D}_Z = \{0000000, 0011110, 0101101, 0110011, 1001011, 1010101, 1100110, 1111000\}$$

Aceste șiruri sunt toate conținute în codul $[7,4,3]$-Hamming, astfel că este îndeplinită condiția CSS: $\mathcal{D}_Z \subseteq \mathcal{C}_X,$ sau echivalent, $\mathcal{D}_X \subseteq \mathcal{C}_Z.$

Dat fiind că $\mathcal{D}_X$ conține jumătate din toate șirurile lui $\mathcal{C}_Z,$ există doar doi vectori diferiți $\vert u\oplus \mathcal{D}_X\rangle$ ce pot fi obținuți alegând $u\in\mathcal{C}_Z.$ Aceasta era de așteptat, deoarece codul Steane de 7 qubiți are un spațiu al codului bidimensional. Putem folosi cele două stări obținute astfel pentru a codifica starea logică $\vert 0\rangle$ și $\vert 1\rangle$ după cum urmează.

$$\begin{aligned} \vert 0\rangle & \mapsto \frac{ \vert 0000000\rangle + \vert 0011110\rangle + \vert 0101101\rangle + \vert 0110011\rangle + \vert 1001011\rangle + \vert 1010101\rangle + \vert 1100110\rangle + \vert 1111000\rangle }{\sqrt{8}}\\[4mm] \vert 1\rangle & \mapsto \frac{ \vert 0000111\rangle + \vert 0011001\rangle + \vert 0101010\rangle + \vert 0110100\rangle + \vert 1001100\rangle + \vert 1010010\rangle + \vert 1100001\rangle + \vert 1111111\rangle }{\sqrt{8}} \end{aligned}$$

Ca de obicei, această alegere nu ne este impusă — suntem liberi să folosim spațiul codului pentru a codifica qubiți după cum dorim.