Algoritmo de Shor

Ahora nos centraremos en el problema de la factorización entera y veremos cómo puede resolverse de forma eficiente en un ordenador cuántico utilizando la estimación de fase. El algoritmo que obtendremos es el algoritmo de Shor para la factorización de enteros. Shor no describió su algoritmo específicamente en términos de estimación de fase, pero es una forma natural e intuitiva de explicar cómo funciona.

Empezaremos analizando un problema intermedio conocido como el problema de búsqueda de órdenes y veremos cómo la estimación de fase proporciona una solución a este problema. A continuación veremos cómo una solución eficiente al problema de búsqueda de órdenes nos da una solución eficiente al problema de factorización de enteros. (Cuando la solución a un problema proporciona una solución a otro problema como éste, decimos que el segundo problema se reduce al primero - así que en este caso estamos reduciendo la factorización entera a la búsqueda de órdenes) Esta segunda parte del algoritmo de Shor no hace uso de la computación cuántica en absoluto; es completamente clásica. La computación cuántica sólo es necesaria para resolver la búsqueda de órdenes.

---

El problema de la búsqueda de pedidos

Algunos conceptos básicos de teoría de números

Para explicar el problema de la búsqueda de órdenes y cómo se puede resolver utilizando la estimación de fase, será útil empezar con un par de conceptos básicos de teoría de números e introducir algunas notaciones útiles por el camino.

Para empezar, para cualquier número entero positivo dado $N,$ defina el conjunto $\mathbb{Z}_N$ de la siguiente manera.

$$\mathbb{Z}_N = \{0,1,\ldots,N-1\}$$

Por ejemplo, $\mathbb{Z}_1 = \{0\},\;$ $\mathbb{Z}_2 = \{0,1\},\;$ $\mathbb{Z}_3 = \{0,1,2\},\;$ etc.

Son conjuntos de números, pero podemos pensar en ellos como algo más que conjuntos. En concreto, podemos pensar en operaciones aritméticas en $\mathbb{Z}_N$, como la suma y la multiplicación, y si acordamos tomar siempre nuestras respuestas en módulo $N$ (es decir, dividir por $N$ y tomar el resto como resultado), siempre nos mantendremos dentro de este conjunto cuando realicemos estas operaciones. Las dos operaciones específicas de suma y multiplicación, ambas tomadas módulo $N,$ convierten $\mathbb{Z}_N$ en un anillo, que es un tipo de objeto fundamentalmente importante en álgebra.

Por ejemplo, $3$ y $5$ son elementos de $\mathbb{Z}_7,$ y si los multiplicamos entre sí obtenemos $3\cdot 5 = 15,$ que deja un resto de $1$ al dividirlo por $7.$ A veces expresamos esto de la siguiente manera

$$3 \cdot 5 \equiv 1 \; (\textrm{mod } 7)$$

Pero también podemos escribir simplemente $3 \cdot 5 = 1,$, siempre que quede claro que estamos trabajando en $\mathbb{Z}_7,$, para que nuestra notación sea lo más sencilla posible.

Como ejemplo, aquí están las tablas de sumar y multiplicar para $\mathbb{Z}_6.$

