CSS-Codes

Klassische lineare Codes

Klassische fehlerkorrigierende Codes wurden erstmals in den 1940er Jahren untersucht, und seitdem sind viele verschiedene Codes bekannt. Die am häufigsten untersuchten und verwendeten Codes gehören zur Kategorie der sogenannten linearen Codes. Was das Wort „linear" in diesem Zusammenhang genau bedeutet, wird gleich klar werden. Einfach ausgedrückt sind lineare Codes Stabilisatorcodes, die jedoch klassischer Natur sind. CSS-Codes sind im Wesentlichen Paare klassischer linearer Codes, die zu einem Quantenfehlerkorrekturcode kombiniert werden. Um die folgende Diskussion zu verstehen, müssen wir einige grundlegende Eigenschaften klassischer linearer Codes kennen.

Sei $\Sigma$ das binäre Alphabet für diese gesamte Diskussion. Wenn wir von einem klassischen linearen Code sprechen, meinen wir eine nichtleere Menge $\mathcal{C}\subseteq\Sigma^n$ binärer Zeichenketten der Länge $n$ (für eine positive ganze Zahl $n$), die genau eine grundlegende Eigenschaft erfüllen muss: Sind $u$ und $v$ binäre Zeichenketten in $\mathcal{C}$, so muss auch $u\oplus v$ in $\mathcal{C}$ liegen. Dabei bezeichnet $u\oplus v$ das bitweise Exklusiv-ODER von $u$ und $v$, wie es uns im Kurs „Grundlagen der Quantenalgorithmen" mehrfach begegnet ist.

Im Wesentlichen betrachten wir bei linearen klassischen Codes binäre Zeichenketten der Länge $n$ als $n$-dimensionale Vektoren mit Einträgen aus $\{0, 1\}$ und fordern, dass der Code selbst einen linearen Unterraum bildet. Statt der gewöhnlichen Vektoraddition über den reellen oder komplexen Zahlen verwenden wir dabei Addition modulo $2$, also das Exklusiv-ODER. Das heißt: Sind $u$ und $v$ zwei Codewörter in $\mathcal{C}$, so muss auch $u + v$ modulo 2, also $u\oplus v$, ein Codewort in $\mathcal{C}$ sein. Beachte insbesondere, dass dies auch dann gilt, wenn $u = v$. Daraus folgt, dass $\mathcal{C}$ die Nullzeichenkette $0^n$ enthalten muss, da das bitweise Exklusiv-ODER einer beliebigen Zeichenkette mit sich selbst die Nullzeichenkette ergibt.

Beispiel: der 3-Bit-Wiederholungscode

Der 3-Bit-Wiederholungscode ist ein Beispiel für einen klassischen linearen Code. Konkret gilt $\mathcal{C} = \{000,111\}$, und für die Linearitätsbedingung gibt es genau zwei mögliche Wahlen für $u$ und zwei für $v$. Es ist einfach nachzuprüfen, dass bei allen vier möglichen Paaren das bitweise Exklusiv-ODER stets ein Codewort ergibt:

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

Beispiel: der $[7,4,3]$-Hamming-Code

Hier ist ein weiteres Beispiel für einen klassischen linearen Code: der $[7,4,3]$-Hamming-Code. Er war einer der allerersten entdeckten klassischen fehlerkorrigierenden Codes und besteht aus diesen 16 binären Zeichenketten der Länge 7. (Manchmal versteht man unter dem $[7,4,3]$-Hamming-Code den Code mit den gespiegelten Zeichenketten, aber wir betrachten hier den Code mit den nachfolgend angezeigten Zeichenketten.)

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

Hinter der Auswahl dieser Zeichenketten steckt eine einfache Logik, die aber für diese Lektion zweitrangig ist und hier nicht erklärt wird. Es genügt festzuhalten, dass dies ein klassischer linearer Code ist: Das XOR beliebiger zwei dieser Zeichenketten ergibt stets eine weitere Zeichenkette im Code.

