Coduri de repetiție

Vom începe lecția cu o discuție despre codurile de repetiție. Codurile de repetiție nu protejează informația cuantică împotriva fiecărui tip de eroare care poate apărea pe qubiți, dar ele formează baza pentru codul Shor de 9 qubiți, pe care îl vom vedea în lecția următoare, și sunt de asemenea utile pentru explicarea elementelor de bază ale corecției erorilor.

Codificare și decodificare clasică

Codurile de repetiție sunt exemple extrem de elementare de coduri de corectare a erorilor. Ideea este că putem proteja biții împotriva erorilor repetând pur și simplu fiecare bit de un număr fix de ori.

În particular, să considerăm mai întâi codul de repetiție pe 3 biți, doar în contextul informației clasice pentru început. Acest cod codifică un bit în trei prin repetarea bitului de trei ori, deci $0$ este codificat ca $000$ și $1$ este codificat ca $111$.

$$\begin{aligned} 0 & \mapsto 000\\ 1 & \mapsto 111 \end{aligned}$$

Dacă nimic nu merge rău, putem distinge în mod evident cele două posibilități pentru bitul original din codificările lor. Ideea este că dacă a apărut o eroare și unul dintre cei trei biți s-a inversat, adică un 0 se schimbă în 1 sau un 1 se schimbă în 0, putem totuși să determinăm care era bitul original prin identificarea valorii binare care apare de două ori. Echivalent, putem decoda prin calcularea valorii majoritare (adică valoarea binară care apare cel mai frecvent).

$$a b c \mapsto \operatorname{majority}(a,b,c)$$

Bineînțeles, dacă 2 sau 3 biți ai codificării se inversează, decodificarea nu va funcționa corect și se va recupera bitul greșit, dar dacă cel mult 1 din cei 3 biți se inversează, decodificarea va fi corectă. Aceasta este o proprietate tipică a codurilor de corectare a erorilor în general: pot permite corecția erorilor, dar numai dacă nu sunt prea multe.

Reducerea zgomotului pentru canalul simetric binar

Pentru un exemplu de situație în care șansele de a face o eroare pot fi reduse folosind un cod de repetiție, presupune că scopul nostru este să comunicăm un singur bit unui receptor ipotetic și putem transmite biți printr-un așa-numit canal simetric binar, care inversează fiecare bit trimis prin el independent cu o probabilitate $p$. Adică, cu probabilitatea $1-p$, receptorul primește orice bit a fost trimis prin canal, dar cu probabilitatea $p$, bitul se inversează și receptorul primește valoarea opusă a bitului.

Deci, dacă alegem să nu folosim codul de repetiție pe 3 biți și pur și simplu trimitem orice bit avem în minte prin canal, receptorul primește, prin urmare, bitul greșit cu probabilitatea $p$. Pe de altă parte, dacă mai întâi codificăm bitul pe care vrem să-l trimitem folosind codul de repetiție pe 3 biți și apoi trimitem fiecare dintre cei trei biți ai codificării prin canal, atunci fiecare dintre ele se inversează independent cu probabilitatea $p$. Șansele de inversare a unui bit sunt acum mai mari deoarece există acum trei biți care s-ar putea inversa în loc de unul, dar dacă cel mult un bit se inversează, receptorul va decoda corect. O eroare persistă, prin urmare, după decodificare numai dacă doi sau mai mulți biți se inversează în timpul transmisiei.

Probabilitatea că doi biți se inversează în timpul transmisiei este $3p^2(1-p)$, care este $p^2(1-p)$ pentru fiecare dintre cele trei alegeri pentru bitul care nu se inversează, în timp ce probabilitatea că toți cei trei biți se inversează este $p^3$. Probabilitatea totală de două sau trei inversări de biți este, prin urmare

$$3 p^2 (1 - p) + p^3 = 3 p^2 - 2 p^3.$$

Pentru valori ale lui $p$ mai mici decât o jumătate, aceasta duce la o scădere a probabilității că receptorul ajunge cu bitul greșit. Va exista totuși o șansă de eroare în acest caz, dar codul scade probabilitatea. (Pentru valori ale lui $p$ mai mari decât o jumătate, pe de altă parte, codul de fapt crește probabilitatea că receptorul primește bitul greșit.)

Codificarea qubiților

