Quantencomputer
Herkömmliche Rechner werden seit langer Zeit in relativ konstanten Zeitintervallen besser und schneller, und das wird auch noch eine Weile so bleiben. Aber es ist absehbar, dass Grenzen erreicht werden, spätestens dann, wenn die Miniaturisierung auf der atomaren Ebene ankommt. Zudem gibt es schon heute eine Vielzahl von Problemen, die in der Praxis von größter Wichtigkeit sind, für die es aber keine effizienten Lösungsverfahren gibt.
Diese beiden Aspekte führen zu starken Aktivitäten, um neuartige Rechnerkonzepte zu erfinden und nutzbar zu machen. In den letzten 20 Jahren haben hier zwei Modelle besondere Beachtung gefunden; das eine ist eine Art Bio-Maschine, in der im wesentlichen DNS-Stränge als Prozessoren fungieren. Damit kann man im Prinzip einen enormen Grad an Parallelität realisieren, idealerweise in der Größenordnung von 10**25 . Das würde zwar einen großen Fortschritt bedeuten, die genannten schweren Probleme würden allerdings nach wie vor schwer bleiben (nur dass die Schwierigkeit erst bei etwas größeren Eingaben beginnen würde).
Das zweite Modell ist der Quantencomputer, in dem versucht werden soll, quantenmechanische Effekte auszunutzen, um Berechnungen tatsächlich essentiell zu beschleunigen (d.h. nicht nur um einen konstanten Faktor).
Die Idee stammt ursprünglich von Richard Feynman, der bereits 1982 aus der Feststellung, dass man quantenmechanische Effekte nicht effizient im Rechner darstellen konnte, den Umkehrschluss zog, dass ein auf solchen Effekten basierender Rechner schneller sein könnte als herkömmliche Rechner.
Es dauerte noch 12 Jahre, bis durch den Aufsehen erregenden Algorithmus von Peter Shor klar wurde, dass ein Quantencomputer in der Lage wäre, große Zahlen effizient zu faktorisieren. Das hätte große Auswirkungen, denn weit verbreitete kryptographische Verfahren, wie etwa die RSA-Verschlüsselung, würden dadurch sofort unbrauchbar.
Quanteneffekte
Was ist ein Quanteneffekt? Das folgende sehr populäre Beispiel soll das verdeutlichen. Es sei vorausgeschickt, dass man intuitiv Hemmungen haben wird, diesen Effekt als Realität hinzunehmen. Er ist aber durch nachprüfbare Experimente einwandfrei nachgewiesen.
Sendet man Photonen auf einen im 45-Grad-Winkel aufgestellten halb durchlässigen Spiegel, so kann man in zwei Detektoren, die hinter dem Spiegel geradlinig bzw. im rechten Winkel aufgestellt sind, jeweils etwa 50 Prozent der abgesendeten Photonen messen. Führt man dagegen durch zwei voll reflektierende Spiegel beide Wege wieder zusammen und stellt am Treffpunkt einen weiteren halb durchlässigen Spiegel auf, so erreichen alle Photonen Detektor 1 und keines Detektor 2.
Anordnung zum Nachweis des Quanteneffekts
Das könnte man nun so interpretieren, dass es einfach eine Eigenschaft der Photonen ist, durch halbdurchlässige Spiegel durchzugehen (d.h. immer) oder nicht (d.h. nie). Dass diese Interpretation falsch ist, zeigt folgender überraschender Effekt: Blockiert man einen der Wege (z.B. durch eine absorbierende Fläche), dann werden in beiden Detektoren etwa gleich viele Photonen registriert.
Dieses Experiment kann nur durch die Folgerung erklärt werden, dass die Photonen generell gleichzeitig beide Wege verfolgen, d.h., jedes Photon befindet sich in einer sog. "kohärenten Superposition" zweier möglicher Zustände. Die Zustände sind hier: oberen Weg nehmend oder unteren Weg nehmend.
Die Tatsache, dass sich ein System gleichzeitig in zwei Zuständen befinden kann, ist die Neuigkeit, die man auszunutzen versucht, um einen sog. Quantenrechner zu bauen. Während ein Bit im klassischen Computer immer einen der Werte 0 oder 1 annimmt, kann man, auf Quanteneffekten aufbauend, ein Qubit definieren, das eine gewichtete Überlagerung dieser zwei Basiszustände als aktuellen Wert annehmen kann. Die jeweiligen Gewichte, mit denen die Basiszustände in der Überlagerung vorkommen, nennt man Amplituden. Aus ihnen berechnet sich die Wahrscheinlichkeit, im Falle einer Messung den entsprechenden Basiszustand zu erhalten.
Realisierung
Zunächst erscheint es nicht allzu wertvoll, ein einzelnes Qubit zur Verfügung zu haben. Zwar kann man (je nachdem, welche Amplituden in der Überlagerung realisierbar sind) evtl. auch schon mit einem Qubit erstaunliche Ergebnisse erzielen, richtig interessant wird Quantencomputing aber erst dann, wenn man viele Qubits nutzen kann. Ein Computer mit n Qubits befindet sich nämlich in einer Überlagerung von 2**n Basiszuständen, d.h., er verfügt über 2**n parallele Prozessoren.
Hier ergeben sich natürlich große praktische Probleme. Qubits können nur dann funktionieren, wenn sie von äußeren Einflüssen völlig abgeschottet werden. Zudem sind auch die Amplituden als physikalische Größen grundsätzlich fehlerbehaftet. Die Herstellung und schrittweise gezielte Manipulation einer großen Zahl von Qubits stellt daher ein enormes technisches Problem dar, an dessen Lösung aber zur Zeit massiv gearbeitet wird. Das aktuelle Highlight ist ein System mit 5 Qubits.
Schliesslich muss man noch beachten, dass zwar ein System mit n Qubits eine Überlagerung von 2**n Basiszuständen darstellen kann, dass es aber nicht allgemein möglich ist, alle Informationen, die in dieser Superposition vorliegen, auch auf die Außenwelt zu übertragen.
Stattdessen muss man mit einer sog. "Messung" das System zwingen, in einen der Basiszustände überzugehen, wobei die einzige nach außen abgegebene Information der tatsächlich angenommene Basiszustand ist. Eine gezielte Nutzung dieses Effekts muss also dadurch geschehen, dass man die Wahrscheinlichkeiten (die sich aus den oben erwähnten Amplituden berechnen lassen) für die verschiedenen möglichen Messergebnisse entsprechend manipuliert, so dass man mit hoher Wahrscheinlichkeit das gewünschte Resultat erhält.
Algorithmen
Um Quantenalgorithmen exakt zu beschreiben, muss man den gesamten mathematischen Apparat, der zur Beschreibung quantenmechanischer Systeme herangezogen wird, einführen; hierbei handelt es sich im Wesentlichen um einen Hilbert-Raum der Dimension 2**n , wenn das System n Qubits verwendet. Für eine angemessene Darstellung dieser Theorie ist an dieser Stelle nicht genug Raum. Aber wir können einen Eindruck vermitteln, wie kohärente Superpositionen im Idealfall genutzt werden könnten. Wir betrachten zwei Algorithmen, die wir jeweils grob skizzieren. Einzelheiten zu beiden Algorithmen kann man z.B. dem Buch von J. Gruska entnehmen. Zuerst wollen wir von einer Blackbox, die eine (unbekannte) Funktion f: {0, 1}->{0, 1} berechnet, herausbekommen, ob sie eine konstante Funktion realisiert oder nicht. Mit einem klassischen Algorithmus benötigt man offensichtlich zwei Testfragen an die Blackbox, einmal für die Berechnung von f(0) und dann für die Berechnung von f(1).
Ein Quantencomputer kann nun ein Qubit in die Zustände 0 und 1 mit gleicher Amplitude bringen und dieses Qubit als Eingabe für die Blackbox verwenden. Die Ausgabe der Blackbox ist dann eine Superposition der beiden Funktionswerte.
Nun bleibt nur zu testen, ob das Ergebnis ein Basiszustand ist (d.h. beide Funktionswerte waren gleich) oder nicht (d.h. es wurden zwei verschiedene Funktionswerte geliefert).
Für den zweiten Algorithmus betrachten wir das folgende Datenbankzugriffsproblem: Es liegt eine Datenbank mit n verschiedenen Datensätzen (die alle verschieden sein sollen) vor, etwa x1 ,. . .,x n . Zudem ist ein Element t vorgegeben.
Die Frage soll beantwortet werden, ob t in der Datenbank vorkommt, d.h., ob ein i existiert mit t = x i . Ein klassischer Computer braucht hierfür im schlimmsten Fall n Operationen, da er jedes xi mit t vergleichen muss. Selbst dann, wenn der Algorithmus probabilistisch arbeiten darf, muss man noch mehr als n/2 viele Schritte ausführen. Der Quantenalgorithmus, den Lov Grover 1996 entwarf, benutzt log n viele Qubits, um zunächst eine gleichverteilte Superposition aller Indizes aus dem Bereich {1,. . .,n} zu erzeugen. Dann prüft er (gleichzeitig in Quantensuperposition für alle Indizes), ob der gespeicherte Index zu dem Element t führt. Die Antwort auf diese Frage kann in der Superposition notiert werden. Nun würde man gerne durch eine einfache Instruktion die Frage beantworten lassen: Kommt in der Superposition ein Basiszustand vor, in dem die Antwort JA gespeichert ist? Leider ist das nicht möglich.
Stattdessen muss man ganz allmählich durch Anwendung geeigneter Operationen die Wahrscheinlichkeit, dass man bei einer Messung des gespeicherten Index gerade denjenigen bekommt, an dem t in der Datenbank steht (falls ein solcher existiert), erhöhen, bis sie hoch genug ist, dass man notfalls durch mehrmaliges Ausführen eine zuverlässige Aussage erhält. Eine sorgfältige Analyse hat ergeben, dass man mit einem solchen Algorithmus in Zeit proportional zu Wurzel aus n eine mit hoher Wahrscheinlichkeit richtige Aussage finden kann.
Grenzen
Der Datenbankalgorithmus von Grover kann zwar benutzt werden, um beliebige NP-vollständige Probleme zu lösen. Allerdings ist der Gewinn relativ gering, denn der nahe liegende Exponentialzeitalgorithmus, bei dem man alle Möglichkeiten probiert und nachprüft, ob eine Lösung dabei ist, würde selbst dann, wenn er nicht aus Platzgründen scheitert, nur eine Verbesserung von Rechenzeit 2**p(n) auf 2**p(n)/2 bringen (dabei ist p ein Polynom).
Tatsächlich ist sogar mit komplexitätstheoretischen Untersuchungen (unter Benutzung sog. Relativierungen") gezeigt worden, dass es höchst wahrscheinlich keine effizienten Quantenalgorithmen für NP-harte Probleme geben kann. Dennoch gibt der oben erwähnte Algorithmus von Shor für das Faktorisieren großer Zahlen Anlass zur Hoffnung auf essentielle Fortschritte durch Quantencomputing.
Literatur
- Feynman, R. P.: Simulating physics with computers. International Journal of Theoretical Physics 21, 467-488 (1982)
- Grover, L. K.: A fast quantum mechanical algorithm for database search. Proceedings of the 28th ACM STOC, 212-219 (1996)
- Gruska, J.: Quantum computing. New York: McGraw-Hill 1999
- Shor, P. W.: Algorithms for quantum computation: discrete log and factoring. Proceedings of the 35th IEEE FOCS, 124-134 (1994)
Autor und Copyright
Ulrich Hertrampf
Universität Stuttgart,
Institut für Informatik,
Abteilung Theoretische Informatik,
Breitwiesenstraße 2022,
D-70565 Stuttgart
© 2000 Informatik Spektrum, Springer-Verlag Berlin Heidelberg