Quantencomputing verständlich erklärt — Episode 6

Quantencomputing verständlich erklärt — Episode 6### Wie der Grover-Algorithmus eine Listenposition findet

In Episode 5 haben wir gesehen, wie sich Amplituden verstärken oder auslöschen können.

Der Grover-Algorithmus nutzt dieses Prinzip für eine konkrete Aufgabe:

*Finde in einer ungeordneten Liste einen bestimmten Eintrag.*Als Beispiel verwenden wir nur vier Einträge, damit sich jeder Schritt vollständig nachvollziehen lässt:

Position Kundennummer
00 5832
01 1947
10 4711
11 8264Der gesuchte Eintrag ist der mit der Kundennummer 4711 an Position 10.

Die gemeinsame Grundlage

Ein klassischer Computer und ein Quantencomputer erhalten für diese Aufgabe dieselben Daten:

• die Liste mit den vier Kundennummern
• die gesuchte Kundennummer 4711 Auch die Positionen werden in beiden Fällen gleich dargestellt. Für vier Positionen genügen zwei Bits beziehungsweise zwei Qubits:

00
01
10
11Die Bedeutung ist ebenfalls dieselbe:

00 → 1. Listeneintrag
01 → 2. Listeneintrag
10 → 3. Listeneintrag
11 → 4. ListeneintragBits oder Qubits stellen hier also die Position eines Eintrags dar. Die Kundennummer selbst steht in der Liste.

Auch die Prüfung ist bei beiden Computerarten dieselbe:

Kundennummer an dieser Position = 4711?Der Unterschied liegt darin, wie die Positionen durchlaufen werden.

So arbeitet das klassische Suchprogramm

Das klassische Programm schreibt zunächst 00 in sein Positionsregister. Während der Suche setzt das Programm diese beiden Bits nacheinander auf 00, 01, 10 und 11, liest die Kundennummer an der jeweiligen Position und vergleicht sie mit 4711.

Position 00 → 5832 = 4711? nein
Position 01 → 1947 = 4711? nein
Position 10 → 4711 = 4711? ja
Position 11 → 8264 = 4711? neinDa die Übereinstimmung bereits an Position 10 besteht, erübrigt sich der letzte Schritt. Daher bricht das Programm hier ab und liefert die Position 10 als Ergebnis.

Im ungünstigsten Fall müsste das Programm aber alle vier Positionen nacheinander prüfen.

Die Daten liegen im Speicher

Wie beim klassischen Computer liegen die Liste und die gesuchte Kundennummer im Speicher:

00 → 5832
01 → 1947
10 → 4711
11 → 8264Beim Quantencomputer übernimmt eine Vergleichsschaltung dieselbe Prüfung wie das klassische Programm:

Ist die Kundennummer an der angegebenen Position gleich 4711?Damit sind Eingabe und Aufgabe vollständig festgelegt. Noch hat der Quantencomputer aber nichts gesucht.

Der Unterschied beginnt beim Positionsregister

Beim Quantenprogramm wird die Position durch zwei Qubits dargestellt.

Wir nennen sie Qubit 1 und Qubit 2.

Am Anfang werden beide Qubits auf 0 gesetzt:

Qubit 1: 0
Qubit 2: 0Würden wir die beiden Qubits jetzt messen, lautete das gemeinsame Messergebnis sicher:

00Das Messergebnis 00 bezeichnet in unserer Tabelle die Position des ersten Eintrags.

Bis zu diesem Punkt besteht noch kein wesentlicher Unterschied: Bei beiden Programmen lautet die Position 00.

Der Unterschied entsteht erst durch die folgenden H-Gatter.

Hier müssen wir zwei Dinge auseinanderhalten:

• Der Quantencomputer besitzt weiterhin nur zwei Qubits.
• 00, 01, 10 und 11 sind die vier möglichen gemeinsamen Messergebnisse dieser zwei Qubits. Diese vier Messergebnisse entsprechen den vier möglichen Positionen in unserer Liste.

Das erste H-Gatter

Zuerst wenden wir ein H-Gatter auf Qubit 1 an. Das H-Gatter erzeugt für dieses Qubit eine Amplitude für 0 und eine Amplitude für 1.

Qubit 2 bleibt unverändert bei 0.

Deshalb besitzt der gemeinsame Zustand jetzt Amplituden für zwei mögliche Messergebnisse:

