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 $N$, definimos 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 considerarlos como algo más que simples 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 nuestros resultados módulo $N$ (es decir, dividir entre $N$ y considerar el resto como resultado), siempre nos mantendremos dentro de este conjunto al realizar estas operaciones. Las dos operaciones específicas de suma y multiplicación, ambas realizadas módulo $N$, convierten $\mathbb{Z}_N$ en un anillo, que es un tipo de objeto de importancia fundamental en álgebra.

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

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

Pero también podemos escribir simplemente « $3 \cdot 5 = 1$ », siempre que haya quedado claro que estamos trabajando en « $\mathbb{Z}_7$ », con el fin de que nuestra notación sea lo más sencilla posible.

A modo de ejemplo, aquí están las tablas de suma y multiplicación de $\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 elementos $N$ de $\mathbb{Z}_N$, los elementos $a\in\mathbb{Z}_N$ que cumplen $\gcd(a,N) = 1$ son especiales. A menudo, el conjunto que contiene estos elementos se denota con un asterisco, como se muestra aquí.

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

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

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

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

Como segundo ejemplo, tomemos $N = 21$. Si repasamos los números desde $0$ hasta $20$, los que tienen un MCD 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 un número de $1$ e. Estas son las potencias mínimas 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)$

Por otra parte, según la notación que acabamos de introducir, se nos da un número $a \in \mathbb{Z}_N^{\ast}$ y buscamos el menor entero positivo $r$ tal que $a^r = 1$. Este número $r$ se denomina orden de $a$ módulo $N$.

Para relacionar el problema de la determinación del orden con la estimación de fase, pensemos en la operación definida en 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 realizando la multiplicación en « $\mathbb{Z}_N$ », por lo que queda implícito que estamos tomando el producto módulo « $N$ » dentro del ket que aparece en el lado derecho de la ecuación.

Por ejemplo, si tomamos $N = 15$ y $a=2$, 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}$$

Se trata de una operación unitaria siempre que $\gcd(a,N)=1$; mezcla 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. De su definición se desprende que esta operación es determinista, y una forma sencilla de comprobar que es invertible es pensar en el orden $r$ de $a$ módulo $N$, y darse cuenta de 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 forma de plantearse la inversa que no requiere ningún conocimiento de « $r$ » (que, al fin y al cabo, es lo que estamos intentando calcular). Para cada elemento $a\in\mathbb{Z}_N^{\ast}$ siempre existe un elemento único $b\in\mathbb{Z}_N^{\ast}$ que satisface $ab=1$. Denotamos este elemento $b$ por $a^{-1}$, y puede calcularse de forma eficiente; una extensión del algoritmo del MCD de Euclides lo hace con un coste cuadrático en $\operatorname{lg}(N)$. Y, por lo tanto,

$$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.

Ahora pensemos en los vectores propios y los valores propios de la operación $M_a$, suponiendo que $a\in\mathbb{Z}_N^{\ast}$. Como acabamos de ver, esta suposición nos indica que $M_a$ es unitaria.

Hay $N$ valores propios de $M_a$, entre los que puede figurar el mismo valor propio repetido varias veces, y, en general, existe cierta libertad a la hora de seleccionar los vectores propios correspondientes; pero no tendremos que preocuparnos por todas las posibilidades. Empecemos por algo sencillo e identifiquemos un solo 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$, tanto aquí como en el resto de la lección. El valor propio asociado a este vector propio es $1$, ya que no varía al multiplicarlo 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 ocurre porque $a^r = 1$, por lo que cada estado de la 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$ vuelve a situarse en $\vert 1\rangle$. Hablando de manera informal, es como si estuviéramos removiendo lentamente $\vert \psi_0 \rangle$, pero ya está completamente removido, por lo que no cambia nada.

He aquí otro ejemplo de vector propio de $M_a$. Este resulta ser más interesante en el contexto de la determinación del 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 cómo aparece de forma natural el número complejo $\omega_r = e^{2\pi i/r}$, debido a la forma en que funciona la multiplicación por $a$ módulo $N$. En esta ocasión, el valor propio correspondiente es $\omega_r$. Para comprobarlo, podemos realizar primero el siguiente cálculo.

