Torický kód

Dále si povíme o konkrétním CSS kódu známém jako torický kód, který objevil Alexej Kitaev v roce 1997. Ve skutečnosti torický kód není jediný kód, ale spíše rodina kódů, jeden pro každé kladné celé číslo od 2 výše. Tyto kódy mají několik klíčových vlastností:

• Stabilizátorové generátory mají nízkou váhu, a konkrétně mají všechny váhu 4. V terminologii teorie kódování je torický kód příkladem kvantového kódu s nízkou hustotou paritních kontrol, neboli kvantového LDPC kódu (kde nízká v tomto případě znamená 4). To je výhodné, protože každé měření stabilizátorového generátoru nemusí zahrnovat příliš mnoho qubitů.

• Torický kód má geometrickou lokalitu. To znamená, že stabilizátorové generátory mají nejen nízkou váhu, ale je také možné qubity prostorově uspořádat tak, aby každé měření stabilizátorového generátoru zahrnovalo pouze qubity, které jsou blízko sebe. V principu to činí tato měření snadnějšími na implementaci, než kdyby zahrnovala prostorově vzdálené qubity.

• Členové rodiny torického kódu mají stále větší vzdálenost a dokážou tolerovat poměrně vysokou míru chyb.

Popis torického kódu

Nechť $L\geq 2$ je kladné celé číslo a uvažujme mřížku $L\times L$ s takzvanými periodickými hranicemi. Například tento obrázek znázorňuje mřížku $L\times L$ pro $L=9.$

Všimni si, že čáry vpravo a dole jsou přerušované. To má naznačit, že přerušovaná čára vpravo je tatáž čára jako čára úplně vlevo, a podobně přerušovaná čára dole je tatáž čára jako čára úplně nahoře.

Pro fyzickou realizaci takové konfigurace jsou zapotřebí tři rozměry. Konkrétně bychom mohli mřížku stočit do válce tak, že nejprve spojíme levou a pravou stranu, a pak válec ohnout tak, aby se kružnice na koncích, které bývaly horní a dolní hranou mřížky, setkaly. Nebo bychom mohli nejprve spojit horní a dolní stranu a pak boky; funguje to oběma způsoby a pro účely této diskuze nezáleží na tom, který zvolíme.

To, co získáme, je torus — jinými slovy, kobliha (i když si to lépe můžeš představit jako duši pneumatiky, protože to není těleso: mřížka se stala pouze povrchem toru). Odtud pochází název „torický kód".

Způsob, jakým se lze na takovém toru „pohybovat" mezi sousedními body mřížky, bude pravděpodobně povědomý těm, kdo hráli staré videohry, kde pohyb přes horní okraj obrazovky způsobil, že jsi se objevil dole, a totéž platilo pro levý a pravý okraj obrazovky. Takto budeme nahlížet na tuto mřížku s periodickými hranicemi, místo abychom hovořili konkrétně o toru ve trojrozměrném prostoru.

Dále jsou qubity rozmístěny na hranách této mřížky, jak znázorňuje následující obrázek, kde jsou qubity vyznačeny plnými modrými kroužky.

Všimni si, že qubity umístěné na přerušovaných čarách nejsou plné, protože jsou již reprezentovány na nejvyšších a nejlevějších čarách mřížky. Celkem je $2L^2$ qubitů: $L^2$ qubitů na vodorovných čarách a $L^2$ qubitů na svislých čarách.

Pro popis samotného torického kódu zbývá popsat stabilizátorové generátory:

• Pro každou dlaždici tvořenou čarami mřížky existuje jeden $Z$ stabilizátorový generátor, získaný tensorovým součinem matic $Z$ na čtyřech qubitech dotýkajících se dané dlaždice spolu s jednotkovými maticemi na všech ostatních qubitech.

• Pro každý vrchol tvořený čarami mřížky existuje jeden $X$ stabilizátorový generátor, získaný tensorovým součinem matic $X$ na čtyřech qubitech sousedících s daným vrcholem spolu s jednotkovými maticemi na všech ostatních qubitech.

V obou případech získáme Pauliho operaci s váhou 4. Jednotlivě lze tyto stabilizátorové generátory znázornit takto.

Zde je ilustrace ukazující příklady stabilizátorových generátorů v kontextu samotné mřížky. Všimni si, že jsou zahrnuty i stabilizátorové generátory, které se obtáčejí kolem periodických hranic. Tyto generátory obtáčející se kolem periodických hranic nejsou nijak speciální ani odlišné od těch, které se neobtáčejí.

