Quantencomputing verständlich erklärt — Episode 7

Quantencomputing verständlich erklärt — Episode 7### Eine Million Einträge: Wo liegen die Daten?

In Episode 6 haben wir den Grover-Algorithmus mit vier Kundennummern betrachtet:

Position Kundennummer
00 5832
01 1947
10 4711
11 8264Zwei Qubits reichten aus, um die vier möglichen Positionen darzustellen. Die Vergleichsschaltung wirkte auf den gemeinsamen Zustand aller vier Positionen und markierte die Position, an der 4711 gespeichert war.

Für vier Einträge lässt sich dabei leicht übersehen, was bei einer wirklichen Datenbank zum entscheidenden Problem wird:

*Woher erhält die Vergleichsschaltung die Kundennummer, die zu einer Position gehört?*Bei einem klassischen Computer ist die Antwort selbstverständlich: Die Liste liegt im Arbeitsspeicher. Das Programm legt eine Position an den Speicher an und erhält den dort gespeicherten Wert zurück.

Bei einem Quantencomputer ist dieser Schritt nicht selbstverständlich.

Eine Million Positionen benötigen nur 20 Qubits

Mit jedem zusätzlichen Bit verdoppelt sich die Zahl der darstellbaren Positionen:

10 Bits → 1.024 Positionen
20 Bits → 1.048.576 PositionenEin Register aus 20 Qubits besitzt ebenfalls 1.048.576 mögliche Messergebnisse. Es kann deshalb alle Positionen einer Liste mit einer Million Einträgen darstellen.

Das klingt zunächst spektakulär: Nur 20 Qubits für eine Million Positionen.

Diese 20 Qubits enthalten jedoch nicht die eine Million Kundennummern. Sie enthalten nur das Positionsregister — also die möglichen Nummern der Listenplätze.

Die Daten selbst müssen an anderer Stelle liegen.

Was ein klassischer Speicherzugriff macht

Ein klassischer Arbeitsspeicher erhält genau eine Position:

Position 10 → Kundennummer 4711Das Suchprogramm kann den Wert anschließend mit 4711 vergleichen. Stimmt er nicht überein, setzt das Programm die nächste Position und wiederholt den Ablauf.

Position setzen
→ gespeicherte Kundennummer lesen
→ mit 4711 vergleichen
→ nächste Position setzenEin gewöhnlicher Speicherzugriff verarbeitet also eine bestimmte Position. Genau das passt zu einem klassischen Programm, das die Liste Eintrag für Eintrag durchsucht.

Was die Quantenschaltung benötigt

Nach den H-Gattern besitzt das Positionsregister nicht mehr nur eine bestimmte Position. Sein gemeinsamer Zustand enthält eine Amplitude für jede der rund eine Million möglichen Positionen.

Vereinfacht dargestellt:

Position 00000000000000000000 Amplitude
Position 00000000000000000001 Amplitude
Position 00000000000000000010 Amplitude
...
Position 11111111111111111111 AmplitudeDie Vergleichsschaltung soll nun für jede dieser Positionen feststellen, welche Kundennummer dort gespeichert ist und ob sie 4711 entspricht.

Dabei darf sie das Positionsregister nicht messen. Eine Messung würde nur eine einzige Position liefern und den gemeinsamen Zustand der übrigen Positionen zerstören.

Die benötigte Operation muss daher mit dem gesamten Quantenzustand arbeiten:

Positionen im gemeinsamen Quantenzustand
→ zugehörige Kundennummern bereitstellen
→ mit 4711 vergleichen
→ passende Amplitude markierenIn der Theorie wird diese gesamte Operation meist als Orakel bezeichnet. Unser Begriff Vergleichsschaltung aus Episode 6 beschreibt also nur ihre sichtbare Aufgabe. Damit sie vergleichen kann, muss sie jedoch zuerst an die zu jeder Position gehörenden Daten gelangen.

Ein gewöhnlicher Arbeitsspeicher reicht dafür nicht aus

Wir können das Quantenregister nicht einfach an einen normalen Arbeitsspeicher anschließen.

Der Arbeitsspeicher würde eine einzelne klassische Position erwarten. Das Quantenregister enthält vor der Messung aber keine einzelne Position, die wir ihm übergeben könnten. Es enthält Amplituden für alle möglichen Positionen.

Würden wir das Register messen, um eine klassische Position zu erhalten, wäre aus der Quantensuche wieder eine Suche nach nur einem Listeneintrag geworden.

Für Grovers Algorithmus benötigen wir stattdessen einen Speicherzugriff, der den gemeinsamen Zustand erhält. Aus

Position 00 + Position 01 + Position 10 + Position 11müsste vereinfacht

00 mit 5832

• 01 mit 1947
• 10 mit 4711
• 11 mit 8264werden — ohne vorher eine der vier Positionen auszuwählen.