Messergebnis Position in der Liste Amplitude
00 1. Eintrag +0,707
10 3. Eintrag +0,707Die Messergebnisse 01 und 11 können noch nicht auftreten, weil Qubit 2 weiterhin eindeutig 0 ist.

Das zweite H-Gatter

Nun wenden wir ein H-Gatter auf Qubit 2 an.

Beim bisherigen Bestandteil 00 erhält Qubit 2 eine Amplitude für 0 und für 1. Dadurch entstehen die möglichen Messergebnisse:

00 und 01Beim bisherigen Bestandteil 10 geschieht dasselbe. Dadurch entstehen:

10 und 11Es wurden keine weiteren Qubits erzeugt. Der Zustand derselben zwei Qubits besitzt jetzt lediglich eine Amplitude für jedes ihrer vier möglichen gemeinsamen Messergebnisse.

Jedes der vier möglichen Messergebnisse entspricht damit einer Position in der Liste:

Messergebnis Position Amplitude Wahrscheinlichkeit
00 1. Eintrag +0,5 25 %
01 2. Eintrag +0,5 25 %
10 3. Eintrag +0,5 25 %
11 4. Eintrag +0,5 25 %Warum beträgt jede Amplitude 0,5?

Für jedes der beiden Qubits erzeugt das H-Gatter die Amplituden 0,707 für 0 und 1. Für ein gemeinsames Messergebnis werden die beiden zugehörigen Amplituden multipliziert:

0,707 × 0,707 ≈ 0,5Die Messwahrscheinlichkeit jedes gemeinsamen Messergebnisses ergibt sich aus dem Quadrat seiner Amplitude:

0,5² = 0,25 = 25 %Würden wir jetzt messen, erhielten wir 00, 01, 10 oder 11. Damit hätten wir eine der vier Positionen ausgewählt. Jede Position wäre gleich wahrscheinlich. Das wäre noch keine Suche.

Ein Vergleichsdurchgang erfasst alle Positionen

Beim klassischen Programm wird die Vergleichsoperation mehrmals aufgerufen. Sie erhält bei jedem Aufruf genau eine Position:

1. Aufruf: Position 00
2. Aufruf: Position 01
3. Aufruf: Position 10Beim Quantenprogramm ist die Vergleichsschaltung mit den beiden Qubits verbunden, die gemeinsam die Position darstellen.

Nach den beiden H-Gattern besitzen diese Qubits keinen einzelnen Positionswert. Ihr gemeinsamer Zustand enthält eine Amplitude für jede der vier möglichen Positionen:

Amplitude für 00
Amplitude für 01
Amplitude für 10
Amplitude für 11Die Vergleichsschaltung wird einmal auf die beiden Qubits und damit auf ihren gesamten gemeinsamen Zustand angewendet. Dadurch prüft sie in einem Durchgang alle vier möglichen Positionen:

00 → 5832 ist ungleich 4711
01 → 1947 ist ungleich 4711
10 → 4711 ist gleich 4711
11 → 8264 ist ungleich 4711Das bedeutet nicht, dass die Schaltung vier klassische Ergebnisse ausgibt. Wir erhalten also keine Liste mit dreimal „nein“ und einmal „ja“.

Stattdessen verändert die Schaltung den gemeinsamen Quantenzustand. Bei einer Übereinstimmung — hier bei Position 10 – kehrt sie das Vorzeichen der zugehörigen Amplitude um. Bei den anderen Positionen verändert sie nichts:

Position Kundennummer Vorher Nachher
00 5832 +0,5 +0,5
01 1947 +0,5 +0,5
10 4711 +0,5 −0,5
11 8264 +0,5 +0,5Der gesamte Vergleich hat damit nur einen Durchgang benötigt. Sein Ergebnis ist jedoch noch nicht die gesuchte Position, sondern das veränderte Amplitudenmuster:

+0,5 +0,5 −0,5 +0,5Dieses Muster ist der Grund, weshalb Quanteninterferenz benötigt wird. Erst der nächste Programmschritt macht die passende Position wahrscheinlicher.

Warum wird das Vorzeichen verändert?

Eine Messung unmittelbar nach dem Vergleich würde noch nicht helfen. Für Position 10 gilt weiterhin:

