Torischer Code

Als nächstes besprechen wir einen spezifischen CSS-Code, den Torischen Code, der 1997 von Alexei Kitaev entdeckt wurde. Tatsächlich ist der Torische Code kein einzelner Code, sondern eine Familie von Codes – einer für jede positive ganze Zahl ab 2. Diese Codes besitzen einige wichtige Eigenschaften:

• Die Stabilisatorgeneratoren haben niedriges Gewicht, insbesondere haben sie alle Gewicht 4. In der Codierungstheorie ist der Torische Code ein Beispiel für einen Quanten-Low-Density-Parity-Check-Code, oder Quanten-LDPC-Code (wobei niedrig in diesem Fall 4 bedeutet). Das ist vorteilhaft, weil die Messung jedes Stabilisatorgenerators nicht zu viele Qubits erfordert.

• Der Torische Code hat geometrische Lokalität. Das bedeutet, dass die Stabilisatorgeneratoren nicht nur niedriges Gewicht haben, sondern es auch möglich ist, die Qubits räumlich so anzuordnen, dass jede der Stabilisatorgenerator-Messungen nur Qubits einbezieht, die nahe beieinander liegen. Das macht diese Messungen prinzipiell einfacher zu implementieren als wenn sie räumlich weit entfernte Qubits einbeziehen würden.

• Mitglieder der Torischen-Code-Familie haben zunehmend große Distanz und können eine relativ hohe Fehlerrate tolerieren.

Beschreibung des Torischen Codes

Sei $L\geq 2$ eine positive ganze Zahl, und betrachte ein $L\times L$-Gitter mit sogenannten periodischen Rändern. Dieses Diagramm zeigt zum Beispiel ein $L\times L$-Gitter für $L=9.$

Man beachte, dass die Linien auf der rechten Seite und am unteren Rand gestrichelte Linien sind. Das soll anzeigen, dass die gestrichelte Linie rechts dieselbe Linie ist wie die ganz links, und ebenso ist die gestrichelte Linie am unteren Rand dieselbe wie die ganz oben.

Um eine solche Konfiguration physisch zu realisieren, sind drei Dimensionen erforderlich. Insbesondere könnte man das Gitter zu einem Zylinder formen, indem man zuerst die linke und rechte Seite zusammenfügt, und dann den Zylinder so biegt, dass die Kreise an den Enden – die früher die obere und untere Kante des Gitters waren – zusammentreffen. Oder man kann zuerst Ober- und Unterseite zusammenfügen und dann die Seiten; beides funktioniert und es spielt für diese Diskussion keine Rolle, was man zuerst tut.

Was wir erhalten, ist ein Torus – oder mit anderen Worten, ein Donut (wobei die Vorstellung eines Reifenschlauchs vielleicht ein besseres Bild ist, da dies kein Feststoff ist: das Gitter ist nur die Oberfläche eines Torus). Daher kommt der Name „Torischer Code".

Die Art, wie man sich auf einem solchen Torus zwischen benachbarten Punkten des Gitters bewegen kann, ist denjenigen wahrscheinlich vertraut, die alte Videospiele gespielt haben: Wenn man den oberen Bildschirmrand verlässt, taucht man unten wieder auf, und dasselbe gilt für den linken und rechten Rand. So werden wir dieses Gitter mit periodischen Rändern betrachten, anstatt konkret über einen Torus im dreidimensionalen Raum zu sprechen.

Als nächstes werden Qubits auf den Kanten dieses Gitters angeordnet, wie in der folgenden Abbildung dargestellt, wobei Qubits durch ausgefüllte blaue Kreise angezeigt werden.

Man beachte, dass die auf den gestrichelten Linien platzierten Qubits nicht ausgefüllt sind, da sie bereits durch die Qubits auf den obersten und linksten Linien des Gitters repräsentiert werden. Insgesamt gibt es $2L^2$ Qubits: $L^2$ Qubits auf horizontalen Linien und $L^2$ Qubits auf vertikalen Linien.

Zur Beschreibung des Torischen Codes selbst verbleiben noch die Stabilisatorgeneratoren:

• Für jede Kachel, die durch die Linien des Gitters gebildet wird, gibt es einen $Z$-Stabilisatorgenerator, der durch Tensorierung von $Z$-Matrizen auf die vier die Kachel berührenden Qubits zusammen mit Identitätsmatrizen auf allen anderen Qubits erhalten wird.

• Für jeden Eckpunkt, der durch die Linien des Gitters gebildet wird, gibt es einen $X$-Stabilisatorgenerator, der durch Tensorierung von $X$-Matrizen auf die vier dem Eckpunkt benachbarten Qubits zusammen mit Identitätsmatrizen auf allen anderen Qubits erhalten wird.

