Verborgen-subgroepprobleem: de wiskunde achter Shors kwantumalgoritme
Stel je een gigantische ronde klok voor met miljoenen streepjes in plaats van twaalf. Ergens op die klok zit een geheim patroon verstopt: een getal dat aangeeft na hoeveel stappen de klok zichzelf herhaalt. Je mag de klok bevragen — voor elk streepje krijg je een antwoord terug — maar het herhalingsgetal zelf blijft verborgen totdat je genoeg vragen hebt gesteld en de antwoorden slim combineert. Een gewone computer moet bij zo'n taak vaak bijna alle streepjes langslopen voordat het patroon zichtbaar wordt. Een kwantumcomputer kan, dankzij een wiskundige truc die golfpatronen laat interfereren, het verborgen getal soms met slechts een handvol vragen blootleggen.
Dit voorbeeld is een concreet geval van een veel algemener wiskundig raadsel: het verborgen-subgroepprobleem (Engels: hidden subgroup problem, afgekort HSP). In de wiskunde heet een verzameling elementen met een bewerking, zoals optellen of het combineren van symmetrieën, een groep. Een subgroep is een kleinere groep die binnen die grotere groep verstopt zit en zelf ook aan alle groepsregels voldoet. Bij het HSP krijg je een functie die deze verborgen subgroep als het ware markeert zonder hem direct te tonen, en is het de kunst om met zo min mogelijk metingen te achterhalen welke subgroep het is. Dit klinkt abstract, maar het probleem ligt aan de basis van enkele van de belangrijkste kwantumalgoritmes ooit bedacht — algoritmes die grote delen van de huidige internetbeveiliging kunnen ondermijnen.
Wat is het precies?
Een groep is in de wiskunde elke verzameling objecten die je op een consistente manier kunt combineren, met een neutraal element (dat niets verandert) en voor elk element een tegengestelde. Bekende voorbeelden zijn de gehele getallen onder optelling, de mogelijke draaiingen van een vierkant, of alle manieren om een rij voorwerpen anders te ordenen (permutaties).
Een subgroep is een deelverzameling van zo'n groep die zelf ook een groep vormt. Denk aan "alleen de veelvouden van 5" binnen de gehele getallen, of "alleen de draaiingen van 0 en 180 graden" binnen alle mogelijke draaiingen van een vierkant.
Elke subgroep verdeelt de hele groep automatisch in gelijke stroken, nevenklassen genoemd. Zo verdeelt de subgroep "veelvouden van 5" de gehele getallen in vijf stroken: getallen met rest 0, 1, 2, 3 of 4 bij deling door 5.
Bij het HSP krijg je toegang tot een zwarte doos, een functie f, die voor elk element van de groep een label teruggeeft. Die functie is zo gemaakt dat elementen in dezelfde nevenklasse altijd hetzelfde label krijgen, en elementen in verschillende nevenklassen vrijwel altijd een ander label. De opgave: ontdek de verborgen subgroep puur door f te bevragen, met zo min mogelijk vragen én zo min mogelijk rekentijd.
Op een kwantumcomputer kun je f in superpositie tegelijk op alle groepselementen toepassen — een kwantumbit kan namelijk tegelijk meerdere waarden "bevatten", waardoor je in één stap als het ware de hele groep tegelijk bevraagt. Door daarna een wiskundige bewerking toe te passen die kwantum-Fourier-transformatie heet, laat je de golfpatronen van al die antwoorden met elkaar interfereren: patronen die bij de verborgen subgroep passen versterken elkaar, andere doven uit. Wat na meting overblijft, bevat informatie over de subgroep.
Voor "abelse" groepen, waarin de volgorde van combineren er niet toe doet (zoals bij optellen), werkt deze aanpak altijd efficiënt: de benodigde tijd groeit netjes mee met de grootte van het probleem in plaats van exponentieel te exploderen. Voor "niet-abelse" groepen, waarin volgorde er wél toe doet (zoals bij permutaties), is dit veel lastiger en in de meeste gevallen nog onopgelost.
Wat wil men ermee bereiken?
Het HSP fungeert als een soort eenheidskader waarmee onderzoekers proberen te begrijpen waar precies de kracht van kwantumcomputers vandaan komt: welke problemen laten zich wél exponentieel versnellen met interferentie, en welke niet? Door verschillende bekende kwantumalgoritmes te herkennen als speciale gevallen van hetzelfde onderliggende probleem, ontstaat een overzichtelijker landschap van wat kwantumcomputers wel en niet goed kunnen.
De meest concrete drijfveer is echter praktisch: veel gangbare cryptografie, zoals RSA en op elliptische krommen gebaseerde systemen, is veilig omdat bepaalde rekenproblemen (grote getallen ontbinden in factoren, discrete logaritmes berekenen) voor gewone computers onhaalbaar traag zijn. Deze problemen blijken wiskundig gezien abelse HSP-instanties te zijn — en dus wél efficiënt oplosbaar voor een voldoende krachtige kwantumcomputer. Het begrijpen en oplossen van het HSP is daarmee direct verbonden met de vraag hoe kwetsbaar onze huidige digitale beveiliging op termijn is.
Daarnaast hoopt men dat het oplossen van niet-abelse gevallen, zoals het HSP over de symmetrische groep, een doorbraak zou opleveren voor het beroemde graafisomorfismeprobleem: het vaststellen of twee ogenschijnlijk verschillende netwerken in wezen identiek zijn. Ook voedt het HSP het ontwerp van nieuwe cryptografische systemen die juist wél bestand moeten zijn tegen kwantumaanvallen, doordat ze steunen op groepen waarvoor geen efficiënt kwantumalgoritme bekend is.
Voorbeelden uit de praktijk
Simon's algoritme (Daniel Simon, 1994) was het eerste voorbeeld dat overtuigend liet zien dat een kwantumcomputer een probleem exponentieel sneller kan oplossen dan elke klassieke computer. Het draait om een verborgen subgroep binnen bitstrings die je met XOR (een optelling waarbij 1+1=0) combineert. Dit resultaat inspireerde Peter Shor rechtstreeks.
Shor's algoritme (Peter Shor, 1994) is het bekendste voorbeeld: het ontbinden van grote getallen in priemfactoren en het berekenen van discrete logaritmes blijken beide abelse HSP-instanties te zijn. Omdat RSA-versleuteling steunt op de moeilijkheid van factorisatie, en Diffie-Hellman- en elliptische-krommecryptografie op discrete logaritmes, zou een voldoende grote, foutbestendige kwantumcomputer met dit algoritme veel van de huidige internetbeveiliging kunnen breken.
Kuperberg's algoritme (Greg Kuperberg, begin jaren 2000) pakt het HSP aan voor de diedrische groep, de groep van symmetrieën van een veelhoek (spiegelingen en draaiingen samen). Dit is een niet-abelse groep, en het algoritme vindt de verborgen subgroep in subexponentiële tijd: sneller dan elke klassieke methode, maar nog niet zo snel als bij Shor. Latere werk verfijnde de geheugen- en tijdscompromissen van dit algoritme verder.
De link met graafisomorfisme: onderzoekers als Cristopher Moore, Alexander Russell en Leonard Schulman onderzochten begin jaren 2000 of dezelfde "Fourier-sampling"-aanpak die bij Shor werkt, ook het HSP over de symmetrische groep zou kunnen oplossen — wat een efficiënt kwantumalgoritme voor graafisomorfisme zou opleveren. Hun resultaten laten zien dat de meest voor de hand liggende versie van deze techniek daarvoor niet volstaat, een belangrijk negatief resultaat dat de zoektocht een andere richting op stuurde.
Postkwantumcryptografie-standaardisatie door NIST: mede gedreven door de dreiging van Shors algoritme (en dus het abelse HSP) startte het Amerikaanse standaardisatie-instituut NIST een jarenlang traject om cryptografie te selecteren die ook tegen kwantumcomputers bestand is. In 2024 publiceerde NIST de eerste definitieve standaarden hiervoor, gebaseerd op roosterproblemen (lattices) en hashfuncties, die naar verwachting de komende jaren RSA en ECC geleidelijk gaan vervangen.
Hoe ver is de techniek?
Wiskundig gezien is het abelse geval van het HSP al decennia opgelost: er bestaat een efficiënt, algemeen kwantumalgoritme dat via de kwantum-Fourier-transformatie werkt. Het niet-abelse geval, met als beroemdste open deelvraag de symmetrische groep (en dus graafisomorfisme), blijft grotendeels onopgelost. Er is stevige aanwijzing dat de gangbare technieken hier fundamenteel tekortschieten, wat betekent dat een oplossing waarschijnlijk een wezenlijk nieuw idee vergt.
De grootste hobbel zit intussen niet bij het algoritme zelf, maar bij de hardware. Om Shors algoritme daadwerkelijk te gebruiken tegen cryptografisch relevante sleutelgroottes (bijvoorbeeld RSA met 2048 bits) zijn schattingen nodig van duizenden foutgecorrigeerde "logische" qubits, wat met de huidige foutcorrectiemethoden al snel neerkomt op miljoenen fysieke qubits. Onderzoekers als Craig Gidney en Martin Ekerå publiceerden in 2019 (en werkten dit later verder uit) concrete resourceschattingen die dat aantal geleidelijk naar beneden bijstelden, maar de kloof met de huidige generatie kwantumcomputers — die typisch enkele honderden tot ruim duizend, foutgevoelige fysieke qubits tellen — blijft groot.
Precies daardoor is er discussie over het tempo: sommige experts verwachten dat het nog zeker een decennium of langer duurt voordat een cryptografisch relevante factorisatie haalbaar is, terwijl anderen wijzen op de snelle vooruitgang in foutcorrectie van de afgelopen jaren. Juist die onzekerheid, gecombineerd met het risico dat versleutelde data vandaag wordt opgeslagen om pas later te worden ontcijferd ("store now, decrypt later"), is de reden dat de overstap naar postkwantumcryptografie nu al in gang wordt gezet, ruim voordat een kwantumcomputer daadwerkelijk bestaande encryptie kan breken.
Wie werken eraan?
Peter Shor werkt bij MIT, waar hij zijn beroemde algoritme ontwikkelde; Daniel Simon werkte destijds bij Microsoft Research. Greg Kuperberg is verbonden aan de University of California, Davis. Onderzoek naar de niet-abelse en cryptografische kant van het HSP wordt onder meer gedaan aan het Institute for Quantum Computing van de University of Waterloo (met onderzoekers als Michele Mosca) en aan diverse Amerikaanse universiteiten zoals Caltech en de University of Chicago.
In Nederland houden QuSoft, het onderzoeksinstituut voor kwantumsoftware van het CWI en de Universiteit van Amsterdam, en QuTech, het samenwerkingsverband tussen TU Delft en TNO, zich bezig met kwantumalgoritmes en de theoretische fundamenten daarvan, waaronder vraagstukken die aan het HSP raken.
Op de toepassingskant investeren grote technologiebedrijven als IBM, Google, Microsoft en gespecialiseerde spelers als IonQ en Quantinuum in kwantumhardware waarop dit soort algoritmes ooit moet draaien. Aan de defensieve kant coördineert het Amerikaanse NIST, met inbreng van cryptografen wereldwijd, de ontwikkeling van postkwantumcryptografie als tegenmaatregel tegen precies het soort dreiging dat het HSP oplevert.