© OlgaYastremska / 123RF.com

Seit verschiedene Hersteller den Zugriff auf Quantencomputer über Cloud-Dienste anbieten, lässt sich deren Programmierung von jedermann auch praktisch bewerkstelligen. Die nötigen Grundlagen, angefangen bei Schrödingers Katze, vermittelt dieser Beitrag.

Die Grundlage des Quantencomputers ist das Quantenbit, gleichermaßen als physisches Bauteil wie auch konzeptionell als elementare Informationseinheit. Das klassische Bit kann bekanntlich nur die Werte 0 oder 1 annehmen. Greifen Sie auf ein Quantenbit oder Qubit zu und lesen es aus, dann erhalten Sie ebenfalls einen der Werte 0 oder 1. Vor dem Auslesen besteht allerdings eine fundamental andere Situation, es sind nämlich Superpositionen möglich. Auf diese besondere Art von Quantenzustand kommen wir im Folgenden noch genauer zu sprechen.

Quantenmechanische Phänomene lassen sich nicht aus den Erfahrungen mit unserer Alltagswelt oder mit klassischen Computern erklären. Dazu müssten wir auf Experimente wie das Doppelspaltexperiment eingehen, das Sie vielleicht kennen. Weil das aber Stoff für einen eigenen Artikel oder eher ein ganzes Buch wäre, beschränken wir uns hier darauf zu beschreiben, wie sich Qubits verhalten und was man mit ihnen machen kann.

@LDie Beschreibung beginnt mit einem Modell, das sich aus einem berühmten Gedankenexperiment ableitet: Schrödingers Katze. In unserer stark vereinfachten Version befindet sich eine Katze in einer Kiste, die das Tier von der Außenwelt abschottet. Der Gesundheitszustand des Tiers befindet sich in der Schwebe: Es ist unbestimmt, ob es lebendig oder tot ist, eine Superposition dieser beiden Möglichkeiten liegt vor. Die besteht aber nur solange, wie die Kiste fest verschlossen bleibt. Öffnen wir sie, finden wir entweder eine lebendige oder eine tote Katze vor. Welchen der Fälle wir beobachten, entscheidet sich erst im Moment des Öffnens, und zwar durch Zufall. Mit einer Wahrscheinlichkeit von 50 Prozent lebt die Katze, mit derselben Wahrscheinlichkeit ist sie tot.

Ganz ähnlich verhalten sich Qubits. Ein Beispiel für einen konkreten Qubit-Zustand ist 0,60> + 0,81>. Die spitzen Klammern kennzeichnen Quantenzustände, man spricht von der Dirac- oder Bra-ket-Notation. Dabei entsprechen |0> oder |1> den klassischen Bitwerten. Hier kommen beide vor, und zwar |0> mit dem Vorfaktor 0,6 (der sogenannten Amplitude) und |1> mit der Amplitude 0,8.

Der Qubit-Zustand und die Werte der Amplituden selbst sind nicht zu erkennen. Es gibt laut den Gesetzen der Quantenmechanik kein Verfahren, mit dem man die Amplituden bestimmen könnte. Möglich ist eine quantenmechanische Messung: Dadurch wird die Superposition zerstört und man erhält ein zufälliges Ergebnis. Um Wahrscheinlichkeiten zu berechnen, quadrieren wir die Amplituden: Wir finden das Qubit nach der Messung mit der Wahrscheinlichkeit 0,36 als |0> vor und in 64 Prozent der Fälle im Zustand |1>. Das Befinden von Schrödingers Katze könnten wir nun als Superposition angeben:

Diese Wurzelbrüche wirken vielleicht etwas ungewohnt. Im gegebenen Zusammenhang ist nur wichtig, dass das Quadrat der Kehrwerte der Wurzel aus 2 den Wert 1/2 ergibt. Diese Superposition lässt sich nicht erkennen; sie existiert nur so lange, bis wir die Kiste öffnen und dadurch messen. Danach würden wir die Katze mit jeweils gleicher Wahrscheinlichkeit putzmunter oder verstorben vorfinden. Solange die Kiste so fest verschlossen bleibt, dass kein Kontakt mit der Außenwelt stattfindet, bleibt der Zustand weiter in der zombiehaften Schwebe.

Das ist freilich nur eine Veranschaulichung: Katzen findet man nicht in Superpositionen vor. Qubits werden in der Realität zum Beispiel mit Supraleitern oder Ionenfallen gebaut. Für Berechnungen mit Qubits sind Superpositionen wie diese besonders wichtig:

