Résumé - Le problème de sous-groupe caché pour les groupes infinis

Le problème de sous-groupe caché pour les groupes infinis

2025-07-24 15:16:20

{"Greg Kuperberg"}

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

Ce papier explore le problème de sous-groupe caché (HSP) pour les groupes discrets infinis, établit des parallèles avec l'algorithme de Shor pour la recherche de période dans les entiers. **Résultats de Dureté** : * Le papier montre que le problème HSP est NP-dure pour le groupe additif des nombres rationnels et pour les sous-groupes normaux des groupes libres non abéliens. * Il réduit également indirectement une version du problème des vecteurs courts au problème HSP dans Zk avec un coût d'interrogation pseudo-polynomial. **Résultats Algorithmiques** : * Le papier généralise l'algorithme de Shor-Kitaev pour le problème HSP dans Zk aux cas où le sous-groupe caché a un rang déficient ou un index infini. * Il esquisse un algorithme exponentiel étiré pour le problème du décalage caché abélien (AHShP), étendant le travail précédent de l'auteur et de Regev et Peikert. **Contributions Clés** : * **Groupes Infinis** : Le papier étudie le problème HSP dans les groupes infinis, ce qui est une extension significative des travaux précédents qui se concentraient sur les groupes finis. * **Dureté et Algorithmes** : Il présente à la fois des résultats de dureté et des résultats algorithmiques, fournissant une compréhension complète du problème. * **AHShP** : Le papier introduit un nouveau algorithme pour AHShP, pertinent pour résoudre le problème HSP dans les groupes virtuellement abéliens. **Implications** : * Les résultats de ce papier mettent en lumière la complexité computationnelle du problème HSP dans les groupes infinis, le rendant un problème délicat pour les algorithmes classiques. * Les algorithmes proposés fournissent des algorithmes quantiques pour certains cas du problème HSP, offrant des solutions potentielles pour certains problèmes. * Ce travail contribue à une compréhension plus large de la théorie des groupes et de ses applications en informatique quantique et en cryptographie.