Der 18-jährige Yuvin Tan hat bewiesen, dass klassische Computer das „Empfehlungsproblem“ fast so schnell lösen können wie Quantencomputer. Dieses Ergebnis macht eines der besten Beispiele für die Quantenbeschleunigung von Berechnungen ungültig.
Ein Teenager aus Texas belagerte die Entwicklung des Quantencomputers. In einem Artikel, der diesen Monat im Internet veröffentlicht wurde
, hat der 18-jährige Yuvin Tan bewiesen, dass gewöhnliche Computer ein wichtiges Rechenproblem mit einer Geschwindigkeit lösen können, die
möglicherweise mit Quantencomputern
vergleichbar ist .
In seiner praktischsten Form hängt das Empfehlungsproblem damit zusammen, wie Dienste wie Amazon und Netflix bestimmen, welche Produkte Ihnen gefallen könnten. Informatiker betrachteten es als
eines der besten Beispiele für Aufgaben, die auf Quantencomputern exponentiell schneller gelöst werden könnten - was die potenziellen
Fähigkeiten dieser futuristischen Maschinen hervorhob. Und jetzt widerlegte Tan diese Meinung.
"Es war eines der bestimmenden Beispiele für Quantenbeschleunigung - und jetzt ist es verschwunden", sagt Tang, der im Frühjahr seinen Abschluss an der University of Texas in Austin gemacht hat und sein Herbst-Doktoratsstudium an der Washington University beginnt.
Im Jahr 2014, im Alter von 14 Jahren, sprang Tang durch die Klassen 4, 5 und 6 und ging an die University of Texas, wo er Mathematik und Informatik studierte. Im Frühjahr 2017 belegte Tan einen Kurs in Quanteninformation, der von
Scott Aaronson , einem bekannten Forscher auf dem Gebiet des Quantencomputers, unterrichtet wurde. Aaronson erkannte einen ungewöhnlich talentierten Studenten in Tan und lud ihn ein, sein Berater in einem unabhängigen Forschungsprojekt zu werden. Aaronson gab Tan mehrere Aufgaben zur Auswahl, einschließlich der Ausgabe von Empfehlungen. Tan wählte sie etwas widerstrebend.
"Ich zögerte, weil es ziemlich kompliziert schien, aber es war die einfachste aller Aufgaben, die er mir vorschlug", sagte Tan.
Ziel der Empfehlungen ist es, Empfehlungen zu Produkten abzugeben, die dem Benutzer gefallen könnten. Betrachten Sie Netflix. Er weiß, welche Filme Sie gesehen haben. Er weiß, was Millionen seiner Benutzer gesehen haben. Ist es mit diesen Informationen möglich herauszufinden, wonach Sie weiter suchen möchten?
Diese Daten können in Form eines riesigen Rasters oder einer Matrix dargestellt werden, auf der alle Filme aufgelistet sind, auf der Seite alle Benutzer und im Inneren Werte, die messen, wie sehr jeder Benutzer jeden Film mochte. Ein guter Algorithmus erstellt eine Liste mit Empfehlungen, erkennt schnell und genau die Ähnlichkeiten zwischen Filmen und Benutzern und füllt die leeren Zellen der Matrix aus.
2016 veröffentlichten die Informatiker
Iordanis Kerenidis und
Anupam Prakash einen
Quantenalgorithmus , der das Empfehlungsproblem exponentiell schneller löste als jeder der bekannten klassischen Algorithmen. Sie erhielten eine solche Quantenbeschleunigung insbesondere aufgrund der Vereinfachung des Problems. Anstatt die gesamte Matrix auszufüllen und das einzig beste zu empfehlende Produkt zu ermitteln, haben sie eine Möglichkeit gefunden, Benutzer in eine kleine Anzahl von Kategorien zu unterteilen - mögen sie Blockbuster oder unabhängiges Kino? - und die vorhandenen Daten so verarbeiten, dass eine Empfehlung abgegeben wird, die einfach ganz gut wäre.
Als die Arbeit von Kerenidis und Prakash erschien, gab es nur sehr wenige Beispiele für Probleme, die Quantencomputer exponentiell schneller lösen sollten als klassische. Diese Aufgaben waren größtenteils spezialisiert - enge Probleme, die speziell entwickelt wurden, um die Stärken von Quantencomputern auszunutzen (einschließlich des Problems der „
Korrelation “, über das wir bereits geschrieben haben). Die Arbeit von Kerenidis und Prakash war interessant, weil sie ein echtes Problem hervorhob, das für Menschen wichtig ist und bei dem Quantencomputer die klassischen überholten.
"Aus meiner Sicht war dies eines der ersten Beispiele für maschinelles Lernen und Big Data-Verarbeitung, bei denen wir gezeigt haben, dass Quantencomputer etwas können, was wir mit klassischen Methoden noch nicht können", sagte Kerenidis, Spezialist für Informatik vom Pariser Institut für Informatikforschung.
Kerenidis und Prakash haben bewiesen, dass ein Quantencomputer das Problem der Empfehlungen exponentiell schneller lösen kann als jeder der bekannten Algorithmen, aber sie haben nicht bewiesen, dass es keinen schnellen klassischen Algorithmus gibt. Als Aaronson 2017 mit Tan zusammenarbeitete, stellte er genau diese Aufgabe - das Fehlen eines schnellen klassischen Algorithmus zu beweisen und die Quantenbeschleunigung von Kerenidis und Prakash zu bestätigen.
"Es schien mir, dass dies ein wichtiger Punkt sein würde, um diese Geschichte zu vervollständigen", sagte Aaronson, der zu dieser Zeit glaubte, dass es keinen schnellen klassischen Algorithmus gibt.
Tang begann seine Arbeit im Herbst 2017 in der Hoffnung, dass die Aufgabe der Empfehlungen Gegenstand seiner Dissertation sein würde. Mehrere Monate lang versuchte Tan, die Unmöglichkeit der Existenz eines klassischen Algorithmus zu beweisen. Die Zeit verging und Tan begann zu glauben, dass es vielleicht einen solchen Algorithmus gab.
"Ich begann an die Existenz des klassischen Algorithmus zu glauben, aber ich konnte mich nicht davon überzeugen, weil Scott dachte, dass er nicht existierte und er eine Autorität für mich war", sagte Tan.
Schließlich, als die Frist für die Dissertation bereits abgelaufen war, schrieb Tan einen Brief an Aaronson, in dem er seinen wachsenden Verdacht gestand. "Tan hat mir im Wesentlichen Folgendes geschrieben: Ich denke, es gibt einen schnellen klassischen Algorithmus", sagte Aaronson.
Während des gesamten Frühlings schrieb Tang die Ergebnisse auf und arbeitete mit Aaronson zusammen, um einige Schritte des Beweises zu klären. Der von Tan entdeckte schnelle klassische Algorithmus wurde von dem schnellen Quantenalgorithmus inspiriert, den Kerenidis und Prakash zwei Jahre zuvor gefunden hatten. Tan zeigte, dass die in ihrem Algorithmus verwendete Quantenabtastung unter klassischen Bedingungen reproduziert werden kann. Der Tan-Algorithmus wurde wie der Kerenidis- und Prakash-Algorithmus in polylogarithmischer Zeit ausgeführt - das heißt, die Berechnungszeit wurde durch den Logarithmus von Parametern wie der Anzahl der Benutzer und Produkte geschätzt - und war exponentiell schneller als jeder andere der zuvor bekannten klassischen Algorithmen.
Nachdem Tan den Algorithmus fertiggestellt hatte, wollte Aaronson vor der Veröffentlichung sicherstellen, dass er korrekt war. "Ich war immer noch nervös darüber, dass sich der erste große Job in Tans Karriere als zilch herausstellen wird, wenn sich Tans Veröffentlichung der Arbeit als falsch herausstellt", sagte Aaronson.
Aaronson plante, im Juni an einem Quantencomputer-Workshop an der University of California in Berkeley teilzunehmen. Dort sollten sich die Leuchten dieses Gebiets versammeln, darunter Kerenidis und Prakash. Aaronson lud Than mit nach Berkeley ein, um seinen Algorithmus nach dem offiziellen Teil der Konferenz informell vorzustellen.
Am Morgen des 18. und am Morgen des 19. Juni hielt Tan zwei Vorträge und beantwortete Fragen des Publikums. Nach vier Stunden war ein Konsens erreicht: Der klassische Tan-Algorithmus sieht aus wie der richtige. Was viele der Anwesenden nicht verstanden, war, wie jung Tan war. "Ich wusste nicht, dass Yuvin 18 Jahre alt ist, und es schien mir aus den Ergebnissen der Gespräche nicht so. Es schien mir, dass Juvin als erwachsener Mann ein Gespräch führte “, sagte Kerenidis. Jetzt wird der Algorithmus vor seiner Veröffentlichung einer formellen Begutachtung unterzogen.
Für das Quantencomputing ist das Tan-Ergebnis ein Rückschritt. Oder nicht. Tang beseitigte eines der verständlichsten und besten Beispiele für Quantenvorteile. Gleichzeitig ist Tans Arbeit ein weiterer Beweis für die Existenz einer
fruchtbaren Wechselwirkung zwischen Studien klassischer und Quantenalgorithmen.
„Tang eliminiert die Quantenbeschleunigung von Kerenidis und Prakash, aber in einem anderen Sinne trägt Tang zu einer großen Verbesserung bei und basiert auf ihrer Arbeit. Tang hätte sich niemals seinen klassischen Algorithmus ausgedacht, wenn sie ihr Quantum nicht veröffentlicht hätten “, sagte Aaronson.