Simons Problem photonisch gelöst
Erstmals gelingt Implementierung des Suchalgorithmus in einem Quantencomputer aus optischen Komponenten.
Quantencomputer versprechen für viele Anwendungen große Vorteile gegenüber konventionellen Rechenmaschinen. Wenn man sich die Überlagerungszustände von Quanten- oder Qubits zunutze macht, werden bestimmte Rechenoperationen deutlich schneller als bei herkömmlichen Computern, die streng binär funktionieren. Insbesondere Suchalgorithmen gelten als gute Kandidaten für das Quantencomputing. Eine solche Anwendung ist bekannt als Simons Problem. Daniel Simon entwickelte diesen Algorithmus vor zwanzig Jahren eigens, um die besonderen Fähigkeiten von Quantencomputern zu testen. Denn auf einem solchen sollte er exponentiell schneller laufen als auf klassischen Computern.
Abb.: Optischer Aufbau des Quantenalgorithmus. (Bild: M. S. Tame et al., APS)
Bei Simons Problem geht es darum herauszufinden, ob eine unbekannte Funktion einen eineindeutigen Output auf einen bestimmten Input liefert oder ob auch mehrere Eingaben zur selben Antwort führen können. Im Fall einer 2:1-Abbildung ist der Algorithmus auch in der Lage, die Differenz zwischen den Variablen festzustellen. Im klassischen Fall muss man die „black box“ allerdings exponentiell häufiger befragen als im Quantenfall.
Wissenschaftlern der University of KwaZulu-Natal in Südafrika ist es nun gelungen, diesen Algorithmus quantenoptisch zu implementieren. Laserpulse eines Titan-Saphir-Lasers mit einer Wellenlänge von 724,5 Nanometern und 8 Nanometern Pulslänge splitteten die Forscher zunächst mithilfe von Strahlteilern auf und modulierten sie mit verschiedenen Filtern. Doppelbrechende photonische Kristallfasern erzeugten schließlich über spontanes four-wave-mixing verschränkte Photonenpaare, mit denen die Forscher den Quantenalgorithmus ausführen konnten.
Mit diesem Aufbau konnten die Forscher die theoretischen Erwartungen hervorragend experimentell bestätigen. Zudem benötigt diese Implementierung auch keine grundlegenden Modifikationen für verschiedene black-box-Funktionen, sondern nur kleine Änderungen am Messprogramm. Bei diesem Experiment reichten sechs Qubits aus, um einen Vorteil gegenüber klassischen Algorithmen zu erzielen. Der Quantenalgorithmus löste die Aufgabe in drei Vierteln der Schritte, die man mit konventioneller Logik benötigt.
Dies ist nicht nur die erste experimentelle Umsetzung von Simons Problem; sie erlaubt auch eine Erweiterung auf mehr Qubits und damit in Bereiche, in denen der Unterschied zwischen klassischem und Quantencomputing relevant wird. Der Aufbau eignet sich jedoch nicht als Quantencomputer im eigentlichen Sinn, da er nicht frei programmierbar ist, sondern lediglich den Algorithmus von Simons Problem umsetzt.
Noch gibt es zwar keine praktischen Anwendungen für Simons Problem. Der Algorithmus ist eher für die Grundlagen der Quanteninformatik von Interesse und dient dem Nachweis der besonderen Eigenschaften von Quantencomputern. Das Ergebnis macht aber Hoffnung, dass auch anwendungsnähere Algorithmen wie etwa der Shor-Algorithmus sich in einem Quantencomputer implementieren lassen.
Dirk Eidemüller
Weitere Infos
Weitere Beiträge
PH