Wiederholungscodes

Wir beginnen die Lektion mit einer Diskussion der Wiederholungscodes. Wiederholungscodes schützen Quanteninformation nicht gegen jeden Fehlertyp, der auf Qubits auftreten kann, aber sie bilden die Grundlage für den 9-Qubit-Shor-Code, den wir in der nächsten Lektion kennenlernen werden, und sind auch nützlich, um die Grundlagen der Fehlerkorrektur zu erläutern.

Klassische Kodierung und Dekodierung

Wiederholungscodes sind äußerst einfache Beispiele für fehlerkorrigierende Codes. Die Idee ist, dass wir Bits gegen Fehler schützen können, indem wir jedes Bit einfach eine feste Anzahl von Malen wiederholen.

Betrachten wir zunächst den 3-Bit-Wiederholungscode, und zwar erst einmal nur im Kontext klassischer Information. Dieser Code kodiert ein Bit in drei Bits, indem das Bit dreimal wiederholt wird, so dass $0$ als $000$ und $1$ als $111$ kodiert wird.

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

Wenn nichts schiefgeht, können wir die zwei Möglichkeiten für das ursprüngliche Bit offensichtlich anhand ihrer Kodierungen unterscheiden. Der Punkt ist, dass wir, wenn ein Fehler auftrat und eines der drei Bits umgekippt wurde (also eine 0 zu einer 1 wurde oder umgekehrt), dennoch herausfinden können, welches das ursprüngliche Bit war – indem wir feststellen, welcher der beiden Binärwerte zweimal vorkommt. Äquivalent dazu können wir dekodieren, indem wir den Mehrheitswert berechnen (also den Binärwert, der am häufigsten vorkommt).

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

Natürlich funktioniert das Dekodieren nicht korrekt, wenn 2 oder 3 Bits der Kodierung umkippen – dann wird das falsche Bit wiederhergestellt. Aber wenn höchstens 1 der 3 Bits umkippt, ist die Dekodierung korrekt. Das ist eine typische Eigenschaft von fehlerkorrigierenden Codes im Allgemeinen: Sie können die Korrektur von Fehlern ermöglichen, aber nur, wenn es nicht zu viele davon sind.

Rauschreduzierung für den binären symmetrischen Kanal

Als Beispiel für eine Situation, in der die Fehlerwahrscheinlichkeit durch einen Wiederholungscode verringert werden kann, nehmen wir an, unser Ziel ist es, ein einzelnes Bit an einen hypothetischen Empfänger zu übermitteln, und wir können Bits durch einen sogenannten binären symmetrischen Kanal übertragen, der jedes gesendete Bit unabhängig mit einer Wahrscheinlichkeit $p$ umkippt. Das heißt, mit Wahrscheinlichkeit $1-p$ empfängt der Empfänger das Bit, das durch den Kanal gesendet wurde, aber mit Wahrscheinlichkeit $p$ kippt das Bit um, und der Empfänger erhält den entgegengesetzten Bitwert.

Wenn wir also den 3-Bit-Wiederholungscode nicht verwenden und das gewünschte Bit einfach durch den Kanal senden, empfängt der Empfänger das falsche Bit mit Wahrscheinlichkeit $p$. Wenn wir hingegen zuerst das zu sendende Bit mit dem 3-Bit-Wiederholungscode kodieren und dann jedes der drei Bits der Kodierung durch den Kanal senden, kippt jedes davon unabhängig mit Wahrscheinlichkeit $p$ um. Die Wahrscheinlichkeit eines Bit-Flips ist jetzt höher, weil drei Bits statt einem umkippen könnten – aber wenn höchstens eines der Bits umkippt, dekodiert der Empfänger korrekt. Ein Fehler bleibt nach der Dekodierung also nur bestehen, wenn zwei oder mehr Bits während der Übertragung umkippen.

Die Wahrscheinlichkeit, dass zwei Bits während der Übertragung umkippen, beträgt $3p^2(1-p)$ – das ist $p^2(1-p)$ für jede der drei Möglichkeiten, welches Bit nicht umkippt –, während die Wahrscheinlichkeit, dass alle drei Bits umkippen, $p^3$ beträgt. Die Gesamtwahrscheinlichkeit von zwei oder drei Bit-Flips beträgt daher

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

