CSS kódy

Klasické lineární kódy

Klasické kódy opravující chyby se začaly studovat ve 40. letech 20. století a od té doby je známo mnoho různých kódů. Nejčastěji studované a používané kódy spadají do kategorie známé jako lineární kódy. Za chvíli přesně uvidíme, co slovo „lineární" v tomto kontextu znamená, ale velmi jednoduchý způsob, jak lineární kódy vyjádřit, je ten, že jde o stabilizátorové kódy, které jsou náhodou klasické. CSS kódy jsou v podstatě páry klasických lineárních kódů, které se kombinují dohromady za účelem vytvoření kvantového kódu opravujícího chyby. Takže pro účely následující diskuse budeme potřebovat porozumět několika základním věcem o klasických lineárních kódech.

Nechť $\Sigma$ je binární abeceda pro celou tuto diskusi. Když mluvíme o klasickém lineárním kódu, máme na mysli neprázdnou množinu $\mathcal{C}\subseteq\Sigma^n$ binárních řetězců délky $n$ pro nějaké kladné celé číslo $n,$ která musí splňovat jednu základní vlastnost: pokud $u$ a $v$ jsou binární řetězce v $\mathcal{C},$ pak řetězec $u\oplus v$ je také v $\mathcal{C}.$ Zde $u\oplus v$ označuje bitovou operaci exkluzivní-OR řetězců $u$ a $v,$ se kterou jsme se setkali několikrát v kurzu „Fundamentals of quantum algorithms".

V podstatě, když o klasickém kódu opravujícím chyby mluvíme jako o lineárním, představujeme si binární řetězce délky $n$ jako $n$-rozměrné vektory, jejichž složky jsou buď $0,$ nebo $1,$ a požadujeme, aby samotný kód tvořil lineární podprostor. Místo běžného vektorového sčítání nad reálnými nebo komplexními čísly však používáme sčítání modulo $2,$ což je prostě exkluzivní-OR. To znamená, že pokud máme dvě kódová slova $u$ a $v,$ tedy binární řetězce v $\mathcal{C},$ pak $u + v$ modulo 2, tedy $u\oplus v,$ musí být také kódovým slovem v $\mathcal{C}.$ Všimni si zejména, že tato implikace musí platit i v případě $u = v.$ Z toho vyplývá, že $\mathcal{C}$ musí obsahovat samý nulový řetězec $0^n,$ protože bitový exkluzivní-OR jakéhokoli řetězce se sebou samým je samý nulový řetězec.

Příklad: 3-bitový opakovací kód

3-bitový opakovací kód je příkladem klasického lineárního kódu. Konkrétně máme $\mathcal{C} = \{000,111\},$ takže vzhledem k podmínce linearity existují pouze dvě možné volby pro $u$ a dvě možné volby pro $v.$ Je triviální projít čtyři možné páry a ověřit, že při bitovém exkluzivním-OR vždy dostaneme kódové slovo:

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

Příklad: $[7,4,3]$-Hammingův kód

Zde je další příklad klasického lineárního kódu nazývaného $[7,4,3]$-Hammingův kód. Byl jedním z vůbec prvních klasických kódů opravujících chyby, které byly kdy objeveny, a skládá se z těchto 16 binárních řetězců délky 7. (Někdy se $[7,4,3]$-Hammingův kód chápe jako kód s těmito řetězci pozpátku, ale my budeme používat kód obsahující řetězce zobrazené zde.)

$$\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 výběrem těchto řetězců stojí velmi jednoduchá logika, ale to je vedlejší záležitost této lekce a nebude zde vysvětlena. Prozatím stačí pozorovat, že se jedná o klasický lineární kód: XOR jakýchkoli dvou těchto řetězců vždy dá další řetězec v kódu.

