Problema de Simon

En álgebra abstracta y computación cuántica, el problema planteado por Daniel R. Simon (conocido como problema de Simon) es un caso particular del problema del subgrupo oculto (Hidden Subgroup Problem, HSP), el cual ha sido útil para el planteamiento de algoritmos cuánticos que son eficientes, a diferencia de sus homólogos clásicos, permitiendo resolver problemas teóricos propuestos en las últimas décadas cuyas soluciones son de vital importancia en el campo de la computación cuántica.

Para resolver el problema de Simon se han desarrollado algoritmos clásicos que utilizan fuerza bruta, de los cuales se sabe que su complejidad es exponencial. Para encontrar una  solución eficiente se ha recurrido a algoritmos cuánticos, como el propuesto por el mismo Simon, cuya complejidad es polinomial, reduciendo así el tiempo de cómputo de forma significativa.

Se han desarrollado algoritmos cuánticos para otros casos particulares del problema del subgrupo oculto, pero solo son eficientes aquellos que trabajan sobre grupos abelianos (como el de Simon). Para los grupos no abelianos aún no se han encontrado algoritmos cuánticos eficientes, de hecho estos no llegan a tener mejor desempeño que las soluciones clásicas.

Conceptos previos

Relación de equivalencia

Una relación de equivalencia sobre un grupo ${\displaystyle G}$ es una relación ${\displaystyle E\subseteq G\times G}$ que cumple las propiedades:

1. Reflexiva: ${\displaystyle gEg}$ para cada ${\displaystyle g}$ que pertenece a ${\displaystyle G}$.
2. Simétrica: Si ${\displaystyle gEt}$ entonces ${\displaystyle tEg}$.
3. Transitiva: Si ${\displaystyle gEt}$ y ${\displaystyle tEu}$ entonces ${\displaystyle gEu}$.

Los elementos ${\displaystyle g,t}$ y ${\displaystyle u}$ son elementos de ${\displaystyle G}$; note que cada elemento de ${\displaystyle G}$ está envuelto en un requerimiento 1,2 o 3.

Congruencia entre conjuntos

Congruencia por izquierda

Sea ${\displaystyle H}$ un subgrupo de ${\displaystyle G}$, entonces dos elementos ${\displaystyle g_{i}}$ y ${\displaystyle g_{j}}$ de ${\displaystyle G}$ son congruentes módulo ${\displaystyle H}$ si hay un elemento ${\displaystyle h_{k}}$ para el cual ${\displaystyle g_{i}=g_{j}h_{k}.}$

Congruencia por derecha

Sea ${\displaystyle H}$ un subgrupo de ${\displaystyle G}$, entonces dos elementos ${\displaystyle g_{i}}$y ${\displaystyle g_{j}}$ de ${\displaystyle G}$ son congruentes módulo ${\displaystyle H}$ si hay un elemento ${\displaystyle h_{k}}$ para el cual ${\displaystyle g_{i}=h_{k}g_{j}.}$

Suponiendo que ${\displaystyle H}$ es un subgrupo de ${\displaystyle G}$, la congruencia módulo ${\displaystyle H}$ es una relación de equivalencia en ${\displaystyle G}$. La congruencia módulo ${\displaystyle H}$ particiona a ${\displaystyle G}$ en una colección de clases de equivalencia que son disyuntas 2 a 2. Cada clase está formada por elementos que son congruentes entre sí.

Cosets

Sea ${\displaystyle H}$ un subgrupo de ${\displaystyle G}$, y sea ${\displaystyle g\in G}$. El coset por izquierda de ${\displaystyle g}$ respecto a ${\displaystyle H}$ es el conjunto ${\displaystyle gH=\{gh_{1},gh_{2},...,gh_{k},...\}}$ siendo ${\displaystyle H=\{h_{1},h_{2},...,h_{k},...\}}$. Así mismo se define el coset por derecha como el conjunto ${\displaystyle Hg=\{h_{1}g,h_{2}g,...,h_{k}g,...\}}$ siendo ${\displaystyle H=\{h_{1},h_{2},...,h_{k},...\}}$.

Note que ${\displaystyle g_{i}\equiv }$${\displaystyle g_{j}}$(mod ${\displaystyle H}$), si y sólo si, sus respectivas clases de equivalencia o cosets son iguales, es decir, ${\displaystyle g_{i}H=g_{j}H}$. Para obtener distintos cosets, se usarán elementos ${\displaystyle g_{i}}$y ${\displaystyle g_{j}}$que sean incongruentes módulo ${\displaystyle H}$.^[1]​

