Wie viel schneller kann ein Quantencomputer sein, wenn seine Eingaben keine erkennbare Struktur haben? Ein Forschungsteam von Physical Superintelligence (PSI) hat einen Beweis für eine langjährige Vermutung vorgestellt, die diese Frage in einem theoretischen Modell eingrenzt. Nach Angaben des Unternehmens entstand der Beweis mit einem KI-Forschungssystem und wurde vom Beweisassistenten Lean überprüft.
Der angekündigte Befund betrifft eine genau definierte Art von Aufwand: wie oft ein Algorithmus seine Eingabe abfragen muss. Er besagt nicht, dass Quantencomputer bei jeder praktischen Aufgabe nur einen kleinen Vorteil haben. Gerade Aufgaben mit besonderer Struktur bleiben ein eigener Fall.
Die Frage hinter dem Beweis
In der Informatik lässt sich die Schwierigkeit eines Problems auf verschiedene Arten messen. Eine davon zählt, wie oft ein Programm Informationen aus einer Eingabe lesen muss. Man kann sich die Eingabe als lange Folge aus Nullen und Einsen vorstellen. Eine klassische Abfrage liest dabei eine Stelle. Eine Quantenabfrage kann sich im mathematischen Modell auf eine Überlagerung mehrerer Stellen beziehen.
Aus dieser besonderen Möglichkeit folgt aber nicht, dass alle Daten auf einmal als lesbare Antwort vorliegen. Die Frage ist vielmehr, ob ein Quantenalgorithmus für eine bestimmte Ja-Nein-Frage sehr viel weniger solcher Abfragen benötigt als ein klassischer Algorithmus.
Die Informatiker Scott Aaronson und Andris Ambainis formulierten dazu eine Vermutung über mathematische Funktionen. In ihrer ursprünglichen Arbeit zeigten sie: Wenn diese Vermutung stimmt, lässt sich jeder Quantenalgorithmus mit T Abfragen auf den meisten Eingaben durch ein klassisches Verfahren nachahmen, das höchstens eine feste Potenz von T Abfragen benötigt. Das Modell betrachtet also Abfragen, nicht die gesamte Rechenzeit eines realen Computers.
Warum Struktur den Unterschied machen kann
Bei manchen Aufgaben steckt in der Eingabe ein besonderes Muster. Ein Quantenalgorithmus kann solche Struktur unter Umständen ausnutzen. Bei zufällig gewählten Eingaben sind solche seltenen Muster dagegen normalerweise nicht vorausgesetzt. Hier sollte nach der Vermutung ein exponentieller Vorsprung bei der Zahl der Abfragen auf den meisten Eingaben ausbleiben.
Ein polynomialer Unterschied kann dennoch erheblich sein: Wenn ein Verfahren beispielsweise eine Zahl von Schritten benötigt, die mit dem Quadrat statt linear wächst, verändert sich der Abstand mit der Größe der Aufgabe. Die theoretische Aussage grenzt die Art des Wachstums ein. Sie liefert keine Stoppuhr für einen bestimmten Chip und sagt auch nichts darüber, ob ein bestimmter heutiger Quantencomputer eine Aufgabe praktisch schneller löst.
Bereits im August hatte ein Team um Guy Blanc einen Spezialfall für parallele Quantenalgorithmen untersucht. Dort ist die Zahl der aufeinanderfolgenden Abfragerunden begrenzt. Der neue Anspruch von PSI geht über diese Einschränkung hinaus und betrifft die zugrunde liegende Vermutung.
Welche Rolle KI und Lean spielten
In der Ankündigung vom 6. November beschreibt PSI ein intern entwickeltes Forschungssystem, das Instanzen eines nicht öffentlich verfügbaren Anthropic-Modells verwendete. Demnach lag am dritten Tag eines Laufs ein vollständiger Beweis vor; anschließend verbesserte das System das Ergebnis. PSI veröffentlichte das Manuskript und die formale Umsetzung.
Lean ist ein Beweisassistent: Eine mathematische Aussage und ihre Beweisschritte werden so formuliert, dass Software ihre logische Verknüpfung nach festen Regeln überprüfen kann. Das ist ein starkes Werkzeug gegen Fehler in formalisierten Schritten. Ob die formulierte Aussage die ursprüngliche mathematische Frage vollständig und richtig erfasst und wie das Ergebnis einzuordnen ist, bleibt auch eine Aufgabe für Fachleute.
PSI nennt David Turturean als Verantwortlichen für die Entwicklung des Forschungssystems, die Aufgabenstellung und die Prüfung des Manuskripts. Das Unternehmen berichtet außerdem, dass die Autoren der Stanford-Vorarbeit den Beweis lesen und kommentiert haben. Eine abgeschlossene unabhängige Begutachtung wird in der Ankündigung nicht ausgewiesen. Für die Einordnung zählt deshalb sowohl die formale Prüfung als auch die weitere fachliche Auseinandersetzung mit dem veröffentlichten Beweis.
Quellen
- Physical Superintelligence: A proof of the Aaronson-Ambainis conjecture, 6. November 2026.
- Scott Aaronson und Andris Ambainis: The Need for Structure in Quantum Speedups, 2009.
- Guy Blanc und weitere: Quantum Speedups Require Structure or Depth, 2026.
Für diesen Artikel wurden KI-gestützte Recherche- und Editierwerkzeuge verwendet. Der Inhalt wurde redaktionell geprüft.
