Quantencomputing verständlich erklärt — Episode 4

Quantencomputing verständlich erklärt — Episode 4### Was unterscheidet ein Quantenprogramm von einem klassischen Programm?

In Episode 3 haben wir den gemeinsamen Zustand mehrerer Qubits betrachtet.

Drei Qubits besitzen acht mögliche Messergebnisse. Zu jedem dieser Ergebnisse gehört eine Amplitude. Alle acht Amplituden zusammen sind die Koordinaten eines einzigen Quantenzustands.

Aber wie wird mit diesen Koordinaten gerechnet?

Bei einem klassischen Computer ist uns der Ablauf vertraut:

Eingabewerte festlegen
↓
Programm mit Befehlen ausführen
↓
Bitwerte verändern sich
↓
Ergebnis auslesenEin Quantenprogramm besitzt grundsätzlich denselben äußeren Ablauf:

Eingangszustand vorbereiten
↓
Programm mit Quantengattern ausführen
↓
Amplituden des Quantenzustands verändern sich
↓
Qubits messenDer entscheidende Unterschied liegt in dem, was zwischen Eingabe und Ausgabe geschieht.

Ein klassisches Programm arbeitet mit vorhandenen Bitwerten

Wir wählen eine kleine Programmaufgabe: Ein Bit speichert einen Zustand. Ein zweites Bit teilt dem Programm mit, ob dieser Zustand umgeschaltet werden soll.

Nehmen wir zwei klassische Bits:

erstes Bit: Umschaltauftrag = 1
zweites Bit: gespeicherter Zustand = 0Das Programm soll den gespeicherten Zustand umkehren, wenn der Umschaltauftrag den Wert 1 hat:

wenn das erste Bit 1 ist:
kehre das zweite Bit umDamit wird aus der Eingabe 10 die Ausgabe 11: Der Umschaltauftrag bleibt erhalten, der gespeicherte Zustand wechselt von 0 auf 1.

Ein klassisches Programm besteht aus genau solchen Regeln. Es kann vorhandene Bitwerte lesen, abhängig davon einen Befehl auswählen und Bitwerte überschreiben.

Für unsere Eingabe geschieht konkret:

10 → 11Während der Berechnung besitzen beide Bits zu jedem Zeitpunkt einen eindeutigen Wert. Ein Debugger könnte nach dem Befehl anzeigen:

erstes Bit = 1
zweites Bit = 1Die Werte können gelesen, kopiert, gespeichert und für eine Fallunterscheidung verwendet werden.

Das CNOT-Gatter verwendet dieselbe Grundidee

Ein Quantencomputer besitzt ein Gatter mit einer ähnlichen Funktion. Es heißt Controlled NOT, kurz CNOT.

Das erste Qubit dient als Steuer-Qubit. Hat es den Wert 1, wird das zweite Qubit umgekehrt. Bei eindeutigen Eingangszuständen gilt:

EingangAusgang0000010110111110

Bei der Eingabe 10 sieht der Ablauf daher zunächst genauso aus wie im klassischen Beispiel:

|10⟩ → CNOT → |11⟩Messen wir anschließend, erhalten wir sicher 11.

Bis hierhin ist der Unterschied zwischen klassischer und Quantenprogrammierung kaum sichtbar.

Eingabe, Programm und Ausgabe bei Qubits

Auch bei einem Quantencomputer müssen wir Eingabe, Programm und Ausgabe klar trennen.

Für unser Beispiel legen wir den folgenden vollständigen Ablauf fest:

Eingabe: 00
Programm: H auf das erste Qubit, danach CNOT
Ausgabe: beide Qubits messenWarum wählen wir gerade dieses Programm? Ein einzelnes CNOT mit einer eindeutigen Eingabe verhielt sich noch wie die klassische Regel. Die Folge aus H und CNOT ist das einfachste Beispiel, an dem wir sehen können, was ein Quantenprogramm anders macht: Der erste Programmbefehl erzeugt eine Superposition. Der zweite Programmbefehl verändert anschließend diesen gemeinsamen Zustand.