In beiden Fällen erhalten wir eine Pauli-Operation mit Gewicht 4. Einzeln können diese Stabilisatorgeneratoren wie folgt dargestellt werden.

Hier ist eine Abbildung mit einigen Beispielen von Stabilisatorgeneratoren im Kontext des Gitters selbst. Man beachte, dass die Stabilisatorgeneratoren, die um die periodischen Ränder herum verlaufen, enthalten sind. Diese Generatoren, die um die periodischen Ränder herum verlaufen, sind nicht besonders oder in irgendeiner Weise von den anderen unterschieden.

Die Stabilisatorgeneratoren müssen kommutieren, damit dies ein gültiger Stabilisator-Code ist. Wie üblich kommutieren die $Z$-Stabilisatorgeneratoren alle miteinander, weil $Z$ mit sich selbst und die Identität mit allem kommutiert, und ebenso für die $X$-Stabilisatorgeneratoren. Die $Z$- und $X$-Stabilisatorgeneratoren kommutieren offensichtlich, wenn sie auf disjunkten Qubit-Mengen nicht-trivial wirken, wie in den Beispielen der vorherigen Abbildung. Die verbleibende Möglichkeit ist, dass ein $Z$-Stabilisatorgenerator und ein $X$-Stabilisatorgenerator sich auf den Qubits überlappen, auf denen sie nicht-trivial wirken, und immer wenn das passiert, überlappen die Generatoren immer auf zwei Qubits, wie in der nächsten Abbildung.

Folglich kommutieren zwei solche Stabilisatorgeneratoren, genau wie $Z\otimes Z$ und $X\otimes X$ kommutieren. Die Stabilisatorgeneratoren kommutieren daher alle miteinander.

Die zweite erforderliche Bedingung für die Stabilisatorgeneratoren eines Stabilisator-Codes ist, dass sie eine minimale Erzeugendenmenge bilden. Diese Bedingung ist bei dieser Kollektion tatsächlich nicht erfüllt: Multipliziert man alle $Z$-Stabilisatorgeneratoren miteinander, erhält man die Identitätsoperation, und ebenso für die $X$-Stabilisatorgeneratoren. Daher kann jeder der $Z$-Stabilisatorgeneratoren als Produkt aller verbleibenden ausgedrückt werden, und entsprechend kann jeder der $X$-Stabilisatorgeneratoren als Produkt der verbleibenden $X$-Stabilisatorgeneratoren ausgedrückt werden. Wenn wir jedoch einen der $Z$-Stabilisatorgeneratoren und einen der $X$-Stabilisatorgeneratoren entfernen, erhalten wir eine minimale Erzeugendenmenge.

Um das klarzustellen: Wir interessieren uns tatsächlich gleichermaßen für alle Stabilisatorgeneratoren, und streng operationell gesehen besteht keine Notwendigkeit, je einen Stabilisatorgenerator von jedem Typ zu entfernen. Aber zur Analyse des Codes – insbesondere zur Zählung der Generatoren – können wir uns vorstellen, dass ein Stabilisatorgenerator von jedem Typ entfernt wurde, um eine minimale Erzeugendenmenge zu erhalten, wobei wir im Hinterkopf behalten, dass wir die Ergebnisse dieser entfernten Generatoren (die man als Observablen betrachten kann) immer aus den Ergebnissen aller anderen Stabilisatorgenerator-Observablen desselben Typs ableiten könnten.

Das lässt $L^2 - 1$ Stabilisatorgeneratoren von jedem Typ, also $2L^2 - 2$ insgesamt, in einer (hypothetischen) minimalen Erzeugendenmenge übrig. Da insgesamt $2L^2$ Qubits vorhanden sind, bedeutet das, dass der Torische Code $2L^2 - 2 (L^2 - 1) = 2$ Qubits kodiert.

Die letzte erforderliche Bedingung an Stabilisatorgeneratoren ist, dass mindestens ein Quantenzustandsvektor von allen Stabilisatorgeneratoren fixiert wird. Wir werden sehen, dass das der Fall ist, wenn wir mit der Analyse des Codes fortfahren, aber man kann auch argumentieren, dass es keine Möglichkeit gibt, $-1$ mal die Identität auf allen $2L^2$ Qubits aus den Stabilisatorgeneratoren zu erzeugen.

Fehlererkennung

