Schließlich gab es ein Problem, das nur Quantencomputer lösen können

Seit Jahren suchen Informatiker nach Aufgaben eines bestimmten Typs, die nur ein Quantencomputer lösen könnte, aber selbst von zukünftigen Generationen kein klassischer Computer. Und so fanden sie einen von ihnen.

In den frühen Stadien der Untersuchung von Quantencomputern stellten Informatiker eine Frage, deren Antwort ihrer Meinung nach eine tiefe Wahrheit über die Fähigkeiten dieser futuristischen Maschinen enthüllen sollte. 25 Jahre später wurde eine Antwort darauf gefunden. In einem im Mai 2018 veröffentlichten Artikel haben die Informatiker Ren Rez und Avishai Tal überzeugende Beweise dafür geliefert, dass die Rechenleistung von Quantencomputern alles übertrifft, was klassische Computer erreichen können.

Rez, Professor an der Princeton University und am Wiseman Institute of Science, sowie Tal, Postdoc an der Stanford University, identifizierten eine bestimmte Art von Rechenproblem. Mit einer Einschränkung haben sie bewiesen, dass Quantencomputer das Problem effektiv lösen können, und herkömmliche Computer würden für immer stecken bleiben und versuchen, dies zu tun. Informatiker haben seit 1993 nach einem solchen Problem gesucht, als sie erstmals die BQP-Aufgabenklasse identifizierten, die alle Aufgaben enthält, die ein Quantencomputer lösen kann.

Seitdem hofften sie, die als PH bekannte BQP-Aufgabenklasse gegenüberzustellen, die alle Aufgaben umfasst, die auf jedem klassischen Computer ausgeführt werden können, selbst die unglaublich fortschrittlichen, die von einer Zivilisation der Zukunft entwickelt wurden. Die Möglichkeit eines solchen Kontrasts hing davon ab, ein Problem zu finden, das zur BQP-Klasse, nicht aber zur PH-Klasse gehörte. Und jetzt haben Rez und Tal es geschafft.

Dieses Ergebnis macht Quantencomputer aus praktischer Sicht nicht besser als klassische. Erstens wissen theoretische Informatiker bereits, dass Quantencomputer in der Lage sind, alle Aufgaben zu lösen, zu denen klassische fähig sind. Und Ingenieure haben Mühe, das Problem der Schaffung einer nützlichen Quantenmaschine zu lösen. Aber die Arbeit von Reza und Tal zeigt den Unterschied in den Kategorien, in denen sich Quanten- und klassische Computer befinden - und dass selbst in einer Welt, in der klassische Computer die Grenzen aller Träume überschritten haben, Quantencomputer ihnen immer noch voraus sein können.

Quantenklassen

Die Grundaufgabe der theoretischen Informatik besteht darin, Aufgaben in Komplexitätsklassen zu unterteilen. Die Komplexitätsklasse enthält alle Aufgaben, die mit einer bestimmten Ressource wie Zeit oder Speicher gelöst werden können.

Wissenschaftler haben zum Beispiel einen effektiven Algorithmus entdeckt, der prüft, ob eine Zahl eine Primzahl ist. Sie konnten jedoch keinen effektiven Algorithmus zum Auffinden von Primfaktoren großer Zahlen finden. Daher glauben sie (obwohl sie es nicht beweisen konnten), dass diese beiden Probleme zu verschiedenen Komplexitätsklassen gehören.

Zwei berühmte Schwierigkeitsgrade sind P und NP. P sind alle Aufgaben, die ein klassischer Computer schnell lösen kann. (Das Problem "Ist die Zahl Primzahl?" Gehört zu P). NP umfasst alle Aufgaben, die ein klassischer Computer nicht unbedingt schnell löst, sondern die Richtigkeit der vorhandenen Lösung, die er schnell überprüfen kann. ("Was sind Primfaktoren einer Zahl?" Gehört zu NP). Wissenschaftler glauben, dass die Klassen P und NP unterschiedlich sind, aber die Aufgabe, diesen Unterschied zu beweisen, ist das schwierigste und wichtigste der offenen Probleme in diesem Bereich.


