El algoritmo de Shor

Para este módulo de Qiskit en el aula, los estudiantes deben tener un entorno de Python funcional con los siguientes paquetes instalados:

• qiskit v2.1.0 o más reciente
• qiskit-ibm-runtime v0.40.1 o más reciente
• qiskit-aer v0.17.0 o más reciente
• qiskit.visualization
• numpy
• pylatexenc

Para configurar e instalar los paquetes anteriores, consulta la guía Instalar Qiskit. Para ejecutar trabajos en computadoras cuánticas reales, los estudiantes deberán crear una cuenta en IBM Quantum® siguiendo los pasos de la guía Configura tu cuenta de IBM Cloud.

Este módulo fue probado y utilizó tres segundos de tiempo de QPU. Esta es solo una estimación. Tu uso real puede variar.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Introducción

A principios de la década de 1990, había una creciente expectativa en torno al potencial de las computadoras cuánticas para resolver problemas que eran difíciles para las computadoras clásicas. Algunos talentosos científicos de la computación habían diseñado algoritmos que demostraban el poder de la computación cuántica para ciertos problemas de nicho y muy específicos, pero nadie había encontrado la «aplicación estrella» de la computación cuántica que fuera a revolucionar el campo. Eso fue hasta 1994, cuando Peter Shor presentó lo que hoy se conoce como el algoritmo de Shor para factorizar números grandes.

Era bien sabido en aquel entonces que encontrar los factores primos de un número grande era extremadamente difícil para una computadora clásica. De hecho, los protocolos de seguridad en internet se basaban en esa dificultad. Shor encontró una manera de hallar esos factores de forma exponencialmente más eficiente, delegando algunos de los pasos más complejos a una teórica computadora cuántica del futuro.

En este módulo exploraremos el algoritmo de Shor. Primero, daremos un poco más de contexto al algoritmo, formalizando el problema que resuelve y explicando su relevancia para la ciberseguridad. Luego, haremos una introducción a las matemáticas modulares y cómo aplicarlas al problema de factorización, mostrando cómo la factorización se reduce a otro problema llamado «búsqueda de orden». Veremos cómo la Transformada de Fourier Cuántica y la Estimación de Fase Cuántica que aprendimos en un módulo anterior entran en juego, y cómo usarlas para resolver el problema de búsqueda de orden.

Por último, ¡ejecutaremos el algoritmo de Shor en una computadora cuántica real! Ten en cuenta, sin embargo, que este algoritmo solo será verdaderamente útil cuando dispongamos de una computadora cuántica grande y tolerante a fallos, lo cual todavía está a varios años de distancia. Así que por ahora factorizaremos un número pequeño para demostrar cómo funciona el algoritmo.

El problema de factorización

El objetivo del problema de factorización es encontrar los factores primos de un número $N$. Para algunos números $N$, esto es bastante sencillo. Por ejemplo, si $N$ es par, uno de sus factores primos será 2. Si $N$ es una potencia prima, es decir, $N=p^k$ para algún número primo $p$, también es relativamente fácil encontrar $p$: simplemente aproximamos la raíz $k$-ésima de $N$ y buscamos primos cercanos que puedan ser $p$.

Donde las computadoras clásicas tienen dificultades es cuando $N$ es impar y no es una potencia prima. Este es el caso que aborda el algoritmo de Shor. El algoritmo encuentra dos factores $p$ y $q$ tales que $N=pq$. Puede aplicarse de forma recursiva hasta que todos los factores sean primos. En las siguientes secciones veremos cómo se aborda este problema.

Relevancia para la ciberseguridad

Muchos esquemas criptográficos se han construido basándose en el hecho de que factorizar números grandes es difícil, incluyendo uno que se usa comúnmente hoy en día, llamado RSA. En RSA, se crea una clave pública multiplicando dos números primos grandes para obtener $N = p\cdot q$. Luego, cualquiera puede usar esa clave pública para cifrar datos. Pero solo alguien con la clave privada, $p$ y $q$, puede descifrar esos datos.

Si $N$ fuera fácil de factorizar, cualquiera podría determinar cuáles son $p$ y $q$ y romper el cifrado. Pero no lo es. Este es un problema famosamente difícil. De hecho, los factores primos de un número llamado RSA1024, que tiene 1024 dígitos binarios y 309 dígitos decimales de longitud, aún no han sido encontrados, a pesar de que se ofreció un premio de $100,000 dólares por su factorización allá por 1991.

La solución de Shor

En 1994, Peter Shor se dio cuenta de que una computadora cuántica podría factorizar un número grande de forma exponencialmente más eficiente que una computadora clásica. Su intuición se basó en la relación entre este problema de factorización y la aritmética modular. Haremos una breve introducción a la aritmética modular y luego veremos cómo podemos usarla para factorizar $N$.