$$\begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \end{array} \qquad \begin{array}{c|cccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \end{array}$$

Entre los $N$ elementos de $\mathbb{Z}_N,$ los elementos $a\in\mathbb{Z}_N$ que satisfacen $\gcd(a,N) = 1$ son especiales. Con frecuencia, el conjunto que contiene estos elementos se denota con una estrella, como en el caso anterior.

$$\mathbb{Z}_N^{\ast} = \{a\in \mathbb{Z}_N : \gcd(a,N) = 1\}$$

Si centramos nuestra atención en la operación de multiplicación, el conjunto $\mathbb{Z}_N^{\ast}$ forma un grupo -concretamente un grupo abeliano-, que es otro tipo de objeto importante en álgebra. Es un hecho básico sobre estos conjuntos (y grupos finitos en general), que si escogemos cualquier elemento $a\in\mathbb{Z}_N^{\ast}$ y multiplicamos repetidamente $a$ a sí mismo, siempre obtendremos eventualmente el número $1.$

Para un primer ejemplo, tomemos $N=6.$ Tenemos que $5\in\mathbb{Z}_6^{\ast}$ porque $\gcd(5,6) = 1,$ y si multiplicamos $5$ a sí mismo obtenemos $1,$ como confirma la tabla anterior.

$$5^2 = 1 \quad \text{(working within $\mathbb{Z}_6$)}$$

Como segundo ejemplo, tomemos $N = 21.$ Si recorremos los números de $0$ a $20,$ los que tienen DGC igual a $1$ con $21$ son los siguientes.

$$\mathbb{Z}_{21}^{\ast} = \{1,2,4,5,8,10,11,13,16,17,19,20\}$$

Para cada uno de estos elementos, es posible elevar ese número a una potencia entera positiva para obtener $1.$ Estas son las potencias más pequeñas para las que esto funciona:

$$\begin{array}{ccc} 1^{1} = 1 \quad & 8^{2} = 1 \quad & 16^{3} = 1 \\[1mm] 2^{6} = 1 \quad & 10^{6} = 1 \quad & 17^{6} = 1 \\[1mm] 4^{3} = 1 \quad & 11^{6} = 1 \quad & 19^{6} = 1 \\[1mm] 5^{6} = 1 \quad & 13^{2} = 1 \quad & 20^{2} = 1 \end{array}$$

Naturalmente, estamos trabajando en $\mathbb{Z}_{21}$ para todas estas ecuaciones, que no nos hemos molestado en escribir: las damos por implícitas para no complicar las cosas. Seguiremos haciéndolo durante el resto de la lección.

Descripción del problema y relación con la estimación de fase

Ahora podemos plantear el problema de búsqueda de órdenes.

Entrada: enteros positivos $N$ y $a$ que satisfagan $\gcd(N,a) = 1$\ Salida: el menor entero positivo $r$ tal que $a^r \equiv 1$ $(\textrm{mod } N)$

Alternativamente, en términos de la notación que acabamos de introducir más arriba, se nos da $a \in \mathbb{Z}_N^{\ast},$ y buscamos el menor número entero positivo $r$ tal que $a^r = 1.$ Este número $r$ se llama el orden de $a$ módulo $N.$

Para conectar el problema de búsqueda de orden con la estimación de fase, pensemos en la operación definida sobre un sistema cuyos estados clásicos corresponden a $\mathbb{Z}_N,$ donde multiplicamos por un elemento fijo $a\in\mathbb{Z}_N^{\ast}.$

$$M_a \vert x\rangle = \vert ax \rangle \qquad \text{(for each $x\in\mathbb{Z}_N$)}$$

Para que quede claro, estamos haciendo la multiplicación en $\mathbb{Z}_N,$ por lo que está implícito que estamos tomando el producto módulo $N$ dentro de la cometa en el lado derecho de la ecuación.

Por ejemplo, si tomamos $N = 15$ y $a=2,$ entonces la acción de $M_2$ sobre la base estándar $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$ es la siguiente.

$$\begin{array}{ccc} M_{2} \vert 0 \rangle = \vert 0\rangle \quad & M_{2} \vert 5 \rangle = \vert 10\rangle \quad & M_{2} \vert 10 \rangle = \vert 5\rangle \\[1mm] M_{2} \vert 1 \rangle = \vert 2\rangle \quad & M_{2} \vert 6 \rangle = \vert 12\rangle \quad & M_{2} \vert 11 \rangle = \vert 7\rangle \\[1mm] M_{2} \vert 2 \rangle = \vert 4\rangle \quad & M_{2} \vert 7 \rangle = \vert 14\rangle \quad & M_{2} \vert 12 \rangle = \vert 9\rangle \\[1mm] M_{2} \vert 3 \rangle = \vert 6\rangle \quad & M_{2} \vert 8 \rangle = \vert 1\rangle \quad & M_{2} \vert 13 \rangle = \vert 11\rangle \\[1mm] M_{2} \vert 4 \rangle = \vert 8\rangle \quad & M_{2} \vert 9 \rangle = \vert 3\rangle \quad & M_{2} \vert 14 \rangle = \vert 13\rangle \end{array}$$

Esta es una operación unitaria siempre que $\gcd(a,N)=1;$ baraje los elementos de la base estándar $\{\vert 0\rangle,\ldots,\vert N-1\rangle\},$ por lo que como matriz es una matriz de permutación. Es evidente por su definición que esta operación es determinista, y una forma sencilla de ver que es invertible es pensar en el orden $r$ de $a$ módulo $N,$ y reconocer que la inversa de $M_a$ es $M_a^{r-1}.$

$$M_a^{r-1} M_a = M_a^r = M_{a^r} = M_1 = \mathbb{I}$$

Hay otra manera de pensar en la inversa que no requiere ningún conocimiento de $r$ (que, después de todo, es lo que estamos tratando de calcular). Para cada elemento $a\in\mathbb{Z}_N^{\ast}$ siempre hay un único elemento $b\in\mathbb{Z}_N^{\ast}$ que satisface $ab=1.$ Denotamos este elemento $b$ por $a^{-1},$ y puede ser calculado eficientemente; una extensión del algoritmo GCD de Euclides lo hace con un coste cuadrático en $\operatorname{lg}(N).$ Y así

$$M_{a^{-1}} M_a = M_{a^{-1}a} = M_1 = \mathbb{I}.$$

Así pues, la operación $M_a$ es a la vez determinista e invertible. Eso implica que está descrita por una matriz de permutación y, por tanto, es unitaria.

Pensemos ahora en los vectores y valores propios de la operación $M_a,$ suponiendo que $a\in\mathbb{Z}_N^{\ast}.$ Como se acaba de argumentar, esta suposición nos dice que $M_a$ es unitaria.

Hay $N$ valores propios de $M_a,$, incluido posiblemente el mismo valor propio repetido varias veces, y en general hay cierta libertad a la hora de seleccionar los vectores propios correspondientes, pero no tendremos que preocuparnos por todas las posibilidades. Empecemos de forma sencilla e identifiquemos sólo un vector propio de $M_a.$

$$\vert \psi_0 \rangle = \frac{\vert 1 \rangle + \vert a \rangle + \cdots + \vert a^{r-1} \rangle}{\sqrt{r}}$$

El número $r$ es el orden de $a$ módulo $N,$ aquí y en el resto de la lección. El valor propio asociado a este vector propio es $1$ porque no cambia cuando multiplicamos por $a.$

$$M_a \vert \psi_0 \rangle = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert a^r \rangle}{\sqrt{r}} = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert 1 \rangle}{\sqrt{r}} = \vert \psi_0 \rangle$$