(−0,5)² = 0,25 = 25 %Das Vorzeichen ändert die Messwahrscheinlichkeit zunächst nicht. Es erzeugt aber einen Unterschied, den eine weitere Quantenoperation nutzen kann.

Die vier Amplituden lauten jetzt:

+0,5 +0,5 −0,5 +0,5Nur die Amplitude der passenden Position zeigt in die entgegengesetzte Richtung. Genau dieser Unterschied wird im nächsten Schritt in eine höhere Messwahrscheinlichkeit umgewandelt.

Die Amplituden werden an ihrem Mittelwert gespiegelt

Zuerst bestimmen wir den Mittelwert der vier Amplituden:

(+0,5 + 0,5 − 0,5 + 0,5) ÷ 4
= 1 ÷ 4
= 0,25Eine festgelegte Folge von Quantengattern spiegelt anschließend jede Amplitude an diesem Mittelwert.

Die Rechenregel dieser Operation lautet:

neue Amplitude = 2 × Mittelwert − alte AmplitudeDa der Mittelwert 0,25 beträgt, wird daraus:

neue Amplitude = 0,5 − alte AmplitudeFür unsere vier Positionen ergibt sich:

Position 00: 0,5 − (+0,5) = 0
Position 01: 0,5 − (+0,5) = 0
Position 10: 0,5 − (−0,5) = 1
Position 11: 0,5 − (+0,5) = 0Position Vorher Nachher Wahrscheinlichkeit
00 +0,5 0 0 %
01 +0,5 0 0 %
10 −0,5 1 100 %
11 +0,5 0 0 %Die Spiegelung wird Diffusionsoperator genannt. Die Vergleichsschaltung und der Diffusionsoperator bilden zusammen eine Runde des Grover-Algorithmus.

Der Quantencomputer liest die Amplituden dabei nicht aus und berechnet ihren Mittelwert nicht mit einem klassischen Unterprogramm. Die Gatterfolge verändert den Quantenzustand direkt nach genau dieser mathematischen Regel.

Die Messung liefert die Position

Unmittelbar vor der Messung lauten die Amplituden:

Position 00: 0
Position 01: 0
Position 10: 1
Position 11: 0Die Messung der beiden Qubits liefert deshalb in diesem idealen Beispiel sicher:

10Das ist die Position des gesuchten Listeneintrags. Der Eintrag an Position 10 enthält die Kundennummer 4711.

Warum funktioniert eine Runde hier so genau?

Unser Beispiel besitzt vier gleich wahrscheinliche Positionen und genau einen Treffer.

Vor dem Vergleich hat jede Position die Amplitude +0,5. Der Vergleich kehrt genau eine davon in −0,5 um. Dadurch liegt der Mittelwert bei 0,25.

Die Spiegelung macht anschließend aus

+0,5 → 0
−0,5 → 1Deshalb verschwindet in diesem besonderen kleinen Beispiel die Messwahrscheinlichkeit der drei nicht passenden Positionen vollständig.

Bei größeren Listen reicht eine Runde gewöhnlich nicht aus. Vergleich und Spiegelung werden mehrfach wiederholt. Dabei wächst die Amplitude der passenden Position, bis ihre Messwahrscheinlichkeit nahe am erreichbaren Maximum liegt.

Die Operationen dürfen nicht beliebig oft wiederholt werden. Nach dem günstigsten Zeitpunkt würde die Wahrscheinlichkeit wieder sinken.

Wo liegt der Geschwindigkeitsvorteil?

Ein klassisches Suchprogramm benötigt bei einer ungeordneten Liste im ungünstigsten Fall so viele Vergleiche, wie die Liste Einträge besitzt:

N Einträge → bis zu N VergleicheDer Grover-Algorithmus benötigt ungefähr:

√N RundenEine Grover-Runde besteht aus zwei wesentlichen Operationen:

• Die Vergleichsschaltung wird einmal auf den gesamten Zustand angewendet und prüft damit in einem Durchgang alle möglichen Positionen.
• Der Diffusionsoperator verändert anschließend die Amplituden so, dass die passende Position bei einer späteren Messung wahrscheinlicher wird. Warum sind trotz des gemeinsamen Vergleichsdurchgangs mehrere Runden nötig?