Aritmética modular

La aritmética modular es un sistema de conteo cíclico: aunque el conteo comienza de la manera habitual, con los enteros 0, 1, 2, etc., en cierto punto, tras un período $N$, el conteo vuelve a empezar. Veamos cómo funciona esto con un ejemplo. Supongamos que nuestro período es 5. Entonces, al contar, donde normalmente llegaríamos a 5, en cambio empezamos de nuevo en 0:

$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, ...$

Esto se debe a que en el mundo «módulo 5», el 5 es equivalente al 0. Decimos que $5\bmod 5 \ = 0$. De hecho, todos los múltiplos de 5 serán equivalentes a $0\bmod 5$.

Comprueba tu comprensión

Lee la(s) pregunta(s) a continuación, piensa en tu respuesta y luego haz clic en el triángulo para revelar la solución.

Usa la aritmética modular para resolver el siguiente problema:

Partes en un largo viaje transcontinental en tren a las 8 AM. El viaje dura 60 horas. ¿A qué hora llegas?

Respuesta:

El período es 24, ya que hay 24 horas en un día. Por lo tanto, este problema se puede escribir en aritmética modular como:

$(8+60)\text{mod}(24) = 20$

Llegarías a tu destino a las 20:00, o las 8 PM.

$\mathbb{Z}_N$ y $\mathbb{Z}_N^*$

Con frecuencia es útil introducir dos conjuntos, $\mathbb{Z}_N$ y $\mathbb{Z}_N^*$. $\mathbb{Z}_N$ es simplemente el conjunto de números que existen en el mundo «módulo $N$». Por ejemplo, cuando contábamos módulo 5, el conjunto sería $\mathbb{Z}_5=\{0,1,2,3,4\}$. Otro ejemplo: $\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$. Podemos realizar sumas y multiplicaciones (módulo $N$) sobre los elementos de $\mathbb{Z}_N$, y el resultado de cada una de estas operaciones también es un elemento de $\mathbb{Z}_N$, lo que convierte a $\mathbb{Z}_N$ en un objeto matemático llamado anillo.

Hay un subconjunto especial de $\mathbb{Z}_N$ que nos resulta de particular interés para el algoritmo de Shor. Es el subconjunto de números en $\mathbb{Z}_N$ tales que el máximo común divisor entre cada elemento y $N$ es 1, es decir, cada elemento es «coprimo» con $N$. Si tomamos el conjunto de estos números junto con la operación de multiplicación modular, se forma otro objeto matemático llamado grupo. A este grupo lo denominamos $\mathbb{Z}_N^*$. Resulta que con $\mathbb{Z}_N^*$ (y los grupos finitos en general), si tomamos cualquier elemento $a \in \mathbb{Z}_N^*$ y lo multiplicamos repetidamente por sí mismo, siempre terminaremos obteniendo el número $1$. El número mínimo de veces que hay que multiplicar $a$ por sí mismo para obtener $1$ se llama el orden de $a$. Este hecho será muy importante para nuestra discusión sobre cómo factorizar números a continuación.

Comprueba tu comprensión

Lee la(s) pregunta(s) a continuación, piensa en tu respuesta y luego haz clic en el triángulo para revelar la solución.

¿Cuál es $\mathbb{Z}_{15}^*$?

Respuesta:

$\mathbb{Z}_{15}^* = \{1,2,4,7,8,11,13,14\}$

Excluimos los siguientes números:

$$\begin{aligned} 3: GCD(3,15)=3 \\ 5: GCD(5,15)=5 \\ 6: GCD(6,15)=3 \\ 9: GCD(9,15)=3 \\ 10: GCD(10,15)=5 \\ 12: GCD(12,15)=3 \\ \end{aligned}$$

¿Cuál es el orden de cada uno de los elementos de $\mathbb{Z}_{15}^*$?

Respuesta:

El orden $r$ es el número más pequeño tal que $a^r\text{mod}(15)=1$ para cada elemento $a$.

$$\begin{aligned} 1^1\text{mod}(15) = 1, r=1 \\ 2^4\text{mod}(15) = 1, r=4 \\ 4^2\text{mod}(15) = 1, r=2 \\ 7^4\text{mod}(15) = 1, r=4 \\ 8^4\text{mod}(15) = 1, r=4 \\ 11^2\text{mod}(15) = 1, r=2 \\ 13^4\text{mod}(15) = 1, r=4 \\ 14^2\text{mod}(15) = 1, r=2 \\ \end{aligned}$$