Esto sucede porque $a^r = 1,$ por lo que cada estado base estándar $\vert a^k \rangle$ se desplaza a $\vert a^{k+1} \rangle$ para $k\leq r-1,$ y $\vert a^{r-1} \rangle$ se desplaza de nuevo a $\vert 1\rangle.$ Informalmente hablando, es como si estuviéramos agitando lentamente $\vert \psi_0 \rangle,$ pero ya está completamente agitado así que nada cambia.

He aquí otro ejemplo de un vector propio de $M_a.$ Este resulta ser más interesante en el contexto de la búsqueda de orden y la estimación de fase.

$$\vert \psi_1 \rangle = \frac{\vert 1 \rangle + \omega_r^{-1} \vert a \rangle + \cdots + \omega_r^{-(r-1)}\vert a^{r-1} \rangle}{\sqrt{r}}$$

Alternativamente, podemos escribir este vector utilizando una suma de la siguiente manera.

$$\vert \psi_1 \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle$$

Aquí vemos que el número complejo $\omega_r = e^{2\pi i/r}$ aparece de forma natural, debido a la forma en que funciona la multiplicación por $a$ módulo $N.$ Esta vez el valor propio correspondiente es $\omega_r.$ Para ver esto, primero podemos calcular de la siguiente manera.

$$M_a \vert \psi_1 \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} M_a\vert a^k \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^{k+1} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-(k - 1)} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\omega_r \sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle$$

Entonces, porque $\omega_r^{-r} = 1 = \omega_r^0$ y $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle,$ vemos que

$$\frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle = \vert\psi_1\rangle,$$

así que $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle.$

Utilizando el mismo razonamiento, podemos identificar pares adicionales de vector propio/valor propio para $M_a.$ Para cualquier elección de $j\in\{0,\ldots,r-1\}$ tenemos que

$$\vert \psi_j \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-jk} \vert a^k \rangle$$

es un vector propio de $M_a$ cuyo valor propio correspondiente es $\omega_r^j.$

$$M_a \vert \psi_j \rangle = \omega_r^j \vert \psi_j \rangle$$

Existen otros vectores propios de $M_a,$, pero no es necesario que nos ocupemos de ellos; nos centraremos únicamente en los vectores propios $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$ que acabamos de identificar.

---

Búsqueda de órdenes mediante estimación de fase

Para resolver el problema de búsqueda de orden para una elección dada de $a\in\mathbb{Z}_N^{\ast},$ podemos aplicar el procedimiento de estimación de fase a la operación $M_a.$

Para ello, necesitamos implementar no sólo $M_a$ eficientemente con un circuito cuántico, sino también $M_a^2,$ $M_a^4,$ $M_a^8,$ y así sucesivamente, llegando tan lejos como sea necesario para obtener una estimación suficientemente precisa del procedimiento de estimación de fase. Aquí explicaremos cómo se puede hacer, y más adelante averiguaremos exactamente cuánta precisión se necesita.

Empecemos con la operación $M_a$ por sí misma. Naturalmente, como estamos trabajando con el modelo de circuito cuántico, utilizaremos notación binaria para codificar los números comprendidos entre $0$ y $N-1.$ El mayor número que necesitamos codificar es $N-1,$, por lo que el número de bits que necesitamos es

