Opakovací kódy

Tuto lekci začneme diskuzí o opakovacích kódech. Opakovací kódy nechrání kvantovou informaci proti každému typu chyby, která může na Qubitech nastat, ale tvoří základ 9-Qubitového Shorova kódu, který uvidíme v příští lekci, a jsou také užitečné pro vysvětlení základů oprav chyb.

Klasické kódování a dekódování

Opakovací kódy jsou mimořádně základní příklady kódů pro opravu chyb. Myšlenka spočívá v tom, že můžeš chránit bity proti chybám tím, že jednoduše zopakuješ každý bit nějaký pevný počet krát.

Konkrétně se nejprve podívejme na 3-bitový opakovací kód, zatím pouze v kontextu klasické informace. Tento kód zakóduje jeden bit do tří tím, že bit zopakuje třikrát, takže $0$ se zakóduje jako $000$ a $1$ se zakóduje jako $111.$

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

Pokud se nic nepokazí, můžeš očividně rozlišit dvě možnosti původního bitu z jejich kódování. Podstatné je, že pokud došlo k chybě a jeden ze tří bitů se překlopil, tedy 0 se změnila na 1 nebo 1 se změnila na 0, stále můžeš zjistit, jaký byl původní bit, tím že určíš, která ze dvou binárních hodnot se vyskytuje dvakrát. Ekvivalentně můžeš dekódovat výpočtem většinové hodnoty (tedy binární hodnoty, která se vyskytuje nejčastěji).

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

Samozřejmě, pokud se překlopí 2 nebo 3 bity kódování, dekódování nebude fungovat správně a obnoví se špatný bit, ale pokud se překlopí nejvýše 1 ze 3 bitů, dekódování bude správné. Toto je typická vlastnost kódů pro opravu chyb obecně: mohou umožnit opravu chyb, ale pouze pokud jich není příliš mnoho.

Snížení šumu pro binární symetrický kanál

Jako příklad situace, ve které lze pravděpodobnost chyby snížit pomocí opakovacího kódu, předpokládej, že tvým cílem je sdělit jediný bit hypotetickému příjemci a máš možnost přenášet bity přes takzvaný binární symetrický kanál, který každý poslaný bit nezávisle překlopí s pravděpodobností $p.$ To znamená, že s pravděpodobností $1-p$ příjemce dostane jakýkoli bit, který byl kanálem poslán, ale s pravděpodobností $p$ se bit překlopí a příjemce dostane opačnou hodnotu bitu.

Pokud se tedy rozhodneš nepoužít 3-bitový opakovací kód a jednoduše pošleš jakýkoli bit, který máš na mysli, kanálem, příjemce obdrží špatný bit s pravděpodobností $p.$ Na druhou stranu, pokud nejprve zakóduješ bit, který chceš poslat, pomocí 3-bitového opakovacího kódu a poté pošleš každý ze tří bitů kódování kanálem, každý z nich se nezávisle překlopí s pravděpodobností $p.$ Šance na překlopení bitu jsou nyní větší, protože nyní existují tři bity, které se mohou překlopit, místo jednoho, ale pokud se překlopí nejvýše jeden z bitů, příjemce dekóduje správně. Chyba tedy přetrvá po dekódování pouze tehdy, pokud se během přenosu překlopí dva nebo více bitů.

Pravděpodobnost, že se překlopí dva bity během přenosu, je $3p^2(1-p),$ což je $p^2(1-p)$ pro každou ze tří voleb bitu, který se nepřeklopí, zatímco pravděpodobnost, že se překlopí všechny tři bity, je $p^3.$ Celková pravděpodobnost překlopení dvou nebo tří bitů je tedy

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

Pro hodnoty $p$ menší než jedna polovina to vede ke snížení pravděpodobnosti, že příjemce skončí se špatným bitem. Stále bude existovat šance na chybu v tomto případě, ale kód snižuje její pravděpodobnost. (Pro hodnoty $p$ větší než jedna polovina naopak kód zvyšuje pravděpodobnost, že příjemce dostane špatný bit.)

Kódování Qubitů

3-bitový opakovací kód je klasický kód pro opravu chyb, ale můžeme se podívat, co se stane, když se ho pokusíme použít k ochraně Qubitů proti chybám. Jak uvidíme, není to příliš působivý kvantový kód pro opravu chyb, protože ve skutečnosti zvyšuje pravděpodobnost některých chyb. Je to však první krok k Shorovu kódu a z pedagogického hlediska nám dobře poslouží.

Pro upřesnění, když odkazujeme na 3-bitový opakovací kód používaný pro Qubity, máme na mysli kódování Qubitu, kde se stavy standardní báze opakují třikrát, takže stavový vektor jednoho Qubitu se zakóduje následovně.

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

Toto kódování lze snadno implementovat následujícím kvantovým Circuit, který využívá dva inicializované pracovní Qubity a dva controlled-NOT Gate.