Zápis $[7,4,3]$ (v jednoduchých hranatých závorkách) znamená něco analogického k zápisu ve dvojitých hranatých závorkách pro stabilizátorové kódy zmíněnému v předchozí lekci, ale zde jde o klasické lineární kódy. Konkrétně kódová slova mají $7$ bitů, pomocí kódu můžeme zakódovat $4$ bity (protože je $16 = 2^4$ kódových slov) a jedná se o kód se vzdáleností $3,$ což znamená, že jakákoli dvě různá kódová slova se musí lišit alespoň ve $3$ pozicích — takže k přeměně jednoho kódového slova na jiné je třeba překlopit alespoň $3$ bity. Skutečnost, že se jedná o kód se vzdáleností $3,$ implikuje, že dokáže opravit až jednu chybu překlopení bitu.

Popis klasických lineárních kódů

Právě uvedené příklady jsou velmi jednoduché příklady klasických lineárních kódů, ale i $[7,4,3]$-Hammingův kód vypadá poněkud záhadně, když jsou kódová slova jednoduše vypsána. Existují lepší a efektivnější způsoby popisu klasických lineárních kódů, včetně následujících dvou způsobů.

1. Generátory. Jedním ze způsobů popisu klasického lineárního kódu je minimální seznam kódových slov, který kód generuje, což znamená, že vzájemným XORováním všech možných podmnožin těchto kódových slov dostaneme celý kód.

   Podrobněji, řetězce $u_1,\ldots,u_m\in\Sigma^n$ generují klasický lineární kód $\mathcal{C},$ pokud

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

   s tím, že $\alpha u = u$ když $\alpha = 1$ a $\alpha u = 0^n$ když $\alpha = 0,$ a říkáme, že tento seznam je minimální, pokud odstraněním jednoho z řetězců dostaneme menší kód. Přirozený způsob, jak o takovém popisu přemýšlet, je ten, že kolekce $\{u_1,\ldots,u_m\}$ tvoří bázi pro $\mathcal{C}$ jako podprostor, kde si řetězce představujeme jako vektory s binárními hodnotami složek, přičemž máme na paměti, že pracujeme ve vektorovém prostoru, kde se aritmetika provádí modulo $2.$