Hier treten beim Messen die Werte |0> und |1> mit gleicher Wahrscheinlichkeit auf. Allgemein ist jedes a|0> + b|1> eine gültige Superposition, wenn für die Amplituden a und b die Relation |a|² + |b|² = 1 gilt. Es gibt also unendlich viele mögliche Superpositionen.

Quantenparallelismus

Nun könnte man zu Recht fragen, was denn die Arbeit mit solchen Qubits erstrebenswert machen sollte, erscheinen deren Eigenschaften doch zunächst eher lästig.

Angenommen, uns liegt ein Algorithmus vor, den wir auf die 256 Belegungen von acht Bits anwenden müssen. Mit einem klassischen Computer führen wir diesen Algorithmus 256 Mal aus und speichern die Ergebnisse. Nun verwenden wir acht Qubits. Der Zustand eines solchen Quantenregisters ist eine Superposition der 256 klassischen Möglichkeiten. Wenn wir den Algorithmus quantentauglich umarbeiten, können wir mit nur einem Durchlauf eine Superposition der 256 Ergebnisse erzeugen. Das bezeichnet man als Quantenparallelismus. Mit 100 Qubits ließe sich mit einer Ausführung eine Superposition von 2¹⁰⁰ Funktionswerten erzeugen, wenn auch die zurzeit gebauten Quantencomputer dazu noch nicht in der Lage sind.

Damit sind wir aber noch nicht fertig. Ärgerlicherweise enden viele Darstellungen hier, und es entsteht der Eindruck, so ziemlich jedes komplexe Problem wäre mit einem Quantencomputer exponentiell beschleunigt zu lösen. Allerdings lässt sich die Superposition der 256 oder 2¹⁰⁰ Ergebnisse nicht erkennen. Messen wir das Register, erhalten wir zufällig einen dieser Werte, und wir wissen noch nicht einmal, welchen. Scott Aaronson gab dazu den Hinweis, man könnte stattdessen einfach vorab mit einem Zufallsgenerator eine der 256 Bitbelegungen auswürfeln und anschließend die Funktion auswerten. Dafür müsste man keinen Quantencomputer bauen.

Interferenz

Um nützliche Quantenalgorithmen zu finden, genügt es nicht, einfach dem Parallelismus zu vertrauen. Man muss dazu erreichen, dass vor der Messung die Amplitude des korrekten Ergebnisses in der Superposition groß und die der falschen sehr niedrig liegt. Dabei spielt eine Rolle, dass Amplituden auch negative Vorzeichen haben können. Damit kann Interferenz auftreten: So wie sich zwei Wellen dort gegenseitig auslöschen, wo Berg auf Tal trifft (Abbildung 1), so können sich Amplituden mit entgegengesetzten Vorzeichen zu 0 addieren. Diese Möglichkeit gibt es für klassische Computer nicht.

Abbildung 1: Konstruktive und destruktive Interferenz. Quelle: Reprinted by permission from Springer Nature: Prof. Dr. Homeister: “Quantum Computing verstehen”, 2018

Zur Veranschaulichung: Wir werfen zwei Würfel und addieren die Ergebnisse. Es gibt 36 Zweierkombinationen, und unter fairen Bedingungen hat jede die Wahrscheinlichkeit 1/36. Wir interessieren uns für die Würfelsumme 10. Diese ergibt sich aus 4 + 6, 5 + 5 oder 6 + 4. Das Ergebnis 10 hat damit die Wahrscheinlichkeit 1/36 + 1/36 + 1/36 = 1/12. Wahrscheinlichkeiten addieren sich immer auf diese Weise, Quantenamplituden können sich hingegen gegenseitig auslöschen:

Am Ende dieses Artikels wollen wir die Arbeitsweise von Grovers Suchalgorithmus erläutern, bei der man durch konstruktive und destruktive Interferenz nach und nach die Amplitude des gesuchten Elements vergrößert. Dort wird auch darauf eingegangen, dass Quantenalgorithmen durch den Zufallsprozess bei der Messung häufig eine gewisse Fehlerwahrscheinlichkeit aufweisen.

Wir haben bei der Definition von Qubit-Zuständen nicht angegeben, aus welchem Wertebereich die Amplituden stammen: Es sind die komplexen Zahlen. Während genau zwei reelle Zahlen den Betrag 1 besitzen (1 und -1), gibt es unendlich viele komplexe Zahlen mit dieser Eigenschaft. Das erweitert die Interferenzmöglichkeiten.

