Kody repetycyjne

Zaczniemy tę lekcję od omówienia kodów repetycyjnych. Kody repetycyjne nie chronią informacji kwantowej przed każdym rodzajem błędu, który może pojawić się na qubitach, ale stanowią podstawę 9-qubitowego kodu Shora, który poznasz w następnej lekcji, a poza tym dobrze nadają się do wyjaśnienia podstaw korekcji błędów.

Klasyczne kodowanie i dekodowanie

Kody repetycyjne to absolutnie podstawowe przykłady kodów korekcyjnych. Chodzi o to, że możemy chronić bity przed błędami, po prostu powtarzając każdy bit określoną liczbę razy.

Zacznijmy od 3-bitowego kodu repetycyjnego, rozważanego wyłącznie w kontekście klasycznej informacji. Ten kod koduje jeden bit na trzy bity, powtarzając bit trzykrotnie — a zatem $0$ jest kodowane jako $000$, a $1$ jako $111.$

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

Jeśli nic nie pójdzie nie tak, z łatwością odróżnimy obie możliwe wartości oryginalnego bitu na podstawie ich kodowań. Sęk w tym, że jeżeli nastąpił błąd i jeden z trzech bitów się odwrócił — czyli 0 zmieniło się w 1 lub 1 w 0 — to wciąż możemy odtworzyć oryginalny bit, ustalając, która z dwóch wartości binarnych pojawia się dwa razy. Równoważnie, możemy dekodować, obliczając wartość większościową (tzn. wartość binarną, która pojawia się najczęściej).

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

Oczywiście, jeśli odwrócą się 2 lub 3 bity kodowania, dekodowanie nie zadziała poprawnie i zostanie odtworzony błędny bit — jednak jeśli odwróci się co najwyżej 1 z 3 bitów, dekodowanie będzie prawidłowe. To typowa właściwość kodów korekcyjnych ogólnie: mogą one umożliwiać korekcję błędów, ale tylko wtedy, gdy tych błędów nie jest zbyt wiele.

Redukcja szumów dla binarnego kanału symetrycznego

Jako przykład sytuacji, w której prawdopodobieństwo popełnienia błędu można zmniejszyć za pomocą kodu repetycyjnego, wyobraź sobie, że chcesz przesłać pojedynczy bit do hipotetycznego odbiorcy, dysponując tak zwanym binarnym kanałem symetrycznym, który niezależnie odwraca każdy przesyłany przez siebie bit z pewnym prawdopodobieństwem $p.$ Innymi słowy, z prawdopodobieństwem $1-p$ odbiorca otrzymuje ten sam bit, który został wysłany kanałem, lecz z prawdopodobieństwem $p$ bit ulega odwróceniu i odbiorca otrzymuje przeciwną wartość bitu.

Jeśli więc zdecydujesz się nie korzystać z 3-bitowego kodu repetycyjnego i po prostu wyślesz wybrany bit kanałem, odbiorca otrzyma błędny bit z prawdopodobieństwem $p.$ Z drugiej strony, jeśli najpierw zakodujemy bit za pomocą 3-bitowego kodu repetycyjnego, a następnie każdy z trzech bitów kodowania wyślemy kanałem, to każdy z nich odwróci się niezależnie z prawdopodobieństwem $p.$ Prawdopodobieństwo odwrócenia bitu jest teraz wyższe, bo są trzy bity, które mogą się odwrócić zamiast jednego — jednak jeśli odwróci się co najwyżej jeden bit, odbiorca zdekoduje poprawnie. Błąd po dekodowaniu pojawia się więc tylko wtedy, gdy podczas transmisji odwrócą się dwa lub więcej bitów.

Prawdopodobieństwo odwrócenia dokładnie dwóch bitów podczas transmisji wynosi $3p^2(1-p)$ — jest to $p^2(1-p)$ dla każdego z trzech możliwych wyborów bitu, który się nie odwraca — natomiast prawdopodobieństwo odwrócenia wszystkich trzech bitów wynosi $p^3.$ Całkowite prawdopodobieństwo odwrócenia dwóch lub trzech bitów wynosi zatem

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

