Kody CSS

Klasyczne kody liniowe

Klasyczne kody korekcji błędów były po raz pierwszy badane w latach 40. XX wieku i od tamtej pory poznano wiele różnych kodów. Najczęściej studiowane i stosowane kody należą do kategorii zwanej kodami liniowymi. Za chwilę zobaczymy dokładnie, co słowo „liniowy" oznacza w tym kontekście, ale bardzo prosto można to wyrazić już teraz: kody liniowe to kody stabilizatorowe, które akurat są klasyczne. Kody CSS to w istocie pary klasycznych kodów liniowych, łączone razem w celu stworzenia kwantowego kodu korekcji błędów. Żeby dobrze zrozumieć omawiane dalej zagadnienia, musimy najpierw poznać kilka podstawowych faktów o klasycznych kodach liniowych.

Niech $\Sigma$ będzie binarnym alfabetem w całej tej dyskusji. Przez klasyczny kod liniowy rozumiemy niepusty zbiór $\mathcal{C}\subseteq\Sigma^n$ binarnych ciągów długości $n,$ dla pewnej dodatniej liczby całkowitej $n,$ który musi spełniać jedną podstawową własność: jeśli $u$ i $v$ są binarnymi ciągami należącymi do $\mathcal{C},$ to ciąg $u\oplus v$ również należy do $\mathcal{C}.$ Tutaj $u\oplus v$ oznacza bitowe XOR ciągów $u$ i $v,$ z którym spotykaliśmy się wielokrotnie w kursie „Fundamentals of quantum algorithms".

Mówiąc wprost: gdy klasyczny kod korekcji błędów nazywamy liniowym, traktujemy binarne ciągi długości $n$ jako $n$-wymiarowe wektory o wpisach przyjmujących wartości $0$ lub $1$ i wymagamy, by sam kod tworzył podprzestrzeń liniową. Zamiast zwykłego dodawania wektorów nad liczbami rzeczywistymi lub zespolonymi stosujemy jednak dodawanie modulo $2,$ czyli po prostu XOR. Oznacza to, że jeśli mamy dwa słowa kodowe $u$ i $v,$ czyli $u$ i $v$ są binarnymi ciągami należącymi do $\mathcal{C},$ to $u + v$ modulo 2, czyli $u\oplus v,$ musi być również słowem kodowym w $\mathcal{C}.$ Warto zauważyć, że ten warunek musi zachodzić nawet wtedy, gdy $u = v.$ Wynika z tego, że $\mathcal{C}$ musi zawierać ciąg samych zer $0^n,$ ponieważ bitowe XOR dowolnego ciągu z samym sobą daje ciąg samych zer.

Przykład: 3-bitowy repetition code

3-bitowy repetition code jest przykładem klasycznego kodu liniowego. W szczególności mamy $\mathcal{C} = \{000,111\},$ więc pod względem warunku liniowości są tylko dwie możliwe wartości $u$ i dwie możliwe wartości $v.$ Łatwo sprawdzić wszystkie cztery możliwe pary i przekonać się, że bitowe XOR zawsze daje słowo kodowe:

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

Przykład: kod $[7,4,3]$-Hamming

Oto kolejny przykład klasycznego kodu liniowego — kod $[7,4,3]$-Hamming. Był jednym z pierwszych kiedykolwiek odkrytych klasycznych kodów korekcji błędów i składa się z tych 16 binarnych ciągów długości 7. (Czasami kod $[7,4,3]$-Hamming rozumiany jest jako kod z tymi ciągami odwróconymi, ale tutaj przyjmujemy, że jest to kod zawierający ciągi pokazane poniżej.)

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

Za doborem tych ciągów stoi bardzo prosta logika, ale jest ona drugorzędna wobec tematu lekcji i nie będziemy jej tu wyjaśniać. Na razie wystarczy stwierdzić, że jest to klasyczny kod liniowy: XOR dowolnych dwóch spośród tych ciągów zawsze da inny ciąg należący do kodu.

