Zwei Mathematiker haben ein mathematisches Problem entdeckt, das kein noch so starker klassischer Computer jemals lösen wird, ein Quantencomputer aber recht einfach bewältigt – und damit gezeigt, dass Quantenrechner nicht nur leistungsfähiger sind, sondern grundsätzlich überlegen. Wie Ran Raz vom Weizmann-Institut and Avishay Tal von der Stanford University berichten, lässt sich die Frage, ob zwei scheinbar zufällige Zahlenreihen eine versteckte Gemeinsamkeit haben, zwar durch einen Quantenalgorithmus lösen – ein klassischer Computer kann eine solche Antwort jedoch nicht einmal bestätigen. Nach diesem Ergebnis ist der Quantencomputer tatsächlich etwas grundsätzlich Neues.

Seit den frühen 1990er Jahren grübeln Fachleute über diese Frage. Hintergrund sind die Komplexitätsklassen PH, die P und NP umfasst und die ein hypothetischer unendlich leistungsfähiger klassischer Computer lösen könnte, und BQP, die ein realer Quantencomputer lösen kann. Gibt es Probleme, die in BQP sind, aber nicht in PH? Raz und Tal sagen ja. Ihre neue Veröffentlichung enthält den Beleg, dass das Problem klassischen Methoden nicht zugänglich ist, also selbst auf einem unendlich schnellen klassischen Computer unendlich lange dauern würde. Dass es einen Quantenalgorithmus zur Lösung des Problems gibt, ist dagegen einfacher zu beweisen und schon länger bekannt.

Da die für ein Problem nötige Rechenzeit sehr schwer theoretisch zu bestimmen ist, überführten die beiden Mathematiker es mit einem Trick in ein Problem, bei dem man stattdessen die nötige Zusatzinformation misst. Dieses als »Orakel« bezeichnete Verfahren misst die Menge an Tipps, die ein Computer braucht, um das Problem zu lösen. Die Anzahl dieser Tipps ist ein Maß für die nötige Rechenzeit. Demnach würde ein klassischer Computer die Aufgabe nicht einmal mit unendlich vielen Tipps des Orakels lösen können – der Quantenalgorithmus braucht lediglich einen einzigen. Stimmt das Ergebnis, so wären Quantencomputer sogar dann überlegen, wenn klassische Computer bisher unzugängliche Probleme wie das des Handlungsreisenden oder die Primfaktorzerlegung verbreiteter Verschlüsselungsalgorithmen bewältigen könnten.