Für Werte von $p$ kleiner als ein Halb führt dies zu einer Verringerung der Wahrscheinlichkeit, dass der Empfänger das falsche Bit erhält. In diesem Fall besteht weiterhin eine Fehlerwahrscheinlichkeit, aber der Code verringert die Wahrscheinlichkeit. (Für Werte von $p$ größer als ein Halb hingegen erhöht der Code tatsächlich die Wahrscheinlichkeit, dass der Empfänger das falsche Bit erhält.)

Qubits kodieren

Der 3-Bit-Wiederholungscode ist ein klassischer fehlerkorrigierender Code, aber wir können überlegen, was passiert, wenn wir ihn zum Schutz von Qubits gegen Fehler einsetzen. Wie wir sehen werden, ist er kein besonders beeindruckender Quanten-Fehlerkorrekturcode, da er einige Fehler tatsächlich wahrscheinlicher macht. Er ist jedoch der erste Schritt zum Shor-Code und wird uns aus pädagogischer Sicht gute Dienste leisten.

Wenn wir vom 3-Bit-Wiederholungscode für Qubits sprechen, meinen wir eine Kodierung eines Qubits, bei der Standardbasiszustände dreimal wiederholt werden, sodass ein Ein-Qubit-Zustandsvektor wie folgt kodiert wird.

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

Diese Kodierung lässt sich leicht mit folgendem Quantenschaltkreis implementieren, der zwei initialisierte Hilfsqubits und zwei CNOT-Gates verwendet.

Zu beachten ist insbesondere, dass diese Kodierung nicht dasselbe ist wie das dreimalige Wiederholen des Quantenzustands, also eine Kodierung eines gegebenen Qubit-Zustandsvektors als $\vert\psi\rangle \mapsto \vert\psi\rangle\vert\psi\rangle\vert\psi\rangle$. Eine solche Kodierung kann für einen unbekannten Quantenzustand $\vert\psi\rangle$ aufgrund des No-Cloning-Theorems nicht implementiert werden.

Bit-Flip-Fehler

Nehmen wir nun an, dass nach der Kodierung ein Fehler auftritt. Konkret nehmen wir an, dass ein $X$-Gate – also ein Bit-Flip – auf einem der Qubits auftritt. Wenn beispielsweise das mittlere Qubit einen Bit-Flip erfährt, wird der Zustand der drei Qubits in diesen Zustand transformiert:

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

Das ist natürlich nicht der einzige Fehler, der auftreten könnte – und es ist auch berechtigt, die Annahme zu hinterfragen, dass ein Fehler die Form einer perfekten, unitären Operation annimmt. Wir werden auf diese Fragen im letzten Abschnitt der Lektion zurückkommen; vorerst können wir einen solchen Fehler als einen möglichen Fehlertyp betrachten (wenn auch einen grundlegend wichtigen).

Aus dem mathematischen Ausdruck für den obigen Zustand ist klar ersichtlich, dass das mittlere Bit dasjenige ist, das innerhalb jedes Kets verschieden ist. Aber angenommen, wir hätten die drei Qubits in unserem Besitz und würden ihren Zustand nicht kennen. Wenn wir vermuten, dass ein Bit-Flip stattgefunden haben könnte, wäre eine Möglichkeit zur Überprüfung die Durchführung einer Standardbasismessung, die in dem vorliegenden Fall $010$ oder $101$ mit den Wahrscheinlichkeiten $\vert\alpha\vert^2$ bzw. $\vert\beta\vert^2$ ergeben würde. In beiden Fällen würden wir schlussfolgern, dass das mittlere Bit umgekippt ist – aber leider würden wir den ursprünglichen Quantenzustand $\alpha\vert 0\rangle + \beta \vert 1\rangle$ verlieren. Das ist genau der Zustand, den wir schützen wollen, daher ist die Messung in der Standardbasis keine zufriedenstellende Option.

Was wir stattdessen tun können, ist den folgenden Quantenschaltkreis zu verwenden, in den der kodierte Zustand in die oberen drei Qubits eingegeben wird. Dieser Schaltkreis misst zerstörungsfrei die Parität der Standardbasiszustände der obersten zwei Qubits sowie der untersten zwei Qubits der Drei-Qubit-Kodierung.

Unter der Annahme, dass höchstens ein Bit umgekippt ist, kann man aus den Messergebnissen leicht den Ort des Bit-Flips (oder das Fehlen eines solchen) ableiten. Wie die folgenden vier Schaltkreisdiagramme zeigen, gibt das Messergebnis $00$ an, dass kein Bit-Flip stattgefunden hat, während die drei anderen Möglichkeiten anzeigen, welches Qubit einen Bit-Flip erfahren hat.