$$n = \operatorname{lg}(N-1) = \lfloor \log(N-1) \rfloor + 1.$$

Por ejemplo, si en $N = 21$ tenemos $n = \operatorname{lg}(N-1) = 5.$ Este es el aspecto de la codificación de elementos de $\mathbb{Z}_{21}$ como cadenas binarias de longitud $5$.

$$\begin{gathered} 0 \mapsto 00000\\[1mm] 1 \mapsto 00001\\[1mm] \vdots\\[1mm] 20 \mapsto 10100 \end{gathered}$$

Y ahora, he aquí una definición precisa de cómo $M_a$ se define como una operación $n$ -qubit.

$$M_a \vert x\rangle = \begin{cases} \vert ax \; (\textrm{mod}\;N)\rangle & 0\leq x < N\\[1mm] \vert x\rangle & N\leq x < 2^n \end{cases}$$

La cuestión es que, aunque sólo nos importa cómo funciona $M_a$ para $\vert 0\rangle,\ldots,\vert N-1\rangle,$, tenemos que especificar cómo funciona para el resto de estados de la base estándar $2^n - N$, y tenemos que hacerlo de forma que nos siga dando una operación unitaria. Esto se consigue definiendo $M_a$ de forma que no afecte a los demás estados básicos estándar.

Utilizando los algoritmos para la multiplicación y división de enteros discutidos en la lección anterior, junto con la metodología para implementaciones reversibles y libres de basura de los mismos, podemos construir un circuito cuántico que realice $M_a,$ para cualquier elección de $a\in\mathbb{Z}_N^{\ast},$ a coste $O(n^2).$ He aquí una forma de hacerlo.

1. Construye un circuito para realizar la operación

$$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \vert y \oplus f_a(x)\rangle$$

donde

$$f_a(x) = \begin{cases} ax \; (\textrm{mod}\;N) & 0\leq x < N\\[1mm] x & N\leq x < 2^n \end{cases}$$

utilizando el método descrito en la lección anterior. Esto nos da un circuito de tamaño $O(n^2).$

2. Intercambia los dos sistemas $n$ -qubit utilizando $n$ swap gates para intercambiar los qubits individualmente.

3. De forma similar al primer paso, construye un circuito para la operación

$$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \bigl\vert y \oplus f_{a^{-1}}(x)\bigr\rangle$$

donde $a^{-1}$ es la inversa de $a$ en $\mathbb{Z}_N^{\ast}.$

Inicializando los qubits inferiores $n$ y componiendo los tres pasos, obtenemos esta transformación:

$$\vert x \rangle \vert 0^n \rangle \stackrel{\text{step 1}}{\mapsto} \vert x \rangle \vert f_a(x)\rangle \stackrel{\text{step 2}}{\mapsto} \vert f_a(x)\rangle \vert x \rangle \stackrel{\text{step 3}}{\mapsto} \vert f_a(x)\rangle \bigl\vert x \oplus f_{a^{-1}}(f_a(x)) \bigr\rangle = \vert f_a(x)\rangle\vert 0^n \rangle$$

El método requiere qubits de espacio de trabajo, pero al final vuelven a su estado inicial, lo que nos permite utilizar estos circuitos para la estimación de fase. El coste total del circuito que obtenemos es $O(n^2).$

Para realizar $M_a^2,$ $M_a^4,$ $M_a^8,$ y así sucesivamente, podemos utilizar exactamente el mismo método, excepto que sustituimos $a$ por $a^2,$ $a^4,$ $a^8,$ y así sucesivamente, como elementos de $\mathbb{Z}_N^{\ast}.$ Es decir, para cualquier potencia $k$ que elijamos, podemos crear un circuito para $M_a^k$ no iterando $k$ veces el circuito para $M_a,$ sino calculando $b = a^k \in \mathbb{Z}_N^{\ast}$ y luego usando el circuito para $M_b.$

El cálculo de potencias $a^k \in \mathbb{Z}_N$ es el problema de exponenciación modular mencionado en la lección anterior. Este cálculo se puede hacer de forma clásica, utilizando el algoritmo de exponenciación modular mencionado en la lección anterior (a menudo llamado algoritmo de potencia en la teoría computacional de números). De hecho, sólo requerimos power-of-2 potencias de $a,$ en concreto $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast},$ y podemos obtener estas potencias elevando iterativamente al cuadrado $m-1$ veces. Cada cuadratura puede realizarse mediante un circuito booleano de tamaño $O(n^2).$

En esencia, lo que estamos haciendo aquí es descargar el problema de iterar $M_a$ tantas como $2^{m-1}$ veces a una computación clásica eficiente. Y es una suerte que esto sea posible Para una elección arbitraria de un circuito cuántico en el problema de estimación de fase, es probable que esto no sea posible - y en ese caso el coste resultante para la estimación de fase crece exponencialmente en el número de qubits de control $m.$