Die Notation $[7,4,3]$ (in einfachen eckigen Klammern) hat eine ähnliche Bedeutung wie die doppelte Eckklammer-Notation für Stabilisatorcodes aus der vorherigen Lektion, gilt hier aber für klassische lineare Codes. Konkret bedeutet dies: Codewörter haben $7$ Bits, es lassen sich $4$ Bits kodieren (da es $16 = 2^4$ Codewörter gibt), und es handelt sich um einen Code mit Distanz $3$, d.h. zwei verschiedene Codewörter unterscheiden sich in mindestens $3$ Positionen — es müssen also mindestens $3$ Bits umgekippt werden, um ein Codewort in ein anderes umzuwandeln. Die Tatsache, dass es sich um einen Code mit Distanz $3$ handelt, impliziert, dass er bis zu einem Bit-Flip-Fehler korrigieren kann.

Beschreibung klassischer linearer Codes

Die gerade genannten Beispiele sind sehr einfache klassische lineare Codes, doch selbst beim $[7,4,3]$-Hamming-Code wirkt die bloße Auflistung der Codewörter etwas rätselhaft. Es gibt bessere und effizientere Möglichkeiten, klassische lineare Codes zu beschreiben, darunter die folgenden zwei.

1. Generatoren. Eine Möglichkeit, einen klassischen linearen Code zu beschreiben, ist eine minimale Liste von Codewörtern, die den Code erzeugen, d.h. durch Auswahl aller möglichen Teilmengen dieser Codewörter und deren XOR-Verknüpfung erhält man den gesamten Code.

   Genauer gesagt erzeugen die Zeichenketten $u_1,\ldots,u_m\in\Sigma^n$ den klassischen linearen Code $\mathcal{C}$, wenn

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

   wobei $\alpha u = u$ für $\alpha = 1$ und $\alpha u = 0^n$ für $\alpha = 0$, und diese Liste heißt minimal, wenn das Entfernen einer der Zeichenketten einen kleineren Code erzeugt. Eine natürliche Sichtweise auf diese Beschreibung ist, dass $\{u_1,\ldots,u_m\}$ eine Basis für $\mathcal{C}$ als Unterraum bildet — wir betrachten Zeichenketten als Vektoren mit binärwertigen Einträgen und arbeiten in einem Vektorraum, in dem modulo $2$ gerechnet wird.

