In der Welt der Informatik sind manche Probleme nicht nur schwierig, sondern eine ganz spezifische Art von Unmöglichkeit für traditionelle Maschinen, sie schnell zu lösen. Dies sind sogenannte restriktive Optimierungsprobleme. Stellen Sie sich vor, Sie planen die Lieferroute für eine Flotte von Lastwagen. Sie müssen jeden Kunden genau einmal besuchen, die Gewichtsgrenzen einhalten und so schnell wie möglich fertig werden. Die Anzahl der möglichen Routen ist so gewaltig, dass selbst die leistungsstärksten Supercomputer länger als das Alter des Universums bräuchten, um sie alle einzeln zu prüfen. Jahrzehntelang hofften Wissenschaftler, dass Quantencomputer, die die seltsamen Regeln von subatomaren Teilchen nutzen, um Informationen zu verarbeiten, diese Komplexität durchbrechen könnten. Aktuelle Quantenmaschinen sind jedoch verrauscht und fehleranfällig. Sie liefern oft Antworten, die mathematisch unmöglich sind, wie etwa eine Route, die dieselbe Stadt zweimal besucht oder einen Stopp ganz auslässt. Die große Frage war, ob diese unvollkommenen Maschinen dennoch Teil eines zuverlässigen Systems sein können, das eine gute Lösung in einer angemessenen Zeit garantiert.

Ein Forscherteam hat diese Frage nun beantwortet, indem es eine vollständige Pipeline aufgebaut hat, die einen verrauschten Quantencomputer mit einem klassischen Computer kombiniert, um diese schwierigen Probleme zu lösen. Sie konzentrierten sich auf einen speziellen Typ von Quantenalgorithmus namens Constraint-Enhanced QAOA, der darauf ausgelegt ist, die Regeln des Problems zu respektieren, während er nach der besten Antwort sucht. Ihre Arbeit zeigt, dass selbst wenn die Quantenmaschine aufgrund von Rauschen Fehler macht, ein cleveres klassisches Computerprogramm diese Fehler sofort korrigieren kann. Durch das Überprüfen der Quantenausgabe, das Reparieren etwaiger defekter Routen und das Bewerten der Ergebnisse kann das System die optimale Lösung mit hoher Konfidenz finden. Die Forscher haben mathematisch bewiesen, dass dieser hybride Ansatz in Polynomialzeit funktioniert, was bedeutet, dass die Zeit, die zum Lösen des Problems benötigt wird, in einer handhabbaren Rate wächst, wenn das Problem größer wird, anstatt ins Unendliche zu explodieren.

Der Kern ihrer Entdeckung liegt darin, wie die Quanten- und die klassischen Teile zusammenarbeiten. Der Quantencomputer fungiert als Sampler, der eine riesige Anzahl potenzieller Lösungen generiert. Aufgrund des Rauschens in der Maschine sind viele dieser Stichproben fehlerhaft; sie könnten die Regeln des Problems verletzen, wie etwa zwei Lastwagen derselben Straße zuzuweisen oder eine Stadt un besucht zu lassen. In der Vergangenheit hätten Wissenschaftler diese schlechten Stichproben einfach verworfen, aber das würde die Bemühungen des Quantencomputers verschwenden. Stattdessen entwickelten die Forscher eine Methode, bei der der klassische Computer als Reparaturwerkstatt fungiert. Er nimmt jede einzelne Stichprobe, selbst die defekten, und nutzt eine bekannte mathematische Technik, um sie zu reparieren. Wenn einer Route eine Stadt fehlt oder sie Duplikate enthält, ordnet der klassische Computer den Pfad neu an, um ihn wieder gültig zu machen, wodurch sichergestellt wird, dass jede Stadt genau einmal besucht wird. Dieser Reparaturprozess ist schnell und deterministisch, was bedeutet, dass er immer ein gültiges Ergebnis liefert.

Sobald die Stichproben repariert sind, bewertet das System sie, um zu sehen, welche die beste ist. Die Forscher zeigten, dass der Quantencomputer, wenn er korrekt abgestimmt ist, von Natur aus eine höhere Anzahl guter Lösungen als schlechter produziert, selbst in einer verrauschten Umgebung. Sie zeigten, dass das System garantiert die perfekte Lösung findet, wenn man den Quantenkreis oft genug durchläuft. Sie bewiesen, dass die Anzahl der Male, die die Maschine laufen muss, um die Antwort zu finden, in einer vorhersehbaren Weise mit der Problemgröße ansteigt. Das bedeutet, dass es sich bei der Methode nicht um einen glücklichen Zufall handelt, sondern um einen rigorosen Algorithmus mit Leistungsgarantien. Das Team bezeichnet dies als ein „fully polynomial randomized approximation scheme“ – ein technischer Begriff dafür, dass es sich um eine zuverlässige, schnelle Methode zur Findung nahezu perfekter Antworten auf schwierige Probleme handelt.

