Linear-depth quantum oracles for clique problems from edge colorings and graph states, with linear non-Clifford cost and a provably bounded-error k-clique search

In het uitgestrekte landschap van de computerwetenschappen worden sommige problemen gedefinieerd door hun enorme moeilijkheidsgraad. Het vinden van een "clique" in een netwerk—een groep individuen waarbij iedereen elkaar kent—is een dergelijke uitdaging. Hoewel het vinden van een kleine groep van drie wederzijdse vrienden beheersbaar is, is het zoeken naar grotere, hechte groepen binnen massieve netwerken van duizenden of miljoenen verbindingen een taak die zelfs de krachtigste klassieke computers snel overweldigt. Dit is niet alleen een theoretische puzzel; het is een fundamenteel hulpmiddel dat wordt gebruikt bij alles van het analyseren van hersenconnectiviteit tot het begrijpen van hoe ziekten zich door sociale netwerken verspreiden. Decennialang hebben onderzoekers naar quantumcomputing gekeken voor een oplossing, in de hoop dat de vreemde regels van de quantumwereld de zoektocht zouden kunnen versnellen. Echter, een grote hindernis bleef bestaan: het bouwen van de specifieke quantumcircuits die nodig zijn om voor deze groepen te controleren, was als het proberen te bouien van een wolkenkrabber met stenen die te zwaar zijn om op te tillen. De circuits waren te diep, vereisten te veel stappen en vertrouwden op een type quantumoperatie dat ongelooflijk duur en moeilijk betrouwbaar uit te voeren is op echte hardware.

Een team onderzoekers aan de Universiteit van Teheran heeft nu een nieuwe manier voorgesteld om deze quantumcircuits te bouwen die de kosten van de operatie fundamenteel verandert. In plaats van het netwerk te behandelen als een rigide lijst van verbindingen die één voor één gecontroleerd moeten worden, hebben zij een methode ontwikkeld die de zoektocht organiseert als een goed gepland verkeersysteem. In hun nieuwe aanpak wordt het complexe web van verbindingen in één efficiënte stap op een quantumtoestand gemapt, waarbij gebruik wordt gemaakt van alleen standaard, goedkope operaties. De dure, moeilijk uit te voeren onderdelen van de berekening worden vervolgens beperkt tot een klein, vast gedeelte van het circuit dat niet verandert, ongeacht hoe groot of complex het netwerk is. Dit betekent dat naarmate het netwerk groter wordt, het meest kostbare deel van de berekening niet met het netwerk meegroeit. De onderzoekers bewezen wiskundig dat deze methode werkt met een hoge mate van zekerheid en bevestigden hun bevindingen door exacte simulaties uit te voeren op echte gegevens van hersennetwerken en retina-structuren.

De kern van het probleem ligt in hoe quantumcomputers een graaf "zien". Om een clique te vinden, moet een quantumalgoritme controleren of een specifieke set punten allemaal met elkaar verbonden zijn. Eerdere methoden behandelden elke enkele verbinding in het netwerk als een aparte gate die geactiveerd moest worden. Als een netwerk duizenden verbindingen had, had het circuit duizenden van deze dure gates nodig, wat het proces traag en foutgevoelig maakte. Het nieuwe werk introduceert een slimme planningsmethode gebaseerd op het idee van randkleuring (edge coloring). Stel je een druk kruispunt voor waar auto's vanuit verschillende richtingen moeten passeren zonder op elkaar te botsen. Als je de auto's per kleur groepeert, kun je alle rode auto's tegelijk laten gaan, dan alle blauwe, enzovoort, zonder enige botsing. De onderzoekers pasten dezelfde logica toe op de verbindingen in een graaf. Door verbindingen te groeperen die geen enkel punt delen, kunnen ze deze simultaan in parallelle lagen verwerken. Dit vermindert de diepte van het circuit—het aantal stappen dat nodig is om het uit te voeren—van een kwadratische groei die explodeert met de grootte naar een lineaire groei die veel geleidelijker schaalt.

Echter, het simpelweg versnellen van de stappen was niet genoeg. De onderzoekers moesten ook de "niet-Clifford" kosten verminderen, wat verwijst naar het specifieke type quantumgate dat een zeldzame, gedistilleerde bron vereist om te functioneren. In eerdere ontwerpen vereiste elke enkele verbinding in het netwerk één van deze dure gates. De nieuwe methode verandert de architectuur volledig. De graaf komt het circuit binnen via een specifieke, goedkope operatie die een speciale quantumtoestand bereidt, bekend als een graaftoestand. Zodra deze toestand is voorbereid, verloopt de rest van de berekening met behulp van alleen goedkope, standaard gates. De dure gates worden alleen gebruikt in een vast blok dat onafhankelijk is van de structuur van de graaf. Dit betekent dat voor elke graaf, ongeacht hoe groot, het aantal van deze kostbare operaties alleen proportioneel is aan het aantal knooppunten (vertices), en niet aan het aantal verbindingen. Dit is een significante verschuiving, waarbij een kostenpost die schaalt met het kwadraat van de netwerkomvang wordt omgezet in een die schaalt met het aantal knooppunten.