2. Kontroly parity. Dalším přirozeným způsobem popisu klasického lineárního kódu jsou kontroly parity — tedy minimální seznam binárních řetězců, pro které jsou řetězce v kódu právě ty, jejichž binární skalární součin s každým z těchto řetězců kontroly parity je nula. (Podobně jako bitový exkluzivní-OR se binární skalární součin několikrát objevil v „Fundamentals of quantum algorithms".)

   To znamená, že řetězce $v_1,\ldots,v_r\in\Sigma^n$ jsou řetězce kontroly parity pro klasický lineární kód $\mathcal{C},$ pokud

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

   a tato množina řetězců je minimální, pokud odstraněním jednoho dostaneme větší kód. Nazývají se řetězce kontroly parity, protože $u$ má binární skalární součin rovný nule s $v$ právě tehdy, když bity $u$ na pozicích, kde $v$ má jedničky, mají sudou paritu. Takže pro určení, zda řetězec $u$ patří do kódu $\mathcal{C},$ stačí zkontrolovat paritu určitých podmnožin bitů $u.$

   Důležité je si zde všimnout, že binární skalární součin není ve formálním smyslu vnitřním součinem. Zejména když dva řetězce mají binární skalární součin rovný nule, neznamená to, že jsou ortogonální obvyklým způsobem, jakým o ortogonalitě přemýšlíme. Například binární skalární součin řetězce $11$ se sebou samým je nula — takže je možné, že řetězec kontroly parity pro klasický lineární kód je sám v kódu obsažen.

Klasické lineární kódy nad binární abecedou vždy obsahují počet řetězců, který je mocninou $2$ — a pro jeden klasický lineární kód popsaný dvěma právě uvedenými způsoby bude vždy platit $n = m + r.$ Konkrétně, pokud máme minimální množinu $m$ generátorů, pak kód kóduje $m$ bitů a nutně budeme mít $2^m$ kódových slov; a pokud máme minimální množinu $r$ řetězců kontroly parity, budeme mít $2^{n-r}$ kódových slov. Takže každý generátor zdvojnásobí velikost kódového prostoru, zatímco každý řetězec kontroly parity zmenší velikost kódového prostoru na polovinu.

Například 3-bitový opakovací kód je lineární kód, takže jej lze popsat oběma těmito způsoby. Konkrétně existuje jediná volba generátoru, která funguje: $111.$ Alternativně můžeme kód popsat dvěma řetězci kontroly parity, například $110$ a $011$ — což by mělo vypadat povědomě z našich předchozích diskusí o tomto kódu — nebo bychom mohli vzít řetězce kontroly parity $110$ a $101,$ nebo $101$ a $011.$ (Generátory a řetězce kontroly parity obecně nejsou pro daný klasický lineární kód jednoznačné.)

Jako druhý příklad uvažuj $[7,4,3]$-Hammingův kód. Zde je jedna volba seznamu generátorů, která funguje.

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

A zde je volba seznamu kontrol parity pro tento kód.

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

Zde mimochodem vidíme, že všechny naše řetězce kontroly parity jsou samy obsaženy v kódu.

Jedna závěrečná poznámka o klasických lineárních kódech, která je propojuje se stabilizátorovým formalismem, je ta, že řetězce kontroly parity jsou ekvivalentní stabilizátorovým generátorům, které se skládají pouze z $Z$ a jednotkových Pauliho matic. Například řetězce kontroly parity $110$ a $011$ pro 3-bitový opakovací kód odpovídají přesně stabilizátorovým generátorům $Z\otimes Z\otimes \mathbb{I}$ a $\mathbb{I}\otimes Z\otimes Z,$ což je v souladu s diskusemi o Pauliho observáblech z předchozí lekce.

Definice CSS kódů

CSS kódy jsou stabilizátorové kódy získané kombinací určitých párů klasických lineárních kódů. Toto nefunguje pro dva libovolné klasické lineární kódy — tyto dva kódy musí mít určitý vzájemný vztah. Přesto tato konstrukce otevírá mnoho možností pro kvantové kódy opravující chyby, založených částečně na více než 75 letech klasické teorie kódování.

Ve stabilizátorovém formalismu jsou stabilizátorové generátory obsahující pouze $Z$ a jednotkové Pauliho matice ekvivalentní kontrolám parity, jak jsme právě pozorovali u 3-bitového opakovacího kódu. Jako další příklad uvažuj následující řetězce kontroly parity pro $[7,4,3]$-Hammingův kód.

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

Tyto řetězce kontroly parity odpovídají následujícím generátorům stabilizátoru (zapsaným bez symbolů tenzorového součinu), které získáme nahrazením každé $1$ za $Z$ a každé $0$ za $\mathbb{I}.$ Toto jsou tři ze šesti generátorů stabilizátoru pro 7-qubitový Steaneův kód.

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

Pojmenujme $Z$ generátory stabilizátoru takové generátory stabilizátoru, které mají pouze Pauliho $Z$ a identitu jako tenzorové faktory — takže Pauliho matice $X$ a $Y$ se v $Z$ generátorech stabilizátoru nikdy nevyskytují.

Můžeme také uvažovat generátory stabilizátoru, kde se jako tenzorové faktory objevují pouze $X$ a identita. Takové generátory stabilizátoru lze chápat jako analogii k $Z$-generátorům stabilizátoru, s tím rozdílem, že popisují kontroly parity v bázi $\{\vert+\rangle,\vert-\rangle\}$ místo ve standardní bázi. Generátory stabilizátoru tohoto tvaru se nazývají $X$ generátory stabilizátoru — takže tentokrát nejsou povoleny Pauliho matice $Y$ ani $Z$.

Uvažuj například zbývající tři generátory stabilizátoru ze 7-qubitového Steaneova kódu.

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

Sledují přesně stejný vzor z $[7,4,3]$-Hammingova kódu jako $Z$-generátory stabilizátoru, jenže tentokrát nahrazujeme $1$ za $X$ místo za $Z.$ Z těchto tří generátorů stabilizátoru získáme kód, který zahrnuje 16 stavů uvedených zde, které dostaneme aplikací Hadamardových operací na stavy standardní báze odpovídající řetězcům v $[7,4,3]$-Hammingově kódu. (Kódový prostor tohoto kódu samozřejmě zahrnuje i lineární kombinace těchto stavů.)

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

Nyní můžeme definovat CSS kódy velmi jednoduše.

Definice

CSS kód je stabilizátorový kód, který lze vyjádřit pouze pomocí $X$ a $Z$ generátorů stabilizátoru.

To znamená, že CSS kódy jsou stabilizátorové kódy, u kterých máme generátory stabilizátoru, v nichž se nevyskytují žádné Pauliho matice $Y$, a u kterých se $X$ a $Z$ nikdy nevyskytují ve stejném generátoru stabilizátoru.

Pro upřesnění — podle této definice je CSS kód takový, u kterého je možné zvolit pouze $X$ a $Z$ generátory stabilizátoru — ale musíme mít na paměti, že při volbě generátorů stabilizátoru pro stabilizátorové kódy existuje jistá volnost. Proto budou obecně existovat různé volby generátorů stabilizátoru CSS kódu, které náhodou nejsou $X$ nebo $Z$ generátory stabilizátoru (kromě alespoň jedné volby, při které jsou).

Zde je velmi jednoduchý příklad CSS kódu, který obsahuje jak $Z$ generátor stabilizátoru, tak $X$ generátor stabilizátoru:

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

Je zřejmé, že se jedná o CSS kód, protože první generátor stabilizátoru je $Z$ generátor stabilizátoru a druhý je $X$ generátor stabilizátoru. CSS kód musí samozřejmě být také platným stabilizátorovým kódem — což znamená, že generátory stabilizátoru musí komutovat, tvořit minimální generující množinu a fixovat alespoň jeden kvantový stavový vektor. Tyto požadavky jsou u tohoto kódu snadno ověřitelné. Jak jsme poznamenali v předchozí lekci, kódový prostor tohoto kódu je jednorozměrný prostor generovaný Bellovým stavem $\vert\phi^+\rangle$. Skutečnost, že oba generátory stabilizátoru fixují tento stav, je patrná z následujících dvou vyjádření e-bitu spolu s interpretací těchto generátorů stabilizátoru jako kontrol parity v bázích $\{\vert 0\rangle, \vert 1\rangle\}$ a $\{\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-qubitový Steaneův kód je dalším příkladem CSS kódu.

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

Zde máme tři $Z$ generátory stabilizátoru a tři $X$ generátory stabilizátoru a již jsme ověřili, že se jedná o platný stabilizátorový kód.

A 9-qubitový Shorův kód je dalším příkladem.

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

Tentokrát máme šest $Z$ generátorů stabilizátoru a pouze dva $X$ generátory stabilizátoru. To je v pořádku, mezi oběma typy generátorů nemusí být rovnováha ani symetrie (ačkoli často je).

Ještě jednou zdůrazněme, že CSS kódy musí být platnými stabilizátorovými kódy, a zejména každý $Z$ generátor stabilizátoru musí komutovat s každým $X$ generátorem stabilizátoru. Takže ne každá kolekce $X$ a $Z$ generátorů stabilizátoru definuje platný CSS kód.

Detekce a oprava chyb

Pokud jde o detekci a opravu chyb, CSS kódy obecně mají podobnou vlastnost jako 9-qubitový Shorův kód, a to že $X$ a $Z$ chyby lze detekovat a opravovat zcela nezávisle; $Z$ generátory stabilizátoru popisují kód, který chrání proti překlopení bitů, a $X$ generátory stabilizátoru popisují kód, který nezávisle chrání proti překlopení fáze. To funguje proto, že $Z$ generátory stabilizátoru nutně komutují se $Z$ chybami i se $Z$ operacemi aplikovanými jako opravy, takže jsou vůči obojímu zcela „slepé", a totéž platí pro $X$ generátory stabilizátoru, chyby a opravy.

Jako příklad uvažujme 7-qubitový Steaneův kód.

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

Základní myšlenka tohoto kódu je nyní zřejmá: je to $[7,4,3]$-Hammingův kód pro chyby překlopení bitů a $[7,4,3]$-Hammingův kód pro chyby překlopení fáze. Skutečnost, že $X$ a $Z$ generátory stabilizátoru komutují, je možná šťastná náhoda, protože pokud by nekomutovaly, nejednalo by se o platný stabilizátorový kód. Existuje však mnoho známých příkladů klasických lineárních kódů, které při podobném použití dávají platný stabilizátorový kód.

Obecně předpokládejme, že máme CSS kód, kde $Z$ stabilizátorové generátory umožňují opravu až $j$ chyb překlopení bitů a $X$ stabilizátorové generátory umožňují opravu až $k$ chyb překlopení fáze. Například $j = 1$ a $k = 1$ pro Steaneův kód, protože $[7,4,3]$-Hammingův kód dokáže opravit jeden bit-flip. Z toho pak plyne, díky diskretizaci chyb, že tento CSS kód dokáže opravit libovolnou chybu na počtu qubitů až do minima z $j$ a $k.$ Je to proto, že při měření syndromu se libovolná chyba na tomto počtu qubitů efektivně pravděpodobnostně zkolabuje do nějaké kombinace $X$ chyb, $Z$ chyb, nebo obou — a poté jsou $X$ chyby a $Z$ chyby detekovány a opraveny nezávisle.

Shrnuto, za předpokladu, že máme dva klasické lineární kódy (nebo dvě kopie jednoho klasického lineárního kódu), které jsou kompatibilní v tom smyslu, že definují $X$ a $Z$ stabilizátorové generátory, jež komutují, CSS kód, který jejich kombinací získáme, dědí vlastnosti opravy chyb těchto dvou kódů ve smyslu, který byl právě popsán.

Všimni si ale, že to má svou cenu — nemůžeme kódovat tolik qubitů, kolik bychom mohli kódovat bitů pomocí dvou klasických kódů. Je to proto, že celkový počet stabilizátorových generátorů pro CSS kód je součtem počtů paritních kontrol obou klasických lineárních kódů a každý stabilizátorový generátor zmenší dimenzi kódového prostoru na polovinu. Například $[7,4,3]$-Hammingův kód umožňuje zakódování čtyř klasických bitů, protože pro tento kód máme pouze tři řetězce paritních kontrol, zatímco 7-qubitový Steaneův kód kóduje pouze jeden qubit, protože má šest stabilizátorových generátorů.

Kódové prostory CSS kódů

Poslední věc, kterou v této diskuzi o CSS kódech uděláme, je, že se podíváme na kódové prostory těchto kódů. To nám dá příležitost podrobněji prozkoumat vztah, který musí platit mezi dvěma klasickými lineárními kódy, aby byly kompatibilní ve smyslu, že je lze zkombinovat dohromady a vytvořit CSS kód.

Uvažuj libovolný CSS kód na $n$ qubitech a nechť $z_1, \ldots, z_s \in \Sigma^n$ jsou $n$-bitové řetězce paritních kontrol, které odpovídají $Z$ stabilizátorovým generátorům tohoto kódu. To znamená, že klasický lineární kód popsaný pouze $Z$ stabilizátorovými generátory, který nazveme $\mathcal{C}_Z,$ má následující tvar.

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

Slovně řečeno, klasický lineární kód $\mathcal{C}_Z$ obsahuje každý řetězec, jehož binární skalární součin s každým z řetězců paritních kontrol $z_1, \ldots, z_s$ je nula.

Obdobně nechť $x_1,\ldots,x_t\in\Sigma^n$ jsou $n$-bitové řetězce paritních kontrol odpovídající $X$ stabilizátorovým generátorům našeho kódu. Klasický lineární kód odpovídající $X$ stabilizátorovým generátorům má tedy tento tvar.

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

Samotné $X$ stabilizátorové generátory tedy popisují kód, který je podobný tomuto kódu, ale v bázi $\{\vert {+}\rangle,\vert {-}\rangle\}$ namísto standardní báze.

Nyní zavedeme dva nové klasické lineární kódy, které jsou odvozeny ze stejných voleb řetězců $z_1,\ldots,z_s$ a $x_1,\ldots,x_t,$ ale kde tyto řetězce bereme jako generátory místo řetězců paritních kontrol. Konkrétně získáme tyto dva kódy.

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

Tyto kódy jsou známé jako duální kódy dříve definovaných kódů: $\mathcal{D}_Z$ je duální kód kódu $\mathcal{C}_Z$ a $\mathcal{D}_X$ je duální kód kódu $\mathcal{C}_X.$ V tuto chvíli nemusí být jasné, proč jsou tyto duální kódy relevantní, ale ukazuje se, že jsou velmi relevantní z několika důvodů, včetně dvou důvodů vysvětlených v následujících odstavcích.

Za prvé, podmínky, které musí platit, aby dva klasické lineární kódy $\mathcal{C}_Z$ a $\mathcal{C}_X$ byly kompatibilní ve smyslu, že je lze spárovat a vytvořit CSS kód, lze jednoduše popsat odkazem na duální kódy. Konkrétně musí platit $\mathcal{D}_Z\subseteq\mathcal{C}_X,$ nebo ekvivalentně $\mathcal{D}_X\subseteq\mathcal{C}_Z.$ Slovně řečeno, duální kód $\mathcal{D}_Z$ obsahuje řetězce odpovídající $Z$ stabilizátorovým generátorům a jejich obsažení v $\mathcal{C}_X$ je ekvivalentní tomu, že binární skalární součin každého z těchto řetězců s těmi, které odpovídají $X$ stabilizátorovým generátorům, je nula. To je zase ekvivalentní tomu, že každý $Z$ stabilizátorový generátor komutuje s každým $X$ stabilizátorovým generátorem. Alternativně, pokud prohodíme role $X$ a $Z$ stabilizátorových generátorů a vyjdeme z obsažení $\mathcal{D}_X\subseteq\mathcal{C}_Z,$ dojdeme ke stejnému závěru.

Za druhé, odkazem na duální kódy můžeme snadno popsat kódové prostory daného CSS kódu. Konkrétně je kódový prostor generován vektory následujícího tvaru.

$$\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{(pro všechna $u\in\mathcal{C}_Z$)}$$

Slovně řečeno, tyto vektory jsou rovnoměrné superpozice přes řetězce v duálním kódu $\mathcal{D}_X$ kódu odpovídajícího $X$ stabilizátorovým generátorům, posunuté o (jinými slovy, bitově XORované s) řetězce v kódu $\mathcal{C}_Z$ odpovídajícím $Z$ stabilizátorovým generátorům. Pro upřesnění, různé volby posunu — reprezentovaného řetězcem $u$ v tomto výrazu — mohou vést ke stejnému vektoru. Tyto stavy tedy nejsou všechny různé, ale společně generují celý kódový prostor.

Zde je intuitivní vysvětlení, proč takové vektory leží v kódovém prostoru a zároveň ho generují. Uvažuj $n$-qubitový stav standardní báze $\vert u\rangle$ pro libovolný $n$-bitový řetězec $u$ a předpokládej, že tento stav promítneme na kódový prostor. To znamená, že pokud $\Pi$ označuje projekci na kódový prostor našeho CSS kódu, uvažujeme vektor $\Pi\vert u\rangle.$ Existují dva případy:

• Případ 1: $u\in\mathcal{C}_Z.$ To znamená, že každý $Z$ stabilizátorový generátor našeho CSS kódu působí na $\vert u\rangle$ triviálně. $X$ stabilizátorové generátory na druhou stranu jednoduše překlopí některé bity $\vert u\rangle.$ Konkrétně pro každý generátor $v$ kódu $\mathcal{D}_X$ transformuje $X$ stabilizátorový generátor odpovídající $v$ stav $\vert u\rangle$ na $\vert u\oplus v\rangle.$ Charakterizací projekce $\Pi$ jako průměru přes prvky stabilizátoru (jak jsme viděli v předchozí lekci) získáme tento vzorec:

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

• Případ 2: $u\notin\mathcal{C}_Z.$ To znamená, že alespoň jedna z paritních kontrol odpovídajících $Z$ stabilizátorovým generátorům selže, což znamená, že $\vert u\rangle$ musí být vlastním vektorem s vlastní hodnotou $-1$ alespoň jednoho $Z$ stabilizátorového generátoru. Kódový prostor CSS kódu je průnikem vlastních prostorů s vlastní hodnotou $+1$ stabilizátorových generátorů. Jako vlastní vektor s vlastní hodnotou $-1$ alespoň jednoho $Z$ stabilizátorového generátoru je tedy $\vert u\rangle$ ortogonální ke kódovému prostoru:

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

A nyní, když projdeme všechny $n$-bitové řetězce $u,$ zahodíme ty, pro které $\Pi\vert u\rangle = 0,$ a zbývající normalizujeme, získáme dříve popsané vektory, což dokazuje, že generují kódový prostor.

Můžeme také využít symetrii mezi $X$ a $Z$ stabilizátorovými generátory k popisu kódového prostoru podobným, ale odlišným způsobem. Konkrétně je to prostor generovaný vektory následujícího tvaru.

$$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{(pro $u\in\mathcal{C}_X$)}$$

V podstatě byly $X$ a $Z$ prohozeny v každém výskytu — ale musíme také prohodit standardní bázi za bázi $\{\vert+\rangle,\vert-\rangle\},$ a proto jsou zahrnuty Hadamardovy operace.

Jako příklad uvažujme 7-qubitový Steaneův kód. Řetězce paritních kontrol pro $X$ i $Z$ stabilizátorové generátory jsou stejné: $1111000,$ $1100110,$ a $1010101.$ Kódy $\mathcal{C}_X$ a $\mathcal{C}_Z$ jsou proto stejné; oba se rovnají $[7,4,3]$-Hammingovu kódu.

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

Duální kódy $\mathcal{D}_X$ a $\mathcal{D}_Z$ jsou proto také stejné. Máme tři generátory, takže získáme osm řetězců.

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

Všechny tyto řetězce jsou obsaženy v $[7,4,3]$-Hammingově kódu, a tedy je CSS podmínka splněna: $\mathcal{D}_Z \subseteq \mathcal{C}_X,$ nebo ekvivalentně $\mathcal{D}_X \subseteq \mathcal{C}_Z.$

Vzhledem k tomu, že $\mathcal{D}_X$ obsahuje polovinu všech řetězců v $\mathcal{C}_Z,$ existují pouze dva různé vektory $\vert u\oplus \mathcal{D}_X\rangle,$ které lze získat volbou $u\in\mathcal{C}_Z.$ To je očekávané, protože 7-qubitový Steaneův kód má dvoudimenzionální kódový prostor. Dva stavy, které tímto způsobem získáme, můžeme použít k zakódování logických stavů $\vert 0\rangle$ a $\vert 1\rangle$ následovně.

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

Jako obvykle nám tato volba není vnucena — kódový prostor můžeme použít ke kódování qubitů jakkoli chceme. Toto kódování je však v souladu s příkladem kódovacího obvodu pro 7-qubitový Steaneův kód z předchozí lekce.