Um ihre Theorie zu testen, nahmen die Forscher ihren Algorithmus mit auf echte Hardware. Sie verwendeten einen 127-Qubit-Quantenprozessor von IBM, eine Maschine, die derzeit verfügbar ist, aber immer noch unter erheblichem Rauschen leidet. Sie wandten ihr System auf eine Reihe von Traveling-Salesman-Problemen an, bei denen das Ziel darin besteht, die kürzeste Route zu finden, die eine bestimmte Anzahl von Städten besucht. Die Probleme reichten von kleinen Instanzen mit 1zględlich 16 logischen Variablen bis hin zu größeren mit 100. Trotz der verrauschten Umgebung funktionierte das System. Der Quantencomputer generierte einen Strom von Rohdaten, von denen die meisten ungültig waren. Der klassische Reparatur-Schritt reparierte dann jede einzelne dieser ungültigen Routen. Die Endergebnisse waren beeindruckend: Bei den kleineren Problemen stimmte das System perfekt mit den besten bekannten Lösungen überein. Bei den größeren, schwierigeren Problemen fand das System sogar Routen, die besser waren als die zuvor veröffentlichten Referenzlösungen.

Die Forscher untersuchten auch, wie sie diesen Prozess noch schneller machen könnten. Sie erkannten, dass der Quantencomputer dazu neigt, ein paar sehr häufige Antworten und viele seltene zu produzieren. Anstatt jede einzelne reparierte Route zu überprüfen, entwickelten sie eine Filter-Methode, die sich nur auf die häufigsten Kandidaten konzentriert. Dieser „Heavy-Hitter“-Ansatz reduzierte die Arbeit des klassischen Computers drastisch und senkte die Zeit, die zur Verarbeitung der Ergebnisse benötigt wurde, ohne die Garantie zu verlieren, die beste Antwort zu finden. Diese Verfeinerung macht die gesamte Pipeline viel effizienter und deutet darauf an, dass sie in Zukunft auf noch größere Probleme skalieren könnte.

Ein entscheidender Teil ihrer Arbeit war der Beweis, dass dieser Vorteil tatsächlich vom Quantencomputer selbst kommt und nicht nur vom klassischen Reparatur-Schritt. Sie zeigten, dass ein rein klassischer Computer scheitern würde, wenn er versuchen würde, dieselbe Aufgabe zu erledigen – also zufällige Routen zu generieren und dann zu reparieren, um die optimale Lösung effizient zu finden. Die Fähigkeit des Quantencomputers, seine Wahrscheinlichkeit auf die besten Lösungen zu konzentrieren, ist das, was den Unterschied macht. Ohne diese Quanten-Verzerrung (Bias) wäre der klassische Reparatur-Schritt auf der Suche nach der Nadel im Heuhaufen. Die Studie stellt fest, dass die Quantenmaschine den entscheidenden Vorsprung liefert, während der klassische Computer sicherstellt, dass das Ergebnis nutzbar ist.

Die Ergebnisse deuten auf eine neue Art des Denkens über das Quantencomputing hin. Anstatt auf perfekte, fehlerfreie Maschinen zu warten, die vielleicht erst in Jahrzehnten verfügbar sein werden, zeigt diese Arbeit, dass wir bereits heute leistungsstarke Werkzeuge bauen können, indem wir verrauschte Quanten-Sampler mit robustem klassischem Repair kombinieren. Das System erfordert nicht, dass die Quantenmaschine perfekt ist; sie muss lediglich in Richtung der richtigen Antwort verzerrt sein. Indem wir das Rauschen akzeptieren und ein System bauen, das damit umgehen kann, haben die Forscher einen praktischen Weg aufgezeigt, um einige der schwierigsten Optimierungsprobleme in Wissenschaft und Technik zu lösen. Ihre Arbeit auf dem IBM Eagle-r3 Prozessor dient als konkreter Beweis dafür, dass dieser hybride Ansatz nicht nur eine Theorie ist, sondern eine funktionierende Realität, die bereits heute bestehende Benchmarks bei realen Problemen übertreffen kann.