Všimni si zejména, že toto kódování není totéž jako opakování kvantového stavu třikrát, jako v případě kódování daného stavového vektoru Qubitu jako $\vert\psi\rangle \mapsto \vert\psi\rangle\vert\psi\rangle\vert\psi\rangle.$ Takové kódování nelze implementovat pro neznámý kvantový stav $\vert\psi\rangle$ podle věty o nemožnosti klonování.

Chyby překlopení bitu

Nyní předpokládej, že po provedení kódování dojde k chybě. Konkrétně předpokládejme, že na jednom z Qubitů dojde k aplikaci $X$ Gate, jinými slovy k překlopení bitu. Například pokud prostřední Qubit zažije překlopení bitu, stav tří Qubitů se transformuje do tohoto stavu:

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

Samozřejmě to není jediný typ chyby, který by mohl nastat — a je také oprávněné zpochybnit předpoklad, že chyba má formu dokonalé unitární operace. K těmto otázkám se vrátíme v poslední části lekce a prozatím můžeme chybu tohoto typu považovat za jeden z možných typů chyb (i když zásadně důležitý).

Z matematického výrazu pro výše uvedený stav jasně vidíme, že prostřední bit je ten, který se liší uvnitř každého ketu. Ale předpokládejme, že máme tyto tři Qubity v držení a neznáme jejich stav. Pokud bychom měli podezření, že mohlo dojít k překlopení bitu, jednou z možností ověření by bylo provést měření ve standardní bázi, které by v tomto případě způsobilo, že bychom viděli $010$ nebo $101$ s pravděpodobnostmi $\vert\alpha\vert^2$ a $\vert\beta\vert^2.$ V obou případech by náš závěr byl, že se překlopil prostřední bit — ale bohužel bychom ztratili původní kvantový stav $\alpha\vert 0\rangle + \beta \vert 1\rangle.$ Toto je stav, který se snažíme chránit, takže měření ve standardní bázi je neuspokojivá možnost.

Co můžeme udělat místo toho, je použít následující kvantový Circuit, do kterého přivedeme zakódovaný stav do horních tří Qubitů. Tento Circuit nedestruktivně měří paritu stavů standardní báze horních dvou Qubitů i dolních dvou Qubitů tří-Qubitového kódování.

Za předpokladu, že se překlopil nejvýše jeden bit, lze z výsledků měření snadno odvodit umístění překlopení bitu (nebo jeho absenci). Konkrétně, jak ilustrují následující čtyři diagramy Circuit, výsledek měření $00$ indikuje, že k žádnému překlopení bitu nedošlo, zatímco tři zbývající možnosti ukazují, který Qubit zažil překlopení bitu.

Zásadní je, že stav horních tří Qubitů v žádném z případů nekolabuje, což nám umožňuje opravit chybu překlopení bitu, pokud k ní došlo — jednoduše opětovným aplikováním stejného překlopení bitu pomocí $X$ Gate. Následující tabulka shrnuje stavy, které získáme při nejvýše jednom překlopení bitu, výsledky měření (které se v kontextu oprav chyb nazývají syndrom) a opravu potřebnou k návratu k původnímu kódování.

Stav	Syndrom	Oprava
$\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}$

Znovu připomínáme, že uvažujeme pouze možnost, že došlo k nejvýše jednomu překlopení bitu. Pokud by došlo ke dvěma nebo třem překlopením, toto by nefungovalo správně, a navíc jsme nezohlednili jiné možné chyby kromě překlopení bitů.

Chyby překlopení fáze

V kvantovém prostředí nejsou chyby překlopení bitu jedinými chybami, o které se musíme starat. Například se musíme starat také o chyby překlopení fáze, které jsou popsány $Z$ Gate. Podobně jako u chyb překlopení bitu si můžeme chyby překlopení fáze představit jako další možný typ chyby, který může Qubit postihnout.

Jak však uvidíme v poslední části lekce, která pojednává o takzvané diskretizaci chyb pro kvantové kódy opravující chyby, zaměření na chyby překlopení bitu a chyby překlopení fáze je oprávněné. Konkrétně schopnost opravit chybu překlopení bitu, chybu překlopení fáze nebo obě tyto chyby současně automaticky implikuje schopnost opravit libovolnou kvantovou chybu na jednom Qubitu.

Bohužel 3-bitový opakovací kód vůbec nechrání proti překlopením fáze. Předpokládejme například, že stav Qubitu $\alpha\vert 0\rangle + \beta\vert 1\rangle$ byl zakódován pomocí 3-bitového opakovacího kódu a na prostředním Qubitu došlo k chybě překlopení fáze. Výsledkem je stav

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