Ten en cuenta que, aunque pudimos encontrar el orden de los números en $\mathbb{Z}_{15}^*$, esta NO es una tarea sencilla en general para valores más grandes de $N$. Este es el núcleo del problema de factorización y la razón por la que necesitamos una computadora cuántica. Lo veremos a medida que avancemos en el resto del cuaderno.

Aplicar la aritmética modular al problema de factorización

La clave para encontrar los factores $p$ y $q$ tales que $N=pq$ consiste en encontrar algún otro entero $x$ tal que

$x^2 \equiv 1 \bmod N$ y $x \not\equiv \pm 1 \bmod N.$

¿Cómo nos ayuda encontrar $x$ a encontrar los factores $p$ y $q$? Veamos el razonamiento ahora. Como $x^2 \equiv 1 \bmod N$, eso significa que $x^2 - 1 \equiv 0 \bmod N$. En otras palabras, $x^2 - 1$ es un múltiplo de $N$. Entonces, para algún entero $l$,

$x^2 - 1 = l N$

Podemos factorizar $x^2 - 1$ para obtener:

$(x+1)(x-1) = l N$

Por nuestras suposiciones iniciales sabemos que $x \not\equiv \pm 1 \bmod N$, así que $N$ no divide de forma exacta ni a $x+1$ ni a $x-1$. Por lo tanto, los dos factores de $N$, $p$ y $q$, deben dividir a $x-1$ y $x+1$ respectivamente. O bien $p$ es factor de $x-1$ y $q$ es factor de $x+1$, o viceversa. Entonces, si calculamos los máximos comunes divisores (MCD) entre $N$ y tanto $x-1$ como $x+1$, obtendremos los factores $p$ y $q$. Calcular el MCD entre dos números es una tarea clásicamente sencilla que puede realizarse, por ejemplo, usando el algoritmo de Euclides.

Comprueba tu comprensión

Lee la(s) pregunta(s) a continuación, piensa en tu respuesta y luego haz clic en el triángulo para revelar la solución.

Puede ser complicado entender cada paso de la lógica anterior, así que intenta trabajarlo con un ejemplo. Usa $N=15$ y $x=11$. Primero, verifica que $x^2 \equiv 1 \text{mod}(N)$ y $x \not\equiv \pm 1 \bmod N$. Luego continúa verificando cada paso. Por último, calcula $\text{GCD}(11\pm1,15)$ y verifica que son los factores de $15$.

Respuesta:

$11^2 = 121$, que es $15*8 + 1$, por lo que $11^2\bmod 15 = 1$. $\checkmark$

$11 - 1 = 10$, que no es equivalente a $0\bmod 15$. $\checkmark$

$11 + 1 = 12$, que no es equivalente a $0\bmod 15$. $\checkmark$

Ahora sabemos que $(x+1)(x-1) = l N$ para algún entero $l$. Esto se verifica cuando sustituimos $x$ y $N$: $(12)(10) = l 15$ cuando $l = 8$. $\checkmark$

Ahora necesitamos calcular $\text{GCD}(12,15)$ y $\text{GCD}(10,15)$.

$$\begin{aligned} \text{GCD}(12,15) = 3 \\ \text{GCD}(10,15) = 5 \end{aligned}$$

¡Así encontramos los factores de $15$!

El algoritmo

Ahora que hemos visto cómo encontrar un entero $x$ tal que $x^2 \equiv 1\bmod N$ nos ayuda a factorizar $N$, podemos repasar el algoritmo de Shor. Esencialmente se reduce a encontrar $x$:

1. Elige un entero aleatorio Elige un entero aleatorio $a$ tal que $1 < a < N$.

• Calcula $\text{GCD}(a, N)$ de forma clásica.
  • Si $\text{GCD}(a, N) > 1$, ya encontraste un factor. Detente.
  • De lo contrario, continúa.

2. Encuentra el orden $r$ de $a$ módulo $N$ Encuentra el entero positivo más pequeño $r$ que satisface $a^r \equiv 1 \pmod N$.

3. Verifica si el orden es par

• Si $r$ es impar, regresa al paso 1 y elige un nuevo $a$.
• Si $r$ es par, continúa al paso 4.

4. Calcula $x = a^{r/2} \bmod N$

• Verifica que $x \not\equiv 1 \pmod N$ y $x \not\equiv -1 \pmod N$.
  • Si $x \equiv \pm 1 \pmod N$, regresa al paso 1 y elige un nuevo $a$.
• De lo contrario, calcula los MCD para extraer los factores:

$$p = \text{GCD}(x-1, N), \quad q = \text{GCD}(x+1, N)$$

Estos serán factores no triviales de $N$.

5. Factoriza recursivamente si es necesario

• Si $p$ y/o $q$ no son primos, aplica el algoritmo de forma recursiva para factorizarlos completamente.
• Una vez que todos los factores sean primos, la factorización está completa.