Die Vergleichsschaltung liefert die Treffer nicht als einzeln lesbare Ergebnisse. Sie verändert lediglich die Vorzeichen der passenden Amplituden. Bei einer großen Zahl möglicher Positionen reicht eine einzige solche Veränderung noch nicht aus, um die richtige Position mit hoher Wahrscheinlichkeit zu messen. Vergleich und Diffusion müssen deshalb ungefähr √N-mal wiederholt werden.

Bei vier Einträgen entsteht daraus kein praktischer Vorteil. Das kleine Beispiel zeigt lediglich jeden Rechenschritt.

Das ist eine quadratische Beschleunigung. Der Quantencomputer prüft zwar in jeder Runde alle Positionen gemeinsam, benötigt aber mehrere Runden, um eine davon mit hoher Wahrscheinlichkeit messbar zu machen.

Was geschieht auf einem realen Quantencomputer?

Die Messwahrscheinlichkeit von 100 Prozent gilt für eine ideale Schaltung mit genau vier Positionen und genau einem Treffer.

Ein reales Gerät kann durch ungenaue Gatter, Störungen und Messfehler auch andere Positionen liefern. Deshalb wird die vollständige Schaltung mehrfach ausgeführt.

Wenn 10 deutlich häufiger als die anderen Positionen gemessen wird, prüft ein klassischer Computer den Listeneintrag an dieser Position. So lässt sich bestätigen, dass dort tatsächlich 4711 steht.

Der gesamte Ablauf

Gemeinsame Eingabe:
Liste und gesuchte Kundennummer 4711Klassisches Programm:
Position setzen → Listeneintrag lesen → vergleichen
→ bei Bedarf nächste Position setzen → Ergebnis 10Quantenprogramm:
Positionsregister auf 00 setzen
→ Amplituden für 00, 01, 10 und 11 erzeugen
→ alle Positionen in einem Durchgang mit 4711 vergleichen
→ Vorzeichen der passenden Amplitude umkehren
→ Amplituden am Mittelwert spiegeln
→ Positionsregister messen
→ Ergebnis 10Beide Programme erhalten also dieselben Daten und führen inhaltlich denselben Vergleich aus. Der klassische Computer ruft die Vergleichsoperation nacheinander für einzelne Positionen auf. Der Quantencomputer wendet sie einmal auf den gemeinsamen Zustand aller möglichen Positionen an. Das Ergebnis ist ein verändertes Amplitudenmuster, aus dem erst die weiteren Operationen eine mit hoher Wahrscheinlichkeit messbare Position erzeugen.

Mit einem Missverständnis aufräumen

Missverständnis:* Wenn die Vergleichsschaltung alle Positionen in einem Durchgang prüft, kennt der Quantencomputer danach sofort das Ergebnis.*Die Vergleichsschaltung wirkt in einem Durchgang auf alle Positionen des gemeinsamen Quantenzustands. Sie gibt die einzelnen Vergleichsergebnisse aber nicht aus. Stattdessen verändert sie die Amplituden der passenden Positionen. Erst weitere Grover-Runden und die abschließende Messung liefern eine einzelne Position.

Was wir jetzt wissen

• Klassische und quantische Suche beginnen mit derselben Liste und demselben Suchwert.
• Bits beziehungsweise Qubits stellen die Positionen der Listeneinträge dar.
• Das klassische Programm prüft jeweils eine Position und geht die Liste nacheinander durch.
• Das Quantenprogramm erzeugt einen Zustand mit einer Amplitude für jede mögliche Position.
• Die Vergleichsschaltung wird einmal auf diesen Gesamtzustand angewendet und prüft damit in einem Durchgang alle Positionen.
• Der Vergleich gibt keine einzelnen Antworten aus, sondern verändert das Amplitudenmuster.
• Die Vergleichsschaltung kehrt das Vorzeichen der Amplitude einer passenden Position um.
• Der Diffusionsoperator wandelt diesen Vorzeichenunterschied in eine höhere Messwahrscheinlichkeit um.
• Bei vier Positionen und einem Treffer liefert eine ideale Grover-Runde die passende Position mit 100 Prozent Wahrscheinlichkeit.
• Bei größeren Listen werden Vergleich und Diffusion ungefähr √N-mal ausgeführt. In Episode 7 untersuchen wir, was geschieht, wenn unser Beispiel nicht vier, sondern eine Million Listeneinträge besitzt. Dann geht es nicht mehr nur um den Algorithmus, sondern auch um Speicher, Datenzugriff, benötigte Qubits und Fehlerkorrektur.