Position und Kundennummer wären danach Teil desselben gemeinsamen Quantenzustands. Erst dann könnte die Vergleichsschaltung bei 4711 das Vorzeichen der zugehörigen Amplitude umkehren.

Drei Möglichkeiten, die Daten bereitzustellen

1. Die Daten werden berechnet

Manchmal steht hinter den Daten keine gespeicherte Liste, sondern eine Rechenvorschrift.

Wenn sich die Kundennummer aus der Position berechnen ließe, könnte eine Quantenschaltung diese Berechnung direkt ausführen. Sie benötigt dann keinen Speicherzugriff auf eine Million Einträge.

Grovers Algorithmus eignet sich besonders gut für solche Aufgaben: Eine Schaltung kann für jede mögliche Eingabe berechnen, ob sie die gesuchte Eigenschaft besitzt.

Unsere ungeordnete Kundenliste besitzt aber gerade keine solche Rechenvorschrift. Um zu wissen, welcher Wert an einer Position steht, muss die Schaltung die gespeicherten Daten kennen.

2. Die Liste wird in die Schaltung eingebaut

Man könnte die komplette Liste in Quantengatter übersetzen. Die Vergleichsschaltung wäre dann speziell für genau diese Daten gebaut.

Das funktioniert prinzipiell, hat aber einen Preis:

• Die Schaltung wächst mit der Datenmenge.
• Das Übersetzen der Liste verursacht Arbeit.
• Ändert sich ein Eintrag, muss auch die Schaltung angepasst werden. Die Million Datensätze sind damit nicht verschwunden. Sie stecken nun in einer entsprechend großen Schaltung.

3. Ein Quantenspeicher stellt die Daten bereit

Die dritte Möglichkeit wird Quantum Random Access Memory, kurz qRAM, genannt.

Ein qRAM soll mit Positionen in Superposition umgehen können. Es soll die zugehörigen Daten bereitstellen, ohne das Positionsregister dabei auf eine einzelne Position festzulegen.

Das ist genau der Speicher, den unser vereinfachtes Beispiel stillschweigend vorausgesetzt hat.

Ein qRAM ist jedoch nicht einfach ein gewöhnlicher RAM-Chip mit einem Quantenanschluss. Die Positionen, die Daten und die Schaltelemente des Speichers müssen ihren gemeinsamen Quantenzustand während des Zugriffs bewahren. Fehler in diesem Vorgang verändern die Amplituden, auf denen der weitere Algorithmus beruht.

Es gibt verschiedene theoretische Vorschläge für qRAM. Einen großen, fehlertoleranten Quantenspeicher, den man wie heutigen Arbeitsspeicher als selbstverständliche Komponente verwenden kann, besitzen wir jedoch nicht.

Das Laden der Daten gehört zur Rechnung

Angenommen, unsere eine Million Kundennummern liegen zunächst in einer klassischen Datenbank. Bevor eine Quantenschaltung gemeinsam auf sie zugreifen kann, müssen die Daten in eine geeignete Quantenschaltung oder Speicherstruktur übertragen werden.

Schon das Einlesen aller Werte erfordert Arbeit, die mit der Größe der Liste wächst:

1.000.000 Einträge
→ 1.000.000 Werte müssen bereitgestellt werdenGrovers Algorithmus reduziert die Zahl der Orakelaufrufe von der Größenordnung N auf die Größenordnung √N. Er macht das erstmalige Bereitstellen von N beliebigen Datensätzen aber nicht automatisch billiger.

Für eine einzige Suche kann das Laden der Daten daher den theoretischen Suchvorteil aufzehren. Werden dieselben Daten anschließend sehr oft durchsucht, lässt sich der einmalige Aufwand auf viele Suchvorgänge verteilen. Dann kann die Rechnung anders ausfallen.

Der Satz

*„Grover durchsucht eine Million Einträge in ungefähr tausend Schritten“*ist deshalb unvollständig.

Vollständig müsste er lauten:

Wenn die Vergleichsschaltung bereits vorhanden ist und jeden benötigten Datenzugriff als geeignete Quantenoperation ausführen kann, benötigt Grovers Algorithmus ungefähr *√N Aufrufe dieser Schaltung.*### Aus einer Million werden ungefähr tausend Runden

Für eine Million mögliche Positionen gilt:

√1.000.000 = 1.000Die genaue günstigste Anzahl liegt bei genau einem Treffer etwas unter diesem Wert. Für unsere Betrachtung genügt die Größenordnung von ungefähr tausend Grover-Runden.

Jede Runde enthält mindestens:

Daten bereitstellen
→ mit 4711 vergleichen
→ passende Amplitude markieren
→ Amplituden spiegelnDie Aussage √N zählt also keine einzelnen elementaren Quantengatter und keine Nanosekunden. Sie zählt, wie oft die vollständige Vergleichsschaltung aufgerufen werden muss.

Ist diese Schaltung groß und langsam, ist auch eine Grover-Runde groß und langsam.

20 Qubits sind deshalb nicht genug