Solución dada un vector propio conveniente

Para entender cómo podemos resolver el problema de búsqueda de órdenes utilizando la estimación de fase, empecemos suponiendo que ejecutamos el procedimiento de estimación de fase en la operación $M_a$ utilizando el vector propio $\vert\psi_1\rangle.$ Conseguir este eigenvector no es fácil, así que este no será el final de la historia, pero es útil empezar por aquí.

El valor propio de $M_a$ correspondiente al vector propio $\vert \psi_1\rangle$ es

$$\omega_r = e^{2\pi i \frac{1}{r}}.$$

Es decir, $\omega_r = e^{2\pi i \theta}$ para $\theta = 1/r.$ Por lo tanto, si ejecutamos el procedimiento de estimación de fase en $M_a$ utilizando el vector propio $\vert\psi_1\rangle,$ obtendremos una aproximación a $1/r.$ Calculando el recíproco podremos aprender $r$ - siempre que nuestra aproximación sea lo suficientemente buena.

Más en detalle, cuando ejecutamos el procedimiento de estimación de fase utilizando $m$ qubits de control, lo que obtenemos es un número $y\in\{0,\ldots,2^m-1\}.$ A continuación, tomamos $y/2^m$ como conjetura para $\theta,$, que es $1/r$ en el caso que nos ocupa. Para averiguar cuál es $r$ a partir de esta aproximación, lo natural es calcular el recíproco de nuestra aproximación y redondear al entero más próximo.

$$\left\lfloor \frac{2^m}{y} + \frac{1}{2} \right\rfloor$$

Por ejemplo, supongamos $r = 6$ y realizamos la estimación de fase en $M_a$ con el vector propio $\vert\psi_1\rangle$ utilizando los bits de control de $m = 5$. La mejor aproximación $5$ -bit a $1/r = 1/6$ es $5/32,$ y tenemos bastantes posibilidades (alrededor de $68\%$ en este caso) de obtener el resultado $y=5$ a partir de la estimación de fase. Tenemos

$$\frac{2^m}{y} = \frac{32}{5} = 6.4,$$

y redondeando al entero más próximo se obtiene $6,$, que es la respuesta correcta.

Por otro lado, si no utilizamos la precisión suficiente, es posible que no obtengamos la respuesta correcta. Por ejemplo, si tomamos $m = 4$ qubits de control en la estimación de fase, podríamos obtener la mejor aproximación de $4$ -bit a $1/r = 1/6,$ que es $3/16.$ Si tomamos el recíproco obtenemos

$$\frac{2^m}{y} = \frac{16}{3} = 5.333 \cdots$$

y redondeando al entero más próximo se obtiene una respuesta incorrecta de $5.$

¿Cuánta precisión necesitamos para obtener la respuesta correcta? Sabemos que el orden $r$ es un número entero, e intuitivamente lo que necesitamos es suficiente precisión para distinguir $1/r$ de las posibilidades cercanas, incluyendo $1/(r+1)$ y $1/(r-1).$ El número más cercano a $1/r$ del que tenemos que preocuparnos es $1/(r+1),$ y la distancia entre estos dos números es

$$\frac{1}{r} - \frac{1}{r+1} = \frac{1}{r(r+1)}.$$

Así, si queremos asegurarnos de que no confundimos $1/r$ con $1/(r+1),$ basta con utilizar la precisión suficiente para garantizar que una mejor aproximación $y/2^m$ a $1/r$ está más cerca de $1/r$ que de $1/(r+1).$ Si utilizamos la precisión suficiente para que

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert < \frac{1}{2 r (r+1)},$$

de modo que el error sea inferior a la mitad de la distancia entre $1/r$ y $1/(r+1),$, entonces $y/2^m$ estará más cerca de $1/r$ que de cualquier otra posibilidad, incluidas $1/(r+1)$ y $1/(r-1).$

Podemos comprobarlo de la siguiente manera. Supongamos que

$$\frac{y}{2^m} = \frac{1}{r} + \varepsilon$$

para $\varepsilon$ satisfaciendo

$$\vert\varepsilon\vert < \frac{1}{2 r (r+1)}.$$

Si tomamos el recíproco obtenemos

$$\frac{2^m}{y} = \frac{1}{\frac{1}{r} + \varepsilon} = \frac{r}{1+\varepsilon r} = r - \frac{\varepsilon r^2}{1+\varepsilon r}.$$

Maximizando en el numerador y minimizando en el denominador, podemos acotar lo lejos que estamos de $r$ de la siguiente manera.