Ein PH enthält einen NP, der P enthält. Ist der BQP eine von PH getrennte Klasse?

1993 definierten die Informatiker Ethan Bernstein und Umesh Wazirani eine neue Komplexitätsklasse, die sie BQP oder "Quantenpolynomzeit mit Begrenzung der Fehlerwahrscheinlichkeit" nannten. Sie definierten die Klasse so, dass sie alle Entscheidungsaufgaben enthält - Aufgaben mit der Antwort „Ja“ oder „Nein“ -, die Quantencomputer effektiv lösen können. Etwa zur gleichen Zeit haben sie bewiesen, dass Quantencomputer alle Aufgaben lösen können, zu denen klassische fähig sind. Das heißt, BQP enthält alle in P enthaltenen Aufgaben.

Ein weiteres Beispiel für einzelne Aufgabenklassen. Das Verkäuferproblem fragt, ob ein Weg durch bestimmte Städte kürzer als eine bestimmte Entfernung ist. Eine solche Aufgabe ist in NP. Eine schwierigere Aufgabe fragt, ob diese Entfernung der kürzeste Weg durch diese Städte ist. Eine solche Aufgabe ist in PH.

Sie konnten jedoch nicht feststellen, ob der BQP Aufgaben enthält, die nicht zu einer anderen wichtigen Aufgabenklasse gehören, die als PH oder „Polynomhierarchie“ bezeichnet wird. PH ist eine Verallgemeinerung von NP. Es enthält alle Aufgaben, die Sie erhalten können, indem Sie mit einer Aufgabe von NP beginnen und diese komplizieren, indem Sie klarstellende Aussagen wie „ob“ und „für alle“ hinzufügen. Klassische Computer können die meisten Probleme aus PH immer noch nicht lösen, aber diese Klasse kann als eine Klasse von Problemen angesehen werden, die klassische Computer lösen könnten, wenn sich herausstellen würde, dass P gleich NP ist. Mit anderen Worten, um BQP und PH zu vergleichen, muss festgestellt werden, ob Quantencomputer einen Vorteil gegenüber klassischen Computern haben. Dies bleibt auch dann bestehen, wenn klassische Computer plötzlich lernen, viel mehr Probleme zu lösen, als sie heute lösen können.

"PH ist eine der einfachsten Komplexitätsklassen, die es gibt", sagte Scott Aaronson , IT-Spezialist an der University of Texas in Austin. "Wir wollen also den Ort des Quantencomputers in einer Welt klassischer Komplexität kennenlernen."

Der beste Weg, die beiden Schwierigkeitsklassen zu trennen, besteht darin, ein Problem zu finden, das nachweislich in einer von ihnen enthalten ist und nicht in der anderen. Aufgrund einer Kombination aus grundlegenden und technischen Hindernissen war eine solche Aufgabe jedoch sehr schwer zu finden.

Um eine Aufgabe zu finden, die zu BQP gehört, aber nicht zu PH, müssen Sie etwas definieren, auf das "ein klassischer Computer per Definition die Antwort nicht einmal effektiv überprüfen konnte, ganz zu schweigen davon, sie zu finden", sagte Aaronson. "Dadurch entfallen die vielen Aufgaben, mit denen wir in der Informatik arbeiten."

Fragen Sie Orakel

Herausforderung. Angenommen, wir haben zwei Zufallszahlengeneratoren, von denen jeder eine Folge von Ziffern erzeugt. Frage an den Computer: Sind diese beiden Sequenzen völlig unabhängig voneinander oder sind sie irgendwie unmerklich miteinander verbunden (wird beispielsweise eine Sequenz durch die Fourier-Transformation der anderen erhalten)? Aaronson führte diese „Furrelation“ -Aufgabe 2009 ein und bewies, dass sie zu BQP gehört. Der zweite, schwierigere Schritt bleibt - zu beweisen, dass die Furrelation nicht in der PH enthalten ist.


Ran rez