Notacja $[7,4,3]$ (w pojedynczych nawiasach kwadratowych) oznacza coś analogicznego do notacji z podwójnymi nawiasami kwadratowymi dla kodów stabilizatorowych wspomnianej w poprzedniej lekcji, lecz dotyczy klasycznych kodów liniowych. W szczególności: słowa kodowe mają $7$ bitów, za pomocą kodu możemy zakodować $4$ bity (ponieważ istnieje $16 = 2^4$ słów kodowych), a odległość kodu wynosi $3$, co oznacza, że dowolne dwa różne słowa kodowe muszą różnić się na co najmniej $3$ pozycjach — zatem co najmniej $3$ bity muszą zostać przekłamane, by zamienić jedno słowo kodowe w inne. Fakt, że jest to kod o odległości $3$, oznacza, że może on korygować maksymalnie jeden błąd przekłamania bitu.

Opisywanie klasycznych kodów liniowych

Wspomniane przykłady są bardzo prostymi przykładami klasycznych kodów liniowych, jednak nawet kod $[7,4,3]$-Hamming wygląda dość tajemniczo, gdy słowa kodowe są po prostu wypisane. Istnieją lepsze, bardziej efektywne sposoby opisywania klasycznych kodów liniowych, w tym dwa następujące.

1. Generatory. Jednym ze sposobów opisania klasycznego kodu liniowego jest minimalna lista słów kodowych, które generują kod, tzn. biorąc wszystkie możliwe podzbiory tych słów kodowych i wykonując na nich XOR, otrzymujemy cały kod.

   Dokładniej, ciągi $u_1,\ldots,u_m\in\Sigma^n$ generują klasyczny kod liniowy $\mathcal{C},$ jeśli

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

   przy czym $\alpha u = u$ gdy $\alpha = 1$ oraz $\alpha u = 0^n$ gdy $\alpha = 0,$ i mówimy, że lista jest minimalna, jeśli usunięcie jednego z ciągów generuje mniejszy kod. Naturalny sposób myślenia o takim opisie to traktowanie zbioru $\{u_1,\ldots,u_m\}$ jako bazy dla $\mathcal{C}$ jako podprzestrzeni, gdzie ciągi traktujemy jako wektory o binarnych wpisach, pamiętając, że pracujemy w przestrzeni wektorowej, w której arytmetyka jest wykonywana modulo $2.$

