Direkt zum Inhalt

Mathematik: Quantencomputer sind grundsätzlich anders

Ein mathematisches Resultat zeigt: Selbst ein unendlich schneller klassischer Computer kann dem Quantenrechner nicht das Wasser reichen.
Berge von Computerplatinen auf einer Müllkippe

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.

Schreiben Sie uns!

4 Beiträge anzeigen

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.