$$\left\vert \frac{\varepsilon r^2}{1+\varepsilon r} \right\vert \leq \frac{ \frac{r^2}{2 r(r+1)}}{1 - \frac{r}{2r(r+1)}} = \frac{r}{2 r + 1} < \frac{1}{2}$$

Estamos a menos de $1/2$ de $r,$ así que, como era de esperar, llegaremos a $r$ cuando demos la vuelta.

Por desgracia, como aún no sabemos qué es $r$, no podemos utilizarlo para saber cuánta precisión necesitamos. Lo que podemos hacer en su lugar es utilizar el hecho de que $r$ debe ser menor que $N$ para asegurarnos de que utilizamos la precisión suficiente. En particular, si utilizamos la precisión suficiente para garantizar que la mejor aproximación $y/2^m$ a $1/r$ satisface

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert \leq \frac{1}{2N^2},$$

entonces tendremos suficiente precisión para determinar correctamente $r$ cuando tomemos el recíproco. Tomando $m = 2\operatorname{lg}(N)+1$ nos aseguramos de tener una alta probabilidad de obtener una estimación con esta precisión utilizando el método descrito anteriormente. (Tomar $m = 2\operatorname{lg}(N)$ es suficiente si nos sentimos cómodos con un límite inferior del 40% en la probabilidad de éxito)

Solución general

Como acabamos de ver, si tenemos el vector propio $\vert \psi_1 \rangle$ de $M_a,$ podemos aprender $r$ a través de la estimación de fase, siempre que utilicemos suficientes qubits de control para hacerlo con suficiente precisión. Por desgracia, no es fácil conseguir el vector propio $\vert\psi_1\rangle,$, así que tenemos que averiguar cómo proceder.

Supongamos momentáneamente que procedemos igual que arriba, excepto con el vector propio $\vert\psi_k\rangle$ en lugar de $\vert\psi_1\rangle,$ para cualquier elección de $k\in\{0,\ldots,r-1\}$ en la que decidamos pensar. El resultado que obtengamos del procedimiento de estimación de fase será una aproximación

$$\frac{y}{2^m} \approx \frac{k}{r}.$$

Trabajando bajo el supuesto de que no conocemos ni $k$ ni $r,$ esto podría o no permitirnos identificar $r.$ Por ejemplo, si $k = 0$ obtendremos una aproximación $y/2^m$ a $0,$ que desgraciadamente no nos dice nada. Sin embargo, este es un caso inusual; para otros valores de $k,$ al menos podremos aprender algo sobre $r.$

Podemos utilizar un algoritmo conocido como el algoritmo de la fracción continua para convertir nuestra aproximación $y/2^m$ en fracciones cercanas - incluyendo $k/r$ si la aproximación es lo suficientemente buena. No explicaremos aquí el algoritmo de la fracción continua. En su lugar, he aquí una declaración de un hecho conocido sobre este algoritmo.

Dado un número entero $N\geq 2$ y un número real $\alpha\in(0,1),$ existe a lo sumo una elección de enteros $u,v\in\{0,\ldots,N-1\}$ con $v\neq 0$ y $\gcd(u,v)=1$ satisfaciendo $\vert \alpha - u/v\vert < \frac{1}{2N^2}.$ Dados $\alpha$ y $N,$ el algoritmo de fracción continua encuentra $u$ y $v,$ o informa de que no existen. Este algoritmo puede implementarse como un circuito booleano de tamaño $O((\operatorname{lg}(N))^3).$

Si tenemos una aproximación muy cercana $y/2^m$ a $k/r,$ y ejecutamos el algoritmo de fracción continua para $N$ y $\alpha = y/2^m,$ obtendremos $u$ y $v,$ tal y como se describen en el hecho. El análisis del hecho permite concluir que

$$\frac{u}{v} = \frac{k}{r}.$$

Nótese en particular que no aprendemos necesariamente $k$ y $r,$ sólo aprendemos $k/r$ en los términos más bajos.

Por ejemplo, y como ya nos hemos dado cuenta, no vamos a aprender nada de $k=0.$ Pero ese es el único valor de $k$ en el que ocurre eso. Cuando $k$ es distinto de cero, puede tener factores comunes con $r,$ pero el número $v$ que obtenemos del algoritmo de la fracción continua debe al menos dividir a $r.$