$$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, dado que $\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$.

Siguiendo el mismo razonamiento, podemos identificar otros pares de vectores propios y valores propios para $M_a$. Para cualquier elección de $j\in\{0,\ldots,r-1\}$, se tiene 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$$

Hay 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, debemos implementar de forma eficiente no solo $M_a$ 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 lo suficientemente precisa a partir del procedimiento de estimación de fase. Aquí explicaremos cómo se puede hacer esto y, más adelante, determinaremos exactamente cuánta precisión se necesita.

Empecemos por la operación « $M_a$ » en sí misma. Naturalmente, dado que estamos trabajando con el modelo de circuito cuántico, utilizaremos la notación binaria para codificar los números comprendidos entre $0$ y $N-1$. El número más grande 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 $N = 21$, tenemos $n = \operatorname{lg}(N-1) = 5$. Así es como se ve la codificación de los 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 solo nos interese cómo funciona $M_a$ para $\vert 0\rangle,\ldots,\vert N-1\rangle$, sí que tenemos que especificar cómo funciona para el resto de los estados de la base estándar $2^n - N$, y debemos hacerlo de tal forma que siga dándonos una operación unitaria. Esto se consigue definiendo $M_a$ de tal forma que no realice ninguna acción sobre los estados restantes de la base estándar.

Utilizando los algoritmos de multiplicación y división de números enteros que se han tratado en la lección anterior, junto con la metodología para su implementación reversible y sin residuos, podemos construir un circuito cuántico que realice un $M_a$ para cualquier elección de $a\in\mathbb{Z}_N^{\ast}$, con un coste de $O(n^2)$. A continuación se muestra 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 del espacio de trabajo, pero al final se restablecen 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 de $O(n^2)$.

Para realizar $M_a^2$, $M_a^4$, $M_a^8$, etc., podemos utilizar exactamente el mismo método, salvo que sustituimos $a$ por $a^2$, $a^4$, $a^8$, etc., 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 utilizando luego el circuito para $M_b$.

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

En esencia, lo que estamos haciendo aquí es delegar el problema de iterar « $M_a$ » tantas veces como « $2^{m-1}$ » a un cálculo clásico eficiente. ¡Y qué suerte que esto sea posible! Si se elige un circuito cuántico cualquiera en el problema de la estimación de fase, es poco probable que esto sea posible; y, en ese caso, el coste resultante de la estimación de fase crece exponencialmente con el número de qubits de control $m$.

Solución dada un vector propio conveniente

Para entender cómo podemos resolver el problema de la búsqueda del orden mediante la estimación de fase, empecemos suponiendo que aplicamos el procedimiento de estimación de fase a la operación $M_a$ utilizando el vector propio $\vert\psi_1\rangle$. Resulta que no es fácil conseguir este vector propio, así que esto 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$. Así pues, si aplicamos el procedimiento de estimación de fase a $M_a$ utilizando el vector propio $\vert\psi_1\rangle$, obtendremos una aproximación a $1/r$. Al calcular el recíproco, podremos obtener $r$, siempre que nuestra aproximación sea lo suficientemente buena.

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

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

Por ejemplo, supongamos que $r = 6$ y realizamos la estimación de fase en $M_a$ con el vector propio $\vert\psi_1\rangle$ utilizando $m = 5$ bits de control. La mejor aproximación de $5$ -bit a $1/r = 1/6$ es $5/32$, y tenemos muchas posibilidades (aproximadamente $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, al redondear al entero más cercano, 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 un $m = 4$ qubits de control en la estimación de fase, podríamos obtener la mejor aproximación de $4$ bits a $1/r = 1/6$, que es $3/16$. Tomando el recíproco se obtiene

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

y, al redondear al entero más cercano, se obtiene una respuesta incorrecta de $5$.

Entonces, ¿qué grado de precisión necesitamos para obtener la respuesta correcta? Sabemos que el orden $r$ es un número entero y, intuitivamente, lo que necesitamos es suficiente precisión para distinguir $1/r$ de otras posibilidades cercanas, como $1/(r+1)$ y $1/(r-1)$. El número más cercano a $1/r$ que debemos tener en cuenta 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)}.$$

