Stel je een round-robin toernooi voor waarbij elke deelnemer precies één keer tegen iedere andere deelnemer speelt, zonder dat er gelijke standen zijn toegestaan. In een dergelijk toponst is de uitkomst een volledige kaart van wie van wie heeft gewonnen. Vanuit deze kaart proberen wiskundigen en informatici de "winnaars" te identificeren met behulp van verschillende regels. Sommige regels zoeken naar de persoon die iedereen direct heeft verslagen; andere zoeken naar de persoon die iedereen in slechts twee stappen kan bereiken; weer andere kijken naar de groep mensen die, als een team, iedereen buiten de groep heeft verslagen. Deze regels worden tournament-oplossingen genoemd. In de echte wereld weten we de uitkomst van elke wedstrijd misschien niet onmiddellijk; misschien moeten we een nieuw experiment uitvoeren of een nieuwe peiling houden om te leren wie er in een specifiek paar heeft gewonnen. Dit creëert een puzzel: hoeveel wedstrijden moeten we controleren om de winnaars te achterhalen? Voor een lange tijd leek het antwoord te zijn dat we bijna elke enkele wedstrijd moesten controleren, een aantal dat zeer snel groeit naarmate het toernooi groter wordt. Dit is de klassieke visie op het probleem.

Een team van onderzoekers aan het Indian Institute of Technology Gandhinagar heeft deze vraag nu opnieuw onderzocht met behulp van de instrumenten van quantum computing. In plaats van wedstrijden één voor één te controleren, vroegen zij zich af hoeveel wedstrijden een quantumcomputer zou moeten controleren om de winnaars te vinden. Quantumcomputers kunnen veel mogelijkheden tegelijk bekijken, een vermogen dat hen vaak in staat stelt om problemen veel sneller op te lossen dan klassieke machines. De onderzoekers ontdekten dat het antwoord volledig afhangt van welke regel je gebruikt om een winnaar te kiezen. Voor sommige regels biedt de quantumcomputer een enorme versnelling, waarbij slechts een fractie van de wedstrijden gecontroleerd hoeft te worden. Voor andere regels is het quantumvoordeel veel kleiner, en voor één specifieke regel biedt de quantumcomputer helemaal geen voordeel, waardoor er evenveel controles nodig zijn als bij een klassieke computer.

De studie richtte zich op verschillende standaardmanieren om een winnaar te definiëren. De makkelijkste om te vinden, in de quantumwereld, is de topcyclus. Dit is de kleinste groep spelers die, als een team, iedereen anders heeft verslagen. De onderzoekers toonden aan dat een quantumalgoritme deze groep kan identificeren door een aantal wedstrijden te controleren dat ongeveer evenredig is aan het aantal spelers. Dit is een significante verbetering ten opzichte van de klassieke vereiste, die groeit met het kwadraat van het aantal spelers. Om deze groep te vinden, rangschikt het quantumalgoritme eerst alle spelers in een enkele lijn op basis van hun overwinningen, een proces dat vergelijkbaar is met het sorteren van een kaartspel. Vervolgens gebruikt het een verdeel-en-heers-strategie om exact te bepalen waar de winnende groep in die lijn eindigt. Deze aanpak is zo efficiënt dat het ook een gerelateerd probleem oplost: het bepalen of het gehele toernooi sterk samenhangend is, wat betekent dat elke speler via een keten van overwinningen elke andere speler kan bereiken.

In contrast hiermee wordt het vinden van een enkele "Condorcet-winnaar"—een speler die iedereen direct verslaat—zelfs gemakkelijker voor een quantumcomputer. De onderzoekers demonstreerden dat een dergelijke speler gevonden kan worden door een aantal wedstrijden te controleren dat evenredig is aan de vierkantswortel van het aantal spelers. Dit is een drastische vermindering ten opzime met de klassieke vereiste. De methode houdt in dat eerst een "koning" wordt gevonden, een speler die iedereen in maximaal twee stappen kan bereiken, en vervolgens wordt gecontroleerd of deze koning verliezen heeft geleden. Als de koning geen verliezen heeft, is hij de Condorcet-winnaar; als hij wel verliezen heeft, bestaat er geen dergelijke winnaar. Dit resultaat bevestigt dat voor dit specifieke type winnaar, quantummechanica een krachtige afkorting biedt.

Echter, het verhaal verandert wanneer het doel het vinden van de "Copeland-set" is, die bestaat uit alle spelers met het hoogste aantal overwinningen. Hier bewezen de onderzoekers dat een quantumcomputer geen voordeel behaalt. Om de volledige set topscorers te vinden, moet de quantumcomputer nog steeds een aantal wedstrijden controleren dat evenredig is aan het kwadraat van het aantal spelers, precies hetzelfde als een klassieke computer. Dit is een verrassend resultaat omdat het vinden van slechts één van deze topscorers veel gemakkelijker is voor een quantumcomputer. De moeilijkheid komt voort uit het feit dat het identificeren van de volledige set vereist dat de overwinningen van elke speler met extreme precisie worden geteld, een taak die niet profiteert van de parallelle zoekkracht van quantummechanica op dezelfde manier als het vinden van een enkel doelwit.

De onderzoekers onderzochten ook de "uncovered set", die spelers bevat die iedereen in twee stappen of minder kunnen bereiken. Zij ontdekten dat het vinden van deze volledige groep moeilijker is dan het vinden van een enkele dergelijke speler, maar gemakkelijker dan het vinden van de volledige Copeland-set. Een quantumcomputer moet een aantal wedstrijden controleren dat evenredig is aan het aantal spelers verheven tot de macht éénënaalf. Dit plaatst de uncovered set in een middengebied, wat laat zien dat de moeilijkheid van een tournament-oplossing niet uniform is; sommige zijn makkelijk, sommige zijn moeilijk, en het quantumvoordeel varieert dienovereenkomstig.

Om deze grenzen te bewijzen, ontwikkelde het team nieuwe wiskundige argumenten. Ze creëerden specifieke, moeilijke tournament-scenario's die elk algoritme erin proberen te misleiden om veel wedstrijden te controleren. Door aan te tonen dat zelfs een quantumcomputer deze specifieke puzzels niet kan oplossen zonder een bepaald minimum aantal wedstrijden te controleren, stelden zij vaste ondergrenzen vast voor de vereiste inspanning. Voor het probleem van het vinden van de speler met de meeste overwinningen, leverden zij een nieuw, zelfstandig bewijs van een bekende limiet, waarmee zij aantoonden dat de moeilijkheid voortkomt uit de noodzaak om te tellen in plaats van alleen maar te zoeken. Hun werk verduidelijkt dat hoewel quantumcomputers krachtig zijn, ze geen toverstaf zijn die elke berekening versnelt. Het voordeel hangt af van de specifieke structuur van het probleem, en in het geval van tournament-oplossingen bepalen de regels voor het kiezen van de winnaar of de quantummachine echt kan schitteren.