Está lejos de ser obvio, pero es cierto que si tenemos la capacidad de aprender $u$ y $v$ para $u/v = k/r$ para $k\in\{0,\ldots,r-1\}$ elegidos uniformemente al azar, entonces es muy probable que seamos capaces de recuperar $r$ después de unas pocas muestras. En particular, si nuestra suposición para $r$ es el mínimo común múltiplo de todos los valores para el denominador $v$ que observamos, acertaremos con alta probabilidad. Intuitivamente hablando, algunos valores de $k$ no son buenos porque comparten factores comunes con $r,$ y esos factores comunes se nos ocultan cuando aprendemos $u$ y $v.$ Pero no es probable que las elecciones aleatorias de $k$ oculten los factores de $r$ durante mucho tiempo, y la probabilidad de que no adivinemos $r$ correctamente tomando el mínimo común múltiplo de los denominadores que observamos cae exponencialmente en el número de muestras.

Queda por abordar la cuestión de cómo conseguir un vector propio $\vert\psi_k\rangle$ de $M_a$ para ejecutar el procedimiento de estimación de fase. Resulta que, en realidad, no necesitamos crearlos

Lo que haremos en su lugar es ejecutar el procedimiento de estimación de fase en el estado $\vert 1\rangle,$ por el que entendemos la codificación binaria de $n$ -bit del número $1,$ en lugar de un eigenvector $\vert\psi\rangle$ de $M_a.$ Hasta ahora, sólo hemos hablado de ejecutar el procedimiento de estimación de fase en un eigenvector particular, pero nada nos impide ejecutar el procedimiento en un estado de entrada que no sea un eigenvector de $M_a,$ y eso es lo que estamos haciendo aquí con el estado $\vert 1\rangle.$ (Este no es un eigenvector de $M_a$ a menos que $a=1,$ que no es una opción que nos interese)

La razón para elegir el estado $\vert 1\rangle$ en lugar de un vector propio de $M_a$ es que la siguiente ecuación es cierta.

$$\vert 1\rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle$$

Una forma de verificar esta ecuación es comparar los productos internos de los dos lados con cada estado base estándar, utilizando las fórmulas mencionadas anteriormente en la lección para ayudar a evaluar los resultados del lado derecho. En consecuencia, obtendremos exactamente los mismos resultados de medición que si hubiéramos elegido $k\in\{0,\ldots,r-1\}$ uniformemente al azar y utilizado $\vert\psi_k\rangle$ como vector propio.

Para más detalle, imaginemos que ejecutamos el procedimiento de estimación de fase con el estado $\vert 1\rangle$ en lugar de uno de los vectores propios $\vert\psi_k\rangle.$ Tras realizar la transformada cuántica de Fourier inversa, obtenemos el estado

$$\frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle \vert \gamma_k\rangle,$$

donde

$$\vert\gamma_k\rangle = \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (k/r - y/2^m)} \vert y\rangle.$$

El vector $\vert\gamma_k\rangle$ representa el estado de los qubits superiores $m$ después de haberles realizado la inversa de la transformada cuántica de Fourier.

Así, en virtud del hecho de que $\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$ es un conjunto ortonormal, encontramos que una medición de los qubits superiores $m$ produce una aproximación $y/2^m$ al valor $k/r$ donde $k\in\{0,\ldots,r-1\}$ se elige uniformemente al azar. Como ya hemos comentado, esto nos permite aprender $r$ con un alto grado de confianza tras varias ejecuciones independientes, que era nuestro objetivo.

Coste total

El coste de ejecución de cada operación controlada-unitaria $M_a^k$ es $O(n^2).$ Hay $m$ operaciones controladas-unitarias, y tenemos $m = O(n),$ por lo que el coste total de las operaciones controladas-unitarias es $O(n^3).$ Además, tenemos $m$ puertas Hadamard (que contribuyen $O(n)$ al coste), y la transformada cuántica inversa de Fourier contribuye $O(n^2)$ al coste. Así pues, el coste de las operaciones controladas-unitarias domina el coste de todo el procedimiento - que es por tanto $O(n^3).$

Además del propio circuito cuántico, hay que realizar algunos cálculos clásicos. Esto incluye el cálculo de las potencias $a^k$ en $\mathbb{Z}_N$ para $k = 2, 4, 8, \ldots, 2^{m-1},$ que son necesarias para crear las puertas unitarias controladas, así como el algoritmo de fracción continua que convierte las aproximaciones de $\theta$ en fracciones. Estos cálculos pueden realizarse mediante circuitos booleanos con un coste total de $O(n^3).$

Como es habitual, todos estos límites pueden mejorarse utilizando algoritmos asintóticamente rápidos; estos límites suponen que estamos utilizando algoritmos estándar para las operaciones aritméticas básicas.

---

Factoring por búsqueda de pedidos

Lo último que tenemos que discutir es cómo la resolución del problema de búsqueda de órdenes nos ayuda a factorizar. Esta parte es completamente clásica: no tiene nada que ver específicamente con la computación cuántica.

