Het verborgen subgroepprobleem (HSP) is een onderzoeksthema in de wiskunde en de theoretische informatica. Dit kader omvat problemen zoals ontbinding in priemfactoren, discrete logaritme, grafenisomorfisme en het kortste-vectorprobleem. Het is van bijzonder belang in de theorie van kwantumcomputing omdat het Algoritme van Shor voor priemfactorisatie en discrete logaritmen voorbeelden zijn van HSP voor eindige abelse groepen, terwijl de overige problemen corresponderen met eindige niet-abelse groepen.
Probleemstelling Gegeven een groep , een subgroep en een eindige verzameling , zeggen we dat een functie de subgroep verbergt als voor alle geldt:
Met andere woorden: is constant op elke nevenklasse van en verschillend tussen verschillende nevenklassen.
Verborgen subgroepprobleem: Laat een groep zijn, een eindige verzameling en een functie die een subgroep verbergt. wordt aangeboden via een orakel dat bits gebruikt. Bepaal, met gebruik van orakelaanroepen voor , een genererende verzameling van .
Een speciaal geval is wanneer zelf een groep is en een groephomomorfisme is; dan is de kern van .
Motivatie Het verborgen subgroepprobleem is in de theorie van kwantumcomputers cruciaal: Shor’s algoritme voor priemfactorisatie en discrete logaritmen gebruikt HSP voor eindige abelse groepen. Efficiënte kwantumalgoritmen voor HSP op bepaalde niet-abelse groepen zouden efficiënte oplossingen geven voor het grafenisomorfismeprobleem (symmetrische groep) en het unieke SVP in lattices (dihedrale groep).Mark Ettinger; Peter Høyer (1999). "A quantum observable for the graph isomorphism problem". arXiv:quant-ph/9901029.Oded Regev (2003). "Quantum computation and lattice problems". arXiv:cs/0304005.
Kwantumalgoritmen Voor abelse groepen is er een kwantumalgoritme in tijd polynomiaal in . Voor willekeurige groepen is oplosbaarheid met polynomiaal aantal orakelaanroepen aangetoond, maar de circuitgrootte kan exponentieel worden. Het bestaan van een volledig efficiënt algoritme voor alle groepen is open. Voor semidirecte producten van abelse groepen bestaan wel efficiënte oplossingen.
Algoritme voor abelse groepen Gebaseerd op representatietheorie: karakters (ééndimensionale irréduceerbare representaties) van . De kwantum-Fouriertransformatie over en haar tensorproduct-constructie op leveren bij herhaalde metingen in genoeg lineaire voorwaarden om een genererende verzameling van te reconstrueren in polynomiale tijd.
Belangrijke voorbeelden +ProbleemAlgoritmeAbelse groep?Polyn. tijd?Deutsch’s probleemDeutsch–Jozsa–algoritmeJaJaSimon’s probleemSimon-algoritmeJaJaOrder findingShorJaJaDiscrete logaritmeShorJaJaPeriod findingShorJaJaAbelse stabilisatorKitaev’s algoritmeJaJaGrafenisomorfisme—NeeNeeKortste-vectorprobleem—NeeNee
Zie ook Hidden shift problem Pontryagindualiteit
Referenties Ettinger, Mark & Høyer, Peter (1999). A quantum observable for the graph isomorphism problem. arXiv:quant-ph/9901029. Regev, Oded (2003). Quantum computation and lattice problems. arXiv:cs/0304005. Ettinger, Mark; Høyer, Peter; Knill, Emanuel (2004). “The quantum query complexity of the hidden subgroup problem is polynomial”. Information Processing Letters. 91: 43–48. .
Externe links Richard Jozsa: Quantum factoring, discrete logarithms and the hidden subgroup problem Chris Lomont: The Hidden Subgroup Problem – Review and Open Problems
Categorie:Groepentheorie Categorie:Theoretische informatica