Der Torische Code hat eine einfache und elegante Beschreibung, aber seine quantenfehlerkorrigierenden Eigenschaften sind auf den ersten Blick möglicherweise überhaupt nicht klar. Es ist ein erstaunlicher Code! Um zu verstehen, warum und wie er funktioniert, beginnen wir damit, verschiedene Fehler und die von ihnen erzeugten Syndrome zu betrachten.

Der Torische Code ist ein CSS-Code, weil alle unsere Stabilisatorgeneratoren entweder $Z$- oder $X$-Stabilisatorgeneratoren sind. Das bedeutet, dass $X$-Fehler und $Z$-Fehler separat erkannt (und möglicherweise korrigiert) werden können. Tatsächlich gibt es eine einfache Symmetrie zwischen den $Z$- und $X$-Stabilisatorgeneratoren, die es uns ermöglicht, $X$-Fehler und $Z$-Fehler im Wesentlichen auf dieselbe Weise zu analysieren. Wir konzentrieren uns daher auf $X$-Fehler, die möglicherweise von den $Z$-Stabilisatorgeneratoren erkannt werden – aber die gesamte folgende Diskussion kann von $X$-Fehlern auf $Z$-Fehler übertragen werden, die analog von den $X$-Stabilisatorgeneratoren erkannt werden.

Das folgende Diagramm zeigt die Wirkung eines $X$-Fehlers auf ein einzelnes Qubit. Hierbei wird angenommen, dass unsere $2L^2$ Qubits zuvor in einem im Koderaum des Torischen Codes enthaltenen Zustand waren, sodass alle Stabilisatorgenerator-Messungen $+1$ ausgeben. Die $Z$-Stabilisatorgeneratoren erkennen $X$-Fehler, und es gibt einen solchen Stabilisatorgenerator für jede Kachel in der Abbildung, sodass wir das Messergebnis des entsprechenden Stabilisatorgenerators durch die Farbe dieser Kachel anzeigen können: $+1$-Ergebnisse werden durch weiße Kacheln und $-1$-Ergebnisse durch graue Kacheln angezeigt. Wenn ein Bit-Flip-Fehler auf einem der Qubits auftritt, bewirkt er, dass die Stabilisatorgenerator-Messungen für die beiden Kacheln, die das betroffene Qubit berühren, jetzt $-1$ ausgeben.

Das ist intuitiv, wenn wir $Z$-Stabilisatorgeneratoren und ihr Verhalten betrachten. Im Wesentlichen misst jeder $Z$-Stabilisatorgenerator die Parität der vier Qubits, die die entsprechende Kachel berühren (bezüglich der Standardbasis). Ein $+1$-Ergebnis zeigt also nicht an, dass auf diesen vier Qubits keine $X$-Fehler aufgetreten sind, sondern dass eine gerade Anzahl von $X$-Fehlern aufgetreten ist, während ein $-1$-Ergebnis anzeigt, dass eine ungerade Anzahl von $X$-Fehlern aufgetreten ist. Ein einzelner $X$-Fehler kippt daher die Parität der vier Bits auf beiden Kacheln, die er berührt, wodurch die Stabilisatorgenerator-Messungen $-1$ ausgeben.

Betrachten wir nun mehrere $X$-Fehler, um zu sehen, was passiert. Insbesondere betrachten wir eine Kette benachbarter $X$-Fehler, wobei zwei $X$-Fehler benachbart sind, wenn sie Qubits betreffen, die dieselbe Kachel berühren.

Die beiden $Z$-Stabilisatorgeneratoren an den Endpunkten der Kette geben in diesem Fall beide das Ergebnis $-1$, da auf diesen beiden entsprechenden Kacheln eine ungerade Anzahl von $X$-Fehlern aufgetreten ist. Alle anderen $Z$-Stabilisatorgeneratoren hingegen geben das Ergebnis $+1$, einschließlich derjenigen, die die Kette berühren, aber nicht an den Endpunkten liegen, weil auf den Qubits, die die entsprechenden Kacheln berühren, eine gerade Anzahl von $X$-Fehlern aufgetreten ist.

Solange wir also eine Kette von $X$-Fehlern haben, die Endpunkte hat, erkennt der Torische Code, dass Fehler aufgetreten sind – und die $-1$-Messergebnisse für die $Z$-Stabilisatorgeneratoren zeigen die Endpunkte der Kette. Man beachte, dass die tatsächliche Fehlerkette nicht enthüllt wird, sondern nur die Endpunkte! Das ist in Ordnung – im nächsten Unterabschnitt werden wir sehen, dass wir nicht genau wissen müssen, welche Qubits von $X$-Fehlern betroffen sind, um sie zu korrigieren. (Der Torische Code ist ein Beispiel für einen stark degenerierten Code, in dem Sinne, dass er die korrigierten Fehler im Allgemeinen nicht eindeutig identifiziert.)