In gewisser Hinsicht ist dies genau das, was Resu und Talu getan haben. Ihre Arbeit trennt BQP und PH mit Hilfe der sogenannten " Orakel " oder "Black Box". Dies ist ein häufiges Ergebnis in der Informatik, auf das Forscher zurückgegriffen haben, wenn ihnen das, was sie beweisen wollen, in keiner Weise gegeben wird.

Der beste Weg, die BQP- und PH-Komplexitätsklassen zu trennen, besteht darin, die Rechenzeit zu messen, die erforderlich ist, um Probleme aus jeder Klasse zu lösen. Die Informatik hat jedoch kein "tiefes Verständnis der realen Rechenzeit oder der Fähigkeit, sie zu messen", sagte Henry Youn, Informatiker an der Universität von Toronto.

Stattdessen wird in der Informatik etwas anderes gemessen, von dem angenommen wird, dass es ein Verständnis der Rechenzeit liefert, das nicht direkt gemessen werden kann. Wissenschaftler berechnen die Anzahl der Computeranrufe an das "Orakel", um eine Antwort auf die Frage zu geben. Das Orakel scheint Hinweise zu geben. Wir wissen nicht, wie er sie empfängt, aber wir wissen, dass sie zuverlässig sind.

Wenn Sie herausfinden möchten, ob eine geheime Verbindung zwischen zwei Zufallszahlengeneratoren besteht, können Sie den Orakelfragen wie "Was ist die sechste Nummer jedes Generators?" Stellen. Anschließend müssen Sie die Rechenleistung anhand der Anzahl der Eingabeaufforderungen vergleichen, die von jedem Computer zur Lösung des Problems benötigt werden. Ein Computer, der mehr Hinweise benötigt, läuft langsamer.

„In gewissem Sinne verstehen wir dieses Modell viel besser. Sie spricht mehr über Informationen als über Computer “, sagte Tal.


Avishai Tal

Die neue Arbeit von Reza und Tal beweist, dass ein Quantencomputer weit weniger Hinweise benötigt, um ein Furrelationsproblem zu lösen als ein klassisches. Darüber hinaus benötigt ein Quantencomputer nur einen Hinweis, obwohl PH selbst bei einer unbegrenzten Anzahl von Hinweisen keinen Algorithmus zur Lösung eines solchen Problems hat. "Dies bedeutet, dass es einen äußerst effizienten Quantenalgorithmus gibt, der ein solches Problem löst", sagte Rez. "Aber wenn wir nur klassische Algorithmen betrachten, werden sie selbst dann nicht damit fertig, wenn wir zu den besten Klassen klassischer Algorithmen gelangen." Dies beweist, dass sich Furrelation beim Orakel auf Aufgaben bezieht, die zu BQP gehören, nicht jedoch zu PH.

Rez und Tal haben dieses Ergebnis vor etwa vier Jahren fast erreicht, konnten aber keinen Schritt in die Zukunftssicherung machen. Und dann, nur einen Monat vor der Veröffentlichung, hörte Tal von einer neuen Arbeit über Pseudozufallszahlengeneratoren und erkannte, dass die Technologien aus diesem Artikel nur das geben, was er und Rez brauchten, um ihre eigenen zu beenden. "Es war ein fehlendes Stück", sagte Tal.

Die Nachricht von der Trennung der BQP- und PH-Klassen verbreitete sich schnell. "Die Welt der Quantenkomplexität ist voller Leben", schrieb Lance Fortnau, IT-Spezialist an der Georgia University of Technology am Tag nach der Veröffentlichung der Arbeit.

Die Arbeit gibt eisernes Vertrauen, dass Quantencomputer in einer von den klassischen getrennten Computerwelt existieren (zumindest per Definition mit dem Orakel). Selbst in einer Welt, in der P gleich NP ist - wo das Lösen des Problems des Handlungsreisenden so einfach ist wie das Finden der am besten geeigneten Zeile in der Tabelle - zeigt der Beweis von Reza und Tal, dass es Probleme gibt, die nur ein Quantencomputer lösen kann.

"Selbst wenn P gleich NP wäre, selbst mit einer so starken Annahme", sagte Fortnau, "werden Quantencomputer immer noch nicht aufholen."