Stabilizátorové generátory musí komutovat, aby šlo o platný stabilizátorový kód. Jako obvykle všechny $Z$ stabilizátorové generátory komutují navzájem, protože $Z$ komutuje samo se sebou a identita komutuje se vším, a totéž platí pro $X$ stabilizátorové generátory. $Z$ a $X$ stabilizátorové generátory zjevně komutují, když netriviálně působí na disjunktní množiny qubitů, jako v příkladech na předchozím obrázku. Zbývající možností je, že $Z$ stabilizátorový generátor a $X$ stabilizátorový generátor se překrývají na qubitech, na které netriviálně působí, a kdykoli se to stane, generátory se vždy překrývají na dvou qubitech, jako na dalším obrázku.

V důsledku toho dva takové stabilizátorové generátory komutují, stejně jako komutují $Z\otimes Z$ a $X\otimes X$. Stabilizátorové generátory tedy všechny komutují navzájem.

Druhou požadovanou podmínkou na stabilizátorové generátory pro stabilizátorový kód je, že tvoří minimální generující množinu. Tato podmínka ve skutečnosti není splněna touto kolekcí: pokud vynásobíme všechny $Z$ stabilizátorové generátory dohromady, získáme operaci identity, a totéž platí pro $X$ stabilizátorové generátory. Tedy libovolný $Z$ stabilizátorový generátor lze vyjádřit jako součin všech zbývajících, a podobně libovolný $X$ stabilizátorový generátor lze vyjádřit jako součin zbývajících $X$ stabilizátorových generátorů. Pokud však odebereme libovolný jeden $Z$ stabilizátorový generátor a libovolný jeden $X$ stabilizátorový generátor, získáme minimální generující množinu.

Aby bylo jasno, všechny stabilizátorové generátory nás skutečně zajímají stejně a v přísně operačním smyslu není potřeba vybírat jeden stabilizátorový generátor každého typu k odebrání. Ale pro účely analýzy kódu — a zejména počítání generátorů — si můžeme představit, že jeden stabilizátorový generátor každého typu byl odebrán, abychom získali minimální generující množinu, přičemž máme na paměti, že výsledky těchto odebraných generátorů (chápejme je jako pozorovatelné) bychom vždy mohli odvodit z výsledků všech ostatních stabilizátorových generátorových pozorovatelných téhož typu.

Tím zbývá $L^2 - 1$ stabilizátorových generátorů každého typu, neboli $2L^2 - 2$ celkem, v (hypotetické) minimální generující množině. Vzhledem k tomu, že je celkem $2L^2$ qubitů, torický kód kóduje $2L^2 - 2 (L^2 - 1) = 2$ qubity.

Poslední podmínkou požadovanou od stabilizátorových generátorů je, že alespoň jeden kvantový stavový vektor je fixován všemi stabilizátorovými generátory. Uvidíme, že tomu tak je, až budeme pokračovat v analýze kódu, ale je také možné odůvodnit, že ze stabilizátorových generátorů nelze vygenerovat $-1$ násobek identity na všech $2L^2$ qubitech.

Detekce chyb

Torický kód má jednoduchý a elegantní popis, ale jeho vlastnosti pro kvantovou korekci chyb nemusí být na první pohled vůbec zřejmé. Jak se ukáže, je to úžasný kód! Abychom pochopili proč a jak funguje, začněme uvažováním různých chyb a syndromů, které generují.

Torický kód je CSS kód, protože všechny naše stabilizátorové generátory jsou buď $Z$, nebo $X$ stabilizátorové generátory. To znamená, že $X$ chyby a $Z$ chyby lze detekovat (a případně opravit) odděleně. Ve skutečnosti existuje jednoduchá symetrie mezi $Z$ a $X$ stabilizátorovými generátory, která nám umožňuje analyzovat $X$ chyby a $Z$ chyby v podstatě stejným způsobem. Ve skutečnosti existuje jednoduchá symetrie mezi $Z$ a $X$ stabilizátorovými generátory, která nám umožňuje analyzovat $X$ chyby a $Z$ chyby v podstatě stejným způsobem. Zaměříme se tedy na $X$ chyby, které jsou případně detekovány $Z$ stabilizátorovými generátory — ale celou následující diskusi lze přeložit z $X$ chyb na $Z$ chyby, které jsou analogicky detekovány $X$ stabilizátorovými generátory.

Následující diagram znázorňuje efekt $X$ chyby na jednom qubitu. Zde předpokládáme, že našich $2L^2$ qubitů bylo dříve ve stavu obsaženém v kódovém prostoru torického kódu, takže všechna měření stabilizátorových generátorů dávala výsledek $+1.$ $Z$ stabilizátorové generátory detekují $X$ chyby a pro každou dlaždici na obrázku existuje jeden takový stabilizátorový generátor, takže můžeme výsledek měření příslušného stabilizátorového generátoru indikovat barvou dané dlaždice: výsledky $+1$ jsou označeny bílými dlaždicemi a výsledky $-1$ jsou označeny šedými dlaždicemi. Pokud dojde k bit-flip chybě na jednom z qubitů, efekt je takový, že měření stabilizátorových generátorů odpovídající dvěma dlaždicím dotýkajícím se postiženého qubitu nyní dávají výsledek $-1.$

