Quantenprogrammiersprachen
Algorithmen für Quantenrechner wie der Faktorisierungsalgorithmus von Shor lassen sich mittels neuer Programmiersprachen formulieren, die neben konventionellen auch über für Quantenrechner spezifische Sprachkonstrukte verfügen. In Verbindung mit Simulatoren kann man so auch bereits heute Programme für Quantenrechner entwickeln und testen.
Quantensysteme 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 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 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.
Sprachdesign
Beim 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. 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.
- Soll eine gänzlich neue Sprache geschaffen werden oder wird eine konventionelle Sprache in ihrer Funktionalität über eine Bibliothek erweitert?
- Welcher Sprachfamilie soll die Sprache angehören?
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. auf der Basis von C++ detailliert ausgearbeitet worden ist. Der Ansatz wird allerdings kontrovers diskutiert. 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 Implementierungen
Aus 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 und Q language von Bettelli et al.. 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. 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 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 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 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. 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.
Danksagung
Ich 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.
Literatur
- Bettelli S., Calarco T., Serafini L.: Toward an architecture for quantum programming. Eur Phys J D 25(2):181-200 (2003)
http://arXiv.org/abs/cs.PL/0103009 - Hertrampf U.: Quantencomputer. Informatik Spektrum 23(5):322-324 (2000)
- Institut für mathematische Physik (IMaPh), TU Braunschweig.
http://www.imaph. tu-bs.de/qi/ - Ömer B.: Classical concepts in quantum programming, 2002.
http://tph.tuwien. ac.at/~oemer/papers.html - Rüdiger R.: Quantum Programming Languages - A Survey, 2003.
http://cms.fh-wolfenbuettel.de/fb/i/organisation/personal/ ruediger/
talks/QPLSeminar.IMaPh.pdf - Sanders J. W., Zuliani P.: Quantum programming. In: Mathematics of Program Construction, volume 1837 of LNCS. Heidelberg: Springer 2000, pp. 80-99.
http://web.comlab.ox.ac.uk/oucl/publications/tr/tr-5-99.html - Selinger P.: Towards a quantum programming language. Mathematical Structures in Computer Science (im Druck)
http://quasar.mathstat.uottawa.ca/~selinger/papers.html#qpl - Tonder A. van: A lambda calculus for quantum computation. 2003.
http://arxiv.org/abs/quant-ph/0307150
Hinweis: Die URLs entsprechen dem Stand bei der Veröffentlichung des Artikels und werden nicht aktualisiert.
Autor und Copyright
Prof. Dr. R. Rüdiger
FH Braunschweig/Wolfenbüttel,
Salzdahlumer Str. 46/48,
38302 Wolfenbüttel
Fachbereich Informatik
r.ruediger@fh-wolfenbuettel.de
DOI 10.1007/s00287-003-0350-0
© Springer-Verlag 2003