2. Parity checks. Innym naturalnym sposobem opisania klasycznego kodu liniowego są parity checks — czyli minimalna lista binarnych ciągów, dla których ciągi należące do kodu to dokładnie te, których binarne iloczyny skalarne z każdym z tych ciągów parity check wynoszą zero. (Podobnie jak bitowe XOR, binarne iloczyny skalarne pojawiały się kilkakrotnie w kursie „Fundamentals of quantum algorithms".)

   Oznacza to, że ciągi $v_1,\ldots,v_r\in\Sigma^n$ są ciągami parity check dla klasycznego kodu liniowego $\mathcal{C},$ jeśli

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

   a zbiór tych ciągów jest minimalny, gdy usunięcie jednego skutkuje większym kodem. Ciągi te nazywane są ciągami parity check, ponieważ $u$ ma binarny iloczyn skalarny równy zero z $v$ wtedy i tylko wtedy, gdy bity $u$ na pozycjach, gdzie $v$ ma jedynki, mają parzysty parity. Tak więc, aby sprawdzić, czy ciąg $u$ należy do kodu $\mathcal{C},$ wystarczy sprawdzić parity pewnych podzbiorów bitów ciągu $u.$

   Ważną rzeczą do zauważenia jest to, że binarny iloczyn skalarny nie jest iloczynem wewnętrznym w formalnym sensie. W szczególności, gdy dwa ciągi mają binarny iloczyn skalarny równy zero, nie oznacza to, że są ortogonalne w zwykłym sensie. Na przykład binarny iloczyn skalarny ciągu $11$ z samym sobą wynosi zero — możliwe jest zatem, że ciąg parity check dla klasycznego kodu liniowego sam należy do tego kodu.

Klasyczne kody liniowe nad binarnym alfabetem zawsze zawierają liczbę ciągów będącą potęgą $2$ — i dla pojedynczego klasycznego kodu liniowego opisanego na dwa opisane powyżej sposoby zawsze zachodzi $n = m + r.$ W szczególności, jeśli mamy minimalny zbiór $m$ generatorów, kod koduje $m$ bitów i będziemy mieć $2^m$ słów kodowych; a jeśli mamy minimalny zbiór $r$ ciągów parity check, będziemy mieć $2^{n-r}$ słów kodowych. Tak więc każdy generator podwaja rozmiar przestrzeni kodu, podczas gdy każdy ciąg parity check ją o połowę zmniejsza.

Na przykład, 3-bitowy repetition code jest kodem liniowym, więc można go opisać na obydwa te sposoby. W szczególności, istnieje tylko jeden wybór generatora, który działa: $111.$ Alternatywnie możemy opisać kod za pomocą dwóch ciągów parity check, takich jak $110$ i $011$ — które powinny być znajome z poprzednich dyskusji o tym kodzie — albo możemy wziąć ciągi parity check $110$ i $101,$ bądź $101$ i $011.$ (Generatory i ciągi parity check są na ogół niejednoznaczne dla danego klasycznego kodu liniowego.)

Jako drugi przykład rozważmy kod $[7,4,3]$-Hamming. Oto jeden z możliwych wyborów listy generatorów, który działa.

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

A oto jeden z możliwych wyborów ciągów parity check dla tego kodu.

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

Warto przy okazji zauważyć, że wszystkie nasze ciągi parity check same należą do kodu.

Na koniec jedna uwaga dotycząca klasycznych kodów liniowych, która łączy je z formalizmem stabilizatorów: ciągi parity check są równoważne generatorom stabilizatorów składającym się wyłącznie z macierzy Pauli $Z$ i macierzy jednostkowych. Na przykład ciągi parity check $110$ i $011$ dla 3-bitowego repetition code odpowiadają dokładnie generatorom stabilizatorów $Z\otimes Z\otimes \mathbb{I}$ oraz $\mathbb{I}\otimes Z\otimes Z,$ co jest spójne z omówieniami obserwabli Pauli z poprzedniej lekcji.

Definition of CSS codes

Kody CSS to kody stabilizatorowe otrzymywane przez łączenie ze sobą określonych par klasycznych kodów liniowych. Nie działa to dla dowolnych dwóch klasycznych kodów liniowych — oba kody muszą spełniać pewien wzajemny warunek. Niemniej to podejście otwiera wiele możliwości w zakresie kwantowych kodów korekcji błędów, częściowo czerpiąc z ponad 75 lat klasycznej teorii kodowania.

W formalizmie stabilizatorowym generatory stabilizatora zawierające tylko macierze Pauli $Z$ oraz tożsamościowe są równoważne parity check, co właśnie zaobserwowaliśmy na przykładzie 3-bitowego kodu repetycyjnego. Jako kolejny przykład rozważ następujące ciągi parity check dla kodu $[7,4,3]$-Hamming.

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

Te ciągi parity check odpowiadają następującym generatorom stabilizatora (zapisanym bez symboli iloczynu tensorowego), które otrzymujemy, zastępując każde $1$ przez $Z$, a każde $0$ przez $\mathbb{I}.$ Są to trzy z sześciu generatorów stabilizatora dla 7-qubitowego kodu Steane'a.

$$\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}$$

Nadajmy generatorom stabilizatora tego rodzaju nazwę generatorów stabilizatora $Z$, co oznacza, że zawierają one wyłącznie czynniki tensorowe Pauli $Z$ i tożsamości — a zatem macierze Pauli $X$ i $Y$ nigdy nie występują w generatorach stabilizatora $Z$.

Możemy też rozważyć generatory stabilizatora, w których jako czynniki tensorowe pojawiają się tylko macierze $X$ i tożsamościowe. Takie generatory stabilizatora można traktować jako analogiczne do generatorów stabilizatora $Z$, z tą różnicą, że opisują parity check w bazie $\{\vert+\rangle,\vert-\rangle\}$, a nie w bazie standardowej. Generatory stabilizatora tej postaci nazywane są generatorami stabilizatora $X$ — tym razem nie są dozwolone macierze Pauli $Y$ ani $Z$.