To je intuitivní, když zvážíme $Z$ stabilizátorové generátory a jejich chování. V podstatě každý $Z$ stabilizátorový generátor měří paritu čtyř qubitů, které se dotýkají příslušné dlaždice (vzhledem ke standardní bázi). Takže výsledek $+1$ neznamená, že na těchto čtyřech qubitech nedošlo k žádným $X$ chybám, ale spíše indikuje, že došlo k sudému počtu $X$ chyb na těchto qubitech, zatímco výsledek $-1$ indikuje, že došlo k lichému počtu $X$ chyb. Jediná $X$ chyba proto převrátí paritu čtyř bitů na obou dlaždicích, kterých se dotýká, což způsobí, že měření stabilizátorových generátorů dají výsledek $-1.$

Nyní zavedeme více $X$ chyb, abychom viděli, co se stane. Konkrétně budeme uvažovat řetězec sousedních $X$ chyb, kde dvě $X$ chyby jsou sousední, pokud ovlivňují qubity dotýkající se stejné dlaždice.

Dva $Z$ stabilizátorové generátory na koncových bodech řetězce v tomto případě oba dávají výsledek $-1$, protože na těchto dvou odpovídajících dlaždicích došlo k lichému počtu $X$ chyb. Všechny ostatní $Z$ stabilizátorové generátory naopak dávají výsledek $+1,$ včetně těch, které se dotýkají řetězce, ale nejsou na jeho koncových bodech, protože na qubitech dotýkajících se příslušných dlaždic došlo k sudému počtu $X$ chyb.

Takže pokud máme řetězec $X$ chyb, který má koncové body, torický kód detekuje, že došlo k chybám, což vede k výsledkům měření $-1$ pro $Z$ stabilizátorové generátory odpovídající koncovým bodům řetězce. Všimni si, že samotný řetězec chyb není odhalen, pouze koncové body! To je v pořádku — v další podsekci uvidíme, že nepotřebujeme vědět přesně, které qubity byly postiženy $X$ chybami, abychom je opravili. (Torický kód je příkladem vysoce degenerovaného kódu v tom smyslu, že obecně jednoznačně neidentifikuje chyby, které opravuje.)

Je však možné, aby řetězec sousedních $X$ chyb neměl koncové body, což znamená, že řetězec chyb by mohl tvořit uzavřenou smyčku, jako na následujícím obrázku.

V takovém případě došlo na každé dlaždici k sudému počtu $X$ chyb, takže každé měření stabilizátorového generátoru dá výsledek $+1.$ Uzavřené smyčky sousedních $X$ chyb proto nejsou kódem detekovány.

To může vypadat zklamáním, protože k vytvoření uzavřené smyčky stačí pouze čtyři $X$ chyby (a doufáme v něco mnohem lepšího než kód se vzdáleností 4). Nicméně uzavřená smyčka $X$ chyb tvaru znázorněného na předchozím obrázku ve skutečnosti není chybou — protože je obsažena ve stabilizátoru! Připomeň si, že kromě $Z$ stabilizátorových generátorů máme také $X$ stabilizátorový generátor pro každý vrchol mřížky. A pokud vynásobíme sousední $X$ stabilizátorové generátory dohromady, výsledkem je, že získáme uzavřené smyčky $X$ operací. Například uzavřenou smyčku na předchozím obrázku lze získat vynásobením $X$ stabilizátorových generátorů označených na následujícím obrázku.

Toto však není jediný typ uzavřené smyčky $X$ chyb, který můžeme mít — a není pravda, že každá uzavřená smyčka $X$ chyb je obsažena ve stabilizátoru. Konkrétně lze různé typy smyček charakterizovat následovně.

1. Uzavřené smyčky $X$ chyb se sudým počtem $X$ chyb na každé horizontální a každé vertikální linii qubitů. (Výše uvedený příklad spadá do této kategorie.) Smyčky tohoto tvaru jsou vždy obsaženy ve stabilizátoru, protože je lze efektivně zmenšit na nic násobením $X$ stabilizátorovými generátory.

2. Uzavřené smyčky $X$ chyb s lichým počtem $X$ chyb na alespoň jedné horizontální nebo alespoň jedné vertikální linii qubitů. Smyčky tohoto tvaru nejsou nikdy obsaženy ve stabilizátoru, a proto představují netriviální chyby, které kód nedetekuje.

