Unveröffentlichtes anthropisches Modell half dabei, die 18 Jahre alte Quantencomputer-Vermutung zu beweisen

Ein vom Startup Physical Superintelligence entwickeltes Forschungssystem, das Instanzen eines nicht-öffentlichen anthropischen Modells verwendet, hat einen vollständigen Beweis der Aaronson-Ambainis-Vermutung erbracht, eines mathematischen Problems, das seit 2008 offen war und sich mit der Frage befasst, wann Quantencomputer exponentielle Vorteile gegenüber klassischen Maschinen erzielen können. Der Beweis wurde vom Lean-Proof-Assistenten akzeptiert, wie aus einem vom Unternehmen veröffentlichten Papier hervorgeht.

Das Ergebnis, über das erstmals von The Quantum Insider berichtet und von Business Insider berichtet wurde, wird von unabhängigen Forschern als Meilenstein für die KI-gestützte Mathematik beschrieben – und als eines der folgenreichsten Ergebnisse, die bisher einem Grenzmodell zugeschrieben werden, das noch nie der Öffentlichkeit zugänglich gemacht wurde. Weitere Informationen zu dieser Geschichte finden Sie in unserer KI-Branchenberichterstattung.

Was die Vermutung sagt

Scott Aaronson und Andris Ambainis stellten die Frage in einer Arbeit, die auf einen Vortrag von Aaronson aus dem Jahr 2008 zurückgeht: Kann ein Quantenalgorithmus immer noch einen exponentiellen Vorteil erzielen, wenn die Eingabe, die er empfängt, keine auszunutzende Struktur hat? Die bekanntesten Quantenbeschleuniger, wie der Faktorisierungsalgorithmus von Peter Shor aus dem Jahr 1994, funktionieren, weil ihre Eingaben sich wiederholende Muster enthalten, die der Algorithmus ausnutzen kann. Die Aaronson-Ambainis-Frage befasst sich mit dem umgekehrten Fall – einheitlich zufälligen, unstrukturierten Eingaben, bei denen solche Muster fehlen.

Um die Frage zu untersuchen, verwenden Forscher das Abfragemodell, das zählt, wie oft ein Algorithmus auf seine Eingabe zugreift und nicht auf jede Operation, die er ausführt. Ein klassischer Algorithmus liest ein Bit pro Abfrage, während eine Quantenabfrage auf eine Überlagerung vieler Eingabepositionen gleichzeitig reagieren kann. Aaronson und Ambainis vermuteten, dass jedes begrenzte Polynom niedrigen Grades – das mathematische Objekt, das die Ausgabewahrscheinlichkeit eines Quantenalgorithmus nach einer bestimmten Anzahl von Abfragen beschreibt – eine Variable mit großem Einfluss haben muss.

Wenn die Vermutung wahr ist, impliziert sie, dass ein Quantenalgorithmus, der T-Abfragen durchführt, durch einen klassischen Algorithmus simuliert werden kann, der bei den meisten Eingaben nur polynomiell viele Abfragen durchführt, was exponentielle Beschleunigungen für unstrukturierte Probleme ausschließt. Die Vermutung wurde unter der Annahme einer formalen Aussage über Polynome bewiesen, aber die Aussage selbst hatte sich 18 Jahre lang einem Beweis widersetzt.

Wie der Beweis gefunden wurde

Laut dem PSI-Blogbeitrag und dem Begleitpapier erbrachte das Forschungssystem am dritten Tag eines Laufs auf der PSI-eigenen Infrastruktur einen vollständigen Beweis. Der Hauptsatz und seine Formulierung der ursprünglichen Vermutung wurden in Lean 4 formalisiert, und der Lean-Kernel – die Softwarekomponente, die jeden logischen Schritt mechanisch überprüft – akzeptierte den Beweis. PSI ordnete daraufhin die systembedingten offenen Probleme zu, was dazu führte, dass das Ergebnis vor der Abnahme der endgültigen Version zweimal verstärkt wurde.

Die aufgezeichnete Prüfung des Repositoriums besagt, dass die formale Entwicklung keine Beweisplatzhalter und keine hinzugefügten Axiome enthält. Die Deklarationen wurden durch den Lean-Kernel und durch Lean4lean, eine unabhängige Implementierung des Lean-Typprüfers, wiedergegeben, und ein Komparator, der beide Kernel nutzte, akzeptierte die vier endgültigen Theoreme. In einem Kontrolltest auf einer zweiten Maschine akzeptierte der Vergleicher eine richtige kleine Lösung und verwarf vier absichtlich falsche.