Codul de repetiție pe 3 biți este un cod clasic de corectare a erorilor, dar putem considera ce se întâmplă dacă încercăm să-l folosim pentru a proteja qubiții împotriva erorilor. Așa cum vom vedea, nu este un cod cuantic de corectare a erorilor foarte impresionant, deoarece de fapt face unele erori mai probabile. Este, totuși, primul pas spre codul Shor și ne va servi bine dintr-un punct de vedere pedagogic.

Pentru a fi clar, atunci când ne referim la codul de repetiție pe 3 biți utilizat pentru qubiți, avem în vedere o codificare a unui qubit unde stările bazei standard sunt repetate de trei ori, astfel că un vector de stare al unui qubit unic este codificat după cum urmează.

$$\alpha \vert 0\rangle + \beta \vert 1\rangle \mapsto \alpha \vert 000\rangle + \beta \vert 111\rangle$$

Această codificare este ușor de implementat prin următorul circuit cuantic, care utilizează doi qubiți de spațiu de lucru inițializați și două porți CNOT.

Observă, în particular, că această codificare nu este la fel ca repetarea stării cuantice de trei ori, ca în cazul în care un vector de stare al qubitului dat ar fi codificat ca $\vert\psi\rangle \mapsto \vert\psi\rangle\vert\psi\rangle\vert\psi\rangle$. O astfel de codificare nu poate fi implementată pentru o stare cuantică necunoscută $\vert\psi\rangle$ din cauza teoremei non-clonării.

Erori de inversare a biților

Acum să presupunem că are loc o eroare după ce codificarea a fost efectuată. Mai exact, să presupunem că o poartă $X$, sau cu alte cuvinte o inversare de bit, apare pe unul dintre qubiți. De exemplu, dacă qubitul din mijloc suferă o inversare de bit, starea celor trei qubiți este transformată în această stare:

$$\alpha \vert 010\rangle + \beta \vert 101\rangle.$$

Bineînțeles, acesta nu este singurul tip de eroare care ar putea apărea — și este, de asemenea, rezonabil să punem la îndoială presupunerea că o eroare ia forma unei operații unitare perfecte. Ne vom întoarce la aceste probleme în ultima secțiune a lecției, iar deocamdată putem privi o eroare de acest tip ca fiind doar un tip posibil de eroare (deși unul fundamental important).

Putem vedea clar din expresia matematică pentru starea de mai sus că bitul din mijloc este cel care diferă în interiorul fiecărui ket. Dar să presupunem că am avea cei trei qubiți în posesia noastră și nu am ști starea lor. Dacă am suspecta că a avut loc o inversare de bit, o opțiune pentru a verifica dacă un bit s-a inversat ar fi să efectuăm o măsurătoare în baza standard, ceea ce, în cazul de față, ne-ar face să vedem $010$ sau $101$ cu probabilitățile $\vert\alpha\vert^2$ și $\vert\beta\vert^2$, respectiv. În ambele cazuri, concluzia noastră ar fi că bitul din mijloc s-a inversat — dar, din păcate, am pierde starea cuantică originală $\alpha\vert 0\rangle + \beta \vert 1\rangle$. Aceasta este starea pe care încercăm să o protejăm, deci măsurarea în baza standard este o opțiune nesatisfăcătoare.

Ceea ce putem face în schimb este să folosim următorul circuit cuantic, introducând starea codificată în primii trei qubiți de sus. Acest circuit măsoară nedistructiv paritatea stărilor din baza standard ale primilor doi qubiți de sus, precum și a ultimilor doi qubiți din codificarea cu trei qubiți.

Presupunând că cel mult un bit s-a inversat, se poate deduce cu ușurință din rezultatele măsurătorii locația inversării de bit (sau absența acesteia). În special, așa cum ilustrează următoarele patru diagrame de circuit, rezultatul măsurătorii $00$ indică faptul că nu a avut loc nicio inversare de bit, în timp ce celelalte trei posibilități indică care qubit a suferit o inversare de bit.

Este crucial că starea primilor trei qubiți nu colapsează în niciunul dintre cazuri, ceea ce ne permite să corectăm o eroare de inversare a bitului dacă a apărut una — prin simpla aplicare a aceleiași inversări de bit din nou cu o poartă $X$. Tabelul de mai jos rezumă stările pe care le obținem din cel mult o inversare a bitului, rezultatele măsurătorilor (care se numesc sindrom în contextul corecției erorilor) și corecția necesară pentru a reveni la codificarea originală.