Die Aufgabe des Beispiels besteht nicht darin, eine praktisch nützliche Rechnung auszuführen. Wir verfolgen zunächst nur lückenlos, wie eine festgelegte Eingabe durch zwei Programmbefehle verändert und am Ende gemessen wird.

Die Eingabe

Wir setzen beide Qubits auf 0. Die Eingabe lautet damit:

|00⟩Würden wir sofort messen, erhielten wir mit Sicherheit 00. Die Wahrscheinlichkeit für 00 beträgt also 100 Prozent; die Wahrscheinlichkeiten für 01, 10 und 11 betragen 0 Prozent.

Wie in Episode 3 beschrieben, gehört zu jedem möglichen Messergebnis eine Amplitude. Eine Amplitude von 1 ergibt beim Quadrieren eine Wahrscheinlichkeit von 1 – also 100 Prozent. Eine Amplitude von 0 ergibt eine Wahrscheinlichkeit von 0 Prozent.

Deshalb besitzt der Zustand 00 diese vier Amplituden:

Mögliches ErgebnisAmplitude001010100110

Der erste Programmbefehl: H

Nun beginnt das Programm. Sein erster Befehl ist das H-Gatter auf dem ersten Qubit.

Wie das bereits erklärte CNOT-Gatter besitzt auch das H-Gatter eine festgelegte Wirkung. CNOT ordnet beispielsweise den Eingang 10 dem Ausgang 11 zu. Das H-Gatter verändert die Amplituden einer eingegebenen 0 nach folgender Regel:

Amplitude für 0: 1 → +0,707
Amplitude für 1: 0 → +0,707Das H-Gatter verteilt die zuvor vollständig bei 0 liegende Amplitude damit gleichmäßig auf 0 und 1. Die Superposition ist also keine zusätzliche Eingabe. Sie ist der Zwischenstand, den der erste Programmbefehl aus der Eingabe 00 erzeugt.

Das H-Gatter wirkt nur auf das erste Qubit. Das zweite Qubit bleibt deshalb unverändert bei 0.

Dadurch kann der gemeinsame Zustand anschließend als 00 oder als 10 gemessen werden. Beide Möglichkeiten besitzen nun die Amplitude +0,707:

Mögliches ErgebnisAmplitude00+0,70701010+0,707110

Der Zustand lässt sich verkürzt so schreiben:

0,707|00⟩ + 0,707|10⟩Würden wir jetzt messen, erhielten wir zu ungefähr 50 Prozent 00 und zu ungefähr 50 Prozent 10.

Wir messen aber noch nicht, denn das Programm ist noch nicht beendet. Als zweiten Programmbefehl wenden wir das CNOT-Gatter an.

Der zweite Programmbefehl: CNOT

Eine klassische Formulierung des CNOT-Gatters könnte lauten:

wenn das erste Bit 1 ist:
kehre das zweite Bit umBeim Quantencomputer darf das Gatter jedoch nicht zuerst nachsehen, ob das erste Qubit 0 oder 1 ist. Eine solche Messung würde die Superposition beenden.

Das CNOT-Gatter wendet stattdessen seine feste Transformationsregel direkt auf den gesamten Quantenzustand an:

00 bleibt 00
10 wird 11Damit werden die vorhandenen Amplituden neu zugeordnet:

Mögliches ErgebnisVor CNOTNach CNOT00+0,707+0,707010010+0,7070110+0,707

Nach dem CNOT-Gatter lautet der Zustand:

0,707|00⟩ + 0,707|11⟩Das Gatter hat keine Fallunterscheidung nach einer Messung vorgenommen. Es hat die vier Koordinaten des gemeinsamen Zustands nach einer festen Regel transformiert.

Was liefert die Messung?

Aus den Amplituden ergeben sich die Messwahrscheinlichkeiten:

00: 0,707² ≈ 50 %
01: 0² = 0 %
10: 0² = 0 %
11: 0,707² ≈ 50 %Bei einer einzelnen Messung erhalten wir daher entweder:

00oder:

11Wir erhalten niemals 01 oder 10.