Periodicidad de funciones que actúan sobre grupos

Definición

Una función f se dice periódica si, para alguna constante P diferente de cero, se tiene que:

${\displaystyle f(x+P)=f(x)}$

Para todos los valores de x en el dominio de f. Una constante P distinta de cero para la cual se cumpla la propiedad anterior se denomina período de la función. La menor constante positiva P con esta propiedad, se denomina período fundamental (también período primitivo, período básico o período primo). A menudo, el "período" de una función se utiliza para indicar su período fundamental. Una función con período P se repetirá en intervalos de longitud P, y estos intervalos a veces también se conocen como períodos de la función.

Importancia

Aunque en principio pueda no parecerlo, lo cierto es que las funciones periódicas se relacionan de manera directa con uno de los problemas más difíciles de resolver hasta el momento: la descomposición de un número entero en factores primos.

Aun cuando cualquier número entero tiene una descomposición única en un producto de números primos, encontrar dichos factores primos es un problema difícil. De hecho, la seguridad de las transacciones en línea se basa en el criptosistema de clave pública RSA, cuya fuerza reside en la dificultad de factorizar números grandes.^[2]​ En la práctica factorizar enteros con cientos de dígitos es prácticamente imposible, el número más grande factorizado hasta la fecha es RSA-768, un número de 232 cifras decimales, el cual fue factorizado en 2009.^[3]​ En la actualidad RSA usa números primos del orden de ${\displaystyle 10^{300}}$ y ${\displaystyle 10^{600}}$.

Desde la década de los 70’s es conocido por los matemáticos que factorizar se hace más fácil si se puede resolver otro problema difícil: encontrar el periodo de la función exponencial modular.^[2]​ El problema de Simon está estrechamente relacionado con este problema, ya que el algoritmo de Simon, un algoritmo cuántico probabilístico con una complejidad polinomial, resuelve el problema de la determinación del periodo de una función periódica ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{n}}$ (el problema de la factorización se puede reducir a este último). En contraste, el algoritmo clásico tiene una complejidad exponencial. La implicación del uso de estas técnicas teóricas es la vulnerabilidad de la información protegida en la actualidad por métodos tipo RSA.

Problema del subgrupo oculto

Historia

El problema del subgrupo oculto surge en 1994, cuando Peter Shor Williston, profesor estadounidense de matemáticas aplicadas, basándose en el trabajo de David Elieser Deutsch, profesor israelí y pionero de la computación cuántica, y Daniel R. Simon, master en ciencias de la computación de la Universidad de Toronto, encontró un algoritmo cuántico que podía factorizar enteros exponencialmente más rápido que los métodos clásicos conocidos. Alexei Kitaev, un profesor de física ruso-estadounidense, concluyó que estos algoritmos encajan en un marco para encontrar generadores de subgrupos que son ocultados mediante una función.^[4]​

Definición

La definición formal del problema del subgrupo oculto (HSP) es:

Input: Sea ${\displaystyle (G,f)}$, donde ${\displaystyle G}$ es un grupo y ${\displaystyle f}$ una función. ${\displaystyle f:G\rightarrow X}$, entonces existe ${\displaystyle H\subseteq G}$ tal que ${\displaystyle f}$ es constante sobre los cosets de ${\displaystyle H}$.

Problema: Encontrar ${\displaystyle H}$.

Eficiencia cuántica

Si ${\displaystyle G}$ es un grupo Abeliano finito, la determinación del problema del subgrupo oculto puede ser teóricamente resuelta mediante un algoritmo cuántico de manera eficiente, es decir con un orden de complejidad ${\displaystyle O[poly{\bigl (}\log \mid G\mid {\bigr )}]}$. Sin embargo, no se tiene conocimiento de una solución cuántica eficiente que se pueda implementar cuando se trata con grupos finitos no-Abelianos.

Ejemplo

Definiendo el tamaño de un circuito cuántico como el número mínimo de operaciones elementales que deben componerse para obtener el circuito, y definiendo un Qubit como un vector de módulo unidad en un espacio vectorial complejo bidimensional; suponga que se quiere determinar el orden de un grupo finito Abeliano dado un conjunto generador. Dado un grupo ${\displaystyle G}$ es posible representar cada elemento del grupo utilizando aproximadamente ${\displaystyle \log \mid G\mid }$ Qubits.