což je přesně stav, který bychom získali zakódováním stavu Qubitu $\alpha\vert 0\rangle - \beta\vert 1\rangle.$ Chyba překlopení fáze na kterémkoli ze tří Qubitů kódování má skutečně stejný efekt, který je ekvivalentní chybě překlopení fáze na původním Qubitu před zakódováním. Za předpokladu, že původní kvantový stav je neznámý, neexistuje žádný způsob, jak detekovat, že k chybě došlo, protože výsledný stav je naprosto platné kódování jiného stavu Qubitu. Konkrétně spuštění Circuit pro detekci chyb z dřívějška na stav $\alpha \vert 000\rangle - \beta \vert 111\rangle$ jistě povede k syndromu $00,$ což mylně naznačuje, že k žádným chybám nedošlo.

Mezitím existují nyní tři Qubity místo jednoho, které by potenciálně mohly zažít chyby překlopení fáze. Takže v situaci, kdy se předpokládá, že chyby překlopení fáze nastávají nezávisle na každém Qubitu s nějakou nenulovou pravděpodobností $p$ (podobně jako binární symetrický kanál, ale pro překlopení fáze místo překlopení bitů), tento kód ve skutečnosti zvyšuje pravděpodobnost chyby překlopení fáze po dekódování pro malé hodnoty $p.$ Abychom byli přesnější, chyba překlopení fáze na původním Qubitu po dekódování nastane, kdykoli je lichý počet chyb překlopení fáze na třech Qubitech kódování, což nastane s pravděpodobností

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

Tato hodnota je větší než $p$ když $0<p<1/2,$ takže kód zvyšuje pravděpodobnost chyby překlopení fáze pro hodnoty $p$ v tomto rozsahu.

Modifikovaný opakovací kód pro chyby překlopení fáze

Zjistili jsme, že 3-bitový opakovací kód je zcela nevšímavý vůči chybám překlopení fáze, takže se nezdá být příliš užitečný pro řešení tohoto typu chyby. Můžeme však 3-bitový opakovací kód jednoduchým způsobem modifikovat tak, aby detekoval chyby překlopení fáze. Tato modifikace způsobí, že kód bude nevšímavý vůči chybám překlopení bitu — ale, jak uvidíme v příští části, můžeme 3-bitový opakovací kód zkombinovat s touto modifikovanou verzí a získat Shorův kód, který dokáže opravit jak chyby překlopení bitu, tak chyby překlopení fáze.

Zde je modifikovaná verze kódovacího Circuit z výše, která nyní bude schopna detekovat chyby překlopení fáze. Modifikace je velmi jednoduchá: po provedení dvou controlled-NOT Gate jednoduše aplikujeme Hadamardův Gate na každý Qubit.

Hadamardův Gate transformuje stav $\vert 0\rangle$ na stav $\vert + \rangle$ a stav $\vert 1\rangle$ na stav $\vert - \rangle$, takže celkový efekt je, že stav jednoho Qubitu $\alpha\vert 0\rangle + \beta \vert 1\rangle$ je zakódován jako

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

kde $\vert {+}\,{+}\,{+} \rangle = \vert + \rangle \otimes \vert + \rangle \otimes\vert + \rangle$ a $\vert {-}\,{-}\,{-} \rangle = \vert - \rangle \otimes \vert - \rangle \otimes\vert - \rangle.$

Chyba překlopení fáze, neboli ekvivalentně $Z$ Gate, přepíná mezi stavy $\vert + \rangle$ a $\vert - \rangle,$ takže toto kódování bude užitečné pro detekci (a opravu) chyb překlopení fáze. Konkrétně Circuit pro detekci chyb z dřívějška lze modifikovat následovně.

Slovně řečeno, vezmeme Circuit z dřívějška a jednoduše přidáme Hadamardovy Gate na horní tři Qubity na začátek i na konec. Myšlenka je taková, že první tři Hadamardovy Gate transformují stavy $\vert + \rangle$ a $\vert - \rangle$ zpět na stavy $\vert 0\rangle$ a $\vert 1\rangle$, provedou se stejné kontroly parity jako předtím, a poté druhá vrstva Hadamardových Gate transformuje stav zpět na stavy $\vert + \rangle$ a $\vert - \rangle$, takže obnovíme naše kódování. Pro budoucí referenci si všimni, že tento Circuit pro detekci překlopení fáze lze zjednodušit následovně.

Následující čtyři diagramy Circuit popisují, jak naše modifikovaná verze 3-bitového opakovacího kódu, včetně kroku kódování a kroku detekce chyb, funguje, když dojde k nejvýše jedné chybě překlopení fáze. Chování je podobné jako u běžného 3-bitového opakovacího kódu pro překlopení bitů.

Zde je analogická tabulka k té předchozí, tentokrát uvažující možnost nejvýše jedné chyby překlopení fáze.

Stav	Syndrom	Oprava
$\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}$

Bohužel tato modifikovaná verze 3-bitového opakovacího kódu již nedokáže opravit chyby překlopení bitu.