Abb. 1. Anordnung zum Nachweis des Quanteneffekts
Informatik-Lexikon
Q
Quantencomputer
Quantenprogrammiersprachen
ErläuterungDiese 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 [1],
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. QuanteneffekteWas 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 (Abb. 1). |
|
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. RealisierungZunä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. AlgorithmenUm 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 [3] 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 [2], 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. GrenzenDer 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. |
Quantenprogrammiersprachen
ErläuterungQuantensysteme können durch herkömmliche Rechner nicht effizient simuliert werden. Richard Feynman war der erste, der im Jahre 1982 den positiven Aspekt dieser Tatsache gesehen hat. Wenn es nämlich umgekehrt möglich wäre, mit Quantensystemen zu rechnen, dann sollten diese manche Probleme effizienter lösen können als klassische Rechner, vorausgesetzt, es lassen sich entsprechende Algorithmen finden, die den sogenannten Quantenparallelismus auszunutzen erlauben. Einen regelrechten Boom an Forschungsaktivitäten zu solchen Quantenrechnern [2] hat die Entdeckung eines Algorithmus durch Peter Shor im Jahre 1994 ausgelöst, jetzt Shor-Algorithmus genannt, durch den ein hinreichend großer Quantenrechner die Primfaktorzerlegung einer natürlichen Zahl in bezüglich der Stellenzahl polynomialer Zeit durchführen könnte. Demgegenüber besitzen die derzeitig besten Verfahren (Siebverfahren) eine exponentielle Zeitkomplexität. Damit ist zumindest der theoretische Nachweis geführt, dass verbreitete kryptographische Verfahren, die auf der Faktorisierung von Zahlen und dem diskreten Logarithmus beruhen wie RSA und ElGamal potenziell unsicher sind. Die Beschreibung von Algorithmen bedarf einer Notation. In der Literatur zur Quanteninformationstheorie (Zitate s. unter [3]) werden Algorithmen, wie in der Informatik-Literatur üblich, als ein Gemisch aus mathematischer Notation und Beschreibung in natürlicher Sprache formuliert. Es ist daher naheliegend, hier einen Schritt weiter zu gehen und zu versuchen, eine Notation zu definieren, die eine echte Programmiersprache darstellt, mit der Algorithmen also in eine auf einem Rechner lauffähige Form gebracht werden können. Solche Sprachen werden als Quantenprogrammiersprachen („quantum programming languages", kurz QPLs) bezeichnet, wobei durch Bibliotheken entsprechend erweiterte konventionelle Sprachen auch dieser Kategorie zugerechnet werden. Man kann sicherlich einwenden, dass eine Beschäftigung mit QPLs noch verfrüht ist angesichts der Tatsache, dass Quantenrechner mit einer großen Zahl von qubits, wie sie für eine brauchbare Implementierung etwa des Shor-Algorithmus erforderlich sind, nach vorherrschender Meinung auf absehbare Zeit nicht zur Verfügung stehen werden. Es gibt aber durchaus eine Reihe guter Gründe für solche Arbeiten. Niklaus Wirth hat stets betont, dass Programmiersprachen auch ein Kommunikationsmittel zwischen Menschen sind. In diesem Sinn erlauben QPLs, über Quantensysteme in einer aus Sicht der Physik durchaus neuartigen Weise zu sprechen; viele altbekannte Phänomene der Quantenphysik erscheinen so in neuem Licht, wenn konkrete Probleme in einer QPL formuliert werden. Vor allem können die bisher bekannten Algorithmen in einer wesentlich genaueren und detaillierteren Weise formuliert werden, als es mit einer Art Pseudocode-Notation möglich ist; das hat insbesondere auch einen didaktischen Wert. Natürlich sollte man seine Erwartungen nicht zu hoch ansetzen. Informatik-Konzepte stammen aus physikalischer Sicht aus einer klassischen Welt, d.h. also einer solchen, in der die spezifischen Phänomene der Quantenphysik keine Rolle spielen. Man kann daher nicht erwarten, dass alle programmiersprachlichen Konzepte beim Umgang mit Quantenrechnern, also Quantensystemen, tragfähig bleiben. Man kann erst recht nicht erwarten, dass man Antworten auf Fragen erhält, die als Merkwürdigkeiten oder - aus der Sicht vieler Physiker nach wie vor - als Paradoxa der Theorie gelten, also im Sinne von Roger Penrose der Z- und der X-Rätsel („puzzles" und „paradoxa"). Die Modularisierung als eines der zentralen Konzepte im Software- und Sprachdesign bildet ein typisches Beispiel für ein nicht unmittelbar übertragbares Konzept. Wenn in einem (klassischen) Programm mit einem Modul (modul-globaler) Speicher verbunden ist, so verhält sich dieser beim Zusammensetzen von Modulen naturgemäß additiv. Setzt man dagegen in einem Quantenprogramm zwei Module zusammen, in denen jeweils n bzw. m qubits allokiert sind, und die damit jeweils einen Speicherplatz für die komplexen Amplituden eines (reinen)Zustandes von 2n bzw 2m bereitstellen, so ist der Speicherplatz des zusammengesetzten Systems 2n+m. Hinzufügen eines qubits bedeutet also Verdopplung des Speichers. Das ist ein Ausdruck für die Existenz von nichtklassischen Korrelationen, wie sie typisch für Mehrkomponenten-Quantensysteme sind. Gelegentlich wird in der Literatur die Hoffnung geäußert, dass QPLs hilfreich sein könnten beim Auffinden neuer Algorithmen für Quantenrechner. Hier ist sicherlich eine gewisse Skepsis angebracht: nur durch das Erlernen einer Sprache wie Pascal wird ein Programmieranfänger auch nicht Quicksort (wieder)entdecken. SprachdesignBeim Design einer QPL geht es nicht um Fragen der Numerik: die Simulation eines Quantenrechners mit n qubits bedeutet im wesentlichen den Umgang mit 2n × 2n -Matrizen über C, bildet also - von der Größe der Matrizen abgesehen - im Prinzip kein Problem, wenn man jederzeit Zugriffe auf den Simulatorzustand zulässt. Es soll vielmehr eine Sprache geschaffen werden, die konventionelle programmiersprachliche Konstrukte zum Teil übernimmt und gleichzeitig anreichert um spezifische Funktionen eines Quantenrechners. Korrektes Design impliziert insbesondere natürlich, dass die Gesetze der Quantenphysik beachtet werden, so dass also ein angeschlossener Simulator durch einen Quantenrechner ausgetauscht werden könnte unter Beibehaltung der Schnittstelle. Man kann daher über Design einer QPL nicht sprechen, wenn nicht wenigstens ein rudimentäres Bild von der Hardware vorhanden ist. Verwendet wird heute ein Modell, dem eine Master-Slave-Architektur zugrunde liegt: der Master ist ein klassischer Rechner, der über einen „quantum device driver" den eigentlichen Quantenrechner, also ein parametrisiertes physikalisches Quantenexperiment, steuert (Quantum Random Access Machine, QRAM, Zitate zu Details in [5]).Das eigentliche Programm läuft auf dem klassischen Rechner, für den die einzige blockierende Aktion eine am Quantenrechner ausgelöste Messung ist mit einer Rücksendung des Messergebnisses. In diesem Modell ist der Quantenrechner also anzusprechen wie eine exotische Hardware, eine in der Informatik nicht ganz ungewöhnliche Situation. Das Design einer QPL setzt voraus, dass zunächst mehrere Grundsatzentscheidungen getroffen werden.
Mehrere der bereits realisierten Möglichkeiten sind im nächsten Abschnitt beschrieben. Ein aus Sicht der Informatik besonders attraktiv erscheinender Weg besteht sicherlich in einer Schnittstellendefinition des Quantenrechners als abstraktem Datentyp (ADT), ein Ansatz, der zuerst von Bettelli et al. [1] auf der Basis von C++ detailliert ausgearbeitet worden ist. Der Ansatz wird allerdings kontrovers diskutiert (Zitate in [5]).Für konkrete Programmierarbeiten bedeutet ein derartiger ADT-basierter Zugang, dass ein Programmierer, der auf der Basis dieser Schnittstelle ein syntaktisch korrektes Programm schreibt, jedenfalls nichts programmieren kann, was gegen Gesetze der Quantenphysik verstößt. Jede Aktion auf der Schnittstelle belässt das System, gegebenenfalls also repräsentiert durch den angeschlossenen Simulator, in einem physikalisch realisierbaren Quantenzustand. Existierende ImplementierungenAus Sicht der Physik ist der Ablauf eines Algorithmus auf einem Quantenrechner ein Experiment an einem Quantensystem. Zu diesem gehören eine initiale Zustandspräparation und die abschließende Messung des Zustands. Die zeitliche Zustandsentwicklung dazwischen wird nach den Regeln der Quantenmechanik durch unitäre Transformationen im Raum der Zustände, einem Hilbert-Raum, beschrieben. Jede Implementierung einer QPL muss auf diesen theoretischen Grundlagen aufsetzen. Die zur Zeit am weitesten ausgearbeiteten Implementierungen von QPLs sind QCL von B. Ömer [4] und Q language von Bettelli et al. [1]. QCL ist eine eigene C/Pascal-ähnliche prozedurale interpretierte Sprache, die neben den klassischen Konstrukten einer traditionellen klassischen Sprache auch Sprachkonstrukte enthält, die sich spezifisch auf den Quantenrechner beziehen. Prozedural bedeutet hier insbesondere, dass nichttriviale unitäre Operationen Funktionen in der Sprache sind. Zu den spezifischen Sprachkonstrukten gehören insbesondere das automatische Speichermanagement, welches im Zusammenhang mit der Allokation lokaler qubits wie auch bei der Berechnung von Werten von Funktionen eine Rolle spielt, wenn temporäre Register benötigt werden. Eine einfache Freigabe von Speicherplatz wie bei dem klassischen „garbage collection" reicht nicht; die temporären Register müssen in einen definierten Zustand zurückversetzt werden, um die Interferenzeigenschaften des Systems nicht zu zerstören (auch als Bennett-style uncomputation bezeichnet). Die Idee stammt aus Arbeiten (u.a. von C. H.Bennett) zu der Frage, wie klassische Schaltkreise aus rein reversibel arbeitenden Bauelementen aufgebaut werden können. In QCL wird dieses Speicher-Management in einer für den Programmierer transparenten Weise durchgeführt. Im Unterschied zu QCL ist die Sprache Q language von Bettelli et al. [1] eine Sammlung von C++-Klassen, die Quantenoperationen als Objekte bereitstellt. Die eigentliche Programmierung besteht daher in einer konventionellen objektorientierten Entwicklung von C++-Programmen auf der Basis dieser Bibliothek. Der Hauptvorteil dieses Ansatzes ist nach Meinung der Autoren, dass damit - analog zu Techniken für die Vereinfachung klassischer Schaltkreise - zusammengesetzte Operationen automatisch vereinfacht werden können, bevor das Quantenprogramm vom Master an den Slave übermittelt wird. Beide Ansätze kann man ansehen als Hochsprachen, die als eine Art Erweiterung einen Assembler auf Quantenebene enthalten: man geht in jedem Fall z.B. direkt mit (Quanten)registern um. Eine Reihe von Autoren stellen eher theoretische Aspekte in den Vordergrund; dazu gehört insbesondere die formale Definition einer Semantik. Das wesentliche Argument dafür ist, dass das Verhalten von Quantensystemen hochgradig nichtintuitiv ist, so dass im Prinzip eine formale Programm-Verifikation gegen eine Spezifikation erreichbar sein sollte. Von P. Selinger [7] stammt eine solche neue funktionale Sprache, die insbesondere über eine formal definierte Semantik verfügt. Programme können hier alternativ graphisch oder textuell dargestellt werden. Van Tonder [8] führt frühere Arbeiten fort, in denen der Lambda-Kalkül für Zwecke des Quantum computing erweitert wird; hierzu gibt es auch einen in Scheme implementierten Simulator. Die Sprache qGCL von J. W.Sanders und P. Zuliani [6] ist eine Spezifikationssprache, ,ebenfalls mit einer formal definierten Semantik, die auf der probabilistischen Sprache pGCL beruht. Diese basiert ihrerseits auf GCL („guarded command language"),einer Sprache, die von Dijkstra geschaffen wurde, um Korrektheitsbeweise von Programmen führen zu können. Die Arbeiten, eine für Quantenrechner angemessene Programmiersprache zu definieren, werden zur Zeit von vielen Autoren in verschiedenen Richtungen weiter verfolgt. Nach dem derzeitigen Stand kann man feststellen, dass die Sprachen QCL von Ömer sowie Q language von Bettelli et al., die beide mit Simulatoren verbunden sind, sich sehr gut dazu eignen, eigene Experimente zu unternehmen. Der Schwerpunkt der anderen erwähnten. Arbeiten liegt eher auf der theoretischen Seite; dazu gehört insbesondere die Formulierung einer Semantik zur spezifizierten Sprache. Weitere Details und Beispiele sowie eine ausführliche Zitatenliste zu QPLs findet sich unter [5]. Eine breite Basis für den Einstieg in die wesentlich allgemeinere Thematik Quanteninformationstheorie bietet die www-Seite des Instituts für mathematische Physik der TU Braunschweig [3]. DanksagungIch danke R. F. Werner und der Arbeitsgruppe an seinem Lehrstuhl im Institut für Mathematische Physik (IMaPh) der TU Braunschweig für die freundliche Aufnahme und viele hilfreiche, klärende Diskussionen zu Fragen der Quanteninformationstheorie. |
Hinweis: Die URLs entsprechen dem Stand bei der Veröffentlichung des Artikels und werden nicht aktualisiert. |