Algoritmo de búsqueda de orden para algoritmos cuánticos

Sean ${\displaystyle x}$ y ${\displaystyle N}$ enteros positivos sin divisores comunes, se define el orden ${\displaystyle r}$ como el menor número entero tal que ${\displaystyle x^{r}=1}$ (módulo ${\displaystyle N}$).

No existe un algoritmo clásico que resuelva el problema de encontrar el orden fijados ${\displaystyle x}$ y ${\displaystyle N}$ cualesquiera con recursos polinómicos. Por este motivo se hace necesaria la implementación de un algoritmo cuántico eficiente tal como el que va a explicarse haciendo uso de lo que se conoce como estimación de fase.^[2][3]

De hecho, el algoritmo cuántico para encontrar el orden consiste en el algoritmo cuántico de estimación de fase aplicado al siguiente operador unitario:

${\displaystyle U|y>=|xy(mod\ N)>}$

con ${\displaystyle y\in \{0,1\}^{L}}$, actuando no trivialmente solo cuando ${\displaystyle 0\leq y\leq N-1}$.

Este operador tiene como autoestados:

${\displaystyle |u_{s}>\equiv {\frac {1}{\sqrt {r}}}\sum _{k=0}^{r-1}exp[{\frac {-i2\pi sk}{r}}]|x^{k}\ mod\ N>}$

Fácilmente se comprueba que efectivamente al actuar el operador ${\displaystyle U}$ sobre este autoestado obtenemos el mismo autoestado salvo una fase (su autovalor):