Stare	Sindrom	Corecție
$\alpha\vert 000\rangle + \beta \vert 111\rangle$	$00$	$\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}$
$\alpha\vert 001\rangle + \beta \vert 110\rangle$	$01$	$\mathbb{I}\otimes\mathbb{I}\otimes X$
$\alpha\vert 010\rangle + \beta \vert 101\rangle$	$11$	$\mathbb{I}\otimes X\otimes\mathbb{I}$
$\alpha\vert 100\rangle + \beta \vert 011\rangle$	$10$	$X\otimes\mathbb{I}\otimes\mathbb{I}$

Încă o dată, luăm în considerare numai posibilitatea că cel mult o inversare a bitului a apărut. Aceasta nu ar funcționa corect dacă ar apărea două sau trei inversări de biți și, de asemenea, nu am luat în considerare alte erori posibile în afara inversărilor de biți.

Erori de inversare a fazei

În contextul cuantic, inversările de biți nu sunt singurele erori de care trebuie să ne îngrijorăm. De exemplu, trebuie să ne îngrijorăm și de erorile de inversare a fazei, care sunt descrise de porți $Z$. Pe aceeași linie cu erorile de inversare a biților, putem gândi erorile de inversare a fazei ca reprezentând doar o altă posibilitate pentru o eroare care poate afecta un qubit.

Cu toate acestea, după cum vom vedea în ultima secțiune a lecției, care se referă la așa-numita discretizare a erorilor pentru codurile cuantice de corectare a erorilor, o concentrare pe erorile de inversare a biților și erorile de inversare a fazei se dovedește a fi bine justificată. Concret, capacitatea de a corecta o eroare de inversare a bitului, o eroare de inversare a fazei sau ambele erori simultan implică automat capacitatea de a corecta o eroare cuantică arbitrară pe un singur qubit.

Din păcate, codul de repetiție pe 3 biți nu protejează deloc împotriva inversărilor de fază. De exemplu, presupune că o stare a qubitului $\alpha\vert 0\rangle + \beta\vert 1\rangle$ a fost codificată folosind codul de repetiție pe 3 biți și apare o eroare de inversare a fazei pe qubit-ul din mijloc. Aceasta duce la starea

$$(\mathbb{I} \otimes Z \otimes \mathbb{I}) ( \alpha \vert 000\rangle + \beta \vert 111\rangle) = \alpha \vert 000\rangle - \beta \vert 111\rangle,$$

care este exact starea pe care am fi obținut-o din codificarea stării qubitului $\alpha\vert 0\rangle - \beta\vert 1\rangle$. Într-adevăr, o eroare de inversare a fazei pe oricare dintre cei trei qubiți ai codificării are același efect, care este echivalent cu o eroare de inversare a fazei care apare pe qubit-ul original înainte de codificare. Presupunând că starea cuantică originală este necunoscută, nu există, prin urmare, nicio modalitate de a detecta că a apărut o eroare, deoarece starea rezultantă este o codificare perfect validă a unei stări diferite a qubitului. În particular, rularea circuitului de detectare a erorilor de mai devreme pe starea $\alpha \vert 000\rangle - \beta \vert 111\rangle$ va produce cu certitudine sindromul $00$, care sugerează în mod greșit că nu au apărut erori.

Între timp, există acum trei qubiți în loc de unul care ar putea experimenta erori de inversare a fazei. Deci, într-o situație în care se presupune că erorile de inversare a fazei apar independent pe fiecare qubit cu o probabilitate nenulă $p$ (similar cu un canal simetric binar, cu excepția că sunt inversări de fază în loc de inversări de biți), acest cod crește de fapt probabilitatea unei erori de inversare a fazei după decodificare pentru valori mici ale lui $p$. Mai precis, vom obține o eroare de inversare a fazei pe qubit-ul original după decodificare ori de câte ori există un număr impar de erori de inversare a fazei pe cei trei qubiți ai codificării, ceea ce se întâmplă cu probabilitatea

$$3 p (1 - p)^2 + p^3.$$

Această valoare este mai mare decât $p$ când $0<p<1/2$, deci codul crește probabilitatea unei erori de inversare a fazei pentru valori ale lui $p$ în acest interval.

Codul de repetiție modificat pentru erori de inversare a fazei