Jako przykład rozważ pozostałe trzy generatory stabilizatora z 7-qubitowego kodu Steane'a.

$$\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}$$

Podążają dokładnie tym samym wzorcem z kodu $[7,4,3]$-Hamming co generatory stabilizatora $Z$, z tą różnicą, że tym razem wstawiamy $X$ zamiast $1$, a nie $Z.$ To, co otrzymujemy wyłącznie z tych trzech generatorów stabilizatora, to kod obejmujący 16 stanów pokazanych poniżej, które uzyskujemy, stosując operacje Hadamarda do stanów bazy standardowej odpowiadających ciągom w kodzie $[7,4,3]$-Hamming. (Oczywiście przestrzeń kodu dla tego kodu obejmuje także kombinacje liniowe tych stanów.)

$$\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}$$

Możemy teraz zdefiniować kody CSS w bardzo prostych słowach.

Definicja

Kod CSS to kod stabilizatorowy, który można wyrazić używając wyłącznie generatorów stabilizatora $X$ i $Z$.

Oznacza to, że kody CSS to kody stabilizatorowe, dla których mamy generatory stabilizatora, w których nie pojawiają się macierze Pauli $Y$, oraz w których $X$ i $Z$ nigdy nie występują w tym samym generatorze stabilizatora.

Dla jasności, według tej definicji kod CSS to taki, dla którego możliwy jest wybór wyłącznie generatorów stabilizatora $X$ i $Z$ — należy jednak pamiętać, że wybór generatorów stabilizatora dla kodów stabilizatorowych nie jest jednoznaczny. W związku z tym będą na ogół istnieć różne wybory generatorów stabilizatora kodu CSS, które nie są generatorami stabilizatora $X$ ani $Z$ (oprócz co najmniej jednego wyboru, dla którego nimi są).

Oto bardzo prosty przykład kodu CSS zawierającego zarówno generator stabilizatora $Z$, jak i generator stabilizatora $X$:

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

Jasno widać, że jest to kod CSS, ponieważ pierwszy generator stabilizatora jest generatorem stabilizatora $Z$, a drugi — generatorem stabilizatora $X$. Oczywiście kod CSS musi być też poprawnym kodem stabilizatorowym — co oznacza, że generatory stabilizatora muszą komutować, tworzyć minimalny zbiór generujący i ustalać co najmniej jeden wektor stanu kwantowego. Te wymagania są łatwe do sprawdzenia w przypadku tego kodu. Jak zauważyliśmy w poprzedniej lekcji, przestrzeń kodu dla tego kodu to jednowymiarowa przestrzeń rozpiętana przez stan Bella $\vert\phi^+\rangle$. Fakt, że oba generatory stabilizatora ustalają ten stan, jest oczywisty po rozważeniu dwóch poniższych wyrażeń e-bitu wraz z interpretacją tych generatorów stabilizatora jako parity check w bazach $\{\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}}$$

7-qubitowy kod Steane'a to kolejny przykład kodu 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}$$

Mamy tutaj trzy generatory stabilizatora $Z$ i trzy generatory stabilizatora $X$, a poprawność tego kodu stabilizatorowego już zweryfikowaliśmy.

9-qubitowy kod Shora to kolejny przykład.

$$\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}$$

Tym razem mamy sześć generatorów stabilizatora $Z$ i tylko dwa generatory stabilizatora $X$. To jest w porządku — nie musi istnieć równowaga ani symetria między oboma typami generatorów (choć często tak jest).

Jeszcze raz warto podkreślić, że kody CSS muszą być poprawnymi kodami stabilizatorowymi, a w szczególności każdy generator stabilizatora $Z$ musi komutować z każdym generatorem stabilizatora $X$. A zatem nie każda kolekcja generatorów stabilizatora $X$ i $Z$ definiuje poprawny kod CSS.

Wykrywanie i korekcja błędów