Entscheidend ist, dass der Zustand der oberen drei Qubits in keinem der Fälle kollabiert, was es uns ermöglicht, einen Bit-Flip-Fehler zu korrigieren – falls einer aufgetreten ist –, indem wir einfach denselben Bit-Flip erneut mit einem $X$-Gate anwenden. Die folgende Tabelle fasst die Zustände zusammen, die wir bei höchstens einem Bit-Flip erhalten, die Messergebnisse (die im Kontext der Fehlerkorrektur als Syndrom bezeichnet werden) und die zur Rückkehr zur ursprünglichen Kodierung benötigte Korrektur.

Zustand	Syndrom	Korrektur
$\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}$

Wir betrachten hier nur die Möglichkeit, dass höchstens ein Bit-Flip aufgetreten ist. Das würde nicht korrekt funktionieren, wenn zwei oder drei Bit-Flips aufgetreten wären, und wir haben auch keine anderen möglichen Fehler außer Bit-Flips betrachtet.

Phasen-Flip-Fehler

Im Quantenbereich sind Bit-Flip-Fehler nicht die einzigen Fehler, um die wir uns sorgen müssen. Wir müssen uns zum Beispiel auch um Phasen-Flip-Fehler kümmern, die durch $Z$-Gates beschrieben werden. Ähnlich wie Bit-Flip-Fehler können wir Phasen-Flip-Fehler als eine weitere mögliche Fehlerart betrachten, die ein Qubit beeinflussen kann.

Wie wir im letzten Abschnitt der Lektion über die sogenannte Diskretisierung von Fehlern für quantenfehlerkorrigierende Codes sehen werden, ist der Fokus auf Bit-Flip-Fehler und Phasen-Flip-Fehler jedoch gut begründet. Die Fähigkeit, einen Bit-Flip-Fehler, einen Phasen-Flip-Fehler oder beide gleichzeitig zu korrigieren, impliziert automatisch die Fähigkeit, einen beliebigen Quantenfehler auf einem einzelnen Qubit zu korrigieren.

Leider schützt der 3-Bit-Wiederholungscode überhaupt nicht gegen Phasen-Flips. Angenommen, ein Qubit-Zustand $\alpha\vert 0\rangle + \beta\vert 1\rangle$ wurde mit dem 3-Bit-Wiederholungscode kodiert, und auf dem mittleren Qubit tritt ein Phasen-Flip-Fehler auf. Dies ergibt den Zustand

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

was genau der Zustand ist, den wir durch Kodierung des Qubit-Zustands $\alpha\vert 0\rangle - \beta\vert 1\rangle$ erhalten hätten. Tatsächlich hat ein Phasen-Flip-Fehler auf einem beliebigen der drei Qubits der Kodierung denselben Effekt, was einem Phasen-Flip-Fehler auf dem ursprünglichen Qubit vor der Kodierung entspricht. Unter der Annahme, dass der ursprüngliche Quantenzustand unbekannt ist, gibt es daher keine Möglichkeit festzustellen, dass ein Fehler aufgetreten ist, da der resultierende Zustand eine vollständig gültige Kodierung eines anderen Qubit-Zustands ist. Insbesondere liefert der Fehlererkennungsschaltkreis von vorhin, angewendet auf den Zustand $\alpha \vert 000\rangle - \beta \vert 111\rangle$, mit Sicherheit das Syndrom $00$, was fälschlicherweise nahelegt, dass keine Fehler aufgetreten sind.

Dabei gibt es nun drei Qubits statt einem, die potenziell Phasen-Flip-Fehler erfahren könnten. In einer Situation, in der Phasen-Flip-Fehler unabhängig auf jedem Qubit mit einer gewissen Wahrscheinlichkeit $p > 0$ auftreten (ähnlich wie bei einem binären symmetrischen Kanal, jedoch für Phasen-Flips statt Bit-Flips), erhöht dieser Code tatsächlich die Wahrscheinlichkeit eines Phasen-Flip-Fehlers nach der Dekodierung für kleine Werte von $p$. Genauer gesagt erhalten wir nach der Dekodierung einen Phasen-Flip-Fehler auf dem ursprünglichen Qubit, wenn eine ungerade Anzahl von Phasen-Flip-Fehlern auf den drei Qubits der Kodierung aufgetreten ist, was mit Wahrscheinlichkeit

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

Dieser Wert ist größer als $p$, wenn $0<p<1/2$ gilt, sodass der Code die Wahrscheinlichkeit eines Phasen-Flip-Fehlers für Werte von $p$ in diesem Bereich erhöht.