Dla wartości $p$ mniejszych od jednej drugiej daje to zmniejszenie prawdopodobieństwa, że odbiorca skończy z błędnym bitem. Szansa na błąd nadal istnieje, ale kod zmniejsza to prawdopodobieństwo. (Natomiast dla wartości $p$ większych od jednej drugiej kod wręcz zwiększa prawdopodobieństwo, że odbiorca otrzyma błędny bit.)

Kodowanie qubitów

3-bitowy kod repetycyjny jest klasycznym kodem korekcyjnym, ale możemy sprawdzić, co się stanie, jeśli spróbujemy użyć go do ochrony qubitów przed błędami. Jak się przekonamy, nie jest to zbyt imponujący kwantowy kod korekcyjny, bo w rzeczywistości zwiększa prawdopodobieństwo niektórych błędów. Stanowi jednak pierwszy krok ku kodowi Shora i świetnie posłuży nam z dydaktycznego punktu widzenia.

Żeby było jasne: gdy mówimy o 3-bitowym kodzie repetycyjnym stosowanym do qubitów, mamy na myśli kodowanie qubitu, w którym stany bazy standardowej są powtarzane trzykrotnie, tak że wektor stanu jednego qubitu jest kodowany następująco.

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

To kodowanie można łatwo zaimplementować za pomocą poniższego obwodu kwantowego, który korzysta z dwóch zainicjalizowanych qubitów pomocniczych oraz dwóch bramek CNOT.

Zauważ w szczególności, że to kodowanie nie jest tym samym co trzykrotne powtórzenie stanu kwantowego w postaci $\vert\psi\rangle \mapsto \vert\psi\rangle\vert\psi\rangle\vert\psi\rangle.$ Takiego kodowania nie można zaimplementować dla nieznanego stanu kwantowego $\vert\psi\rangle$ ze względu na twierdzenie o zakazie klonowania.

Błędy odwrócenia bitu

Załóżmy teraz, że po wykonaniu kodowania pojawia się błąd. Konkretnie, przypuśćmy, że na jednym z qubitów działa bramka $X$, czyli innymi słowy następuje odwrócenie bitu. Na przykład, jeśli środkowy qubit doświadcza odwrócenia bitu, stan trzech qubitów przekształca się w następujący stan:

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

Oczywiście to nie jedyny rodzaj błędu, który może wystąpić — i słusznie można też kwestionować założenie, że błąd przybiera postać doskonałej, unitarnej operacji. Wrócimy do tych kwestii w ostatniej części lekcji; na razie możemy traktować błąd tej postaci jako jeden z możliwych typów błędów (choć fundamentalnie ważny).

Z wyrażenia matematycznego na powyższy stan jasno wynika, że środkowy bit jest tym, który różni się wewnątrz każdego ketu. Ale wyobraź sobie, że masz w ręku trzy qubity i nie znasz ich stanu. Jeśli podejrzewasz, że mogło nastąpić odwrócenie bitu, jedną z opcji weryfikacji byłoby wykonanie pomiaru w bazie standardowej, który w tym przypadku da wynik $010$ lub $101$ z prawdopodobieństwami odpowiednio $\vert\alpha\vert^2$ i $\vert\beta\vert^2.$ W obu przypadkach doszedłbyś do wniosku, że środkowy bit się odwrócił — niestety jednak utraciłbyś oryginalny stan kwantowy $\alpha\vert 0\rangle + \beta \vert 1\rangle.$ To właśnie ten stan próbujemy chronić, więc pomiar w bazie standardowej nie jest satysfakcjonującą opcją.

Zamiast tego możemy skorzystać z poniższego obwodu kwantowego, podając zakodowany stan na wejście trzech górnych qubitów. Ten obwód niedestruktywnie mierzy parzystość stanów bazy standardowej dwóch górnych qubitów oraz dwóch dolnych qubitów trójqubitowego kodowania.