Jeśli chodzi o wykrywanie i korekcję błędów, kody CSS mają ogólnie podobną właściwość do 9-qubitowego kodu Shora — mianowicie błędy $X$ i $Z$ można wykrywać i korygować całkowicie niezależnie; generatory stabilizer dla $Z$ opisują kod chroniący przed przerzuceniami bitów, a generatory stabilizer dla $X$ opisują kod niezależnie chroniący przed przerzuceniami fazy. Działa to dlatego, że generatory stabilizer dla $Z$ koniecznie komutują zarówno z błędami $Z$, jak i z operacjami $Z$ stosowanymi jako korekty — są więc na nie całkowicie obojętne; analogicznie dzieje się z generatorami stabilizer dla $X$, błędami $X$ i korektami $X$.

Jako przykład rozważmy 7-qubitowy kod Steane'a.

$$\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}$$

Podstawowa idea tego kodu jest teraz wyraźna: to kod Hamminga $[7,4,3]$ dla błędów przerzucenia bitu oraz kod Hamminga $[7,4,3]$ dla błędów przerzucenia fazy. To, że generatory stabilizer dla $X$ i $Z$ komutują, można uznać za szczęśliwy zbieg okoliczności — gdyby tak nie było, nie mielibyśmy poprawnego kodu stabilizer. Istnieje jednak wiele znanych przykładów klasycznych kodów liniowych, które użyte w analogiczny sposób dają poprawny kod stabilizer.

Ogólnie rzecz biorąc, przyjmijmy, że mamy kod CSS, w którym generatory stabilizer dla $Z$ pozwalają korygować do $j$ błędów przerzucenia bitu, a generatory stabilizer dla $X$ pozwalają korygować do $k$ błędów przerzucenia fazy. Na przykład dla kodu Steane'a $j = 1$ i $k = 1$, gdyż kod Hamminga $[7,4,3]$ potrafi skorygować jedno przerzucenie bitu. Wynika z tego, na mocy dyskretyzacji błędów, że ten kod CSS może korygować dowolny błąd na liczbie kubitów nieprzekraczającej minimum z $j$ i $k.$ Dzieje się tak dlatego, że podczas pomiaru syndrome arbitralny błąd na takiej liczbie kubitów probabilistycznie zapada się do pewnej kombinacji błędów $X$, błędów $Z$ lub obu — a następnie błędy $X$ i $Z$ są wykrywane i korygowane niezależnie.

Podsumowując: o ile dysponujemy dwoma klasycznymi kodami liniowymi (lub dwoma kopiami jednego klasycznego kodu liniowego), które są ze sobą zgodne w tym sensie, że definiują generatory stabilizer dla $X$ i $Z$ komutujące ze sobą, to uzyskany przez ich połączenie kod CSS dziedziczy własności korekcji błędów obu tych kodów w opisany właśnie sposób.

Należy jednak zauważyć, że wiąże się z tym pewna cena: nie możemy kodować tylu kubitów, ile bitów dałoby się zakodować za pomocą tych dwóch kodów klasycznych. Wynika to stąd, że całkowita liczba generatorów stabilizer kodu CSS jest sumą liczby parity check obu klasycznych kodów liniowych, a każdy generator stabilizer zmniejsza wymiar przestrzeni kodu o połowę. Na przykład kod Hamminga $[7,4,3]$ pozwala kodować cztery klasyczne bity, bo ma tylko trzy łańcuchy parity check, natomiast 7-qubitowy kod Steane'a koduje tylko jeden qubit, gdyż ma sześć generatorów stabilizer.

Przestrzenie kodowe kodów CSS

Ostatnią rzeczą, którą zrobimy w tym omówieniu kodów CSS, jest rozważenie przestrzeni kodowych tych kodów. Da nam to możliwość bardziej szczegółowego zbadania relacji, która musi zachodzić między dwoma klasycznymi kodami liniowymi, aby były one kompatybilne w tym sensie, że można je połączyć w kod CSS.

Rozważmy dowolny kod CSS na $n$ kubitach i niech $z_1, \ldots, z_s \in \Sigma^n$ będą $n$-bitowymi ciągami parity check odpowiadającymi generatorom stabilizatora $Z$ tego kodu. Oznacza to, że klasyczny kod liniowy opisany wyłącznie przez generatory stabilizatora $Z$, który nazwiemy $\mathcal{C}_Z,$ przyjmuje następującą postać.

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

