Este documento explora el problema oculto de subgrupo (HSP) para grupos discretos infinitos, trazando paralelos con el algoritmo de Shor para la búsqueda de períodos en los enteros.
**Resultados de Dificultad**:
* El documento demuestra que HSP es NP-hard para el grupo aditivo de números racionales y para subgrupos normales de grupos libres no abelianos.
* También reduce indirectamente una versión del problema de vectores cortos a HSP en Zk con costo de consulta pseudo-polinómico.
**Resultados Algorítmicos**:
* El documento generaliza el algoritmo de Shor-Kitaev para HSP en Zk a casos donde el subgrupo oculto tiene rango deficiente o índice infinito.
* Echa luz sobre un algoritmo de tiempo exponencial estirado para el problema de desplazamiento oculto abeliano (AHShP), extendiendo el trabajo anterior del autor y de Regev y Peikert.
**Contribuciones Clave**:
* **Grupos Infinitos**: El documento investiga HSP en grupos infinitos, lo que es una extensión significativa del trabajo anterior que se centró en grupos finitos.
* **Dificultad y Algoritmos**: Presenta tanto resultados de dificultad como algorítmicos, proporcionando una comprensión completa del problema.
* **AHShP**: El documento introduce un nuevo algoritmo para AHShP, que es relevante para resolver HSP en grupos virtualmente abelianos.
**Implicaciones**:
* Los resultados del documento resaltan la complejidad computacional de HSP en grupos infinitos, haciendo que sea un problema desafiante para los algoritmos clásicos.
* Los algoritmos propuestos ofrecen algoritmos cuánticos para casos específicos de HSP, ofreciendo posibles soluciones para ciertos problemas.
* El trabajo contribuye a una comprensión más amplia de la teoría de grupos y sus aplicaciones en la computación cuántica y la criptografía.