Zakładając, że odwrócił się co najwyżej jeden bit, można łatwo wywnioskować z wyników pomiaru, gdzie nastąpiło odwrócenie bitu (lub że do niego nie doszło). Konkretnie, jak ilustrują poniższe cztery schematy obwodów, wynik pomiaru $00$ oznacza, że żaden bit się nie odwrócił, natomiast trzy pozostałe możliwości wskazują, który qubit doświadczył odwrócenia bitu.

Co kluczowe, stan trzech górnych qubitów nie ulega kolapsowi w żadnym z tych przypadków, co pozwala nam skorygować błąd odwrócenia bitu, jeśli do niego doszło — wystarczy zastosować ponownie to samo odwrócenie bitu za pomocą bramki $X$. Poniższa tabela podsumowuje stany otrzymywane przy co najwyżej jednym odwróceniu bitu, wyniki pomiaru (zwane syndromem w kontekście korekcji błędów) oraz korektę potrzebną do powrotu do oryginalnego kodowania.

Stan	Syndrom	Korekcja
$\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}$

Ponownie rozważamy jedynie możliwość, że odwrócił się co najwyżej jeden bit. Nie zadziałałoby to poprawnie, gdyby odwróciły się dwa lub trzy bity, a poza tym nie wzięliśmy jeszcze pod uwagę innych możliwych błędów poza odwróceniami bitów.

Błędy odwrócenia fazy

W środowisku kwantowym błędy odwrócenia bitu nie są jedynymi błędami, o które musimy się martwić. Na przykład, musimy też brać pod uwagę błędy odwrócenia fazy, opisywane przez bramki $Z$. Podobnie jak w przypadku błędów odwrócenia bitu, możemy traktować błędy odwrócenia fazy jako kolejny możliwy rodzaj błędu, który może dotknąć qubit.

Jednak, jak zobaczymy w ostatniej części lekcji poświęconej tzw. dyskretyzacji błędów dla kwantowych kodów korekcyjnych, skupienie się na błędach odwrócenia bitu i odwrócenia fazy jest dobrze uzasadnione. Konkretnie, zdolność do korekcji błędu odwrócenia bitu, błędu odwrócenia fazy lub obu tych błędów jednocześnie automatycznie implikuje zdolność do korekcji dowolnego błędu kwantowego na pojedynczym qubicie.

Niestety, 3-bitowy kod repetycyjny w ogóle nie chroni przed odwróceniami fazy. Na przykład, przypuśćmy, że stan qubitu $\alpha\vert 0\rangle + \beta\vert 1\rangle$ został zakodowany za pomocą 3-bitowego kodu repetycyjnego, a na środkowym qubicie pojawia się błąd odwrócenia fazy. Daje to stan

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

który jest dokładnie tym stanem, jaki otrzymalibyśmy po zakodowaniu stanu qubitu $\alpha\vert 0\rangle - \beta\vert 1\rangle.$ Rzeczywiście, błąd odwrócenia fazy na którymkolwiek z trzech qubitów kodowania daje ten sam efekt, równoważny błędowi odwrócenia fazy na oryginalnym qubicie przed kodowaniem. Zakładając, że oryginalny stan kwantowy jest nieznany, nie ma więc żadnego sposobu na wykrycie, że wystąpił błąd, ponieważ wynikowy stan jest całkowicie poprawnym kodowaniem innego stanu qubitu. W szczególności, uruchomienie wcześniejszego obwodu wykrywania błędów na stanie $\alpha \vert 000\rangle - \beta \vert 111\rangle$ z pewnością da syndrom $00$, co błędnie sugeruje, że żadne błędy nie wystąpiły.

Tymczasem mamy teraz trzy qubity zamiast jednego, które potencjalnie mogą doświadczyć błędów odwrócenia fazy. Tak więc w sytuacji, gdy błędy odwrócenia fazy są zakładane jako niezależne na każdym qubicie z pewnym niezerowym prawdopodobieństwem $p$ (podobnie jak binarny kanał symetryczny, tyle że dla odwróceń fazy zamiast odwróceń bitu), ten kod faktycznie zwiększa prawdopodobieństwo błędu odwrócenia fazy po dekodowaniu dla małych wartości $p.$ Mówiąc dokładniej, błąd odwrócenia fazy na oryginalnym qubicie po dekodowaniu pojawi się wtedy, gdy wystąpi nieparzysta liczba błędów odwrócenia fazy na trzech qubitach kodowania, co zdarza się z prawdopodobieństwem

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