Innymi słowy, klasyczny kod liniowy $\mathcal{C}_Z$ zawiera każdy ciąg, którego binarny iloczyn skalarny z każdym z ciągów parity check $z_1, \ldots, z_s$ wynosi zero.

Analogicznie, niech $x_1,\ldots,x_t\in\Sigma^n$ będą $n$-bitowymi ciągami parity check odpowiadającymi generatorom stabilizatora $X$ naszego kodu. Zatem klasyczny kod liniowy odpowiadający generatorom stabilizatora $X$ przyjmuje następującą postać.

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

Same generatory stabilizatora $X$ opisują zatem kod podobny do tego kodu, ale w bazie $\{\vert {+}\rangle,\vert {-}\rangle\}$ zamiast w bazie standardowej.

Teraz wprowadzimy dwa nowe klasyczne kody liniowe, które są wyprowadzone z tych samych wyborów ciągów, $z_1,\ldots,z_s$ oraz $x_1,\ldots,x_t,$ ale gdzie traktujemy te ciągi jako generatory zamiast ciągów parity check. W szczególności otrzymujemy te dwa kody.

$$\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}$$

Są one znane jako kody dualne kodów zdefiniowanych wcześniej: $\mathcal{D}_Z$ jest kodem dualnym do $\mathcal{C}_Z,$ a $\mathcal{D}_X$ jest kodem dualnym do $\mathcal{C}_X.$ W tym miejscu może nie być jasne, dlaczego te kody dualne są istotne, ale okazują się one być dość istotne z wielu powodów, w tym z dwóch powodów wyjaśnionych w następnych akapitach.

Po pierwsze, warunki, które muszą być spełnione, aby dwa klasyczne kody liniowe $\mathcal{C}_Z$ i $\mathcal{C}_X$ były kompatybilne, w tym sensie, że można je połączyć w kod CSS, można opisać w prostych słowach, odwołując się do kodów dualnych. Mówiąc dokładniej, musi zachodzić $\mathcal{D}_Z\subseteq\mathcal{C}_X,$ lub równoważnie, $\mathcal{D}_X\subseteq\mathcal{C}_Z.$ Innymi słowy, kod dualny $\mathcal{D}_Z$ zawiera ciągi odpowiadające generatorom stabilizatora $Z,$ a ich zawieranie się w $\mathcal{C}_X$ jest równoważne temu, że binarny iloczyn skalarny każdego z tych ciągów z ciągami odpowiadającymi generatorom stabilizatora $X$ jest zerowy. To z kolei jest równoważne temu, że każdy generator stabilizatora $Z$ komutuje z każdym generatorem stabilizatora $X.$ Alternatywnie, zamieniając role generatorów stabilizatorów $X$ i $Z$ oraz wychodząc od zawierania $\mathcal{D}_X\subseteq\mathcal{C}_Z,$ możemy dojść do tego samego wniosku.

Po drugie, odwołując się do kodów dualnych, możemy łatwo opisać przestrzenie kodowe danego kodu CSS. W szczególności przestrzeń kodowa jest rozpinana przez wektory następującej postaci.

$$\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$)}$$

Innymi słowy, wektory te są jednorodnymi superpozycjami ciągów z kodu dualnego $\mathcal{D}_X$ kodu odpowiadającego generatorom stabilizatora $X,$ przesuniętymi przez (innymi słowy, zXORowanymi bitowo z) ciągi z kodu $\mathcal{C}_Z$ odpowiadającego generatorom stabilizatora $Z.$ Dla jasności, różne wybory przesunięcia — reprezentowanego przez ciąg $u$ w tym wyrażeniu — mogą prowadzić do tego samego wektora. Zatem te stany nie są wszystkie różne, ale razem rozpinają całą przestrzeń kodową.

Oto intuicyjne wyjaśnienie, dlaczego takie wektory znajdują się w przestrzeni kodowej i ją rozpinają. Rozważmy $n$-kubitowy stan bazy standardowej $\vert u\rangle,$ dla dowolnego $n$-bitowego ciągu $u,$ i załóżmy, że rzutujemy ten stan na przestrzeń kodową. To znaczy, oznaczając przez $\Pi$ rzutowanie na przestrzeń kodową naszego kodu CSS, rozważmy wektor $\Pi\vert u\rangle.$ Są dwa przypadki:

