Aaronson-Ambainis-Vermutung
Die Aaronson-Ambainis-Vermutung ist eine offene mathematische Frage aus der Quanteninformatik: Sie behauptet, dass Quantencomputer bei bestimmten Berechnungsproblemen keinen unbegrenzt großen Geschwindigkeitsvorteil gegenüber klassischen Computern haben können. Bleibt sie unbewiesen, lässt sich die wahre Stärke von Quantenalgorithmen nicht vollständig einschätzen.
Die Aaronson-Ambainis-Vermutung ist eine offene Frage der theoretischen Informatik, benannt nach den Forschern Scott Aaronson und Andris Ambainis, die sie 2009 formulierten. Sie dreht sich darum, wie viel schneller ein Quantencomputer — ein Rechner, der die Regeln der Quantenmechanik ausnutzt — gegenüber einem gewöhnlichen Computer sein kann, wenn er eine bestimmte Art von Funktion berechnet. Die Vermutung behauptet: Der mögliche Vorsprung ist immer begrenzt, nie unbegrenzt groß. Das klingt technisch, hat aber weitreichende Folgen dafür, wo Quantencomputer wirklich nützlich sind und wo nicht.
Die Grenze der Quantenbeschleunigung
Quantencomputer gelten als deutlich mächtiger als klassische Computer — aber das stimmt nicht pauschal für jedes Problem. Bei manchen Aufgaben bringen sie enorme Vorteile, bei anderen kaum einen Unterschied. Die Aaronson-Ambainis-Vermutung versucht, diese Grenze präzise zu beschreiben.
Konkret geht es um sogenannte boolesche Funktionen: Rechenprobleme, bei denen die Eingabe aus vielen Ja-Nein-Entscheidungen besteht und am Ende ebenfalls Ja oder Nein herauskommt. Solche Probleme tauchen überall auf, von der Datenbanksuche bis zur Kryptografie. Die Vermutung sagt: Wenn ein Quantencomputer bei einer solchen Funktion deutlich schneller ist, dann muss es einen nachvollziehbaren strukturellen Grund dafür geben — und dieser Grund ist stets messbar.
Das ist keine Selbstverständlichkeit. Ohne diese Einschränkung wäre es denkbar, dass Quantencomputer bei bestimmten Problemen exponentiell schneller sind, ohne dass man je erklären könnte, warum. Die Vermutung schließt genau dieses unkontrollierbare Szenario aus — sofern sie sich als wahr herausstellt.
Was hinter der Vermutung steckt
Um die Vermutung zu verstehen, braucht man den Begriff der Sensitivität. Die Sensitivität einer booleschen Funktion misst, wie viele Eingaben man verändern muss, bis sich das Ergebnis ändert. Eine Funktion mit hoher Sensitivität reagiert schon auf kleine Änderungen. Die Aaronson-Ambainis-Vermutung sagt, vereinfacht ausgedrückt: Je empfindlicher eine Funktion ist, desto kleiner ist der maximale Quantenvorteil beim Berechnen dieser Funktion.
Der Beweis ist bis heute nicht gelungen. Man hat zwar gezeigt, dass die Vermutung für viele spezielle Klassen von Funktionen gilt, aber den allgemeinen Fall konnte noch niemand beweisen oder widerlegen. Das macht sie zu einem der zentralen offenen Probleme der Quantenkomplexitätstheorie — dem Gebiet, das untersucht, welche Probleme wie schwer sind.
Ein verwandtes Problem, die sogenannte Sensitivitätsvermutung über klassische Computer, galt jahrzehntelang ebenfalls als ungelöst — bis Hao Huang sie 2019 mit einem eleganten, nur zweiseitigen Beweis schloss. Das hat Forscher ermutigt: Manchmal reicht ein neuer Blickwinkel, um ein festgefahrenes Problem zu lösen. Für die Aaronson-Ambainis-Vermutung steht dieser Durchbruch noch aus.
Wo die Vermutung in der Praxis eine Rolle spielt
Für die Entwicklung echter Quantenalgorithmen ist die Vermutung ein wichtiger Orientierungsrahmen. Wenn Ingenieure und Forscher neue Algorithmen für Quantencomputer entwerfen, müssen sie abschätzen, bei welchen Problemen sich der Aufwand lohnt. Die Vermutung gibt dabei eine theoretische Leitplanke: Bestimmte Arten von Beschleunigung sind schlicht nicht möglich — oder sollten es zumindest nicht sein.
In der Nachrichtenberichterstattung taucht sie meist dann auf, wenn Unternehmen wie Google oder IBM neue Quantenprozessoren ankündigen und behaupten, bestimmte Probleme exponentiell schneller lösen zu können. Kritiker prüfen solche Behauptungen unter anderem daran, ob sie mit der Aaronson-Ambainis-Vermutung vereinbar sind. Wenn ein angeblicher Quantenvorteil nicht erklärbar wäre, ist er wahrscheinlich keiner.
Scott Aaronson selbst betreibt dazu den einflussreichen Blog Shtetl-Optimized, auf dem er solche Behauptungen regelmäßig öffentlich einordnet. Die Vermutung ist also nicht nur Theorie im Elfenbeinturm — sie ist ein aktives Werkzeug zur kritischen Einschätzung realer Produkte und Ankündigungen.