Es ist jedoch möglich, dass eine Kette benachbarter $X$-Fehler keine Endpunkte hat – das heißt, dass eine Fehlerkette eine geschlossene Schleife bildet, wie in der folgenden Abbildung.

In einem solchen Fall ist auf jeder Kachel eine gerade Anzahl von $X$-Fehlern aufgetreten, sodass jede Stabilisatorgenerator-Messung ein $+1$-Ergebnis liefert. Geschlossene Schleifen benachbarter $X$-Fehler werden daher vom Code nicht erkannt.

Das könnte enttäuschend wirken, da man nur vier $X$-Fehler benötigt, um eine geschlossene Schleife zu bilden (und wir hoffen auf etwas deutlich besser als einen Distanz-4-Code). Eine geschlossene Schleife von $X$-Fehlern wie in der vorherigen Abbildung ist jedoch tatsächlich kein Fehler – denn sie liegt im Stabilisator! Erinnere dich: Zusätzlich zu den $Z$-Stabilisatorgeneratoren haben wir auch einen $X$-Stabilisatorgenerator für jeden Eckpunkt im Gitter. Und wenn wir benachbarte $X$-Stabilisatorgeneratoren miteinander multiplizieren, erhalten wir geschlossene Schleifen von $X$-Operationen. Die geschlossene Schleife in der vorherigen Abbildung kann zum Beispiel durch Multiplikation der in der folgenden Abbildung angezeigten $X$-Stabilisatorgeneratoren erhalten werden.

Das ist jedoch nicht der einzige Typ geschlossener Schleifen von $X$-Fehlern – und es trifft nicht zu, dass jede geschlossene Schleife von $X$-Fehlern im Stabilisator enthalten ist. Insbesondere können die verschiedenen Typen von Schleifen wie folgt charakterisiert werden.

1. Geschlossene Schleifen von $X$-Fehlern mit einer geraden Anzahl von $X$-Fehlern auf jeder horizontalen und jeder vertikalen Qubit-Linie. (Das obige Beispiel fällt in diese Kategorie.) Schleifen dieser Form sind immer im Stabilisator enthalten, da sie durch Multiplikation mit $X$-Stabilisatorgeneratoren auf nichts reduziert werden können.

2. Geschlossene Schleifen von $X$-Fehlern mit einer ungeraden Anzahl von $X$-Fehlern auf mindestens einer horizontalen oder mindestens einer vertikalen Qubit-Linie. Schleifen dieser Form sind niemals im Stabilisator enthalten und stellen daher nicht-triviale Fehler dar, die vom Code nicht erkannt werden.

Ein Beispiel für eine geschlossene Schleife von $X$-Fehlern der zweiten Kategorie ist im folgenden Diagramm dargestellt.

Eine solche Fehlerkette ist nicht im Stabilisator enthalten, da jeder $X$-Stabilisatorgenerator eine gerade Anzahl von $X$-Operationen auf jeder horizontalen und vertikalen Qubit-Linie platziert. Das ist daher ein tatsächliches Beispiel für einen nicht-trivialen Fehler, den der Code nicht erkennt.

Der Schlüssel liegt darin, dass die einzige Möglichkeit, eine Schleife der zweiten Art zu bilden, darin besteht, den Torus zu umrunden – entweder durch das Loch in der Mitte des Torus, durch ihn hindurch oder beides. Intuitiv gesagt kann eine solche $X$-Fehlerkette nicht durch Multiplikation mit $X$-Stabilisatorgeneratoren auf nichts reduziert werden, weil die Topologie eines Torus das verhindert. Der Torische Code wird aus diesem Grund manchmal als topologischer quantenfehlerkorrigierender Code kategorisiert. Die kürzestmögliche Länge einer solchen Schleife ist $L$, und das ist daher die Distanz des Torischen Codes: Jede geschlossene Schleife von $X$-Fehlern mit Länge kleiner als $L$ muss zur ersten Kategorie gehören und ist daher im Stabilisator enthalten; und jede Kette von $X$-Fehlern mit Endpunkten wird vom Code erkannt.

Da der Torische Code $2L^2$ Qubits verwendet, um $2$ Qubits zu kodieren, und Distanz $L$ hat, ist er ein $[[2L^2,2,L]]$-Stabilisator-Code.

Fehlerkorrektur