2. Paritätsprüfungen. Eine weitere natürliche Beschreibung eines klassischen linearen Codes sind Paritätsprüfungen — also eine minimale Liste binärer Zeichenketten, für die genau die Zeichenketten im Code sind, deren binäres Skalarprodukt mit jeder dieser Paritätsprüfzeichenketten null ist. (Ähnlich wie das bitweise Exklusiv-ODER ist das binäre Skalarprodukt mehrfach im Kurs „Grundlagen der Quantenalgorithmen" vorgekommen.)

   Das heißt: Die Zeichenketten $v_1,\ldots,v_r\in\Sigma^n$ sind Paritätsprüfzeichenketten für den klassischen linearen Code $\mathcal{C}$, wenn

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

   und diese Menge von Zeichenketten ist minimal, wenn das Entfernen einer davon zu einem größeren Code führt. Sie heißen Paritätsprüfzeichenketten, weil $u$ genau dann binäres Skalarprodukt null mit $v$ hat, wenn die Bits von $u$ an den Positionen, an denen $v$ eine 1 hat, eine gerade Parität aufweisen. Um zu prüfen, ob eine Zeichenkette $u$ im Code $\mathcal{C}$ liegt, genügt es also, die Parität bestimmter Teilmengen der Bits von $u$ zu überprüfen.

   Ein wichtiger Hinweis: Das binäre Skalarprodukt ist im formalen Sinne kein inneres Produkt. Insbesondere bedeutet ein binäres Skalarprodukt von null zwischen zwei Zeichenketten nicht, dass sie im üblichen Sinne orthogonal sind. So ist beispielsweise das binäre Skalarprodukt der Zeichenkette $11$ mit sich selbst null — eine Paritätsprüfzeichenkette eines klassischen linearen Codes kann also selbst im Code liegen.

Klassische lineare Codes über dem binären Alphabet enthalten stets eine Anzahl von Zeichenketten, die eine Potenz von $2$ ist — und für einen einzelnen klassischen linearen Code, der auf die beiden beschriebenen Weisen dargestellt wird, gilt stets $n = m + r$. Konkret gilt: Haben wir eine minimale Menge von $m$ Generatoren, kodiert der Code $m$ Bits und hat genau $2^m$ Codewörter; haben wir eine minimale Menge von $r$ Paritätsprüfzeichenketten, gibt es $2^{n-r}$ Codewörter. Jeder Generator verdoppelt also die Größe des Coderaums, während jede Paritätsprüfzeichenkette die Größe halbiert.

Zum Beispiel ist der 3-Bit-Wiederholungscode ein linearer Code, der auf beide Arten beschrieben werden kann. Es gibt genau einen Generator, der funktioniert: $111$. Alternativ lässt sich der Code durch zwei Paritätsprüfzeichenketten beschreiben, z.B. $110$ und $011$ — die aus früheren Diskussionen dieses Codes bekannt vorkommen dürften — oder auch $110$ und $101$ bzw. $101$ und $011$. (Generatoren und Paritätsprüfzeichenketten sind für einen gegebenen klassischen linearen Code im Allgemeinen nicht eindeutig.)

Als zweites Beispiel betrachten wir den $[7,4,3]$-Hamming-Code. Hier ist eine mögliche Liste von Generatoren:

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

Und hier ist eine mögliche Liste von Paritätsprüfungen für diesen Code:

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

Hier sehen wir übrigens, dass alle Paritätsprüfzeichenketten selbst im Code liegen.

Eine abschließende Bemerkung zu klassischen linearen Codes, die sie mit dem Stabilisatorformalismus verbindet: Paritätsprüfzeichenketten entsprechen Stabilisatorgeneratoren, die nur aus $Z$- und Identitäts-Pauli-Matrizen bestehen. Die Paritätsprüfzeichenketten $110$ und $011$ des 3-Bit-Wiederholungscodes entsprechen zum Beispiel genau den Stabilisatorgeneratoren $Z\otimes Z\otimes \mathbb{I}$ und $\mathbb{I}\otimes Z\otimes Z$, was mit den Diskussionen über Pauli-Observablen aus der vorherigen Lektion übereinstimmt.

Definition der CSS-Codes

CSS-Codes sind Stabilisatorcodes, die durch die Kombination bestimmter Paare klassischer linearer Codes entstehen. Das funktioniert nicht für beliebige zwei klassische lineare Codes — die beiden Codes müssen eine bestimmte Beziehung zueinander haben. Dennoch eröffnet diese Konstruktion viele Möglichkeiten für Quantenfehlerkorrekturcodes, die zum Teil auf über 75 Jahre klassischer Codierungstheorie aufbauen.

Im Stabilisatorformalismus sind Stabilisatorgeneratoren, die nur $Z$- und Identitäts-Pauli-Matrizen enthalten, äquivalent zu Paritätsprüfungen, wie wir es gerade beim 3-Bit-Wiederholungscode gesehen haben. Als weiteres Beispiel betrachten wir die folgenden Paritätsprüfzeichenketten für den $[7,4,3]$-Hamming-Code:

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

Diese Paritätsprüfzeichenketten entsprechen den folgenden Stabilisatorgeneratoren (ohne Tensorproduktsymbole), die man erhält, indem man jede $1$ durch $Z$ und jede $0$ durch $\mathbb{I}$ ersetzt. Das sind drei der sechs Stabilisatorgeneratoren des 7-Qubit-Steane-Codes.

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

Stabilisatorgeneratoren dieser Art — bei denen nur Pauli-$Z$- und Identitäts-Tensorfaktoren auftreten ($X$- und $Y$-Pauli-Matrizen kommen nicht vor) — nennen wir $Z$-Stabilisatorgeneratoren.

Daneben gibt es Stabilisatorgeneratoren, bei denen nur $X$- und Identitäts-Pauli-Matrizen als Tensorfaktoren auftreten. Solche Generatoren sind den $Z$-Stabilisatorgeneratoren analog, beschreiben aber Paritätsprüfungen in der $\{\vert+\rangle,\vert-\rangle\}$-Basis statt der Standardbasis. Generatoren dieser Form heißen $X$-Stabilisatorgeneratoren — hier sind weder $Y$- noch $Z$-Pauli-Matrizen erlaubt.

Betrachten wir als Beispiel die verbleibenden drei Stabilisatorgeneratoren des 7-Qubit-Steane-Codes:

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

Sie folgen exakt demselben Muster des $[7,4,3]$-Hamming-Codes wie die $Z$-Stabilisatorgeneratoren, diesmal wird aber $X$ statt $Z$ für jede $1$ eingesetzt. Allein aus diesen drei Stabilisatorgeneratoren erhält man einen Code, der die 16 hier gezeigten Zustände enthält — sie entstehen durch Anwendung von Hadamard-Operationen auf die Standardbasiszustände, die den Zeichenketten im $[7,4,3]$-Hamming-Code entsprechen. (Natürlich enthält der Coderaum auch Linearkombinationen dieser Zustände.)

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

CSS-Codes lassen sich nun in sehr einfachen Worten definieren.

Definition

Ein CSS-Code ist ein Stabilisatorcode, der sich ausschließlich mit $X$- und $Z$-Stabilisatorgeneratoren ausdrücken lässt.

Das heißt, CSS-Codes sind Stabilisatorcodes, für die Stabilisatorgeneratoren existieren, in denen keine Pauli-$Y$-Matrizen vorkommen und bei denen $X$ und $Z$ nie im gleichen Stabilisatorgenerator auftreten.

Um das klarzustellen: Nach dieser Definition ist ein CSS-Code einer, bei dem es möglich ist, ausschließlich $X$- und $Z$-Stabilisatorgeneratoren zu wählen — aber wir müssen im Hinterkopf behalten, dass es bei Stabilisatorcodes Freiheit in der Wahl der Generatoren gibt. Es wird also im Allgemeinen verschiedene Wahlen von Stabilisatorgeneratoren für einen CSS-Code geben, die keine $X$- oder $Z$-Stabilisatorgeneratoren sind (zusätzlich zu mindestens einer Wahl, bei der sie es sind).

Hier ist ein sehr einfaches Beispiel für einen CSS-Code, der sowohl einen $Z$-Stabilisatorgenerator als auch einen $X$-Stabilisatorgenerator enthält:

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

Es ist offensichtlich, dass dies ein CSS-Code ist: Der erste Stabilisatorgenerator ist ein $Z$-Stabilisatorgenerator und der zweite ein $X$-Stabilisatorgenerator. Natürlich muss ein CSS-Code auch ein gültiger Stabilisatorcode sein — das heißt, die Stabilisatorgeneratoren müssen kommutieren, eine minimale Erzeugermenge bilden und mindestens einen Quantenzustandsvektor fixieren. Diese Anforderungen sind für diesen Code leicht zu überprüfen. Wie in der vorherigen Lektion erwähnt, ist der Coderaum dieses Codes der eindimensionale Raum, der vom Bell-Zustand $\vert\phi^+\rangle$ aufgespannt wird. Dass beide Stabilisatorgeneratoren diesen Zustand fixieren, ergibt sich aus den folgenden zwei Ausdrücken für ein E-Bit sowie einer Interpretation dieser Stabilisatorgeneratoren als Paritätsprüfungen in der $\{\vert 0\rangle, \vert 1\rangle\}$- und der $\{\vert +\rangle, \vert -\rangle\}$-Basis.

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

Der 7-Qubit-Steane-Code ist ein weiteres Beispiel für einen CSS-Code.

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

Hier haben wir drei $Z$-Stabilisatorgeneratoren und drei $X$-Stabilisatorgeneratoren, und wir haben bereits überprüft, dass es sich um einen gültigen Stabilisatorcode handelt.

Und der 9-Qubit-Shor-Code ist ein weiteres Beispiel:

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

Diesmal haben wir sechs $Z$-Stabilisatorgeneratoren und nur zwei $X$-Stabilisatorgeneratoren. Das ist in Ordnung — zwischen den beiden Generatortypen muss keine Balance oder Symmetrie bestehen (obwohl das häufig der Fall ist).

Noch einmal sei betont, dass CSS-Codes gültige Stabilisatorcodes sein müssen; insbesondere muss jeder $Z$-Stabilisatorgenerator mit jedem $X$-Stabilisatorgenerator kommutieren. Nicht jede Kombination von $X$- und $Z$-Stabilisatorgeneratoren definiert also einen gültigen CSS-Code.

Fehlererkennung und -korrektur

Bezüglich der Fehlererkennung und -korrektur haben CSS-Codes im Allgemeinen eine ähnliche Eigenschaft wie der 9-Qubit-Shor-Code: $X$- und $Z$-Fehler können vollständig unabhängig voneinander erkannt und korrigiert werden. Die $Z$-Stabilisatorgeneratoren beschreiben einen Code, der gegen Bit-Flips schützt, und die $X$-Stabilisatorgeneratoren beschreiben einen Code, der unabhängig davon gegen Phasen-Flips schützt. Das funktioniert, weil $Z$-Stabilisatorgeneratoren zwangsläufig mit $Z$-Fehlern und $Z$-Korrekturen kommutieren — sie sind also für beide völlig unsichtbar — und dasselbe gilt entsprechend für $X$-Stabilisatorgeneratoren, Fehler und Korrekturen.

Als Beispiel betrachten wir den 7-Qubit-Steane-Code:

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

Die Grundidee dieses Codes ist nun klar: Er ist ein $[7,4,3]$-Hamming-Code für Bit-Flip-Fehler und ein $[7,4,3]$-Hamming-Code für Phasen-Flip-Fehler. Dass die $X$- und $Z$-Stabilisatorgeneratoren kommutieren, ist gewissermaßen ein glücklicher Umstand — wäre das nicht so, wäre es kein gültiger Stabilisatorcode. Tatsächlich gibt es jedoch viele bekannte Beispiele klassischer linearer Codes, die auf ähnliche Weise zu einem gültigen Stabilisatorcode führen.

Angenommen, wir haben einen CSS-Code, bei dem die $Z$-Stabilisatorgeneratoren die Korrektur von bis zu $j$ Bit-Flip-Fehlern ermöglichen und die $X$-Stabilisatorgeneratoren die Korrektur von bis zu $k$ Phasen-Flip-Fehlern. Für den Steane-Code gilt beispielsweise $j = 1$ und $k = 1$, da der $[7,4,3]$-Hamming-Code einen Bit-Flip korrigieren kann. Durch die Diskretisierung von Fehlern folgt daraus, dass dieser CSS-Code beliebige Fehler auf einer Anzahl von Qubits bis zum Minimum von $j$ und $k$ korrigieren kann. Denn beim Messen des Syndroms kollabiert ein beliebiger Fehler auf dieser Anzahl von Qubits probabilistisch in eine Kombination von $X$-Fehlern, $Z$-Fehlern oder beidem — und dann werden $X$-Fehler und $Z$-Fehler unabhängig voneinander erkannt und korrigiert.

Zusammengefasst: Haben wir zwei klassische lineare Codes (oder zwei Kopien eines einzelnen klassischen linearen Codes), die kompatibel sind — also $X$- und $Z$-Stabilisatorgeneratoren definieren, die kommutieren — so erbt der CSS-Code, den wir durch ihre Kombination erhalten, die Fehlerkorrektur-Eigenschaften dieser beiden Codes im beschriebenen Sinne.

Dabei gibt es jedoch einen Preis zu zahlen: Wir können nicht so viele Qubits kodieren wie Bits in den beiden klassischen Codes. Das liegt daran, dass die Gesamtzahl der Stabilisatorgeneratoren des CSS-Codes die Summe der Paritätsprüfungen der beiden klassischen linearen Codes ist, und jeder Stabilisatorgenerator halbiert die Dimension des Coderaums. Zum Beispiel erlaubt der $[7,4,3]$-Hamming-Code die Kodierung von vier klassischen Bits (da er nur drei Paritätsprüfzeichenketten hat), während der 7-Qubit-Steane-Code nur ein Qubit kodiert (da er sechs Stabilisatorgeneratoren hat).

Coderäume von CSS-Codes

Zum Abschluss unserer Diskussion über CSS-Codes betrachten wir die Coderäume dieser Codes. Das gibt uns Gelegenheit, die Beziehung, die zwischen zwei klassischen linearen Codes gelten muss, damit sie kompatibel sind und zu einem CSS-Code kombiniert werden können, genauer zu untersuchen.

Betrachte einen beliebigen CSS-Code auf $n$ Qubits und sei $z_1, \ldots, z_s \in \Sigma^n$ die Menge der $n$-Bit-Paritätsprüfzeichenketten, die den $Z$-Stabilisatorgeneratoren dieses Codes entsprechen. Der klassische lineare Code, der allein durch die $Z$-Stabilisatorgeneratoren beschrieben wird und den wir $\mathcal{C}_Z$ nennen, hat dann folgende Form:

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

Mit anderen Worten enthält der klassische lineare Code $\mathcal{C}_Z$ genau die Zeichenketten, deren binäres Skalarprodukt mit jeder der Paritätsprüfzeichenketten $z_1, \ldots, z_s$ null ist.

Entsprechend sei $x_1,\ldots,x_t\in\Sigma^n$ die Menge der $n$-Bit-Paritätsprüfzeichenketten, die den $X$-Stabilisatorgeneratoren unseres Codes entsprechen. Der klassische lineare Code der $X$-Stabilisatorgeneratoren hat dann diese Form:

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

Die $X$-Stabilisatorgeneratoren allein beschreiben also einen Code, der diesem ähnlich ist, aber in der $\{\vert {+}\rangle,\vert {-}\rangle\}$-Basis statt der Standardbasis.

Nun führen wir zwei neue klassische lineare Codes ein, die aus denselben Zeichenketten $z_1,\ldots,z_s$ und $x_1,\ldots,x_t$ abgeleitet werden, diesmal aber als Generatoren statt als Paritätsprüfzeichenketten. Wir erhalten die folgenden zwei Codes:

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

Diese werden als duale Codes der zuvor definierten Codes bezeichnet: $\mathcal{D}_Z$ ist der duale Code von $\mathcal{C}_Z$ und $\mathcal{D}_X$ ist der duale Code von $\mathcal{C}_X$. Es mag im Moment nicht offensichtlich sein, warum diese dualen Codes relevant sind, aber sie spielen aus mehreren Gründen eine wichtige Rolle, darunter die zwei in den folgenden Absätzen erläuterten.

Erstens lassen sich die Bedingungen, die zwei klassische lineare Codes $\mathcal{C}_Z$ und $\mathcal{C}_X$ erfüllen müssen, um kompatibel zu sein (also zu einem CSS-Code kombiniert werden zu können), mithilfe der dualen Codes einfach beschreiben. Konkret muss gelten: $\mathcal{D}_Z\subseteq\mathcal{C}_X$, was äquivalent ist zu $\mathcal{D}_X\subseteq\mathcal{C}_Z$. Mit anderen Worten: Der duale Code $\mathcal{D}_Z$ enthält die Zeichenketten der $Z$-Stabilisatorgeneratoren, und ihre Enthaltensein in $\mathcal{C}_X$ ist äquivalent dazu, dass das binäre Skalarprodukt jeder dieser Zeichenketten mit denen der $X$-Stabilisatorgeneratoren null ist. Das wiederum ist äquivalent dazu, dass jeder $Z$-Stabilisatorgenerator mit jedem $X$-Stabilisatorgenerator kommutiert. Alternativ kann man durch Vertauschen der Rollen von $X$- und $Z$-Stabilisatorgeneratoren und Ausgehen von der Inklusion $\mathcal{D}_X\subseteq\mathcal{C}_Z$ zur gleichen Schlussfolgerung gelangen.

Zweitens lassen sich mithilfe der dualen Codes die Coderäume eines gegebenen CSS-Codes leicht beschreiben. Insbesondere wird der Coderaum von Vektoren der folgenden Form aufgespannt:

$$\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{(für alle $u\in\mathcal{C}_Z$)}$$

Mit anderen Worten sind diese Vektoren gleichgewichtete Superpositionen über die Zeichenketten des dualen Codes $\mathcal{D}_X$ des den $X$-Stabilisatorgeneratoren entsprechenden Codes, verschoben (d.h. bitweise XOR-verknüpft) mit Zeichenketten aus dem Code $\mathcal{C}_Z$ der $Z$-Stabilisatorgeneratoren. Zur Klarstellung: Verschiedene Wahlen der Verschiebung — dargestellt durch die Zeichenkette $u$ in diesem Ausdruck — können zum selben Vektor führen. Diese Zustände sind also nicht alle verschieden, aber zusammen spannen sie den gesamten Coderaum auf.

Hier ist eine intuitive Erklärung, warum solche Vektoren sowohl im Coderaum liegen als auch ihn aufspannen. Betrachte den $n$-Qubit-Standardbasiszustand $\vert u\rangle$ für eine beliebige $n$-Bit-Zeichenkette $u$ und projiziere diesen Zustand auf den Coderaum. Sei also $\Pi$ die Projektion auf den Coderaum unseres CSS-Codes und betrachte den Vektor $\Pi\vert u\rangle$. Es gibt zwei Fälle:

• Fall 1: $u\in\mathcal{C}_Z.$ Das bedeutet, dass jeder $Z$-Stabilisatorgenerator unseres CSS-Codes auf $\vert u\rangle$ trivial wirkt. Die $X$-Stabilisatorgeneratoren hingegen flippen jeweils einige Bits von $\vert u\rangle$. Insbesondere transformiert für jeden Generator $v$ von $\mathcal{D}_X$ der entsprechende $X$-Stabilisatorgenerator $\vert u\rangle$ in $\vert u\oplus v\rangle$. Indem wir die Projektion $\Pi$ als Mittelwert über die Elemente des Stabilisators charakterisieren (wie in der vorherigen Lektion gesehen), erhalten wir folgende Formel:

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

• Fall 2: $u\notin\mathcal{C}_Z.$ Das bedeutet, dass mindestens eine der den $Z$-Stabilisatorgeneratoren entsprechenden Paritätsprüfungen fehlschlägt, d.h. $\vert u\rangle$ ist Eigenvektor zum Eigenwert $-1$ mindestens eines $Z$-Stabilisatorgenerators. Der Coderaum des CSS-Codes ist der Schnitt der $+1$-Eigenräume der Stabilisatorgeneratoren. Als $-1$-Eigenvektor mindestens eines $Z$-Stabilisatorgenerators ist $\vert u\rangle$ daher orthogonal zum Coderaum:

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

Wenn wir nun über alle $n$-Bit-Zeichenketten $u$ laufen, die Fälle mit $\Pi\vert u\rangle = 0$ verwerfen und die verbleibenden normieren, erhalten wir die zuvor beschriebenen Vektoren — was zeigt, dass sie den Coderaum aufspannen.

Mithilfe der Symmetrie zwischen $X$- und $Z$-Stabilisatorgeneratoren lässt sich der Coderaum auch auf eine ähnliche, aber andere Art beschreiben. Er wird von Vektoren der folgenden Form aufgespannt:

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

Im Wesentlichen wurden $X$ und $Z$ in jedem Auftreten vertauscht — aber wir müssen auch die Standardbasis gegen die $\{\vert+\rangle,\vert-\rangle\}$-Basis tauschen, weshalb die Hadamard-Operationen hinzukommen.

Als Beispiel betrachten wir den 7-Qubit-Steane-Code. Die Paritätsprüfzeichenketten für die $X$- und $Z$-Stabilisatorgeneratoren sind dieselben: $1111000$, $1100110$ und $1010101$. Die Codes $\mathcal{C}_X$ und $\mathcal{C}_Z$ sind daher gleich; beide sind der $[7,4,3]$-Hamming-Code.

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

Auch die dualen Codes $\mathcal{D}_X$ und $\mathcal{D}_Z$ sind daher gleich. Wir haben drei Generatoren und erhalten acht Zeichenketten:

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

Alle diese Zeichenketten sind im $[7,4,3]$-Hamming-Code enthalten, sodass die CSS-Bedingung erfüllt ist: $\mathcal{D}_Z \subseteq \mathcal{C}_X$ bzw. äquivalent $\mathcal{D}_X \subseteq \mathcal{C}_Z$.

Da $\mathcal{D}_X$ die Hälfte aller Zeichenketten in $\mathcal{C}_Z$ enthält, gibt es nur zwei verschiedene Vektoren $\vert u\oplus \mathcal{D}_X\rangle$, die durch Wahl von $u\in\mathcal{C}_Z$ entstehen. Das ist zu erwarten, da der 7-Qubit-Steane-Code einen zweidimensionalen Coderaum hat. Wir können die beiden so erhaltenen Zustände nutzen, um die logischen Zustände $\vert 0\rangle$ und $\vert 1\rangle$ wie folgt zu kodieren:

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

Wie üblich ist diese Wahl nicht zwingend — wir können den Coderaum nach Belieben zur Kodierung von Qubits verwenden. Diese Kodierung ist jedoch konsistent mit dem Beispiel eines Kodierungsschaltkreises für den 7-Qubit-Steane-Code aus der vorherigen Lektion.