The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem

In de zoektocht naar het bouwen van machines die problemen kunnen oplossen die ver buiten het bereik van de huidige computers liggen, hebben wetenschappers lang vertrouwd op een specifiek type afkorting. Deze afkortingen, bekend als quantumalgoritmen, werken vaak door gebruik te maken van de verborgen symmetrieën van een systeem. Stel je een complex slot voor met veel tumblers; een klassieke computer zou misschien elke mogelijke combinatie van tumblers moeten proberen om de één te vinden die het slot opent, een proces dat langer zou kunnen duren dan het huidige tijdperk van het universum. Een quantumcomputer kan echter soms de vorm van het slot van een afstand af voelen, waardoor de juiste combinatie bijna onmiddellijk wordt geïdentificeerd. Dit vermogen om verborgen patronen te vinden, is de motor achter enkele van de beroemdste quantumalgoritmen, inclusief die welke op een dag moderne encryptiecodes zouden kunnen breken.

Decennialang hebben onderzoekers zich gericht op een specifiek type symmetrieprobleem genaamd het verborgen subgroepprobleem (hidden subgroup problem). In dit scenario krijgt een computer een functie die op dezelfde manier werkt voor een verborgen groep invoer, maar anders voor alles daarbuiten. Het doel is om die verborgen groep te vinden. Hoewel dit is opgelost voor eenvoudige, ordelijke groepen, is er onlangs een recentere en meer uitdagende versie opgekomen: het state hidden subgroup problem. Hier, in plaats van een wiskundige functie te krijgen, krijgt de computer een mysterieuze quantumtoestand — een delicate configuratie van deeltjes. De taak is om te achterhalen welke operaties deze toestand onveranderd laten. De moeilijkheid van deze taak hangt sterk af van hoe de computer met de toestand mag interageren. Als de computer alleen statische kopieën van de toestand kan ontvangen, zoals het bekijken van een foto, is het proces traag. Maar als de computer toegang heeft tot de machine die de toestand heeft gecreëerd, waardoor het de creatieprocedure vooruit en achteruit kan draaien, veranderen de spelregels volledig.

Een nieuwe studie door onderzoekers van het Max Planck Instituut voor Quantumoptica en de Freie Universität Berlin heeft eindelijk de vraag beantwoord hoe snel dit probleem kan worden opgelost onder deze verschillende omstandigheden. Het team bewees dat de methode van toegang niet slechts een klein technisch detail is; het bepaalt fundamenteel de snelheid van de oplossing. Ze demonstreerden dat als een quantumcomputer alleen kopieën van de onbekende toestand kan bekijken, hij een aantal kopieën moet onderzoeken dat omgekeerd evenredig is aan de grootte van de "kloof" (gap) tussen de juiste symmetrie en de onjuiste. In simpelere termen: als het signaal zwak is, heeft de computer veel, veel kopieën nodig om het duidelijk te horen. Echter, als de computer toegang heeft tot de preparatie-unitaire (de eigenlijke circuit die de toestand opbouwt), kan hij het proces in omgekeerde richting draaien. Dit vermogen om de toestand coherent te manipuleren, stelt de computer in staat om een techniek genaamd amplitude amplification te gebruiken, wat werkt als een krachtige loep. Met dit instrument daalt het aantal vereiste interacties drastisch, wat de snelheid verbetert met een factor gelijk aan de vierkantswortel van de eerdere vereiste.

De onderzoekers hebben niet alleen een snellere manier gevonden om het probleem op te lossen; ze hebben bewezen dat deze versnelling de absoluut beste mogelijke is. Ze construeerden een rigoureus wiskundig argument dat aantoont dat geen enkel algoritme, hoe slim ook, deze limieten kan verslaan. Zelfs als de computer de meest complexe metingen mogelijk kan uitvoeren op de kopieën, of als hij toegang heeft tot nog krachtigere versies van de preparatiemachine, blijft de fundamentele barrière bestaan. De studie stelt vast dat de kwadratische verbetering in snelheid een echt kenmerk is van het hebben van coherente controle over de creatie van de toestand, en geen artefact van een specifiek algoritme. Deze bevinding verheldert de exacte bron van het quantumvoordeel bij deze leer-taken, waarbij het vermogen om een proces om te keren wordt geïsoleerd van het louter observeren van de output.