Ta wartość jest większa niż $p$ dla $0<p<1/2$, więc kod zwiększa prawdopodobieństwo błędu odwrócenia fazy dla wartości $p$ w tym zakresie.

Zmodyfikowany kod repetycyjny dla błędów odwrócenia fazy

Zaobserwowaliśmy, że 3-bitowy kod repetycyjny jest całkowicie ślepy na błędy odwrócenia fazy, więc nie wydaje się zbyt pomocny w radzeniu sobie z tego rodzaju błędem. Możemy jednak w prosty sposób zmodyfikować 3-bitowy kod repetycyjny tak, aby wykrywał błędy odwrócenia fazy. Ta modyfikacja sprawi, że kod będzie ślepy na błędy odwrócenia bitu — ale, jak zobaczymy w następnej sekcji, oba kody, które właśnie poznaliśmy, możemy połączyć, aby otrzymać kod Shora, który potrafi korygować zarówno błędy odwrócenia bitu, jak i odwrócenia fazy.

Oto zmodyfikowana wersja powyższego obwodu kodowania, która będzie teraz w stanie wykrywać błędy odwrócenia fazy. Modyfikacja jest bardzo prosta: po wykonaniu dwóch bramek CNOT stosujemy bramkę Hadamard do każdego qubitu.

Bramka Hadamard przekształca stan $\vert 0\rangle$ w stan $\vert + \rangle$, a stan $\vert 1\rangle$ w stan $\vert - \rangle$, więc łączny efekt jest taki, że stan jednego qubitu $\alpha\vert 0\rangle + \beta \vert 1\rangle$ jest kodowany jako

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

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

Błąd odwrócenia fazy, czyli równoważnie bramka $Z$, zamienia miejscami stany $\vert + \rangle$ i $\vert - \rangle$, więc to kodowanie będzie przydatne do wykrywania (i korygowania) błędów odwrócenia fazy. Konkretnie, obwód wykrywania błędów z wcześniej można zmodyfikować następująco.

Mówiąc po ludzku, bierzemy poprzedni obwód i po prostu dodajemy bramki Hadamard na trzech górnych qubitach na początku i na końcu. Chodzi o to, że pierwsze trzy bramki Hadamard przekształcają stany $\vert + \rangle$ i $\vert - \rangle$ z powrotem w stany $\vert 0\rangle$ i $\vert 1\rangle$, następnie tak jak poprzednio wykonywane są te same sprawdzenia parzystości, a potem druga warstwa bramek Hadamard przekształca stan z powrotem w stany $\vert + \rangle$ i $\vert - \rangle$, aby odtworzyć nasze kodowanie. Na przyszłość zauważmy, że ten obwód wykrywania błędów fazy można uprościć w następujący sposób.

Poniższe cztery schematy obwodów opisują, jak zmodyfikowana wersja 3-bitowego kodu repetycyjnego — obejmująca etap kodowania i etap wykrywania błędów — działa przy co najwyżej jednym błędzie odwrócenia fazy. Zachowanie jest podobne do zwykłego 3-bitowego kodu repetycyjnego dla odwróceń bitu.

Oto analogiczna tabela do tej powyżej, tym razem rozważająca możliwość co najwyżej jednego błędu odwrócenia fazy.

Stan	Syndrom	Korekcja
$\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}$

Niestety, ta zmodyfikowana wersja 3-bitowego kodu repetycyjnego nie jest już w stanie korygować błędów odwrócenia bitu. Nie wszystko jednak stracone. Jak wcześniej sugerowaliśmy, będziemy mogli połączyć oba kody, które właśnie poznaliśmy, w jeden kod — 9-qubitowy kod Shora — który potrafi korygować zarówno błędy odwrócenia bitu, jak i odwrócenia fazy, a właściwie dowolny błąd na pojedynczym qubicie.