Das Empfehlungsproblem ist ein tatsächliches alltägliches Problem, das Onlineshops und Streamingdienste lösen müssen. Dabei handelt es sich um Algorithmen, die Nutzern vergleichbare Produkte vorschlagen – wir kennen diese Empfehlungen beispielsweise von Amazon oder Netflix. Um diese Empfehlungen zu generieren, ist erhebliche Rechenleistung notwendig, der Algorithmus selbst läuft auf teuren Quantencomputern deutlich performanter als auf gewöhnlicher Hardware. Dieses Problem gilt als führendes Beispiel zum Nachweis der Leistungsfähigkeit der futuristischen Computersysteme.
“Dies war eines der definitivsten Beispiele für eine Quantenbeschleunigung, und es existiert nicht mehr.”, sagte Tang, der im Frühjahr an der University of Texas, Austin, graduierte und im Herbst an der University of Washington promovieren wird. Das Wunderkind übersprang bereits im Alter von 14 drei Klassen in der Schule und schrieb sich an der UT Austin ein. Er studierte dort Mathematik und Informatik. Im Frühjahr 2017 nahm Tang an einer Vorlesung über Quanteninformation teil, die von Scott Aaronson, einem prominenten Forscher im Bereich Quantencomputer, unterrichtet wurde. Aaronson erkannte Tang als außergewöhnlich talentierten Studenten und bot sich als Berater für ein unabhängiges Forschungsprojekt an. Aaronson gab seinem Studenten einige Probleme zur näheren Analyse zur Auswahl – Tang entschied sich für das Empfehlungsproblem.
Das Empfehlungsproblem soll eine Empfehlung für Produkte geben, die dem Anwender gefallen könnten. Nehmen wir das Beispiel Netflix: Der Dienst weiß, welche Filme wir gesehen haben. Ebenso weiß er, was alle anderen Millionen von Nutzern gesehen haben. So werden Tendenzen generiert und schließlich in Empfehlungen umgewandelt. Wie wir auch wissen, gibt es einige zusätzliche Rahmenbedingungen, die das System mit sich bringen. So oder so legt Netflix die Priorität beispielsweise auf Eigenproduktionen.
Wir finden Musik auch ohne Empfehlungen
Rein technisch wird das komplette Verhalten als große Matrix dargestellt. Auf der einen Seite gibt es die Filme und Serien, auf der anderen Seite die Nutzer. Ein guter Algorithmus würde Empfehlungen generieren, indem er schnell und genau Ähnlichkeiten zwischen Filmen und Benutzern erkennt und die Lücken in der Matrix ausfüllt.
Im Jahr 2016 veröffentlichten die Informatiker Iordanis Kerenidis und Anupam Prakash einen Quantenalgorithmus, der das Empfehlungsproblem exponentiell schneller löste als bis dahin. Diese Quantenbeschleunigung erreichten sie unter anderem durch die Vereinfachung des Problems: Anstatt die gesamte Matrix auszufüllen, entwickelten sie eine Möglichkeit, die Nutzer in Kategorien einzuteilen. Damit sind Kategorien wie Genres gemeint – darf es lieber Horror oder doch ein Liebesfilm sein?
“Für mich war es eines der ersten Beispiele für maschinelles Lernen und große Datenmengen, bei dem wir gezeigt haben, dass Quantencomputer etwas können, das wir noch nicht klassisch hinbekommen”, sagte Kerenidis, ein Informatiker am Forschungsinstitut für Grundlagen der Informatik in Paris.
Was damit nicht bewiesen wurde: Dass kein schneller klassischer Algorithmus fernab der Anwendung auf Quantencomputern existiert. Tang zäumte das Pferd eigentlich von hinten auf. Er wollte den Beweis für die Arbeit aus 2016 antreten und zeigen, dass es keinen schnellen klassischen Empfehlungs-Algorithmus gibt. Der Beweis schlug letztlich fehl – Tang fand einen neuen Algorithmus. Er zeigte, dass die Art von Quantenstichprobentechniken, die sie in ihrem Algorithmus verwendeten, in einer klassischen Umgebung reproduziert werden konnte. Die Geschwindigkeit ist dabei vergleichbar.
Intel will Quantencomputer für jeden
Quantencomputer sind teuer und deren Anwendung ist häufig strittig. Immer wieder gibt es Spezialprobleme, bei denen diese Art von Computern deutlich bessere Leistung erzielt – dabei handelt es sich aber um Nischenanwendungen. Ein Lichtblick war das Empfehlungsproblem, damit wurde die Existenz dieser Systeme jetzt zwei Jahre lang größtenteils gerechtfertigt. Diese Zeit ist aber vorbei – ob Quantencomputer ausgedient haben? Wahrscheinlich nicht. Vielmehr befeuern solche Beweise die Wissenschaft nur weiter. Jetzt muss ein neuer Algorithmus für Quantencomputer gefunden werden der, vielleicht, wieder alles andere in den Schatten stellt.
Via Quantummagazin