Die 20 Qubits stellen lediglich die Positionen dar. Eine wirkliche Schaltung benötigt zusätzlich Qubits für:

• die gelesene Kundennummer,
• den Vergleich mit 4711,
• Zwischenergebnisse der Berechnung,
• die Markierung der passenden Amplitude,
• die fehlerfreie Rückführung aller Hilfsqubits in ihren Ausgangszustand. Hinzu kommt die Fehlerkorrektur. Die Qubits, mit denen ein Algorithmus beschrieben wird, sind logische Qubits. Für einen zuverlässigen logischen Qubit können — abhängig von Hardware, Fehlerquote und Korrekturverfahren — viele physische Qubits erforderlich sein.

Die Zahl der Positionsqubits sagt daher nur, wie viele Positionen mathematisch dargestellt werden können. Sie sagt noch nicht, wie groß der gesamte Quantencomputer sein muss.

Warum Fehler bei Grover besonders problematisch sind

Grovers Algorithmus lebt von kleinen, gezielten Veränderungen der Amplituden. Vergleich und Diffusion werden viele Male hintereinander ausgeführt.

Ein Fehler in einer frühen Runde betrifft nicht nur einen klassischen Zwischenwert. Er verändert den Quantenzustand, auf dem alle folgenden Runden weiterarbeiten. Wiederholen sich ungenaue Operationen hunderte Male, können sich ihre Fehler ansammeln und das gewünschte Amplitudenmuster zerstören.

Für eine große Suche genügt deshalb nicht nur eine große Zahl von Qubits. Die Qubits müssen ihren Zustand lange genug bewahren, die Gatter müssen sehr genau arbeiten und auftretende Fehler müssen während der Rechnung korrigiert werden.

Ist Grovers Algorithmus damit nutzlos?

Nein. Grovers Algorithmus zeigt eine echte und mathematisch bewiesene quadratische Verringerung der benötigten Orakelaufrufe.

Der Vorteil ist jedoch an Voraussetzungen gebunden:

• Die möglichen Lösungen lassen sich mit ausreichend wenigen Qubits darstellen.
• Die Prüfung einer möglichen Lösung lässt sich als Quantenschaltung ausführen.
• Die Daten stehen dieser Schaltung in geeigneter Form zur Verfügung.
• Die Kosten für Datenbereitstellung, Gatter und Fehlerkorrektur zerstören den Vorteil nicht.
• Die quadratische Beschleunigung ist groß genug, um eine sehr schnelle klassische Implementierung zu schlagen. Grover macht daher nicht jede Datenbanksuche automatisch schneller. Er beschleunigt einen genau definierten Teil einer Aufgabe unter genau definierten Voraussetzungen.

Mit einem Missverständnis aufräumen

Missverständnis:* Mit 20 Qubits kann ein Quantencomputer eine Datenbank mit einer Million Einträgen speichern und in ungefähr tausend Schritten durchsuchen.20 Qubits können ungefähr eine Million **Positionen* darstellen. Sie speichern aber nicht automatisch die eine Million Datensätze. Damit Grovers Algorithmus diese Datensätze durchsuchen kann, müssen sie in der Vergleichsschaltung berechenbar, in die Schaltung eingebaut oder über einen geeigneten Quantenspeicher zugänglich sein.

Die ungefähr tausend Schritte sind außerdem ungefähr tausend Aufrufe dieser vollständigen Vergleichsschaltung — nicht tausend einfache CPU-Befehle.

Was wir jetzt wissen

• Für eine Million mögliche Positionen genügen 20 Qubits im Positionsregister.
• Das Positionsregister enthält Positionen, nicht die dazugehörigen Datensätze.
• Ein gewöhnlicher Arbeitsspeicher liefert zu einer Zeit den Wert einer bestimmten klassischen Position.
• Grovers Vergleichsschaltung muss mit allen Positionen im gemeinsamen Quantenzustand arbeiten, ohne sie vorher zu messen.
• Die Daten können berechnet, in die Schaltung eingebaut oder über einen geeigneten Quantenspeicher bereitgestellt werden.
• Ein qRAM müsste Speicherpositionen in Superposition verarbeiten und dabei den Quantenzustand erhalten.
• Das Laden einer beliebigen Liste kostet Arbeit und gehört bei einer ehrlichen Laufzeitbetrachtung dazu.
• Die Angabe √N zählt Orakelaufrufe, nicht elementare Gatter oder eine konkrete Laufzeit.
• Die 20 Positionsqubits sind nur ein kleiner Teil der tatsächlich benötigten Hardware.
• Große Grover-Schaltungen benötigen sehr genaue Operationen und Fehlerkorrektur. In Episode 8 wechseln wir von der Software zur Hardware. Wir vergleichen CPU, GPU und QPU und untersuchen, was ein physisches Qubit ist, wie Quantengatter technisch ausgeführt werden und warum eine QPU immer einen klassischen Computer zur Steuerung benötigt.