Por lo tanto, si queremos asegurarnos de no confundir $1/r$ con $1/(r+1)$, basta con utilizar la precisión suficiente para garantizar que la 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, si el error es 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, al redondear obtendremos $r$.

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 disponemos del vector propio $\vert \psi_1 \rangle$ de $M_a$, podemos determinar $r$ mediante la estimación de fase, siempre y cuando utilicemos suficientes qubits de control para hacerlo con la precisión necesaria. Por desgracia, no es fácil conseguir el vector propio $\vert\psi_1\rangle$, así que tenemos que averiguar cómo proceder.

Supongamos por un momento que procedemos tal y como se ha indicado anteriormente, salvo que utilizamos 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\}$ que decidamos considerar. El resultado que obtenemos del procedimiento de estimación de fase será una aproximación

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

Partiendo de la hipótesis de que no conocemos ni $k$ ni $r$, esto podría permitirnos —o no— identificar $r$. Por ejemplo, si $k = 0$, obtendremos una aproximación $y/2^m$ a $0$, lo que, por desgracia, no nos aporta ninguna información. Sin embargo, este es un caso atípico; 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.

Dados un número entero $N\geq 2$ y un número real $\alpha\in(0,1)$, existe como máximo una opción de números enteros $u,v\in\{0,\ldots,N-1\}$ tales que $v\neq 0$ y $\gcd(u,v)=1$ satisfagan $\vert \alpha - u/v\vert < \frac{1}{2N^2}$. Dados $\alpha$ y $N$, el algoritmo de fracciones continuas encuentra $u$ y $v$, o bien indica que no existen. Este algoritmo puede implementarse como un circuito booleano de tamaño $O((\operatorname{lg}(N))^3)$.

Si disponemos de una aproximación muy cercana $y/2^m$ a $k/r$, y aplicamos el algoritmo de fracciones continuas a $N$ y $\alpha = y/2^m$, obtendremos $u$ y $v$, tal y como se describe en el enunciado. Un análisis de los hechos nos permite concluir que

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

Fíjate, sobre todo, en que no aprendemos necesariamente que « $k$ » y « $r$ », sino que solo aprendemos que « $k/r$ » en términos más simples.

Por ejemplo, y como ya hemos observado, no vamos a aprender nada de $k=0$. Pero ese es el único caso en el que ocurre eso en $k$. Cuando $k$ es distinto de cero, puede tener factores comunes con $r$, pero el número $v$ que obtenemos mediante el algoritmo de fracciones continuas debe dividir, como mínimo, a $r$.