Sicher haben Sie schon davon gehört, dass Quantencomputer die Sicherheit von aktuell verwendeten Kryptografieverfahren wie RSA gefährden. Das liegt an Shors Algorithmus, der Zahlen in ihre Primfaktoren zerlegen kann, und zwar mit exponentieller Beschleunigung gegenüber dem besten bekannten klassischen Verfahren für dieses Problem. Diese Beschleunigung beruht auf virtuoser Nutzung von Interferenz.

Vielleicht ist mittlerweile schon deutlich geworden, dass Quantencomputer für spezielle Aufgaben einen Vorteil bringen. Damit ergänzen sie die gewohnten klassischen Rechner und eröffnen fundamental neue Möglichkeiten, lösen aber herkömmliche Computer nicht ab.

Rechenschritte

Quantenalgorithmen werden häufig als Quantenschaltkreis wie in Abbildung 2 dargestellt. Auf ein Bit im Ausgangszustand |0> wird ein als H bezeichnetes Gatter angewendet. Zum Abschluss erfolgt eine Messung. H heißt Hadamard-Transformation und überführt:

Die abschließende Messung zerstört wie oben beschrieben die Superposition. Wir beobachten mit einer Wahrscheinlichkeit von 1/2 jeweils |1> oder |0>. Dieses Vorgehen hat wichtige Anwendungen. Beispielsweise erreichen klassische Rechner nur pseudozufällige Ergebnisse, der Schaltkreis aus Abbildung 2 erzeugt dagegen echte Zufallswerte.

Abbildung 2: Der Schaltkreis für einen Zufallsgenerator.

Mögliche Rechenschritte auf Quantenbits sind stets Transformationen wie H. Sie müssen bestimmte Eigenschaften erfüllen: Unter anderem sind sie stets umkehrbar, als Matrizen darstellbar und daher linear. Mathematisch gesprochen, handelt es sich um unitäre Transformationen. Ein weiteres Beispiel ist der Bitflip X, auch als Pauli-X-Gatter bezeichnet. X bildet |0> auf |1> ab und umgekehrt. Allgemein wechselt a|0> + b|1> durch Anwendung von X in den Zustand b|0> + a|1>.

Mehrere Bits

Mit einem Qubit können wir immerhin schon einen Zufallsgenerator programmieren, für sinnvolle Berechnungen benötigen wir jedoch möglichst viele davon. Falls Sie die folgenden Berechnungen zu detailliert und zu mühsam finden, überfliegen Sie sie zunächst einfach. Wer aber die gezeigten Schaltkreise selbst einmal auf einer Quantencomputerplattform programmieren will, dem helfen die Ausführungen zu verstehen, was tatsächlich passiert.

Abbildung 3: Schaltkreis mit zwei Qubits.

In Abbildung 3 sehen Sie einen Schaltkreis mit zwei Qubits. Das erste wird mit |0> initialisiert und befindet sich nach dem Anwenden von H im Zustand:

Das zweite Qubit ist nach dem Anwenden von H auf |1> im Zustand:

Betrachten wir beide Qubits als ein Register, dann können wir die Superpositionen miteinander multiplizieren:

Links haben wir hier die Beschreibung des ersten Qubits, rechts die des zweiten. Glücklicherweise können wir wie gewohnt ausmultiplizieren, beginnend mit:

Dabei ergibt sich 1/2|0>|0> oder anders geschrieben 1/2|00>, insgesamt erhalten wir 1/2|00> – 1/2|01> + 1/2|10> – 1/2|11>.

Hier bedeutet |01>, dass das erste Qubit den Wert |0> hat und das zweite den Wert |1>. Wir haben es also mit einer Superposition über die vier möglichen Belegungen von zwei klassischen Bits zu tun. Genauso bekommen wir für drei Qubits eine Superposition über acht klassische Belegungen und allgemein für n Qubits eine über 2ⁿ.

Wir haben gesehen, wie in einem Schaltkreis auf einzelne Bits Transformationen angewendet werden. Nehmen wir noch Gatter dazu, die auf mehrere Bits wirken, lassen sich so alle Quantenalgorithmen umsetzen.