Wir haben die Fehlererkennung für den Torischen Code besprochen und wenden uns nun kurz der Korrektur von Fehlern zu. Der Torische Code ist ein CSS-Code, sodass $X$-Fehler und $Z$-Fehler unabhängig erkannt und korrigiert werden können. Mit Fokus auf die $Z$-Stabilisatorgeneratoren, die $X$-Fehler erkennen, betrachten wir, wie eine Kette von $X$-Fehlern korrigiert werden kann. ($Z$-Fehler werden auf symmetrische Weise korrigiert.)

Wenn ein anderes als das $(+1,\ldots,+1)$-Syndrom erscheint, wenn die $Z$-Stabilisatorgeneratoren gemessen werden, zeigen die $-1$-Ergebnisse die Endpunkte einer oder mehrerer $X$-Fehlerketten. Wir können versuchen, diese Fehler zu korrigieren, indem wir die $-1$-Ergebnisse paarweise zusammenfassen und eine $X$-Korrekturkette zwischen ihnen bilden. Dabei ist es sinnvoll, kürzeste Pfade für die Korrekturen zu wählen.

Betrachte zum Beispiel das folgende Diagramm, das ein Syndrom mit zwei $-1$-Ergebnissen zeigt (durch graue Kacheln angezeigt), verursacht durch eine durch die magentafarbene Linie und Kreise dargestellte $X$-Fehlerkette. Wie bereits angemerkt, wird die Kette selbst vom Syndrom nicht enthüllt; nur die Endpunkte sind sichtbar.

Um diese Fehlerkette zu korrigieren, wird ein kürzester Pfad zwischen den $-1$-Messergebnissen ausgewählt und $X$-Gates werden als Korrekturen auf die Qubits entlang dieses Pfades angewendet (in der Abbildung gelb markiert). Obwohl die Korrekturen möglicherweise nicht mit der tatsächlichen Fehlerkette übereinstimmen, bilden Fehler und Korrekturen zusammen eine geschlossene Schleife von $X$-Operationen, die im Stabilisator des Codes enthalten ist. Die Korrektur ist in dieser Situation also erfolgreich, da der kombinierte Effekt von Fehlern und Korrekturen nichts am kodierten Zustand ändert.

Diese Strategie wird nicht immer erfolgreich sein. Eine andere Erklärung für dasselbe Syndrom wie in der vorherigen Abbildung ist in der folgenden Abbildung zu sehen.

Diesmal schlägt dieselbe Korrektukette wie zuvor fehl, weil der kombinierte Effekt von Fehlern und Korrekturen darin besteht, dass wir eine geschlossene Schleife von $X$-Operationen erhalten, die um den Torus herumläuft und daher eine nicht-triviale Wirkung auf den Koderaum hat. Es gibt also keine Garantie, dass die beschriebene Strategie – einen kürzesten Pfad von $X$-Korrekturen zwischen zwei $-1$-Syndrom-Messergebnissen zu wählen – den Fehler, der dieses Syndrom verursacht hat, ordnungsgemäß korrigiert.

Wahrscheinlicher, je nach Rauschmodell, ist jedoch, dass ein Syndrom mit mehr als zwei $-1$-Einträgen gemessen wird, wie die folgende Abbildung andeutet.

In einem solchen Fall sind verschiedene Korrekturstrategien bekannt. Eine naheliegende Strategie ist, die $-1$-Messergebnisse paarweise zusammenzufassen und Korrekturen entlang kürzester Pfade zwischen den Paaren durchzuführen, wie in der Abbildung in Gelb angezeigt. Insbesondere kann ein minimum-weight perfect matching zwischen den $-1$-Messergebnissen berechnet werden, und dann werden die Paare durch kürzeste Pfade von $X$-Korrekturen verbunden. Die Berechnung eines Minimum-Weight-Perfect-Matchings kann effizient mit einem klassischen Algorithmus, dem Blossom-Algorithmus, durchgeführt werden, der von Edmonds in den 1960er Jahren entdeckt wurde.

Dieser Ansatz ist für die am häufigsten untersuchten Rauschmodelle im Allgemeinen nicht optimal, aber basierend auf numerischen Simulationen funktioniert er in der Praxis sehr gut bei Fehlerraten von bis zu etwa 10%, unter der Annahme unabhängiger Pauli-Fehler, bei denen $X,$ $Y$ und $Z$ gleich wahrscheinlich sind. Eine Erhöhung von $L$ hat keinen wesentlichen Einfluss auf den Break-Even-Punkt, ab dem der Code zu helfen beginnt, führt aber zu einer schnelleren Abnahme der Wahrscheinlichkeit eines logischen Fehlers, wenn die Fehlerrate unter den Break-Even-Punkt sinkt.