Basándose en este procedimiento, puede que no sea obvio por qué se necesita una computadora cuántica para completar esta tarea. Es necesaria porque el paso 2, encontrar el orden de $a$ módulo $N$, es clásicamente un problema muy difícil. La complejidad escala exponencialmente con el número $N$. Pero con una computadora cuántica, solo tenemos que usar la Estimación de Fase Cuántica para resolverlo. El paso 4, encontrar el MCD de dos enteros, es en realidad algo bastante sencillo de hacer clásicamente. Entonces, el único paso que realmente necesita el poder de una computadora cuántica es el paso de búsqueda de orden. Decimos que el problema de factorización «se reduce» al problema de búsqueda de orden.

La parte difícil: búsqueda de orden

Ahora veremos cómo podemos usar una computadora cuántica para la búsqueda de orden. Primero, aclaremos qué queremos decir con «orden». Por supuesto, ya te expliqué qué significa el orden matemáticamente: es el primer entero no nulo $r$ tal que $a^r = 1 \pmod N.$ Pero veamos si podemos ganar un poco más de intuición para este concepto.

Para valores de $N$ suficientemente pequeños, podemos determinar el orden simplemente calculando cada potencia de $a$, tomando el módulo $N$ de ese número y deteniéndonos cuando encontremos la potencia $r$ que satisface $a^r = 1 \text{mod}(N)$. Eso fue exactamente lo que hicimos con nuestro ejemplo $N=15$ más arriba. Echemos un vistazo a algunas gráficas de estas potencias modulares para algunos valores de ejemplo de $a$ y $N$:

¿Notas algo? ¡Son funciones periódicas! Y el orden $r$ es lo mismo que el período. Entonces, la búsqueda de orden es equivalente a la búsqueda de período.

Las computadoras cuánticas son muy adecuadas para encontrar el período de funciones. Para esto, podemos usar una subrutina algorítmica llamada Estimación de Fase Cuántica. Discutimos la QPE y su relación con la Transformada de Fourier Cuántica en el módulo anterior. Para un repaso detallado, ve al módulo de QFT o a la lección de John Watrous sobre Estimación de Fase Cuántica en su curso de Algoritmos Cuánticos. A continuación repasaremos la esencia del procedimiento:

En la Estimación de Fase Cuántica (QPE), comenzamos con un unitario $U$ y un autoestado de ese unitario $|\psi\rangle$. Luego, usamos QPE para aproximar el autovalor correspondiente, que, dado que el operador es unitario, tendrá la forma $e^{2\pi i \theta}$. Entonces, encontrar el autovalor es equivalente a encontrar el valor de $\theta$ en la función periódica. El Circuit se ve así:

donde el número de Qubits de control (los $m$ Qubits superiores en la figura anterior) determina la precisión de la aproximación.

En el algoritmo de Shor, usamos QPE sobre el operador unitario $M_a$:

$M_a|y\rangle \equiv |ay \mod N \rangle .$

Aquí, $|y\rangle$ denota un estado de la base computacional del registro de múltiples Qubits, donde el valor binario de los Qubits corresponde al entero $y$. Por ejemplo, si $N=15$ y $y = 2$, entonces $|y\rangle$ está representado por el estado de base de cuatro Qubits $|0010\rangle$, ya que se necesitan cuatro Qubits para codificar números hasta 15. (Si este concepto no te resulta familiar, ve al módulo introductorio de Qiskit en el aula para un repaso sobre la codificación binaria de estados cuánticos.)

Ahora necesitamos encontrar un autoestado de este unitario. Si comenzamos en el estado $|1\rangle$, podemos ver que cada aplicación sucesiva de $U$ multiplicará el estado de nuestro registro por $a \pmod N$, y después de $r$ aplicaciones llegaremos al estado $|1\rangle$ nuevamente. Por ejemplo con $a = 3$ y $N = 35$:

$$\begin{aligned} M_3|1\rangle &= |3\rangle & \\ M_3^2|1\rangle &= |9\rangle \\ M_3^3|1\rangle &= |27\rangle \\ & \vdots \\ M_3^{(r-1)}|1\rangle &= |12\rangle \\ M_3^r|1\rangle &= |1\rangle \end{aligned}$$

Entonces las superposiciones de los estados en este ciclo ($|\psi_j\rangle$) de la forma:

$|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$

son todos autoestados de $M_a$. (Hay más autoestados además de estos. Pero solo nos interesan los de la forma anterior.)

Comprueba tu comprensión

Lee la(s) pregunta(s) a continuación, piensa en tu respuesta y luego haz clic en el triángulo para revelar la solución.