Davon unterscheiden sich auf Quantum Annealing spezialisierte Computer, wie sie das kanadische Unternehmen D-Wave Systems vertreibt. Sie verwenden eine Heuristik für Optimierungsprobleme, die man als Quantenversion des klassischen Simulated Annealing ansehen kann. Für bestimmte Eingaben kann hier der Quantencomputer einen großen Geschwindigkeitsvorteil bedeuten, für andere nicht.

Verschränkung

Es gibt ein faszinierendes Phänomen, dass Einstein einst als spukhafte Fernwirkung bezeichnet hat. Betrachten wir dazu folgende Superposition:

Es liegt also ein Quantenregister aus zwei Bits vor. Die Amplituden der Bitbelegungen |00> und |11> sind jeweils der Kehrwert der Wurzel aus 2, die Amplituden von |01> und |10> sind jeweils 0. Man nennt das einen Bell-Zustand.

Wir messen das Register: Mit der Wahrscheinlichkeit 1/2 haben anschließend beide Bits den Wert |1>, mit derselben Wahrscheinlichkeit beide den Wert |0>. Jetzt trennen wir die beiden Bits, indem wir Bit 2 an einen Kollegen an einem anderen Ort schicken. Auf Photonen basierende Qubits lassen sich beispielsweise über eine Glasfaserleitung transportieren. Wir messen das bei uns verbliebene Bit 1. Mit der Wahrscheinlichkeit 1/2 beobachten wir |1>, mit derselben Wahrscheinlichkeit |0>. Danach rufen wir unseren Kollegen an und bitten ihn, sein Qubit zu messen. Was wird er beobachten? Er erhält in jedem Fall denselben Bitwert wie wir.

Wenn zuerst unser Kollege sein Qubit misst und anschließend wir unseres, werden wir zum gleichen verblüffenden Ergebnis kommen: Vor einer Messung sind beide Bits des Bell-Zustands unbestimmt, der Zufall bestimmt den Wert nach der Messung. Haben wir nun aber eines der Bits gemessen, steht unmittelbar das Ergebnis einer künftigen Messung an dem anderen Bit fest; dabei kann es sich an einem beliebig weit entfernten Ort befinden.

Im Bell-Zustand sind die Qubits verschränkt. Dieses erstaunliche Verhalten nutzt die Quantenteleportation: Dabei wird ein Quantenbit übertragen, ohne dass es selbst den Raum durchqueren muss. Stattdessen transportiert man wie oben ein Qubit eines Bell-Paars vorab zum Ziel. Mit Überlichtgeschwindigkeit findet die Informationsübertragung übrigens nicht statt.

Was nach Science Fiction klingt, hat sehr reale Anwendungen. Wir greifen eine heraus: Quantenrepeater für den Aufbau von Quantenkommunikationsnetzwerken sehen sich zwei Herausforderungen gegenüber. Zum einen werden Qubits bei der Messung verändert, zum anderen lassen sie sich nicht kopieren – das besagt das sogenannte No-Cloning-Theorem. Wie kommt man zu einer solchen Aussage? Hat man vielleicht einfach noch nicht die richtige Methode gefunden?

Wir wissen bereits, dass Operationen auf Quantenbits eine besondere mathematische Eigenschaft haben müssen, “unitär” war der Name. Das kommt daher, dass sich quantenphysikalische Systeme ausschließlich auf diese Weise entwickeln, zumindest bis zu einer Messung. Nun lässt sich zeigen, dass keine derartige Transformation existiert, die jeden beliebigen Quantenzustand auf einen anderen kopiert. Die beiden genannten Herausforderungen für einen Repeater lassen sich anderseits für die Kryptografie nutzen. Ein Lauscher kann ein versendetes Qubit nicht kopieren, und die Veränderung durch eine Messung können Verschlüsselungsprotokolle entdecken.

Den Bell-Zustand können wir mit dem Schaltkreis in Abbildung 4 erzeugen. Zwei Bits werden mit |0> initialisiert, auf das erste wirkt das Gatter H. Darauf folgt eine neue Operation, die Zwei-Bit-Transformation CNOT (controlled-NOT oder auch controlled-X). Dieses Gatter kippt das zweite Bit genau dann, wenn das erste den Wert 1 hat. Es wird also |00> in |00> überführt, |01> in |01>, |10> in |11> und |11> in |10>, und zwar für jede Komponente einer Superposition parallel.

Abbildung 4: Der Schaltkreis zur Erzeugung eines Bell-Zustands.

Damit vollzieht der Schaltkreis folgende Berechnung: |00> wird durch H zu