No resulta nada obvio, pero es cierto que si somos capaces de aprender $u$ y $v$ para $u/v = k/r$ para $k\in\{0,\ldots,r-1\}$, elegidas al azar de manera uniforme, es muy probable que podamos recuperar $r$ tras unas pocas muestras. En concreto, si nuestra estimación para $r$ es el mínimo común múltiplo de todos los valores del denominador $v$ que observamos, acertaremos con una alta probabilidad. Intuitivamente, algunos valores de $k$ no son adecuados porque comparten factores comunes con $r$, y esos factores comunes nos quedan ocultos cuando aprendemos $u$ y $v$. Sin embargo, es poco probable que las elecciones aleatorias de $k$ oculten durante mucho tiempo los factores de $r$, y la probabilidad de que no adivinemos correctamente $r$ calculando el mínimo común múltiplo de los denominadores que observamos disminuye exponencialmente al aumentar 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 cambio, es aplicar el procedimiento de estimación de fase al estado $\vert 1\rangle$, es decir, la codificación binaria de $n$ bits del número $1$, en lugar de un vector propio $\vert\psi\rangle$ de $M_a$. Hasta ahora, solo hemos hablado de aplicar el procedimiento de estimación de fase a un vector propio concreto, pero nada nos impide aplicarlo a un estado de entrada que no sea un vector propio de $M_a$, y eso es lo que estamos haciendo aquí con el estado $\vert 1\rangle$. (Esto no es un vector propio de $M_a$ a menos que $a=1$, lo cual 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 explicarlo con más detalle, imaginemos que aplicamos el procedimiento de estimación de fase utilizando el estado $\vert 1\rangle$ en lugar de uno de los vectores propios $\vert\psi_k\rangle$. Una vez realizada la transformada de Fourier cuántica 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 implementar cada operación « $M_a^k$ » controlada-unitaria 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 de Hadamard (que aportan $O(n)$ al coste), y la transformada de Fourier cuántica inversa aporta $O(n^2)$ al coste. Por lo tanto, el coste de las operaciones unitarias controladas predomina sobre el coste de todo el procedimiento, que, por lo tanto, es « $O(n^3)$ ».

Además del propio circuito cuántico, hay algunos cálculos clásicos que es necesario realizar a lo largo del proceso. Esto incluye el cálculo de las potencias $a^k$ en $\mathbb{Z}_N$ para $k = 2, 4, 8, \ldots, 2^{m-1}$, necesarias para crear las puertas unitarias controladas, así como el algoritmo de fracciones continuas 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 de forma recursiva. En concreto, podemos centrarnos en la tarea de factorizar $N$, lo que significa encontrar dos números enteros cualesquiera $b,c\geq 2$ para los que $N = bc$. Esto no es posible si $N$ es un número primo, pero primero podemos comprobar de forma eficiente si $N$ es primo utilizando un algoritmo de prueba de primalidad y, si $N$ no es primo, intentaremos factorizarlo. Una vez que hayamos dividido $N$, basta con aplicar la recursividad a $b$ y $c$ hasta que todos nuestros factores sean primos y obtengamos la factorización en números primos de $N$.

Dividir números enteros pares es fácil: solo tenemos que mostrar « $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$, simplemente aproximando las raíces $N^{1/2}$, $N^{1/3}$, $N^{1/4}$, y así sucesivamente, y comprobando los números enteros cercanos como posibles candidatos para $s$. No es necesario avanzar más allá de $\log(N)$ pasos en esta secuencia, ya que en ese punto la raíz cae por debajo de $2$ y no revelará candidatos adicionales.

Es bueno que podamos hacer ambas cosas, porque la búsqueda de orden no nos servirá para factorizar números pares ni potencias de números primos, en los que el número $s$ resulta ser primo. Sin embargo, si $N$ es impar y no es una potencia de un número primo, la determinación del orden nos permite dividir $N$.

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

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

3. Si $d > 1$, entonces muestra $b = d$ y $c = N/d$ y detente. De lo contrario, pasa al siguiente paso sabiendo que $a\in\mathbb{Z}_N^{\ast}$.

4. Sea $r$ el orden de $a$ módulo $N$. (Aquí es donde necesitamos la búsqueda de pedidos.)

5. Si $r$ es par:

   5.1 Calcula$x = a^{r/2} - 1$ módulo$N$

   5.2
   Calcula$d = \gcd(x,N)$ . 5.3
   Si$d>1$ , entonces muestra$b=d$ y$c = N/d$ y detén el programa.

6. Si se llega a este punto, significa que el algoritmo no ha conseguido encontrar ningún factor de $N$.

Es posible que, al ejecutar este algoritmo, no se encuentre 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$.

Mediante 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$, ninguno de estos sucesos se produce. De hecho, la probabilidad de que se produzca cualquiera de los dos eventos es, como máximo, $2^{-(m-1)}$, donde $m$ es el número de factores primos distintos de $N$, razón por la cual es necesario suponer que $N$ no es una potencia de un número primo. (Para que esto sea cierto, también es necesario suponer que « $N$ » es impar.)

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 al azar $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 bien, sabemos que $a^r \; (\textrm{mod}\; N) = 1$ por la definición del orden —lo cual es otra forma de decir que $N$ divide exactamente a $a^r - 1$. Eso significa que $N$ divide exactamente 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.