Para resolver de manera eficiente este problema mediante un algoritmo cuántico es necesario que el tamaño del circuito cuántico que va a computar el orden de ${\displaystyle G}$ sea de tamaño polinomial en ${\displaystyle \log \mid G\mid }$, dado que ${\displaystyle G}$ varía en toda la familia de grupos Abelianos finitos. Finalmente se requiere una “Clase uniforme de algoritmos”, la cual afirma que para un problema de tamaño ${\displaystyle n}$, existe una máquina de Turing que dado ${\displaystyle n}$, puede producir la descripción del circuito en un número de pasos igual a un polinomio en ${\displaystyle n}$. Esto permite asegurar que (en teoría)  es posible construir una máquina explícita para resolver cada problema con un tiempo polinomial en el tamaño del problema.^[4]​

Definición del problema de Simon

Daniel R. Simon propuso en 1994 un problema en el que se demuestra el poder de la computación cuántica. Éste se presenta de la siguiente manera:

Input: ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{n}}$, donde la función cumple alguna de las siguientes condiciones:

1. ${\displaystyle f}$ es 1 a 1, es decir, la función es inyectiva.
2. Existe una cadena ${\displaystyle s}$ no trivial tal que ${\displaystyle \forall x,y\in \{0,1\}^{n},\,f(x)=f(y)\leftrightarrow y=x\oplus s}$, donde el símbolo denota la operación binaria XOR (O exclusivo)

Problema: Determinar cuál de las condiciones prevalece para ${\displaystyle f}$ y en caso de ser la segunda, determinar cuál es la cadena ${\displaystyle s}$.^[5]​

Relación del problema del subgrupo oculto con el problema de Simon

La relación entre los problemas de Simon y del subgrupo oculto no es evidente, pero de hecho, es posible definirlo utilizando las herramientas que brinda la teoría de grupos.  Esto puede resultar útil al momento de buscar similitudes entre este y otros problemas, que en principio no tienen relación aparente, así como similitudes en sus posibles soluciones.

Buscando la estructura de grupo en el problema de Simon

Lo primero que se debe buscar para formar un grupo es un conjunto y una operación binaria sobre dicho conjunto. En el caso del problema de Simon, se trabaja sobre el conjunto de cadenas de bits de tamaño ${\displaystyle n}$, donde ${\displaystyle n}$ es un entero positivo. El problema de Simon también involucra la operación binaria XOR, definida de la siguiente manera:

Sean ${\displaystyle a}$ y ${\displaystyle b}$ bits

${\displaystyle a\oplus b=0}$ si ${\displaystyle a=b}$

${\displaystyle a\oplus b=1}$ si ${\displaystyle a\neq b}$

El problema de Simon se refiere al grupo ${\displaystyle G=(\{0,1\}^{n},\oplus )}$, que resulta ser abeliano.^[6]​

Aplicando el problema del subgrupo oculto al grupo de Simon

Sea ${\displaystyle f:\{0,1\}^{n}\rightarrow A}$ y sea ${\displaystyle H}$ subgrupo de ${\displaystyle G}$, se dice que ${\displaystyle f}$ es H-periódica si y sólo si se cumple:

${\displaystyle \forall x\forall h_{i}\forall h_{j}(h_{i},h_{j}\in xH\Rightarrow f(h_{i})=f(h_{j})=f(x))}$

${\displaystyle \forall h\in xH\forall g\notin xH(f(h)\neq f(g))}$

En otras palabras, la función ${\displaystyle f}$ es constante solo para elementos de un mismo coset.

Problema de Simon en términos del problema del subgrupo oculto

El problema de Simon define una función ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{n}}$ que resulta ser H-periódica para un subgrupo ${\displaystyle H=\langle s\rangle }$ de ${\displaystyle G}$ donde ${\displaystyle s}$ pertenece a ${\displaystyle G}$.

En ${\displaystyle G}$ la inversa de cualquier elemento perteneciente al grupo es ella misma, entonces el orden de ${\displaystyle s}$ es 2. Por lo tanto ${\displaystyle H}$ es un subgrupo de dos elementos; ${\displaystyle s}$, y la identidad.

${\displaystyle H=(\{e,s\},\oplus )}$

Se puede entender la condición ${\displaystyle \forall x\in G(f(x)=f(x\oplus s))}$ planteada en el problema de Simon como la condición planteada en el problema del subgrupo oculto, formando el coset ${\displaystyle xH}$.

Según la definición dada para ${\displaystyle H}$, se sabe que ${\displaystyle h}$ puede ser ${\displaystyle s}$ o ${\displaystyle e}$.