• Przypadek 1: $u\in\mathcal{C}_Z.$ To oznacza, że każdy generator stabilizatora $Z$ naszego kodu CSS działa trywialnie na $\vert u\rangle.$ Z kolei generatory stabilizatora $X$ po prostu odwracają niektóre bity $\vert u\rangle.$ W szczególności, dla każdego generatora $v$ z $\mathcal{D}_X,$ generator stabilizatora $X$ odpowiadający $v$ przekształca $\vert u\rangle$ w $\vert u\oplus v\rangle.$ Charakteryzując rzutowanie $\Pi$ jako średnią po elementach stabilizatora (jak widzieliśmy w poprzedniej lekcji), otrzymujemy następujący wzór:

  $$\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.$$

• Przypadek 2: $u\notin\mathcal{C}_Z.$ To oznacza, że co najmniej jeden z parity checków odpowiadających generatorom stabilizatora $Z$ nie jest spełniony, czyli $\vert u\rangle$ musi być wektorem własnym o wartości własnej $-1$ co najmniej jednego z generatorów stabilizatora $Z.$ Przestrzeń kodowa kodu CSS jest przecięciem podprzestrzeni własnych o wartości własnej $+1$ generatorów stabilizatora. Zatem, jako wektor własny o wartości własnej $-1$ co najmniej jednego z generatorów stabilizatora $Z,$ $\vert u\rangle$ jest ortogonalny do przestrzeni kodowej:

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

A teraz, przechodząc po wszystkich $n$-bitowych ciągach $u,$ odrzucając te, dla których $\Pi\vert u\rangle = 0,$ i normalizując pozostałe, otrzymujemy wektory opisane wcześniej, co pokazuje, że rozpinają one przestrzeń kodową.

Możemy również wykorzystać symetrię między generatorami stabilizatorów $X$ i $Z,$ aby opisać przestrzeń kodową w podobny, ale inny sposób. W szczególności jest to przestrzeń rozpinana przez wektory o następującej postaci.

$$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$)}$$

Zasadniczo, $X$ i $Z$ zostały zamienione w każdym przypadku, w którym występują — ale musimy również zamienić bazę standardową na bazę $\{\vert+\rangle,\vert-\rangle\},$ dlatego uwzględniono operacje Hadamarda.

Jako przykład rozważmy 7-kubitowy kod Steane'a. Ciągi parity check zarówno dla generatorów stabilizatora $X,$ jak i $Z$ są takie same: $1111000,$ $1100110$ oraz $1010101.$ Kody $\mathcal{C}_X$ i $\mathcal{C}_Z$ są zatem takie same; oba są równe kodowi Hamminga $[7,4,3].$

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

Kody dualne $\mathcal{D}_X$ i $\mathcal{D}_Z$ są zatem również takie same. Mamy trzy generatory, więc otrzymujemy osiem ciągów.

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

Wszystkie te ciągi zawierają się w kodzie Hamminga $[7,4,3],$ więc warunek CSS jest spełniony: $\mathcal{D}_Z \subseteq \mathcal{C}_X,$ lub równoważnie, $\mathcal{D}_X \subseteq \mathcal{C}_Z.$

Biorąc pod uwagę, że $\mathcal{D}_X$ zawiera połowę wszystkich ciągów z $\mathcal{C}_Z,$ istnieją tylko dwa różne wektory $\vert u\oplus \mathcal{D}_X\rangle,$ które można uzyskać, wybierając $u\in\mathcal{C}_Z.$ Jest to oczekiwane, ponieważ 7-kubitowy kod Steane'a ma dwuwymiarową przestrzeń kodową. Możemy użyć dwóch stanów, które otrzymujemy w ten sposób, aby zakodować stany logiczne $\vert 0\rangle$ i $\vert 1\rangle$ w następujący sposób.

$$\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}$$

Jak zwykle, ten wybór nie jest nam narzucony — możemy dowolnie korzystać z przestrzeni kodowej do kodowania kubitów według własnego uznania.