Bei der Messung erhalten wir entweder 00 oder 11. Deshalb haben die beiden gemessenen Bits immer denselben Wert: entweder sind beide 0 oder beide 1.

Das erste und das zweite Qubit können nicht mehr unabhängig voneinander beschrieben werden. Der gemeinsame Zustand enthält nur noch 00 und 11. Deshalb liefert die Messung entweder zwei Nullen oder zwei Einsen — niemals unterschiedliche Werte. Einen solchen gemeinsamen Quantenzustand nennt man verschränkt.

Diesen Begriff untersuchen wir in Episode 5 genauer. Für den Moment ist nur wichtig, wie er entstanden ist:

bekannter Eingang 00
↓
H verändert die Amplituden
↓
CNOT ordnet die Amplituden neu zu
↓
Messung liefert 00 oder 11Keines der Gatter kannte oder suchte ein „richtiges“ Ergebnis.

Das Quantenprogramm ist eindeutig — das einzelne Messergebnis nicht

Die Gatterfolge ist vollständig festgelegt:

|00⟩
↓
H auf das erste Qubit
↓
CNOT
↓
messenBei jeder idealen Ausführung erzeugen H und CNOT denselben Quantenzustand:

0,707|00⟩ + 0,707|11⟩Das einzelne Messergebnis kann trotzdem 00 oder 11 sein.

Damit sind zwei Ebenen sauber getrennt:

• Das Programm bestimmt den Quantenzustand eindeutig.
• Die Amplituden dieses Zustands bestimmen die Wahrscheinlichkeiten der Messergebnisse. Quantenprogrammierung bedeutet also nicht, dem Computer zu sagen, welches Ergebnis er bevorzugen soll. Man legt eine Folge von Transformationen fest und berechnet, welchen Zustand diese Folge erzeugt.

Klassische Befehle dürfen Information löschen

Ein klassisches Programm kann ohne Weiteres schreiben:

zweites Bit = 0Dabei kann der vorherige Wert des zweiten Bits verloren gehen:

0 → 0
1 → 0Aus dem Ergebnis 0 lässt sich anschließend nicht mehr erkennen, ob das zweite Bit vorher 0 oder 1 war.

Ein Quantengatter darf den Zustand nicht auf diese Weise zusammenstauchen. Unterschiedliche Eingangszustände müssen unterscheidbare Ausgangszustände behalten.

Deshalb sind Quantengatter grundsätzlich umkehrbar.

Das sehen wir bei den bisher verwendeten Gattern:

H gefolgt von H → ursprünglicher Zustand
CNOT gefolgt von CNOT → ursprünglicher ZustandWenden wir in unserem Beispiel ein zweites CNOT und danach ein zweites H-Gatter an, gelangen wir wieder zum Anfang:

|00⟩
↓ H
0,707|00⟩ + 0,707|10⟩
↓ CNOT
0,707|00⟩ + 0,707|11⟩
↓ CNOT
0,707|00⟩ + 0,707|10⟩
↓ H
|00⟩Die Messung ist davon zu unterscheiden. Sie erzeugt ein klassisches Ergebnis und der vorherige Quantenzustand steht danach nicht mehr für die Umkehrung zur Verfügung.

Ein Quantenprogramm kann nicht wie ein klassisches Programm beobachtet werden

Bei einem klassischen Programm können wir an vielen Stellen Protokollausgaben oder Haltepunkte einfügen:

zeige erstes Bit
zeige zweites BitAnschließend kann das Programm mit denselben Bitwerten weiterarbeiten.

Bei einem Quantenprogramm können wir die Amplituden eines realen Qubit-Zustands nicht einfach ausgeben. Eine Messung liefert nur eine Bitfolge und verändert dabei den Zustand.

Darum wird ein Quantenprogramm typischerweise mehrfach ausgeführt:

Eingang erneut vorbereiten
↓
dieselben Gatter erneut ausführen
↓
erneut messenAus den Häufigkeiten der Messergebnisse können wir auf die Wahrscheinlichkeitsverteilung schließen. Die vollständige Liste der Amplituden eines unbekannten Zustands erhalten wir jedoch nicht durch eine einzelne Ausführung.