Esta es la idea básica. Queremos factorizar el número $N,$ y podemos hacerlo recursivamente. En concreto, podemos centrarnos en la tarea de dividir $N,$, lo que significa encontrar dos enteros cualesquiera $b,c\geq 2$ para los que $N = bc.$ Esto no es posible si $N$ es un número primo, pero podemos comprobar eficientemente si $N$ es primo utilizando primero un algoritmo de comprobación de primalidad, y si $N$ no es primo intentaremos dividirlo. Una vez que dividimos $N,$ podemos simplemente recurrir en $b$ y $c$ hasta que todos nuestros factores sean primos y obtengamos la factorización prima de $N.$

Dividir números enteros pares es fácil: simplemente mostramos $2$ y $N/2.$

También es fácil dividir potencias perfectas, es decir, números de la forma $N = s^j$ para números enteros $s,j\geq 2,$ con sólo aproximando las raíces $N^{1/2},$ $N^{1/3},$ $N^{1/4},$ y así sucesivamente, y comprobando los enteros cercanos como sospechosos para $s.$ No necesitamos ir más allá de $\log(N)$ pasos en esta secuencia, porque en ese punto la raíz cae por debajo de $2$ y no revelará candidatos adicionales.

Es bueno que podamos hacer estas dos cosas porque la búsqueda de orden no nos ayudará a factorizar números pares o para potencias primos, donde el número $s$ resulta ser primo. Sin embargo, si $N$ es impar y no una potencia prima, la búsqueda de orden nos permite dividir $N.$

1. Elige al azar $a\in\{2,\ldots,N-1\}.$

2. Compute $d=\gcd(a,N).$

3. Si $d > 1$ entonces salida $b = d$ y $c = N/d$ y parada. De lo contrario, continúe con el siguiente paso sabiendo que $a\in\mathbb{Z}_N^{\ast}.$

4. Sea $r$ el orden de $a$ módulo $N.$ (Aquí es donde necesitamos encontrar el orden.)

5. Si $r$ es par:

   5.1 Calcular $x = a^{r/2} - 1$ módulo $N$ \ 5.2 Calcular $d = \gcd(x,N).$ \ 5.3 Si $d>1$ entonces salida $b=d$ y $c = N/d$ y parada.

6. Si se alcanza este punto, el algoritmo no ha conseguido encontrar un factor de $N.$

Una ejecución de este algoritmo puede no encontrar un factor de $N.$ Concretamente, esto ocurre en dos situaciones:

• El orden de $a$ módulo $N$ es impar.
• El orden de $a$ módulo $N$ es par y $\gcd\bigl(a^{r/2} - 1, N\bigr) = 1.$

Utilizando la teoría básica de números, se puede demostrar que, para una elección aleatoria de $a,$ con una probabilidad de al menos $1/2$, no se produce ninguno de estos sucesos. De hecho, la probabilidad de que ocurra cualquiera de los dos sucesos es como máximo $2^{-(m-1)}$, siendo $m$ el número de factores primos distintos de $N,$ por lo que es necesario suponer que $N$ no es una potencia prima. (La suposición de que $N$ es impar también es necesaria para que este hecho sea cierto)

Esto significa que cada ejecución tiene al menos un 50% de probabilidades de dividir $N.$ Por lo tanto, si ejecutamos el algoritmo $t$ veces, eligiendo aleatoriamente $a$ cada vez, conseguiremos dividir $N$ con una probabilidad de al menos $1 - 2^{-t}.$

La idea básica del algoritmo es la siguiente. Si tenemos una elección de $a$ para la cual el orden $r$ de $a$ módulo $N$ es par, entonces $r/2$ es un número entero y podemos considerar los números

$$a^{r/2} - 1\; (\textrm{mod}\; N) \quad \text{and} \quad a^{r/2} + 1\; (\textrm{mod}\; N).$$

Utilizando la fórmula $Z^2 - 1 = (Z+1)(Z-1),$ concluimos que

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr) = a^r - 1.$$

Ahora, sabemos que $a^r \; (\textrm{mod}\; N) = 1$ por la definición del orden - que es otra manera de decir que $N$ divide uniformemente a $a^r - 1.$ Eso significa que $N$ divide uniformemente el producto

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr).$$

Para que esto sea cierto, todos los factores primos de $N$ deben ser también factores primos de $a^{r/2} - 1$ o $a^{r/2} + 1$ (o ambos) - y para una selección aleatoria de $a$ resulta improbable que todos los factores primos de $N$ dividan uno de los términos y ninguno divida el otro. En caso contrario, siempre que algunos de los factores primos de $N$ dividan al primer término y otros dividan al segundo, podremos encontrar un factor no trivial de $N$ calculando el DGC con el primer término.