${\displaystyle U|u_{s}>\equiv {\frac {1}{\sqrt {r}}}\sum _{k'=0}^{r-1}exp[{\frac {-i2\pi sk'}{r}}]|x^{k'+1}\ mod\ N>={\frac {1}{\sqrt {r}}}\sum _{k=1}^{r}exp[{\frac {-i2\pi s(k-1)}{r}}]|x^{k}\ mod\ N>=exp[{\frac {i2\pi s}{r}}]{\frac {1}{\sqrt {r}}}\sum _{k=1}^{r}exp[{\frac {-i2\pi sk}{r}}]|x^{k}\ mod\ N>=exp[{\frac {i2\pi s}{r}}]|u_{s}>}$

Para recuperar el autoestado hemos necesitado que el sumando correspondiente a ${\displaystyle k=r}$ sea igual al correspondiente a ${\displaystyle k=0}$, lo cual se cumple por la definición de orden que hemos dado.

La estimación de fase proporcionará estos autovalores del cual obtendremos el orden. Para llevar a cabo este procedimiento, hay dos requerimientos:

• Tener procedimientos eficientes para implementar una operación controlada ${\displaystyle U^{2j}}$ para cualquier entero ${\displaystyle j}$, lo que se consigue mediante la exponenciación modular.
• Ser capaces de preparar un autoestado con autovalor no trivial, que se toma como elección ad hoc como:^[2][3]

${\displaystyle {\frac {1}{\sqrt {r}}}\sum _{s=0}^{r-1}|u_{s}>\equiv |1>}$

Buscamos una transformación del tipo:

${\displaystyle |z>|y>\longrightarrow |z>|x^{z}y\ (mod\ N)>}$

donde el primer ${\displaystyle |z>}$ corresponde a los ${\displaystyle t}$ qubits del primer registro e ${\displaystyle |y>}$ corresponde al segundo registro, tal y como se explica en el algoritmo cuántico de estimación de fase.

Por lo visto anteriormente, es conocido que dicha transformación puede darse por medio de la aplicación del operador ${\displaystyle U}$:

${\displaystyle |z>|y>\longrightarrow |z>U^{z}|y>=|z>U^{z_{t}2^{t-1}}...U^{z_{1}2^{0}}|y>=|z>|x^{z_{t}2^{t-1}}\times ...\times x^{z_{1}2^{0}}y>=|z>|x^{z}y\ (mod\ N)>}$

donde se ha escrito ${\displaystyle z}$ (el contenido del primer registro) en notación binaria.

Así, el circuito cuántico del algoritmo para encontrar el orden se resume en lo anterior donde los ${\displaystyle t}$ qubits del primer registro son ${\displaystyle |0>}$ y el estado del segundo registro es precisamente el autovector definido como ${\displaystyle |1>}$. Este algoritmo, como ya se ha visto en estimación de fase, proporciona el valor de ${\displaystyle \varphi ={\frac {s}{r}}}$. Por tanto, ya solo queda ser capaces de hallar el valor de r, para lo cual se va a explicar a continuación la subrutina que habría que implementar:^[2]

La fracción continua constituye una transformación sencilla y original de una fracción que tiene gran utilidad a la hora de estudiar números irracionales, y que en el contexto dentro del algoritmo de Shor no será más que una subrutina puramente clásica que no introducirá una mayor dificultad teórica. Esta idea se entiende muy bien explicándolo con un ejemplo sencillo:

${\displaystyle {\frac {7}{33}}={\frac {1}{\frac {33}{7}}}={\frac {1}{4+{\frac {5}{7}}}}={\frac {1}{4+{\frac {1}{\frac {7}{5}}}}}={\frac {1}{4+{\frac {1}{1+{\frac {2}{5}}}}}}={\frac {1}{4+{\frac {1}{1+{\frac {1}{\frac {5}{2}}}}}}}={\frac {1}{4+{\frac {1}{1+{\frac {1}{2+{\frac {1}{2}}}}}}}}\longrightarrow [4,1,2,2]}$

Con este procedimiento se puede conocer el cociente ${\displaystyle s/r}$ con el previo conocimiento del correspondiente conjunto de enteros. Puesto que no es conocido dicho conjunto de enteros, básicamente se tiene que ir probando aleatoriamente combinaciones de enteros hasta que se obtiene el valor del cociente. Cuando se llega a esta situación basta con realizar marcha atrás el desarrollo y obtendremos unos ${\displaystyle s}$ y ${\displaystyle r,}$ que ahora se verá que no tienen por qué ser los requeridos (${\displaystyle r}$ podría no ser el orden).

Como se puede entender, este algoritmo conlleva un tiempo de cómputo increíblemente alto en general, por lo que no constituye un método muy eficiente para obtener el orden. Además, este método podría dar un ${\displaystyle r}$ que no coincida con el orden por dos motivos:

• Que el algoritmo de estimación de fase haya proporcionado un ${\displaystyle s/r}$ erróneo, posibilidad que se puede minimizar cuanto se quiera aumentando el número de qubits ${\displaystyle t}$ del primer registro en estimación de fase (aumentar el circuito).
• Que ${\displaystyle s}$ y ${\displaystyle r}$ tengan máximo común divisor distinto de 1 y por tanto ${\displaystyle r}$ no sea el menor número posible que cumpla que ${\displaystyle x^{r}=1}$ (módulo ${\displaystyle N}$).

Para estar seguros de que no se da este segundo motivo de error, se puede repetir el proceso un número alto de veces concreto que ahora razonaremos. Para ello, vamos a dar dos resultados útiles:

• Dos números son coprimos si su máximo común divisor es 1. Como consecuencia, cualquier número primo es coprimo con todos.
• Dado un número entero positivo ${\displaystyle \alpha }$, hay como mínimo ${\displaystyle {\frac {\alpha }{2\log {\alpha }}}}$ números primos bajo este. Así, al elegir un número menor que ${\displaystyle \alpha }$ la probabilidad de que este número sea primo es como mínimo ${\displaystyle {\frac {1}{2\log \alpha }}}$.

Por lo contado hasta ahora, también se conoce que ${\displaystyle s<r}$. Puesto que la probabilidad de que conocido ${\displaystyle r}$ se cumpla que ${\displaystyle s}$ es un número primo (y por tanto coprimo con ${\displaystyle r}$) es como mínimo ${\displaystyle {\frac {1}{2\log r}}}$, habría que elegir ${\displaystyle s}$ aleatoriamente ${\displaystyle 2\log r}$ veces para hallar (con alta probabilidad) un ${\displaystyle s}$ primo. Sin embargo, no se conoce ${\displaystyle r}$. Por otro lado, se extrae inmediatamente de la definición de orden dada que ${\displaystyle r<N}$, no haciendo falta conocer ${\displaystyle r}$ previamente, pues repitiendo el proceso de expansión de fracciones ${\displaystyle 2\log N}$ veces aleatoriamente puede asegurarse de nuevo con alta probabilidad que uno de los valores de ${\displaystyle s}$ hallados es primo. Para cada "elección aleatoria" de ${\displaystyle s}$ y ${\displaystyle r}$ hasta que se cumpla ${\displaystyle x^{r}=1}$ (módulo ${\displaystyle N}$), pudiendo afirmar definitivamente que este es el orden.^[2]