Klassischer Programmcode und Quantenschaltung arbeiten zusammen

Ein Quantencomputer ersetzt den klassischen Computer nicht. Ein reales Quantenprogramm besteht aus beiden Teilen.

Der klassische Teil:

• wählt die Eingabedaten aus,
• stellt die Quantenschaltung zusammen,
• startet viele Ausführungen,
• sammelt die Messergebnisse,

• wertet sie aus.
  Der Quantenteil:

• bereitet Qubits vor,

• führt die festgelegten Quantengatter aus,

• erzeugt den gemeinsamen Quantenzustand,

• liefert bei der Messung klassische Bits zurück.
  Ein Quantencomputer ist deshalb eher ein besonderer Rechenbaustein neben einer klassischen CPU als deren vollständiger Ersatz.

Woher kann ein Rechenvorteil kommen?

Unser Beispiel mit H und CNOT ist noch kein schneller Algorithmus. Eine klassische CPU kann dieselbe Verteilung sehr einfach erzeugen.

Das Beispiel zeigt lediglich den entscheidenden Unterschied der Programmierung:

*Ein klassisches Programm verändert konkrete Bitwerte. Ein Quantenprogramm verändert die Amplituden eines gemeinsamen Quantenzustands.*Ein möglicher Rechenvorteil entsteht erst, wenn eine speziell entwickelte Gatterfolge eine für das Problem nützliche Eigenschaft in den Amplituden abbildet und durch Interferenz messbar macht.

Die Gatter filtern dabei nicht auf magische Weise das „richtige“ Ergebnis heraus. Jedes Gatter führt dieselbe festgelegte Transformation aus — unabhängig davon, welches Ergebnis der Programmierer gern erhalten würde.

Nur für bestimmte Probleme kennt man Gatterfolgen, bei denen dieses Vorgehen günstiger ist als ein klassischer Algorithmus.

Klassische und Quantenprogrammierung im Vergleich

Klassisches ProgrammQuantenprogrammarbeitet mit konkreten Bitwertenarbeitet vor der Messung mit AmplitudenBefehle verändern VariablenwerteGatter transformieren den QuantenzustandZwischenwerte können ausgelesen werdeneine Messung verändert den ZustandWerte können beliebig kopiert werdenein unbekannter Quantenzustand kann nicht einfach kopiert werdenBefehle dürfen Information löschenQuantengatter sind grundsätzlich umkehrbarFallunterscheidungen lesen Wertekontrollierte Gatter wirken ohne vorherige MessungAusgabe ist gewöhnlich direkt bestimmtMessungen können probabilistische Ergebnisse liefern

Mit einem Missverständnis aufräumen

Missverständnis:* Ein Quantenprogramm ist ein gewöhnliches Programm, das alle möglichen Eingabewerte gleichzeitig ausführt.*Tatsächlich arbeitet ein Quantenprogramm nicht mit vielen getrennten klassischen Rechenläufen. Seine Gatter transformieren die Amplituden eines einzigen gemeinsamen Quantenzustands. Eine Messung liefert anschließend nur ein klassisches Ergebnis.

Was wir jetzt wissen

• Ein klassisches Programm verändert konkrete Bitwerte.
• Ein Quantenprogramm verändert die Amplituden eines gemeinsamen Quantenzustands.
• Ein Quantengatter misst seine Eingabe nicht, bevor es den Zustand verändert.
• Kontrollierte Gatter ersetzen keine klassische Fallunterscheidung, sondern transformieren den gesamten Zustand.
• Quantengatter sind grundsätzlich umkehrbar.
• Zwischenmessungen können eine Superposition beenden.
• Ein reales Quantenprogramm benötigt weiterhin einen klassischen Computer zur Steuerung und Auswertung. Ein Rechenvorteil entsteht nicht automatisch durch eine Superposition, sondern nur durch einen passenden Quantenalgorithmus.In Episode 5 sehen wir uns den Zustand 0,707|00⟩ + 0,707|11⟩ genauer an. Dann klären wir, was Verschränkung bedeutet – und was sie nicht bedeutet.