Modifizierter Wiederholungscode für Phasen-Flip-Fehler

Wir haben festgestellt, dass der 3-Bit-Wiederholungscode Phasen-Flip-Fehler völlig ignoriert und daher wenig hilfreich für den Umgang mit dieser Art von Fehlern zu sein scheint. Wir können den 3-Bit-Wiederholungscode jedoch auf einfache Weise so modifizieren, dass er Phasen-Flip-Fehler erkennt. Diese Modifikation macht den Code blind für Bit-Flip-Fehler – aber wie wir im nächsten Abschnitt sehen werden, können wir den 3-Bit-Wiederholungscode mit dieser modifizierten Version kombinieren, um den Shor-Code zu erhalten, der sowohl Bit-Flip- als auch Phasen-Flip-Fehler korrigieren kann.

Hier ist die modifizierte Version des obigen Kodierschaltkreises, die nun Phasen-Flip-Fehler erkennen kann. Die Modifikation ist sehr einfach: Wir wenden nach den beiden CNOT-Gates auf jedes Qubit ein Hadamard-Gate an.

Ein Hadamard-Gate wandelt einen $\vert 0\rangle$-Zustand in einen $\vert + \rangle$-Zustand und einen $\vert 1\rangle$-Zustand in einen $\vert - \rangle$-Zustand um, sodass der Gesamteffekt darin besteht, dass der Ein-Qubit-Zustand $\alpha\vert 0\rangle + \beta \vert 1\rangle$ kodiert wird als

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

wobei $\vert {+}\,{+}\,{+} \rangle = \vert + \rangle \otimes \vert + \rangle \otimes\vert + \rangle$ und $\vert {-}\,{-}\,{-} \rangle = \vert - \rangle \otimes \vert - \rangle \otimes\vert - \rangle$.

Ein Phasen-Flip-Fehler, also ein $Z$-Gate, wechselt zwischen den Zuständen $\vert + \rangle$ und $\vert - \rangle$, daher ist diese Kodierung nützlich zur Erkennung (und Korrektur) von Phasen-Flip-Fehlern. Konkret kann der Fehlererkennungsschaltkreis von früher wie folgt modifiziert werden.

Um es in Worten auszudrücken: Wir nehmen den Schaltkreis von früher und fügen einfach am Anfang und am Ende Hadamard-Gates auf den oberen drei Qubits hinzu. Die Idee ist, dass die ersten drei Hadamard-Gates $\vert + \rangle$- und $\vert - \rangle$-Zustände zurück in $\vert 0\rangle$- und $\vert 1\rangle$-Zustände umwandeln, dann finden dieselben Paritätsprüfungen wie zuvor statt, und dann wandelt die zweite Schicht von Hadamard-Gates den Zustand zurück in $\vert + \rangle$- und $\vert - \rangle$-Zustände um, sodass wir unsere Kodierung wiederherstellen. Zur späteren Referenz stellen wir fest, dass sich dieser Schaltkreis zur Erkennung von Phasen-Flips wie folgt vereinfachen lässt.

Beachte, dass die Rolle der Ancilla in den CNOTs im Vergleich zur Bit-Flip-Prüfung geändert wurde. Dies hängt mit dem Phase-Kickback-Phänomen zusammen, das im Kurs zu den Grundlagen der Quantenalgorithmen behandelt wird.

Die folgenden vier Schaltkreisdiagramme beschreiben, wie unsere modifizierte Version des 3-Bit-Wiederholungscodes, einschließlich Kodierungs- und Fehlererkennungsschritt, funktioniert, wenn höchstens ein Phasen-Flip-Fehler auftritt. Das Verhalten ist ähnlich wie beim gewöhnlichen 3-Bit-Wiederholungscode für Bit-Flips.

Hier ist eine analoge Tabelle zur obigen, diesmal unter Berücksichtigung der Möglichkeit von höchstens einem Phasen-Flip-Fehler.

Zustand	Syndrom	Korrektur
$\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}$

Leider kann diese modifizierte Version des 3-Bit-Wiederholungscodes nun keine Bit-Flip-Fehler mehr korrigieren. Aber es ist noch nicht alles verloren. Wie zuvor angedeutet, werden wir in der Lage sein, die beiden soeben betrachteten Codes zu einem einzigen Code zu kombinieren – dem 9-Qubit-Shor-Code –, der sowohl Bit-Flip- als auch Phasen-Flip-Fehler und tatsächlich jeden Fehler auf einem einzelnen Qubit korrigieren kann.