Am observat că codul de repetiție pe 3 biți este complet indiferent la erorile de inversare a fazei, deci nu pare să fie foarte util pentru a face față acestui tip de eroare. Putem, totuși, modifica codul de repetiție pe 3 biți într-un mod simplu astfel încât să detecteze erorile de inversare a fazei. Această modificare va face codul indiferent la erorile de inversare a biților — dar, după cum vom vedea în secțiunea următoare, putem combina codul de repetiție pe 3 biți cu această versiune modificată pentru a obține codul Shor, care poate corecta atât erorile de inversare a biților, cât și erorile de inversare a fazei.

Iată versiunea modificată a circuitului de codificare de mai sus, care va putea acum să detecteze erorile de inversare a fazei. Modificarea este foarte simplă: pur și simplu aplicăm o poartă Hadamard fiecărui qubit după efectuarea celor două porți CNOT.

O poartă Hadamard transformă o stare $\vert 0\rangle$ într-o stare $\vert + \rangle$ și o stare $\vert 1\rangle$ într-o stare $\vert - \rangle$, deci efectul net este că starea qubitului unic $\alpha\vert 0\rangle + \beta \vert 1\rangle$ este codificată ca

$$\alpha \vert {+}\,{+}\,{+} \rangle + \beta \vert {-}\,{-}\,{-} \rangle$$

unde $\vert {+}\,{+}\,{+} \rangle = \vert + \rangle \otimes \vert + \rangle \otimes\vert + \rangle$ și $\vert {-}\,{-}\,{-} \rangle = \vert - \rangle \otimes \vert - \rangle \otimes\vert - \rangle$.

O eroare de inversare a fazei, sau echivalent o poartă $Z$, inversează între stările $\vert + \rangle$ și $\vert - \rangle$, deci această codificare va fi utilă pentru detectarea (și corectarea) erorilor de inversare a fazei. Concret, circuitul de detectare a erorilor de mai devreme poate fi modificat după cum urmează.

Cu alte cuvinte, luăm circuitul de mai devreme și pur și simplu punem porți Hadamard pe primii trei qubiți atât la început, cât și la sfârșit. Ideea este că primele trei porți Hadamard transformă stările $\vert + \rangle$ și $\vert - \rangle$ înapoi în stările $\vert 0\rangle$ și $\vert 1\rangle$, aceleași verificări de paritate ca înainte au loc, și apoi al doilea strat de porți Hadamard transformă starea înapoi la stările $\vert + \rangle$ și $\vert - \rangle$ astfel încât să recuperăm codificarea noastră. Pentru referință viitoare, să observăm că acest circuit de detectare a inversărilor de fază poate fi simplificat după cum urmează.

Reține că rolul ancilei în porțile CNOT a fost schimbat comparativ cu verificarea inversării de bit. Acest lucru este legat de fenomenul de phase kickback discutat în cursul despre fundamentele algoritmilor cuantici.

Următoarele patru diagrame de circuit descriu cum funcționează versiunea noastră modificată a codului de repetiție pe 3 biți, inclusiv pasul de codificare și pasul de detectare a erorilor, atunci când apare cel mult o eroare de inversare a fazei. Comportamentul este similar cu codul de repetiție obișnuit pe 3 biți pentru inversările de biți.

Iată un tabel analog cu cel de mai sus, de data aceasta luând în considerare posibilitatea de cel mult o eroare de inversare a fazei.

Stare	Sindrom	Corecție
$\alpha\vert {+}\,{+}\,{+} \rangle + \beta \vert {-}\,{-}\,{-}\rangle$	$00$	$\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}$
$\alpha\vert {+}\,{+}\,{-}\rangle + \beta \vert {-}\,{-}\,{+}\rangle$	$01$	$\mathbb{I}\otimes\mathbb{I}\otimes Z$
$\alpha\vert {+}\,{-}\,{+}\rangle + \beta \vert {-}\,{+}\,{-}\rangle$	$11$	$\mathbb{I}\otimes Z\otimes\mathbb{I}$
$\alpha\vert {-}\,{+}\,{+} \rangle + \beta \vert {+}\,{-}\,{-}\rangle$	$10$	$Z\otimes\mathbb{I}\otimes\mathbb{I}$

Din păcate, această versiune modificată a codului de repetiție pe 3 biți nu mai poate corecta erorile de inversare a biților. Totuși, nu totul este pierdut. După cum am sugerat anterior, vom putea combina cele două coduri pe care tocmai le-am văzut într-un singur cod — codul Shor de 9 qubiți — care poate corecta atât erorile de inversare a biților, cât și cele de inversare a fazei, și, într-adevăr, orice eroare pe un singur qubit.