Encuentra un autoestado del unitario correspondiente a $a=2$ y $N = 15$.

Respuesta:

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2^2|1\rangle &= |4\rangle \\ M_2^3|1\rangle &= |8\rangle \\ M_2^4|1\rangle &= |1\rangle \\ \end{aligned}$$

Entonces, el orden es $r=4$. Los autoestados que nos interesan serán una superposición equitativa de todos los estados por los que se pasó anteriormente, con varias fases:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{1}{4}}|2\rangle+e^{2 \pi i \frac{2}{4}}|4\rangle+e^{2 \pi i \frac{3}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{2}{4}}|2\rangle+e^{2 \pi i \frac{4}{4}}|4\rangle+e^{2 \pi i \frac{6}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{3}{4}}|2\rangle+e^{2 \pi i \frac{6}{4}}|4\rangle+e^{2 \pi i \frac{9}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Supongamos que pudiéramos inicializar el estado de nuestros Qubits en uno de estos autoestados (spoiler: no podemos, o al menos no fácilmente; explicaremos por qué y qué podemos hacer en su lugar en breve). Entonces podríamos usar QPE para estimar el autovalor correspondiente, $\omega_j = e^{2 \pi i \theta_j}$ donde $\theta_j = \frac{j}{r}$. Luego, podríamos determinar el orden $r$ con la simple ecuación:

$r = \frac{j}{\theta_j}.$

Pero recuerda, dije que QPE estima $\theta_j$, no nos da un valor exacto. Necesitamos que la estimación sea lo suficientemente buena como para diferenciar entre $r$ y $r+1$. Cuantos más Qubits de control $m$ tengamos, mejor será la estimación. En los problemas al final de la lección se te pedirá que determines el $m$ mínimo necesario para factorizar un número $N$.

Ahora tenemos que resolver un problema. Toda la explicación anterior sobre cómo encontrar $r$ comienza con preparar el autoestado $|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$. Pero no sabemos cómo hacer eso sin ya conocer $r$. La lógica es circular. Necesitamos una manera de estimar el autovalor sin inicializar el autoestado.

En lugar de comenzar con un autoestado de $M_a$, podemos preparar el estado inicial en el estado de $n$ Qubits correspondiente a $|1\rangle$ en binario (es decir, $|000...01\rangle$). Aunque este estado en sí mismo evidentemente no es un autoestado de $M_a$, sí es una superposición de todos los autoestados $|\psi_k\rangle$:

$|1\rangle = \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle}$

Comprueba tu comprensión

Lee la(s) pregunta(s) a continuación, piensa en tu respuesta y luego haz clic en el triángulo para revelar la solución.

Verifica que $|1\rangle$ es equivalente a la superposición de los autoestados que encontraste para $N=15$ y $a=2$ en la pregunta de verificación anterior.

Respuesta:

Los cuatro autoestados eran:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Entonces,