Příklad uzavřené smyčky $X$ chyb v druhé kategorii je znázorněn na následujícím diagramu.

Takový řetězec chyb není obsažen ve stabilizátoru, protože každý $X$ stabilizátorový generátor umisťuje sudý počet $X$ operací na každou horizontální a každou vertikální linii qubitů. Toto je tedy skutečný příklad netriviální chyby, kterou kód nedokáže detekovat.

Klíčové je, že jediný způsob, jak vytvořit smyčku druhého druhu, je obejít torus, tedy buď kolem díry uprostřed toru, skrz ni, nebo obojí. Intuitivně řečeno, řetězec $X$ chyb jako tento nelze zmenšit na nic násobením $X$ stabilizátorovými generátory, protože mu v tom brání topologie toru. Torický kód je z tohoto důvodu někdy klasifikován jako topologický kvantový kód opravující chyby. Nejkratší taková smyčka může mít délku $L$, a proto je toto vzdálenost torického kódu: jakákoliv uzavřená smyčka $X$ chyb s délkou menší než $L$ musí spadat do první kategorie, a je tedy obsažena ve stabilizátoru; a jakýkoliv řetězec $X$ chyb s koncovými body je kódem detekován.

Vzhledem k tomu, že torický kód používá $2L^2$ qubitů k zakódování $2$ qubitů a má vzdálenost $L,$ z toho vyplývá, že jde o $[[2L^2,2,L]]$ stabilizátorový kód.

Oprava chyb

Diskutovali jsme o detekci chyb pro torický kód a nyní stručně probereme, jak chyby opravit. Torický kód je CSS kód, takže $X$ chyby a $Z$ chyby lze detekovat a opravovat nezávisle. Pokud se zaměříme na $Z$ stabilizátorové generátory, které detekují $X$ chyby, podívejme se, jak lze řetězec $X$ chyb opravit. ($Z$ chyby se opravují symetrickým způsobem.)

Pokud se při měření $Z$ stabilizátorových generátorů objeví syndrom odlišný od syndromu $(+1,\ldots,+1)$, výsledky $-1$ odhalí koncové body jednoho nebo více řetězců $X$ chyb. Můžeme se pokusit tyto chyby opravit tak, že spárujeme výsledky $-1$ a vytvoříme řetězec $X$ korekcí mezi nimi. Přitom dává smysl volit nejkratší cesty, podél kterých se korekce provádějí.

Například zvaž následující diagram, který znázorňuje syndrom se dvěma výsledky $-1$, označenými šedými dlaždicemi, způsobenými řetězcem $X$ chyb znázorněným purpurovou čárou a kroužky. Jak jsme již poznamenali, samotný řetězec není syndromem odhalen; viditelné jsou pouze koncové body.

Pro pokus o opravu tohoto řetězce chyb se vybere nejkratší cesta mezi výsledky měření $-1$ a na qubity podél této cesty se aplikují $X$ Gate jako korekce (na obrázku označeny žlutě). I když se korekce nemusí shodovat se skutečným řetězcem chyb, chyby a korekce dohromady tvoří uzavřenou smyčku $X$ operací, která je obsažena ve stabilizátoru kódu. Korekce je proto v této situaci úspěšná, protože kombinovaný efekt chyb a korekcí na zakódovaný stav je nulový.

Tato strategie nebude vždy úspěšná. Například jiné vysvětlení pro stejný syndrom jako na předchozím obrázku je znázorněno na následujícím obrázku.

Tentokrát stejný řetězec korekcí jako předtím nedokáže opravit tento řetězec chyb, protože kombinovaný efekt chyb a korekcí je, že získáme uzavřenou smyčku $X$ operací, která obepíná torus, a proto má netriviální efekt na kódový prostor. Takže neexistuje žádná záruka, že právě popsaná strategie volby nejkratší cesty $X$ korekcí mezi dvěma výsledky syndromového měření $-1$ správně opraví chybu, která tento syndrom způsobila.

Pravděpodobněji, v závislosti na modelu šumu, se změří syndrom s více než dvěma záznamy $-1$, jak naznačuje následující obrázek.

V takovém případě jsou známé různé korekční strategie. Jednou přirozenou strategií je pokusit se spárovat výsledky měření $-1$ a provést korekce podél nejkratších cest spojujících páry, jak je na obrázku znázorněno žlutě. Konkrétně lze vypočítat párování s minimální váhou (minimum-weight perfect matching) mezi výsledky měření $-1$ a poté se páry spojí nejkratšími cestami $X$ korekcí. Výpočet párování s minimální váhou lze provést efektivně klasickým algoritmem známým jako blossom algoritmus, který objevil Edmonds v 60. letech 20. století.