En estos términos, el problema de Simon consiste en encontrar el elemento generador del subgrupo oculto ${\displaystyle H}$,^[7]​ o dicho en otras palabras, encontrar el periodo de la función ${\displaystyle f}$ que oculta dicho subgrupo.

A partir de las condiciones que presenta la función puede suponerse que no existe una relación entre ellas pero lo cierto es que independientemente del caso que aplique para la función a estudiar, la segunda condición es parcialmente verdadera y gracias a la estructura que el grupo ${\displaystyle G=(\{0,1\}^{n},\oplus )}$ presenta se puede establecer la siguiente observación:

Se sabe del grupo ${\displaystyle G}$ que su identidad es la cadena ${\displaystyle e=0^{n}}$ y por teoría de grupos es válido afirmar que para toda cadena ${\displaystyle a}$ que pertenezca al grupo, ${\displaystyle a*e=e*a=a}$. Entonces, si se aplica la segunda condición haciendo una excepción a la condición de que ${\displaystyle s}$ es diferente a la cadena trivial, se obtiene que ${\displaystyle f(x)=f(y)\leftrightarrow y=x\oplus 0^{n}}$, lo que es equivalente a decir que ${\displaystyle f(x)=f(y)\leftrightarrow 0^{n}=x\oplus y}$. Por definición de la operación XOR se sabe que al operar dos elementos se obtiene como respuesta 0 si los elementos son iguales, por lo que se puede que concluir que ${\displaystyle x=y}$, lo que implica que la función envía a un elemento en sí mismo si ${\displaystyle s=0^{n}}$ así que la función estudiada corresponde a la función identidad la cual es 1 a 1, por lo que las condiciones (1) y (2) sobre la función están relacionadas y según el valor de ${\displaystyle s}$, se obtiene (2) para una cadena no trivial o (1) en caso contrario.

Soluciones al problema de Simon

Solución clásica

Para solucionar el problema primero es necesario encontrar el valor adecuado de ${\displaystyle s}$ diferente al trivial, o en su defecto, ${\displaystyle s=0^{n}}$; por lo tanto, se deben revisar todos los valores que pueda tomar ${\displaystyle s}$. Como hay ${\displaystyle 2^{n}}$ posibles elecciones de ${\displaystyle s}$, la complejidad sería de ${\displaystyle O(2^{n})}$. Luego se evalúa la función “q” veces:

Si la función es 2 a 1, entonces, como mucho, q tiene que ser la mitad de entradas para encontrar una repetición.

Si se tienen que evaluar más, entonces, la función es 1 a 1 y ${\displaystyle s=0^{n}}$.

En definitiva, el número de evaluaciones en el peor de los casos será ${\displaystyle {\frac {2^{n}}{2}}+1}$, es decir que la complejidad es de ${\displaystyle O(2^{n-1}+1)}$, la cual es mayor a la que se registraría en la solución cuántica al problema de Simon, la cual es polinomial.

Solución cuántica

Simon propone en su escrito la siguiente rutina para resolver el problema con complejidad polinomial:

Se llevan a cabo ${\displaystyle O(n)}$ repeticiones de la Rutina Doble de Fourier:

1. Realizar la transformación ${\displaystyle F}$ en una cadena de ${\displaystyle n}$ ceros, produciendo ${\displaystyle 2^{-n/2}\sum _{x}|x\rangle }$.
2. Calcular ${\displaystyle f(x)}$, concatenando la respuesta a ${\displaystyle x}$, esto produce ${\displaystyle 2^{-n/2}\sum _{x}|(x,f(x))\rangle }$.
3. Ejecutar ${\displaystyle F}$ sobre ${\displaystyle x}$, produciendo ${\displaystyle 2^{-n}\sum _{y}\sum _{x}(-1)^{x*y}|(y,f(x))\rangle }$

Fin de la rutina doble de Fourier

Luego de estas ${\displaystyle O(n)}$ repeticiones, se obtienen suficientes valores linealmente independientes de ${\displaystyle y}$ que permiten determinar el valor de la cadena ${\displaystyle s}$ al resolver el sistema de ecuaciones lineales definido por los valores de ${\displaystyle y}$.

Por lo tanto, la complejidad de todo el algoritmo es ${\displaystyle O(nT_{f}(n)+G(n))}$, donde ${\displaystyle T_{f}(n)}$ es el tiempo requerido para calcular ${\displaystyle f}$ en inputs de tamaño ${\displaystyle n}$, y ${\displaystyle G(n)}$ es el tiempo requerido para resolver el sistema lineal de ecuaciones de ${\displaystyle n}$x${\displaystyle n}$.^[5]​

Referencias