Stellen Sie sich ein Round-Robin-Turnier vor, bei dem jeder Teilnehmer genau einmal gegen jeden anderen Teilnehmer antritt, wobei es keine Unentschieden gibt. Das Ergebnis eines solchen Wettbewerbs ist eine vollständige Karte darüber, wer wen geschlagen hat. Aus dieser Karte versuchen Mathematiker und Informatiker, die „Gewinner“ mithilfe verschiedener Regeln zu identieren. Einige Regeln suchen nach der Person, die alle anderen direkt besiegt hat; andere suchen nach der Person, die jeden anderen in nur zwei Schritten erreichen kann; wieder andere suchen nach der Gruppe von Menschen, die als Team alle außerhalb der Gruppe stehenden Personen besiegt haben. Diese Regeln werden als Turnierlösungen bezeichnet. In der realen Welt wissen wir das Ergebnis nicht jedes Spiels sofort; vielleicht müssen wir ein neues Experiment durchführen oder eine neue Umfrage starten, um zu erfahren, wer in einem bestimmten Paar gewonnen hat. Dies erzeugt ein Rätsel: Wie viele Spiele müssen wir überprüfen, um die Gewinner zu ermitteln? Lange Zeit schien die Antwort zu lauten, dass wir fast jedes einzelne Spiel überprüfen müssten – eine Zahl, die mit zunehmender Größe des Turniers sehr schnell ansteigt. Dies ist die klassische Sicht auf das Problem.

Ein Team von Forschern am Indian Institute of Technology Gandhinagar hat diese Frage nun unter Verwendung der Werkzeuge des Quantencomputings neu aufgerollt. Anstatt die Spiele einzeln zu überprüfen, haben sie gefragt, wie viele Spiele ein Quantencomputer prüfen müsste, um die Gewinner zu finden. Quantencomputer können viele Möglichkeiten gleichzeitig betrachten, eine Fähigkeit, die es oft ermöglicht, Probleme viel schneller zu lösen als klassische Maschinen. Die Forscher fanden heraus, dass die Antwort vollständig davon abhängt, welche Regel man zur Auswahl eines Gewinners verwendet. Für einige Regeln bietet der Quantencomputer eine massive Beschleunigung und muss nur einen winzigen Bruchteil der Spiele überprüfen. Für andere Regeln ist der Quantenvorteil viel geringer, und für eine spezifische Regel bietet der Quantencomputer gar keinen Geschwindigkeitsvorteil und erfordert genauso viele Überprüfungen wie ein klassischer Computer.

Die Studie konzentrierte sich auf mehrere Standardwege, um einen Gewinner zu definieren. Am einfachsten zu finden, in der Quantenwelt, ist der Top-Zyklus (Top Cycle). Dies ist die kleinste Gruppe von Spielern, die als Team alle anderen besiegen. Die Forscher zeigten, dass ein Quantenalgorithmus diese Gruppe identifizieren kann, indem er eine Anzahl von Spielen prüft, die in etwa proportional zur Anzahl der Spieler wächst. Dies ist eine signifikante Verbesserung gegenüber der klassischen Anforderung, die mit dem Quadrat der Anzahl der Spieler wächst. Um diese Gruppe zu finden, ordnet der Quantenalgorithmus zuerst alle Spieler basierend auf ihren Siegen in einer einzigen Linie an, ein Prozess, der dem Sortieren eines Kartendecks ähnelt. Er nutzt dann eine Divide-and-Conquer-Strategie (Teile-und-herrsche), um genau zu bestimmen, wo die Gewinngruppe in dieser Linie endet. Dieser Ansatz ist so effizient, dass er auch ein verwandtes Problem löst: die Bestimmung, ob das gesamte Turnier stark zusammenhängend ist, was bedeutet, dass jeder Spieler jeden anderen durch eine Kette von Siegen erreichen kann.

