Quantencomputer berechnen das Unberechenbare

D-Wave -Wave 2000 Qubit Processor. Bild: Steve Jurvetson/CC BY-2.0

Forscher zeigen, dass Quantencomputer wirklich etwas Neues sind: Sie lösen ein Problem, an dem jeder klassische Rechner unendlich lange beißen würde

Was ist besonders an Quantencomputern? Ihr atemberaubendes Rechentempo, lautet die gängige Antwort. Demnach können diese künftigen Rechner zwar nicht mehr als herkömmliche Computer, manches aber sehr viel schneller. Für das Zerlegen einer riesigen Zahl in ihre Primfaktoren etwa benötigt ein PC Jahrmilliarden. Ein Quantenrechner, wie er laut Expertenmeinung schon in einem Jahrzehnt verfügbar sein könnte, hingegen nur ein paar Minuten.

Zwei Informatiker zeigen nun aber, dass die Überlegenheit des Quantencomputers über bloße Schnelligkeit hinausgeht. Ran Raz und Avishay Tal haben ein Problem gefunden, das kein normaler Rechner je wird lösen können, selbst wenn er unendlich lange dafür Zeit hätte, ein künftiger Quantencomputer jedoch schon. Demnach spielt der Quantencomputer in einer anderen Liga: Das Wort "berechenbar" überdeckt durch ihn eine größere Anzahl an Problemen - mindestens eines mehr, wie die beiden Forscher zeigen.

Raz, Professor an der Princeton University und am Weizmann Institut in Israel und sein ehemaliger Doktorand Tal, jetzt an der kalifornischen Stanford University, beschäftigen sich mit den Fähigkeiten von Computern. Klassische Rechner können zwar alles berechnen, was sich berechnen lässt, der Aufwand kann sich von Aufgabe zu Aufgabe so sehr unterscheiden, dass manches praktisch unlösbar bleibt.

Ein Beispiel ist das schon genannte Faktorisierungsproblem. Primzahlen lassen sich zwar schnell multiplizieren, auch wenn es vielstellige Zahlen sind. Doch der umgekehrte Weg, ausgehend vom Produkt auf darin enthaltenen Primfaktoren zu schließen, kann sehr schwer werden: Die Zahl der nötigen Rechenschritte wächst unverhältnismäßig mit der Größe der zu zerlegenden Zahl.

So spaltet sich die Welt der berechenbaren Aufgaben in zwei so genannte Komplexitätsklassen: Die erste heißt P und beinhaltet die praktisch lösbaren Probleme, die andere heißt NP und beinhaltet die störrischen Knacknüsse.

Für einen Quantencomputer sind auch einige NP-Probleme praktisch lösbar. Grob gesagt liegt das daran, dass er mehrere Lösungswege parallel ausführen kann, somit z.B. alle möglichen Primfaktoren simultan testen kann. Für den Quantencomputer haben Komlpexitätsforscher daher eine eigene Klasse eingeführt: Sie heißt BQP und umfasst alle Probleme, die ein Quantencomputer schnell lösen kann. BQP enthält P und ragt in NP hinein.

Doch ob das allein schon Überlegenheit bedeutet, bezweifeln Mathematiker. Sie glauben, P und NP könnten in Wirklichkeit deckungsgleich sein. Demjenigen, der das beweist, dürfte der Nobelpreis sicher sein. Er hätte aber auch den Quantencomputer entzaubert. Denn wenn P = NP, dann lassen sich störrische Probleme effizient mit einem normalen Rechner lösen. Der enorme technische Aufwand eines Quantencomputers wäre unnötig.

Die Arbeit von Raz zeigt nun aber, dass der Quantencomputer auch dann noch überlegen wäre. Sie haben ein Problem gefunden, dass weder in P und NP liegt, jedoch in BQP. Ein Hinweis darauf, dass BQP über die beiden hinauslappt.

Hier ist es: Man stelle sich zwei Zufallsgeneratoren vor, die jeweils eine Folge von Zahlen ausspucken. Der Computer soll folgende Frage beantworten: Sind die beiden Folgen wirklich unabhängig voneinander oder gibt es einen versteckten Zusammenhang zwischen den beiden?

Weil es schwer ist, die nötige Zahl von Rechenschritten theoretisch zu bestimmen, greifen die Forscher zu einem Trick: Sie schätzten mit Hilfe eines so genannten "Orakels", wie lange ein normaler Rechner und ein Quantencomputer jeweils brauchen würden, um eine solche Verbindung zu finden. Man kann sich das Orakel als einen Tippgeber vorstellen. Man stellt ihm Fragen wie: "Wie lautet die siebte Ziffer, die jeder der Zufallsgeneratoren ausgibt?" Dann prüften die Forscher, wie viele solcher Hinweise der jeweilige Rechner braucht, um den Zusammenhang zu finden. Das frappierende Ergebnis: Der Quantencomputer braucht nur einen solchen Hinweis, während der klassische Rechner auch mit einer unbegrenzten Anzahl von Tipps noch im Dunkeln stochern würde.

Dass der Quantencomputer in allen Belangen dem klassischen Rechner überlegen sei, bedeutet das Ergebnis indessen nicht. Denn erstens ist unklar, ob Quantencomputer überhaupt alle Probleme in NP effizient lösen können. Forscher wie Scott Aaronson von der University of Texas in Austin glauben das nicht. Auch Quantencomputer müssen programmiert werden und bislang sind nur wenige Quantenalgorithmen bekannt, die harte Nüsse zugänglich machen. Und zweitens haben Raz und Tan lediglich ein klassisch unberechenbares Problem gefunden, das ein Quantenrechner effizient löst. Wie mächtig der Superrechner der Zukunft also wirklich ist, muss sich erst noch zeigen. (Christian J. Meier)

Anzeige