Durch CNOT erhalten wir daraus:

Auch mehr als zwei Qubits können verschränkt sein. So lässt sich mit dem Schaltkreis in Abbildung 5 der GHZ-Zustand (benannt nach Greenberger, Horne und Zeilinger) erzeugen:

Dabei wird durch die Messung eines der drei Bits der Zustand der beiden anderen festgelegt.

Abbildung 5: Der Schaltkreis zum Erzeugen eines GHZ-Zustands.

Ein Suchalgorithmus

Von Lov Grover stammt das eingangs erwähnte Verfahren zur Brute-Force-Suche, das hier als Beispiel für einen komplexen Quantenalgorithmus dienen soll. Wir stellen uns vor, dass wir aus 65536 Eingaben diejenige mit einer besonderen Eigenschaft herausfinden sollen. Wir nennen sie den Treffer. Vielleicht handelt es sich bei den Eingaben um die Knoten eines Netzwerks, und wir suchen einen, der nicht verbunden ist. Oder wir suchen zu einer kryptografischen Funktion den Eingabewert, der zu einem uns vorliegenden Ausgabewert gehört.

Der Einfachheit halber soll es genau einen solchen Treffer geben. Weiter setzen wir voraus, dass wir einen Testalgorithmus kennen, der für jede Eingabe ermittelt, ob es sich dabei um den Treffer handelt. Den Testalgorithmus überführen wir in einen Quantenschaltkreis, und zwar so, dass für den Treffer 1 zurückgegeben wird, für alle anderen Eingaben 0. Dieser Schaltkreis liefert nun wiederum die Eingabe für Grovers Suchalgorithmus, das sogenannte Quantenorakel.

Grovers Algorithmus erzeugt zunächst eine Superposition über alle 65536 Eingaben. Jede Amplitude erhält den Wert 1/256, da 256 x 256 insgesamt 65536 ergibt. Man kann dazu 16 Qubits mit |0> initialisieren und auf jedes H anwenden. Zusätzlich benötigen wir noch ein Hilfsbit. Dann ermöglicht der Quantenparallelismus mit einer einzigen Orakelanwendung das Folgende: Die Amplitude des Treffers kippt auf -1/256, alle anderen bleiben bei 1/256.

Noch würde eine Messung keinen Hinweis auf den Treffer bringen. Man kann dennoch ausnutzen, dass dieser innerhalb der Superposition durch das negative Vorzeichen herausgehoben ist: Wir wenden einen Schaltkreis an, der jede einzelne Amplitude am Mittelwert aller Amplituden spiegelt. Dadurch wird die Amplitude des Treffers erstens wieder positiv und zweitens vergrößert. Alle anderen Amplituden verkleinern sich entsprechend. Diese beiden Schritte (Negation der Amplitude des Treffers und Spiegeln am Mittelwert) nennt man die Grover-Iteration. Bei erneuter Anwendung wächst die Amplitude des Treffers weiter. In unserem Fall wiederholen wir sie 200 Mal. Danach liefert uns eine Messung mit hoher Wahrscheinlichkeit den Treffer.

Die Anzahl der Grover-Iterationen liegt in der Größenordnung der Wurzel aus der Anzahl der möglichen Eingaben. Im Vergleich zu klassischen Computern ergibt dies eine quadratische Beschleunigung. Wir bekommen nicht in jedem Fall den Treffer geliefert, sondern nur mit hoher Wahrscheinlichkeit. Das stellt in der Praxis jedoch kein Problem dar: Wir überprüfen das Ergebnis von Grover mit dem Testalgorithmus. So können wir entweder bestätigen, dass es sich um den Treffer handelt, oder starten Grovers Algorithmus erneut.

Angenommen, die Fehlerwahrscheinlichkeit läge bei sehr hohen 5 Prozent. Dann wäre die Wahrscheinlichkeit, dass wir zweimal ein falsches Ergebnis bekommen 0,05 x 0,05 oder 0,25 Prozent. Dreimal würde sich der Algorithmus in 0,0125 Prozent der Fälle täuschen. Der Fehler sinkt also exponentiell mit der Zahl der Wiederholungen.

Ausblick

Mit diesen Grundlagenkenntnissen gerüstet, können Sie jetzt getrost zur Praxis schreiten. Das Framework Qiskit für das Programmieren von Quantenalgorithmen stellt der folgende Artikel [2] dieses Schwerpunkts ausführlich vor. (jcb/jlu)