1994 fand ein Mathematiker heraus, wie man einen Quantencomputer dazu bringt, etwas zu tun, was kein gewöhnlicher klassischer Computer kann. Die Arbeit zeigte, dass eine auf den Regeln der Quantenmechanik basierende Maschine im Prinzip eine große Zahl effizient in ihre Primfaktoren zerlegen könnte – eine Aufgabe, die für einen klassischen Computer so schwierig ist, dass sie die Grundlage für einen Großteil der heutigen Internetsicherheit bildet.
Eine Welle des Optimismus folgte. Vielleicht, dachten die Forscher, können wir Quantenalgorithmen erfinden, die eine Vielzahl unterschiedlicher Probleme lösen können.
Aber der Fortschritt stockte. "Es war ein bisschen wie ein Mist Trajektorie", sagte Ryan O'Donnell der Carnegie Mellon University. „Die Leute sagten: ‚Das ist erstaunlich, ich bin sicher, wir werden alle möglichen anderen erstaunlichen Algorithmen bekommen.' Nö." Wissenschaftler entdeckten dramatische Beschleunigungen nur für eine einzige, enge Klasse von Problemen innerhalb eines Standardsatzes NP genannt, d. h. sie verfügten über effizient überprüfbare Lösungen – wie Factoring.
Das war fast drei Jahrzehnte lang so. Dann im April Forscher erfunden ein grundlegend neuartiges Problem, das ein Quantencomputer exponentiell schneller lösen können soll als ein klassischer. Es beinhaltet die Berechnung der Eingaben für einen komplizierten mathematischen Prozess, der ausschließlich auf seinen durcheinandergebrachten Ausgaben basiert. Ob das Problem allein steht oder das erste in einer neuen Grenze von vielen anderen ist, muss noch bestimmt werden.
„Es gibt ein Gefühl der Aufregung“, sagte er Vinod Vaikuntanathan, Informatiker am Massachusetts Institute of Technology. "Viele Leute denken darüber nach, was es sonst noch gibt."
Informatiker versuchen zu verstehen, was Quantencomputer besser können, indem sie mathematische Modelle untersuchen, die sie darstellen. Oft stellen sie sich ein Modell eines Quanten- oder klassischen Computers gepaart mit einer idealisierten Rechenmaschine namens Orakel vor. Orakel sind wie einfache mathematische Funktionen oder Computerprogramme, die eine Eingabe aufnehmen und eine vorbestimmte Ausgabe ausspucken. Sie könnten ein zufälliges Verhalten haben und „Ja“ ausgeben, wenn die Eingabe in einen bestimmten zufälligen Bereich fällt (z. B. 12 bis 67), und „Nein“, wenn dies nicht der Fall ist. Oder sie können periodisch sein, sodass eine Eingabe zwischen 1 und 10 „ja“ zurückgibt, 11 bis 20 „nein“, 21 bis 30 wieder „ja“ ergibt und so weiter.
Nehmen wir an, Sie haben eines dieser periodischen Orakel und kennen die Periode nicht. Alles, was Sie tun können, ist, es mit Zahlen zu füttern und zu sehen, was es ausgibt. Wie schnell könnte ein Computer mit diesen Einschränkungen den Punkt finden? 1993 fand Daniel Simon, damals an der Universität von Montreal, heraus, dass ein Quantenalgorithmus die Antwort auf ein eng verwandtes Problem exponentiell schneller berechnen kann als jeder klassische Algorithmus.
Das Ergebnis ermöglichte es Simon, einen der ersten Hinweise darauf zu ermitteln, wo eine dramatische Überlegenheit von Quantencomputern zu erwarten war. Aber als er sein Papier bei einer führenden Konferenz einreichte, wurde es abgelehnt. Das Papier interessierte jedoch ein junges Mitglied des Programmkomitees der Konferenz – Peter Schor, der damals in den Bell Laboratories in New Jersey arbeitete. Shor fand weiter heraus, dass er Simons Algorithmus anpassen konnte, um die Periode eines Orakels zu berechnen, falls es eines hatte. Dann erkannte er, dass er den Algorithmus noch einmal anpassen könnte, um eine Gleichung zu lösen, die sich ähnlich wie ein periodisches Orakel verhält: die Gleichung, die das Faktorisieren beschreibt, das periodisch ist.
Shors Ergebnis war historisch. Der von ihm entdeckte Quantenalgorithmus könnte riesige Zahlen schnell in ihre Primfaktoren zerlegen, was kein bekannter klassischer Algorithmus kann. In den Folgejahren entdeckten Forscher weitere effiziente Quantenalgorithmen. Einige von ihnen, wie Shors Algorithmus, lieferten sogar einen exponentiellen Vorteil, aber niemand konnte einen dramatischen Quantenvorteil bei einem NP-Problem nachweisen, das nicht periodisch war.
Dieser Mangel an Fortschritt veranlasste zwei Informatiker, Scott Aaronson der University of Texas, Austin, und Andris Ambainis der Universität von Lettland, um eine Bemerkung zu machen. Beweise für Quantenvorteile schienen immer von Orakeln abhängig zu sein, die eine Art nicht zufälliger Struktur hatten, wie etwa Periodizität. 2009 haben sie vermutet dass es keine dramatischen Beschleunigungen bei NP-Problemen geben konnte, die zufällig oder unstrukturiert waren. Niemand konnte eine Ausnahme finden.
Ihre Vermutung schränkte die Leistungsfähigkeit von Quantencomputern ein. Aber es sagte nur, dass es keine dramatischen Beschleunigungen für eine bestimmte Art von unstrukturierten NP-Problemen gab – diejenigen mit Ja- oder Nein-Antworten. Wenn ein Problem darin bestand, spezifischere, quantitative Antworten zu finden, was als Suchproblem bezeichnet wird, traf die Vermutung nicht zu.
In diesem Sinne, Forscher Takashi Yamakawa von NTT Social Informatics Laboratories und Markus Zhandry von NTT Research und der Princeton University beschlossen, mit einem bestimmten Suchproblem zu experimentieren, das 2005 von eingeführt wurde Oded Regev.
Stellen Sie sich eine Reihe von Wetterfahnen vor, die alle in die gleiche Richtung zeigen. Geben Sie jedem von ihnen einen gemessenen Schubs, dann lassen Sie einen böigen Wind ihre Richtung beeinflussen. Regev wollte auf der Grundlage ihrer endgültigen Richtungen feststellen, wohin sie alle ursprünglich zeigten. Probleme wie dieses wurden als „Lernen mit Fehlern“ bezeichnet, weil der Schub und der Wind wie eine Quelle zufälliger Fehler in der ursprünglichen Richtung wirken. Es gibt Hinweise darauf, dass es sowohl für klassische als auch für Quantenalgorithmen schwer zu lösen ist.
Yamakawa und Zhandry optimierten das Setup. Sie modifizierten die Stärke dieser Startstöße und machten sie vorhersehbarer. Sie ließen auch den Wind von einem zufälligen Orakel bestimmen, so dass er in bestimmten Fällen noch zufälliger war, in anderen jedoch vollständig ruhte.
Mit diesen Modifikationen entdeckten die Forscher, dass ein Quantenalgorithmus die anfängliche Richtung effizient finden könnte. Sie bewiesen auch, dass jeder klassische Algorithmus um einen exponentiellen Faktor langsamer sein muss. Wie Shor passten sie dann ihren Algorithmus an, um eine reale Version des Problems zu lösen, die das Orakel durch eine tatsächliche mathematische Gleichung ersetzt.
Informatiker arbeiten immer noch daran, das Problem zu verstehen und darauf aufzubauen. Vaikuntanathan vergleicht es mit einem anderen, das bei der Datenkomprimierung auftritt: Wenn Informationen komprimiert werden, können versehentlich zwei Bits an die gleiche Stelle gequetscht und überschrieben werden. Das Problem, diese Kollisionen im Voraus vorherzusagen, damit Sie sie vermeiden können, weist eine gewisse Ähnlichkeit auf. „Das ist eine Klasse von Problemen, die im Grunde so aussehen“, sagte er. „Vielleicht lassen sich diese Probleme quantentechnisch lösen.“
Es gab Hoffnungen, dass ein unstrukturiertes Problem wie das neue sogar auf den heutigen jungen Versionen von Quantencomputern lösbar sein könnte, wodurch ein Mittel bereitgestellt würde, sie zu testen. Die Überlegung war, dass unstrukturierte Probleme möglicherweise weniger Ressourcen zum Programmieren benötigen oder weniger empfindlich auf Rauschen reagieren, da sie bereits zufällig sind. Aber bisher scheint das neue Problem noch zu weit fortgeschritten zu sein, als dass bestehende Quantencomputer es lösen könnten. „Es ist ein seltsames Problem. Ich hatte nicht daran gedacht, es zu definieren“, sagte Aaronson. „Aber im Nachhinein hat es einige sehr nette Features.“
Das Ergebnis liefert das erste Beispiel eines dramatischen Quantenvorteils bei einem unstrukturierten NP-Problem. Könnte es noch viele andere Probleme geben, die die Quantenwelt von praktisch unlösbar zu lösbar verändern? Es gibt jetzt mehr Grund, dies zu glauben.
"Es hat unsere Überzeugungen darüber, für welche Arten von Problemen Quantencomputer gut sein könnten, etwas auf den Kopf gestellt", sagte O'Donnell.