De implicaties van dit werk reiken verder dan abstracte theorie en raken de kern van de moderne fysica. Het vermogen om verborgen symmetrieën in quantumtoestanden efficiënt te identificeren, is cruciaal voor het begrijpen van complexe materialen en het verifiëren van quantumapparaten. Bijvoorbeeld, de nieuwe algoritmen kunnen worden gebruikt om te lokaliseren waar een groot quantumsysteem uiteenvalt in onafhankelijke, niet-verstrengelde delen, een taak die essentieel is voor het begrijpen van hoe quantuminformatie zich verspreidt. Ze bieden ook snellere manieren om de stabilizer-groepen te identificeren die quantuminformatie beschermen tegen fouten, wat een hoeksteen is van het bouwen van betrouwbare quantumcomputers. Bovendien kunnen de methoden verborgen translatiesymmetrieën in many-body systemen detecteren, wat natuurkundigen helpt de onderliggende orde in complex quantummateriaal in kaart te brengen. In elk van deze toepassingen laat de studie zien dat als het preparatiecircuit beschikbaar is, de tijd die nodig is om de verborgen structuur te vinden aanzienlijk afneemt, waardoor voorheen onhandelbare problemen oplosbaar worden.

Het pad naar deze ontdekking vereiste een zorgvuldige balans tussen twee concurrerende modellen van toegang. In het eerste model, het "sample"-model, wordt het algoritme behandeld als een passieve waarnemer die een stapel identieke quantumtoestanden krijgt aangeleverd. De onderzoekers toonden aan dat in dit scenario het aantal toestanden dat nodig is om de verborgen symmetrie te vinden, strikt wordt bepaald door de inverse van de beloofde kloof (promise gap). Als de kloof klein is, wat betekent dat het verschil tussen de juiste symmetrie en de onjuiste zeer subtiel is, heeft het algoritme een groot aantal samples nodig om ze te onderscheiden. Het team bewees dat zelfs met de meest geavanceerde collectieve metingen, waarbij alle kopieën samen in een enkele, complexe operatie worden gemeten, deze limiet niet kan worden doorbroken. De informatie is simpelweg niet aanwezig in de kopieën om sneller uit gewonnen te worden.

In contrast hiermee biedt het tweede model, het "query"-model, het algoritme actieve controle. Hier kan de computer een unitaire operator aanroepen die de toestand bereidt en de inverse ervan, die de preparatie ongedaan maakt. Deze toegang stelt het algoritme in staat om te interfereren met de toestand, waardoor de juiste oplossing effectief wordt versterkt terwijl de onjuiste wordt geannuleerd. De onderzoekers ontwikkelden een nieuw algoritme dat deze capaciteit gebruikt om de verborgen symmetrie te vinden met een aantal queries dat schaalt met de inverse vierkantswortel van de kloof. Dit vertegenwoordigt een enorme reductie in de benodigde middelen. Om te verzekeren dat dit niet slechts een gelukstreffer was, construeerden ze een familie van moeilijke problemen gebaseerd op een klassieke uitdaging bekend als Simons probleem. Door dit probleem op te vullen en een fractionele versie van de oracle te introduceren, toonden ze aan dat de ondergrens voor het query-model exact overeenkomt met hun bovengrens. Deze nauwe match bewijst dat het algoritme optimaal is en dat de versnelling inherent is aan het vermogen om het preparatieproces achteruit te draaien.