$$\begin{aligned} \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle} &= \frac{1}{2}(|\psi_0\rangle + |\psi_1\rangle + |\psi_2\rangle + |\psi_3\rangle ) \\ &= \frac{1}{4}(|1\rangle+|2\rangle+|4\rangle+|8\rangle+|1\rangle+i|2\rangle-|4\rangle-i|8\rangle+|1\rangle-|2\rangle+|4\rangle-|8\rangle + |1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ &= \frac{1}{4}(4|1\rangle) = |1\rangle \end{aligned}$$

¿Cómo nos permite esto encontrar el orden $r$? Dado que el estado inicial es una superposición de todos los autoestados de la forma indicada arriba, el algoritmo QPE estima simultáneamente cada uno de los $\theta_k$ correspondientes a esos autoestados. Así, la medición de los $m$ Qubits de control al final producirá una aproximación al valor $k/r$ donde $k \in \{0,1,2,...,r-1\}$ es uno de los autovalores elegido aleatoriamente. Si repetimos este Circuit unas pocas veces y obtenemos varias muestras con diferentes valores de $k$, podremos deducir $r$ rápidamente.

Implementar en Qiskit

Como mencionamos antes, nuestro hardware todavía no está en el punto en que podamos factorizar números grandes como RSA1024. Solo vamos a factorizar un número pequeño para demostrar cómo funciona el algoritmo. Para esta demostración, usaremos una versión simplificada del código presentado en el tutorial del algoritmo de Shor. Si quieres más detalles, visita el tutorial.

Ejecutaremos el algoritmo usando nuestro marco de trabajo estándar para resolver problemas cuánticos, llamado el marco de patrones de Qiskit. Este consta de cuatro pasos:

1. Mapear tu problema a un circuito cuántico
2. Optimizar el circuito para ejecutarlo en hardware cuántico
3. Ejecutar tu circuito en el computador cuántico
4. Posprocesar las mediciones

1. Mapear

Vamos a factorizar $N=15$, seleccionando $a=2$ como nuestro entero coprimo.

Primero, necesitamos construir el circuito que implementará la unitaria de multiplicación modular, $M_a$. Esta es, de hecho, la parte más complicada de toda la implementación y puede ser computacionalmente muy costosa, dependiendo de cómo se haga. Para esto, vamos a hacer trampa un poco: sabemos que empezamos en el estado $|1\rangle$, y a partir de una pregunta de comprensión anterior,

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2|2\rangle &= |4\rangle \\ M_2|4\rangle &= |8\rangle \\ M_2|8\rangle &= |1\rangle \\ \end{aligned}$$

Así que construiremos una unitaria que realice las operaciones correctas sobre estos cuatro estados, pero que deje todos los demás estados sin cambios. Esto es hacer trampa porque estamos usando nuestro conocimiento del orden de $2\bmod 15$ para simplificar la unitaria. Si realmente estuviéramos intentando factorizar un número cuyos factores nos fueran desconocidos, no podríamos hacer esto.

Comprueba tu comprensión

Lee la(s) pregunta(s) a continuación, piensa en tu respuesta y luego haz clic en el triángulo para ver la solución.

Con tu conocimiento de cómo el operador $M_2$ transforma los estados anteriores, construye el operador a partir de una serie de puertas SWAP, que intercambian los estados de dos qubits. (Pista: escribir cada estado $|i\rangle$ en binario te ayudará.)

Respuesta:

Reescribamos la acción de $M_2$ sobre los estados en binario:

$$\begin{aligned} M_2|0001\rangle &= |0010\rangle \\ M_2|0010\rangle &= |0100\rangle \\ M_2|0100\rangle &= |1000\rangle \\ M_2|1000\rangle &= |0001\rangle \\ \end{aligned}$$

Cada una de estas acciones puede lograrse con un simple SWAP. $M_2|0001\rangle$ se obtiene intercambiando los estados del qubit $0$ y $1$. $M_2|0010\rangle$ se obtiene intercambiando los estados del qubit $1$ y $2$. Y así sucesivamente. Por lo tanto, podemos descomponer la matriz $M_2$ en la siguiente serie de puertas SWAP:

$$M_2 = SWAP(0,1)SWAP(1,2)SWAP(2,3)$$

Recordando que los operadores actúan de derecha a izquierda, comprobemos que esto tiene el efecto deseado sobre cada uno de los estados:

$$\begin{aligned} M_2|0001\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0001\rangle \\ &= SWAP(0,1)SWAP(1,2)|0001\rangle \\ &= SWAP(0,1)|0001\rangle \\ &=|0010\rangle \checkmark \\ M_2|0010\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0010\rangle \\ &= SWAP(0,1)SWAP(1,2)|0010\rangle \\ &= SWAP(0,1)|0100\rangle \\ &=|0100\rangle \checkmark \\ M_2|0100\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0100\rangle \\ &= SWAP(0,1)SWAP(1,2)|1000\rangle \\ &= SWAP(0,1)|1000\rangle \\ &=|1000\rangle \checkmark \\ M_2|1000\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|1000\rangle \\ &= SWAP(0,1)SWAP(1,2)|0100\rangle \\ &= SWAP(0,1)|0010\rangle \\ &=|0001\rangle \checkmark \\ \end{aligned}$$

Ahora podemos programar el circuito equivalente a este operador en Qiskit.

Primero, importamos los paquetes necesarios:

# Import necessary packages

import numpy as np
from fractions import Fraction
from math import floor, gcd, log

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import QFTGate
from qiskit.transpiler import generate_preset_pass_manager
from qiskit.visualization import plot_histogram

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

Luego, construimos el operador $M_2$:

def M2mod15():
    """
    M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M2 operator
M2 = M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M2, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

El algoritmo QPE usa una puerta $U$ controlada. Así que, ahora que tenemos un circuito $M_2$, necesitamos convertirlo en un circuito $M_2$ controlado:

def controlled_M2mod15():
    """
    Controlled M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M2 operator
controlled_M2 = controlled_M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M2, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Ahora tenemos nuestra puerta $U$ controlada. Pero para ejecutar el algoritmo de Estimación de Fase Cuántica, necesitaremos $U^2$ controlada, $U^4$ controlada, hasta $U^{2^{m-1}}$ controlada, donde $m$ es el número de qubits usados para estimar la fase. Cuantos más qubits, más precisa será la estimación de la fase. Usaremos $m=8$ qubits de control para nuestro procedimiento de estimación de fase. Así que necesitamos:

$$M_{a^{2^k}}|y\rangle \equiv |a^{2^k} y \bmod N \rangle$$

donde el índice $k$, con $0 \le k \le m-1 = 7$, corresponde al qubit de control. Ahora calculemos $a^{2^k}\bmod N$ para cada valor de $k$:

def a2kmodN(a, k, N):
    """Compute a^{2^k} (mod N) by repeated squaring"""
    for _ in range(k):
        a = int(np.mod(a**2, N))
    return a

k_list = range(8)
b_list = [a2kmodN(2, k, 15) for k in k_list]

print(b_list)

[2, 4, 1, 1, 1, 1, 1, 1]

Como $a^{2^k} \bmod N = 1$ para $k \ge 2$, todos los operadores correspondientes ($M_8$ y superiores) son equivalentes a la identidad. Así que solo necesitamos construir una matriz más, $M_4.$

Nota: Esta simplificación solo funciona aquí porque el orden de $2 \bmod 15$ es $4$. Una vez que $k=2$ (es decir, $2^k = 4$), cada potencia posterior del operador es la identidad. En general, para números $N$ más grandes o diferentes elecciones de $a$, no se puede omitir la construcción de las potencias superiores. Esta es una de las razones por las que esto se considera un ejemplo de juguete: los números pequeños permiten atajos que no funcionarían para casos más grandes.

def M4mod15():
    """
    M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M4 operator
M4 = M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M4, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

Y, como antes, lo convertimos en un operador $M_4$ controlado:

def controlled_M4mod15():
    """
    Controlled M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M4 operator
controlled_M4 = controlled_M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M4, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Ahora podemos juntarlo todo para encontrar el orden de $2\bmod 15$ con un circuito cuántico, usando la estimación de fase:

# Order finding problem for N = 15 with a = 2
N = 15
a = 2

# Number of qubits
num_target = floor(log(N - 1, 2)) + 1  # for modular exponentiation operators
num_control = 2 * num_target  # for enough precision of estimation

# List of M_b operators in order
k_list = range(num_control)
b_list = [a2kmodN(2, k, 15) for k in k_list]

# Initialize the circuit
control = QuantumRegister(num_control, name="C")
target = QuantumRegister(num_target, name="T")
output = ClassicalRegister(num_control, name="out")
circuit = QuantumCircuit(control, target, output)

# Initialize the target register to the state |1>
circuit.x(num_control)

# Add the Hadamard gates and controlled versions of the
# multiplication gates
for k, qubit in enumerate(control):
    circuit.h(k)
    b = b_list[k]
    if b == 2:
        circuit.compose(
            M2mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    elif b == 4:
        circuit.compose(
            M4mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    else:
        continue  # M1 is the identity operator

# Apply the inverse QFT to the control register
circuit.compose(QFTGate(num_control).inverse(), qubits=control, inplace=True)

# Measure the control register
circuit.measure(control, output)

circuit.draw("mpl", fold=-1)

2. Optimizar

Ahora que hemos mapeado nuestro circuito, el siguiente paso es optimizarlo para ejecutarlo en un computador cuántico específico. Primero necesitamos cargar el backend.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

Si no tienes tiempo disponible en tu cuenta o quieres usar un simulador por cualquier razón, puedes ejecutar la celda a continuación para configurar un simulador que imitará el dispositivo cuántico que seleccionamos arriba:

pm = generate_preset_pass_manager(optimization_level=2, backend=backend)

transpiled_circuit = pm.run(circuit)

print(f"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}")
print(f"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}")
print(f"Operator counts: {transpiled_circuit.count_ops()}")
transpiled_circuit.draw(output="mpl", fold=-1, style="clifford", idle_wires=False)

2q-depth: 188
2q-size: 281
Operator counts: OrderedDict({'sx': 548, 'rz': 380, 'cz': 281, 'measure': 8, 'x': 6})

3. Ejecutar

# Sampler primitive to obtain the probability distribution
sampler = Sampler(backend)

# Turn on dynamical decoupling with sequence XpXm
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XpXm"
# Enable gate twirling
sampler.options.twirling.enable_gates = True

pub = transpiled_circuit
job = sampler.run([pub], shots=1024)

result = job.result()[0]
counts = result.data["out"].get_counts()

plot_histogram(counts, figsize=(35, 5))

Vemos cuatro picos claros en 00000000, 01000000, 10000000 y 11000000, con algunos conteos en otras cadenas de bits debidos al ruido en el computador cuántico. Ignoraremos estos y nos quedaremos solo con los cuatro dominantes imponiendo un umbral: solo los conteos por encima de este umbral se consideran una señal verdadera por encima del ruido.

# Dictionary of bitstrings and their counts to keep
counts_keep = {}
# Threshold to filter
threshold = np.max(list(counts.values())) / 2

for key, value in counts.items():
    if value > threshold:
        counts_keep[key] = value

print(counts_keep)

4. Posprocesar

En el algoritmo de Shor, una gran parte del algoritmo se ejecuta de forma clásica. Por eso, pondremos el resto en el paso de "posprocesamiento", después de haber obtenido nuestras mediciones del computador cuántico. Cada una de las mediciones anteriores puede convertirse en enteros que, después de dividir entre $2^m$, son nuestras aproximaciones de $\frac{k}{r}$, donde $k$ es aleatorio en cada ocasión.

a = 2
N = 15

FACTOR_FOUND = False
num_attempt = 0

while not FACTOR_FOUND:
    print(f"\nATTEMPT {num_attempt}:")
    # Here, we get the bitstring by iterating over outcomes
    # of a previous hardware run with multiple shots.
    # Instead, we can also perform a single-shot measurement
    # here in the loop.
    bitstring = list(counts_keep.keys())[num_attempt]
    num_attempt += 1
    # Find the phase from measurement
    decimal = int(bitstring, 2)
    phase = decimal / (2**num_control)  # phase = k / r
    print(f"Phase: theta = {phase}")

    # Guess the order from phase
    frac = Fraction(phase).limit_denominator(N)
    r = frac.denominator  # order = r
    print(f"Order of {a} modulo {N} estimated as: r = {r}")

    if phase != 0:
        # Guesses for factors are gcd(a^{r / 2} ± 1, 15)
        if r % 2 == 0:
            x = pow(a, r // 2, N) - 1
            d = gcd(x, N)
            if d > 1:
                FACTOR_FOUND = True
                print(f"*** Non-trivial factor found: {x} ***")

ATTEMPT 0:
Phase: theta = 0.0
Order of 2 modulo 15 estimated as: r = 1

ATTEMPT 1:
Phase: theta = 0.75
Order of 2 modulo 15 estimated as: r = 4
*** Non-trivial factor found: 3 ***

Conclusión

Después de recorrer el módulo, puede que te haya llegado una nueva apreciación por el ingenio de Peter Shor al haber concebido un algoritmo tan brillante. Pero esperamos que también hayas alcanzado un nuevo nivel de comprensión de su engañosa sencillez. Aunque el algoritmo puede parecer impresionantemente (o intimidantemente) complejo, si lo desglosas en cada paso de lógica y lo recorres poco a poco, tú también serás capaz de ejecutar el algoritmo de Shor.

Si bien estamos lejos de usar este algoritmo para factorizar números como RSA1024, nuestros computadores cuánticos mejoran cada día, y una vez que se alcance un umbral llamado tolerancia a fallos, algoritmos como estos no tardarán en seguir. ¡Es un momento apasionante para aprender sobre computación cuántica!

Problemas

Conceptos clave:

• Los sistemas criptográficos modernos se basan en la dificultad clásica de factorizar enteros grandes.
• La aritmética modular —incluyendo las estructuras $\mathbb{Z}_N$ y $\mathbb{Z}_N^*$— proporciona los fundamentos matemáticos del algoritmo de Shor.
• El problema de factorizar un entero $N$ puede reducirse al problema de encontrar el orden de un número módulo $N$.
• La búsqueda cuántica del orden usa técnicas de estimación de fase cuántica para determinar el período de la función $a^x \mod N$.
• El algoritmo de Shor consiste en un flujo de trabajo híbrido clásico-cuántico que selecciona una base, realiza la búsqueda cuántica del orden y luego calcula los factores clásicamente a partir del resultado.

Verdadero/Falso:

1. V/F La eficiencia del algoritmo de Shor amenaza la seguridad del cifrado RSA.
2. V/F El algoritmo de Shor puede ejecutarse eficientemente en cualquier computador cuántico actual.
3. V/F El algoritmo de Shor usa la estimación de fase cuántica (QPE) como subrutina clave.
4. V/F La parte clásica del algoritmo de Shor implica calcular el máximo común divisor (MCD).
5. V/F El algoritmo de Shor solo funciona para factorizar números pares.
6. V/F Una ejecución exitosa del algoritmo de Shor siempre garantiza los factores correctos.

Respuesta corta:

1. ¿Por qué se considera el algoritmo de Shor una potencial amenaza futura para el cifrado RSA?
2. ¿Por qué encontrar el período, u orden, de una función exponencial modular es útil para factorizar un número en el algoritmo de Shor?

Problemas de desafío:

1. ¿Cuántos qubits de control $m$ necesitamos para un número dado $N$ que queremos factorizar, con el fin de obtener la precisión en el QPE necesaria para encontrar el valor correcto del orden $r$?