Algoritmos cuánticos y el problema del subgrupo oculto

En otro post comentamos los requisitos para que exista una ventaja cuántica exponencial:

• El problema debe tener cierta estructura que pueda ser accedida por el algoritmo cuántico usando la superposición, el entrelazado y la interferencia.
• Un algoritmo clásico no puede acceder fácilmente a dicha estructura y por lo tanto no puede resolver el problema en tiempo polinómico.

Uno de estos problemas, es el problema del subgrupo oculto (HSP, hidden subgroup problem) que podemos enunciar de la siguiente manera:

Dado un grupo y una función , siendo un conjunto finito, el problema o función f tiene la propiedad de que existe un subgrupo tal que f es constante dentro de cada clase lateral (coset) y distinto en cosets diferentes: si y solo si . El objetivo es encontrar el subgrupo o el generador de dichos subgrupo.

Recordemos que dado un subgrupo H de un grupo G, un coset son los conjuntos obtenidos multiplicando cada elemento de H por un elemento fijo g del grupo G. gH sería el coset izquierdo y Hg el coset derecho. De esta forma H descompone el conjunto G en subconjuntos disjuntos y del mismo tamaño.

Vamos a ver como la factorización de un número entero es una instancia de el problema HSP.

Se puede factorizar un número grande N resolviendo el siguiente problema: Dado un x que es coprimo con N, y una función asociada , encuentra el período r de f.

El grupo es y el subgrupo de todos los múltiplos de r hasta . Como f es periódica, es constante en cada coset y distinta en diferentes costes. Como el subgrupo H es generado por r, resolver el problema HSP y encontrar el generador de H resuelve el problema de la factorización.

Para resolver el problema HSP de manera eficiente para grupos abelianos G y la función , siguiendo el algoritmo de Kitaev, es necesario preparar dos registros iniciales y crear una superposición en f:

Cuando se mide el segundo registro, el resultado es algún valor f(s) para un s del grupo G. Entonces el primer registro colapsa a una superposición de los elementos de g con el mismo valor f(g), que como hemos visto sería el coset en el caso del problema de factorización) ya que f es constante dentro de cada coset.

Después, habría que aplicar a la superposición la transformada cuántica de fourier (QFT) para obtener el generador del subgrupo H.

Hemos visto un problema que se puede resolver eficientemente usando un algoritmo cuántico para el que no se ha encontrado todavía un algoritmo clásico eficiente. Este problema matemático abstracto tiene una fuerte estructura, ya que la función tiene que ser constante en los cosets.

Por lo tanto, como hemos comentado en varios posts, es un tema abierto encontrar problemas prácticos sin una estructura matemática clara en los que los algoritmos cuánticos aporten una ventaja exponencial.