Om de nauwkeurigheid van de zoektocht te waarborgen, moesten de onderzoekers een lastig probleem oplossen: de nieuwe methode werkt niet als een perfecte aan/uit-schakelaar. In plaats van direct een clique als "gevonden" te markeren en een niet-clique als "niet gevonden", produceert het circuit een subtiel signaal dat sterk is voor cliques maar zwak voor de rest. Om dit subtiele signaal in een betrouwbaar resultaat te veranderen, voegden de onderzoekers een filterstap toe met behulp van een techniek genaamd fase-estimatie (phase estimation). Dit werkt als een stemvork, die het juiste signaal versterkt terwijl de ruis wordt onderdrukt. Ze bewezen wiskundig dat dit filter garandeert dat een ware clique nooit gemist zal worden, terwijl de kans dat een niet-clique onterecht als een clique wordt geïdentificeerd, extreem laag wordt gehouden. In hun simulaties werd deze foutmarge beperkt tot een zeer klein deel, wat ervoor zorgt dat de zoektocht robuust is.

De onderzoekers testten hun theorie niet alleen op willekeurige getallen, maar op echte gegevens. Ze namen geïnduceerde subgrafen van twee werkelijke biologische netwerken: de cerebrale cortex van een makakaapje en de retina van een muis. Dit zijn complexe, rommelige, echte structuren, geen geïdealiseerde wiskundige vormen. Ze voerden hun algoritme uit op honderden van deze subgrafen, waarbij ze het exacte gedrag van het quantumcircuit simuleerden. De resultaten waren opmerkelijk. Wanneer ze de nieuwe gefilterde oracle gebruikten, was het succespercentage van het vinden van de juiste clique consequent hoog, vaak boven de 90 procent en in veel gevallen bijna 100 procent. In contrast hiermee, toen ze de oudere, ongefilterde versie van hun nieuwe circuit probeerden te gebruiken, daalde het succespercentage aanzienlijk, en faalde het algoritme vaak om de oplossing te vinden of vond het de verkeerde oplossing. De simulaties bevestigden dat de theoretische garanties in de praktijk standhielden, zelfs met de imperfecties van de quantumtoestand.

De studie vergeleek hun nieuwe ontwerp ook met andere bekende quantumcircuits voor hetzelfde probleem. Hoewel de nieuwe methode iets dieper is qua aantal stappen voor zeer kleine netwerken, wordt deze aanzienlijk minder diep en veel efficiënter wat betreft de dure gates naarmate het netwerk groeit. Voor een netwerk met veertig knooppunten gebruikt de nieuwe methode veel minder van de kostbare operaties dan elk vorig ontwerp. Deze afweging is cruciaal voor de toekomst van quantumcomputing, waarbij de beschikbaarheid van de dure middelen de primaire flessenhals is. De onderzoekers merken op dat hun methode geen wondermiddel is dat het probleem direct voor alle groottes oplost; klassieke computers zijn nog steeds sneller voor kleine instanties. Echter, voor de specifieke beperkingen van toekomstige fouttolerante quantummachines biedt deze aanpak een rigoureus pad vooruit. Het biedt een manier om deze complexe patronen te zoeken met een voorspelbare, begrensde fout en een bronkost die niet explodeert naarmate het probleem groter wordt.

Uiteindelijk demonstreert dit werk dat de moeilijkheid van het clique-probleem in quantumcomputing niet een inherente eigenschap van het probleem zelf was, maar een gevolg van hoe de circuits werden gebouwd. Door de architectuur te heroverwegen en de structuur van de graaf zelf te gebruiken om de operaties te plannen, hebben de onderzoekers aangetoond dat het mogelijk is om een quantumoracle te bouwen die zowel diepte-efficiënt als resource-efficiënt is. De resultaten, geverifieerd via exacte simulaties op echte biologische gegevens, suggereren dat deze aanpak de basis kan vormen voor toekomstige quantumalgoritmen die complexe netwerkanalyse-taken aanpakken die momenteel buiten bereik liggen. De weg naar het oplossen van deze problemen wordt niet langer geblokkeerd door een onoverkomelijke muur van dure gates; in plaats daarvan is deze geplaveid met een nieuwe, efficiëntere route die de fysieke beperkingen van de machines die we hopen te bouwen, respecteert.