Im Gegensatz dazu wird das Finden eines einzelnen „Condorcet-Gewinners“ – eines Spielers, der jeden anderen direkt besiegt – für einen Quantencomputer sogar noch einfacher. Die Forscher demonstrierten, dass ein solcher Spieler gefunden werden kann, indem man eine Anzahl von Spielen prüft, die proportional zur Quadratwurzel der Anzahl der Spieler ist. Dies ist eine dramatische Reduktion gegenüber der klassischen Anforderung. Die Methode besteht darin, zuerst einen „King“ zu finden – einen Spieler, der jeden anderen in höchstens zwei Schritten erreichen kann – und dann zu prüfen, ob dieser King irgendwelche Niederlagen hat. Wenn der King keine Niederlagen hat, ist er der Condorcet-Gewinner; wenn er Verluste hat, existiert kein solcher Gewinner. Dieses Ergebnis bestätigt, dass die Quantenmechanik für diesen spezifischen Typ von Gewinner eine leistungsstarke Abkürzung bietet.

Die Geschichte ändert sich jedoch, wenn das Ziel darin besteht, die „Copeland-Menge“ zu finden, die aus allen Spielern besteht, die die höchste Anzahl an Siegen haben. Hier bewiesen die Forscher, dass ein Quantencomputer keinen Vorteil gewinnt. Um die gesamte Menge der Spitzenscorer zu finden, muss der Quantencomputer immer noch eine Anzahl von Spielen prüfen, die proportional zum Quadrat der Anzahl der Spieler ist, genau wie ein klassischer Computer. Dies ist ein überraschendes Ergebnis, da das Finden nur eines dieser Spitzenscorer für einen Quantencomputer viel einfacher ist. Die Schwierigkeit ergibt sich daraus, dass die Identifizierung der gesamten Menge ein extrem präzises Zählen der Siege jedes Spielers erfordert – eine Aufgabe, die nicht in gleicher Weise von der parallelen Suchleistung der Quantenmechanik profitiert wie das Finden eines einzelnen Ziels.

Die Forscher untersuchten auch die „uncovered set“ (unbedeckte Menge), die Spieler umfasst, die jeden anderen in zwei Schritten oder weniger erreichen können. Sie fanden heraus, dass das Finden dieser gesamten Gruppe schwieriger ist als das Finden eines einzelnen solchen Spielers, aber einfacher als das Finden der vollständigen Copeland-Menge. Ein Quantencomputer muss eine Anzahl von Spielen prüfen, die proportional zur Anzahl der Spieler hoch 1,5 ist. Dies platziert die „uncovered set“ in einen Mittelweg und zeigt, dass die Schwierigkeit einer Turnierlösung nicht einheitlich ist: Manche sind einfach, manche sind schwer, und der Quantenvorteil variiert entsprechend.

Um diese Grenzen zu beweisen, entwickelte das Team neue mathematische Argumente. Sie entwarfen spezifische, schwierige Turnierszenarien, die darauf ausgelegt sind, jeden Algorithmus zu überlisten, damit er viele Spiele überprüfen muss. Indem sie zeigten, dass selbst ein Quantencomputer diese spezifischen Rätsel nicht ohne eine bestimmte Mindestanzahl an Prüfungen lösen kann, etablierten sie feste untere Schranken für den Arbeitsaufwand. Für das Problem, den Spieler mit den meisten Siegen zu finden, lieferten sie einen frischen, in sich geschlossenen Beweis für eine bekannte Grenze und zeigten auf, dass die Schwierigkeit aus der Notwendigkeit des Zählens und nicht bloß des Suchens resultiert. Ihre Arbeit klärt, dass Quantencomputer zwar leistungsstark sind, aber kein Zauberstab sind, der jede Art von Berechnung beschleunigt. Der Geschwindigkeitsvorteil hängt von der spezifischen Struktur des Problems ab, und im Falle von Turnierlösungen bestimmen die Regeln für die Auswahl des Gewinners, ob die Quantenmaschine wirklich glänzen kann.