Een van de meest significante bijdragen van het werk is de oplossing van een langdurige onzekerheid over de grootte van de verborgen subgroep. Eerdere algoritmen gingen vaak uit van een worst-case scenario waarbij de verborgen groep zeer klein was, wat leidde tot middelenramingen die afhankelijk waren van de totale grootte van de gehele groep. De nieuwe studie introduceert een adaptieve strategie die het algoritme in staat stelt om te stoppen zodra er genoeg informatie is gevonden, ongeacht de grootte van de groep. Dit betekent dat de complexiteit nu afhangt van de grootte van de quoënt, of de ratio tussen de totale groep en de verborgen subgroep. Als de verborgen subgroep groot is, wordt het probleem veel gemakkelijker, en het algoritme weerspiegelt dit door minder middelen te vereisen. Deze adaptieve stopregel werkt zonder dat het algoritme vooraf de grootte van de verborgen groep hoeft te kennen, wat de oplossing zowel efficiënt als praktisch maakt.

De studie behandelt ook de rol van geavanceerde quantumkenmerken zoals gecontroleerde queries en conjunct-toegang. In sommige theoretische modellen kan het hebben van toegang tot het complexe conjugaat van een operator of de mogelijkheid om de oracle te controleren met een quantum bit, potentieel verdere voordelen bieden. De onderzoekers testten deze mogelijkheden en stelden vast dat voor de door hen geconstrueerde worst-case scenario's deze extra krachten geen bijkomend voordeel boden. De kwadratische versnelling die werd bereikt door simpelweg toegang te hebben tot de inverse van de preparatie-unitaire was de maximale winst. Dit resultaat is cruciaal omdat het suggereert dat voor een brede klasse van het leren van symmetrieën, het vermogen om het omkeren van de toestand te gebruiken het sleutelingredient is, en dat het toevoegen van complexere controlemechanismen geen verdere asymptotische verbeteringen oplevert.

De praktische toepassingen van deze bevindingen worden al gevoeld in het ontwerp van quantumalgoritmen voor specifieke fysieke taken. Bijvoorbeeld, in de taak van het lokaliseren van unentanglement, waarbij het doel is om de grenzen te vinden tussen onafhankelijke delen van een quantumsysteem, biedt de nieuwe query-gebaseerde aanpak een kwadratische verbetering in de afhankelijkheid van de gap-parameter. Dit betekent dat voor systemen waar de scheiding tussen delen subtiel is, de coherente toegangsmethode de oplossing veel sneller kan vinden dan welke methode dan ook die steunt op statische kopieën. Op dezelfde manier, bij het leren van stabilizer-groepen, die essentieel zijn voor quantumfoutcorrectie, bieden de nieuwe grenzen een duidelijker beeld van de benodigde middelen. De studie verheldert dat terwijl het aantal kopieën dat nodig is schaalt met de inverse van de kloof, het aantal queries schaalt met de inverse vierkantswortel, wat een duidelijk pad biedt voor het optimaliseren van quantumverificatieprotocollen.

Uiteindelijk biedt dit werk een definitieve kaart van het terrein voor het abelian state hidden subgroup problem. Het trekt een scherpe lijn tussen wat mogelijk is met passieve observatie en wat mogelijk is met actieve controle. De onderzoekers hebben aangetoond dat de kracht van quantumalgoritmen in dit domein geen vaag potentieel is, maar een precies kwantificeerbaar voordeel dat voortkomt uit het vermogen om de state-preparatie coherent te manipuleren. Door te bewijzen dat hun algoritmen optimaal zijn en dat geen betere methode bestaat, hebben ze het boek over de complexiteit van dit fundamentele probleem gesloten. De resultaten bieden een solide fundament voor toekomstig onderzoek, waarbij ze de ontwikkeling van quantumalgoritmen sturen die de meest uitdagende symmetrieproblemen in de fysica en computerwetenschappen met de maximale efficiëntie kunnen aanpakken.