Der Beweis folgt einer von den Mathematikern Shachar Lovett und Jiapeng Zhang entwickelten Strategie, die auf gebrochenen Zertifikaten und Level-Sets basiert, ersetzt aber eine Ungleichung, die ihr Plan als Vermutung belassen hatte, durch eine neue All-Paar-Ungleichung, die auf einer determinantengenerierten Paarung von Eingabeeinstellungen basiert – eine Konstruktion, die laut PSI über David Reimers früheres Butterfly-Lemma hinausgeht.

Menschliche Aufsicht und überprüfte Grenzen

David Turturean, ein technischer Mitarbeiter des PSI, entwickelte und leitete das Forschungssystem, grenzte das Problem ein, veranlasste das Modell, einen ersten Entwurf zu verfassen, und überprüfte diesen Entwurf; das Repositorium nennt ihn als Verantwortlichen für die Richtigkeit der Arbeit. Jim Halverson prüfte den Beweis und Phiala Shanahan kommentierte die Formalisierung. Aus dem Repository geht hervor, dass KI-Modelle die mathematischen Aussagen, den ersten Entwurf und die Lean-Formalisierung erstellt haben.

Die Verifizierung unterliegt auch expliziten Grenzen, was im Papier des PSI anerkannt wird. Ein menschlicher Leser muss immer noch bestätigen, dass die formale Aussage in Lean mit der gedruckten Vermutung übereinstimmt und dass das für Menschen lesbare Papier selbst nicht maschinell überprüft wird. Der Lean-Kernel, die Definitionen der Mathlib-Bibliothek und die zur Überprüfung verwendeten Maschinen bleiben Teil der vertrauenswürdigen Basis.

Expertenreaktion

Die Ankündigung folgt auf eine Arbeit von Guy Blanc, Jordan Docter, Carmen Strassle und Li-Yang Tan vom August 2026, in der die klassische Simulationskonsequenz für parallele Quantenalgorithmen geklärt wurde – ein Teilergebnis, das hinter der vollständigen Vermutung zurückblieb. Nach Angaben des PSI haben alle vier Forscher die vollständigen Beweise gelesen, Kommentare abgegeben und bereiten eine kürzere, an Experten gerichtete Darstellung vor.

In ihrer vom PSI veröffentlichten Bewertung schrieben die Forscher: „Dies ist ein großartiges Ergebnis. Es löst eine jahrzehntealte Vermutung mit wichtigen Implikationen für die Natur von Problemen auf, die Quantenbeschleunigungen zulassen. Der Beweis stützt sich auf mehrere Arbeitslinien in der Analyse boolescher Funktionen und probabilistischer Kombinatorik und erweitert diese. Alles wird auf eher magische Weise zusammengeführt.“

Was es für das Quantencomputing bedeutet

Für die Quantencomputerforschung verschärft das Theorem die Grenze zwischen Problemen, bei denen Quantenmaschinen helfen können, und Problemen, bei denen sie nicht helfen können. Es weist Algorithmenentwickler auf Probleme hin, deren mathematische oder physikalische Struktur echte Vorteile bietet, anstatt nach Beschleunigungen bei generischen Eingaben zu suchen. Das Ergebnis bestimmt jedoch nicht, welche realen Anwendungen nützliche Beschleunigungen liefern, und das Abfragemodell berücksichtigt nicht den gesamten Arbeitsaufwand für die Datenverarbeitung, sodass es keine allgemeine Grenze für die Gesamtrechenzeit oder den kommerziellen Wert von Quantenmaschinen festlegt.

Das Manuskript und seine Lean-4-Formalisierung sind auf GitHub öffentlich, wo die Community nun versuchen kann, die Übereinstimmung zwischen der formalen Aussage und der ursprünglichen Vermutung zu überprüfen – der verbleibende Schritt, der einen maschinengeprüften Beweis von einem vollständig zertifizierten trennt.

Für Anthropic bietet die Folge eine Vorschau auf Funktionen, die für keine API freigegeben wurden: Das Modell, das die mathematischen Aussagen erstellt hat, bleibt nicht öffentlich, und das Unternehmen hat nicht bekannt gegeben, wann oder ob es ausgeliefert wird.

---

Bleib vorne bei KI

Die neuesten KI-Nachrichten, Analysen und Durchbrüche – alles an einem Ort.

Mehr KI-Nachrichten lesen →