Zusammenfassung - Das versteckte Untergruppenproblem für unendliche Gruppen

Das versteckte Untergruppenproblem für unendliche Gruppen

2025-07-24 15:16:20

{"Greg Kuperberg"}

{quant-ph,cs.CC,math.GR}

Dieses Papier untersucht das verborgene Untergruppenproblem (HSP) für diskrete unendliche Gruppen und zieht Parallelen zu Shors Algorithmus zur Bestimmung von Perioden in den Ganzen. **Schwere Ergebnisse**: * Das Papier zeigt, dass das HSP NP-schwer für die additive Gruppe der rationalen Zahlen und für reguläre Untergruppen nichtabelscher freier Gruppen ist. * Es reduziert ebenfalls eine Version des kürzesten Vektorproblems indirekt auf das HSP in Zk mit pseudopolynomialer Anfragenkosten. **Algorithmische Ergebnisse**: * Das Papiereneralisiert den Shor-Kitaev-Algorithmus für das HSP in Zk auf Fälle, in denen die verborgene Untergruppe einen defizienten Rang oder einen unendlichen Index hat. * Es skizziert ein Algorithmus mit gestreckter Exponentialzeit für das abelsche Hidden Shift Problem (AHShP), der frühere Arbeiten des Autors und von Regev und Peikert erweitert. **Schlüsselfortschritte**: * **Unendliche Gruppen**: Das Papier untersucht das HSP in unendlichen Gruppen, was eine bedeutende Erweiterung der vorherigen Arbeiten darstellt, die sich auf finite Gruppen konzentrierten. * **Schwere und Algorithmen**: Es präsentiert sowohl Ergebnisse über Schwierigkeiten als auch algorithmische Ergebnisse, was zu einem umfassenden Verständnis des Problems beiträgt. * **AHShP**: Das Papier führt einen neuen Algorithmus für AHShP ein, der für die Lösung des HSP in fast abelschen Gruppen relevant ist. **Bedeutungen**: * Die Ergebnisse des Papieres betonen die Rechenkomplexität des HSP in unendlichen Gruppen, was es zu einem herausfordernden Problem für klassische Algorithmen macht. * Die vorgeschlagenen Algorithmen bieten quantenmechanische Algorithmen für bestimmte Fälle des HSP, was potenzielle Lösungen für bestimmte Probleme bietet. * Die Arbeit trägt zu einer breiteren Verständnis der Gruppentheorie und ihren Anwendungen in Quantencomputing und Kryptografie bei.