Algoritmo de Shor

Para este módulo de Qiskit in Classrooms, los estudiantes deben disponer de un entorno de Python trabajo con los siguientes paquetes instalados:

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

Para configurar e instalar los paquetes anteriores, consulte la guía Instalar Qiskit. Para ejecutar trabajos en ordenadores cuánticos reales, los estudiantes deberán crear una cuenta siguiendo los pasos que IBM Quantum® se indican en la guía Configurar su IBM Cloud cuenta.

Este módulo se probó y utilizó tres segundos de tiempo de QPU. Esto es solo una estimación. Su uso real puede variar.

# 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 1990s, crecía el entusiasmo en torno al potencial de los ordenadores cuánticos para resolver problemas que resultaban difíciles para los ordenadores clásicos. Algunos informáticos con talento habían ideado algoritmos que demostraban el poder de la computación cuántica para algunos problemas específicos y artificiales, pero nadie había encontrado una única «aplicación revolucionaria» de la computación cuántica que fuera capaz de revolucionar el campo. Así fue hasta 1994, cuando Peter Shor ideó lo que hoy se conoce como el algoritmo de Shor para factorizar números grandes.

En aquella época era bien sabido que encontrar los factores primos de un número grande resultaba extremadamente difícil para un ordenador clásico. De hecho, los protocolos de seguridad de Internet se basaban en esta dificultad. Shor encontró una forma de hallar estos factores de manera exponencialmente más eficiente al descargar algunos de los pasos más difíciles en un ordenador cuántico teórico futuro.

En este módulo, exploraremos el algoritmo de Shor. En primer lugar, daremos un poco más de contexto al algoritmo, formalizando el problema que resuelve y explicando su relevancia para la ciberseguridad. A continuación, ofreceremos una introducción a las matemáticas modulares y cómo aplicarlas al problema de la factorización, mostrando cómo la factorización se reduce a otro problema denominado «búsqueda de orden» Mostraremos cómo se aplican la transformada de Fourier cuántica y la estimación de fase cuántica que aprendimos en un módulo anterior, y cómo utilizarlas para resolver el problema de búsqueda de orden.

¡Por fin ejecutaremos el algoritmo de Shor en un ordenador cuántico real! Sin embargo, hay que tener en cuenta que este algoritmo solo será realmente útil cuando dispongamos de un ordenador cuántico grande y tolerante a fallos, lo que aún tardará algunos años en llegar. Por lo tanto, solo factorizaremos un número pequeño para demostrar cómo funciona el algoritmo.

El problema del factoring

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 fácil. 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 bastante fácil encontrar $p$ : solo hay que aproximar la raíz $k^{\text{th}}$ de $N$ y buscar números primos cercanos que podrían ser $p$.

Sin embargo, donde los ordenadores clásicos 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$. Se puede aplicar 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

Se han creado muchos sistemas criptográficos basados en el hecho de que factorizar números grandes es difícil, incluido uno que se utiliza habitualmente en la actualidad, llamado RSA. En RSA, se crea una clave pública multiplicando dos números primos grandes entre sí para obtener $N = p\cdot q$. A continuación, cualquiera puede utilizar esta clave pública para cifrar datos. Pero solo alguien que tenga la clave privada, $p$ y $q$, puede descifrar esos datos.

Si $N$ fuera fácil de factorizar, entonces cualquiera podría determinar cuáles $p$ son $q$ y y descifrar la encriptación. Pero no lo es. Este es un problema famoso por su dificultad. De hecho, los factores primos de un número llamado RSA1024, que tiene 1024 dígitos binarios y 309 dígitos decimales, aún no se han encontrado, a pesar de que en 1991 se ofreció un premio de 100 000 dólares por su factorización.

La solución de Shor

En 1994, Peter Shor se dio cuenta de que un ordenador cuántico podía factorizar un número grande de forma exponencialmente más eficiente que un ordenador clásico. Su visión se basaba en la relación entre este problema de factorización y la aritmética modular. Repasaremos brevemente los fundamentos de la aritmética modular y luego veremos cómo podemos utilizarla para factorizar $N$.

Aritmética modular

La aritmética modular es un sistema de conteo cíclico, lo que significa que, aunque el conteo comienza de la forma habitual, con los números enteros 0, 1, 2, etc., En algún momento, tras un periodo de tiempo $N$, el recuento vuelve a empezar. Veamos cómo funciona esto con un ejemplo. Digamos que nuestro período es 5. Entonces, mientras contamos, donde normalmente llegaríamos a 5, en su lugar volvemos a empezar desde 0:

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

Esto se debe a que en el mundo «» modulo-5, 5 equivale a 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

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

Sale en un largo viaje transcontinental en tren a las 8 de la mañana. El viaje en tren 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$

  Por lo tanto, llegarías a tu destino a las 20:00, o las 8 de la tarde.

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

A menudo resulta útil introducir dos conjuntos, $\mathbb{Z}_N$ y $\mathbb{Z}_N^*$. $\mathbb{Z}_N$ es simplemente el conjunto de números que existen en un mundo «módulo $N$ ». Por ejemplo, cuando contábamos modulo-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$ ) con 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 denominado anillo.

Hay un subconjunto especial de $\mathbb{Z}_N$ que nos interesa especialmente para el algoritmo de Shor. Es el subconjunto de números en $\mathbb{Z}_N$ tal que el máximo común divisor entre cada elemento y $N$ es 1, por lo que cada elemento es «coprimario» con respecto a $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 $\mathbb{Z}_N^*$ llamamos. Resulta que con $\mathbb{Z}_N^*$ (y con los grupos finitos en general), si elegimos cualquier elemento $a \in \mathbb{Z}_N^*$ y multiplicamos repetidamente $a$ por sí mismo, siempre acabaremos obteniendo el número $1$. El número mínimo de veces que hay que multiplicar $a$ por sí mismo para obtener $1$ se denomina orden de $a$. Este hecho será muy importante para nuestro análisis sobre cómo factorizar números más adelante.

Comprueba tu comprensión

¿Qué es $\mathbb{Z}_{15}^*$?

• Respuesta

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

  Hemos excluido 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 en $\mathbb{Z}_{15}^*$?

• Respuesta

  El orden $r$ es el número más bajo 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}$$

  Tenga en cuenta que, aunque pudimos encontrar el orden de los números en $\mathbb{Z}_{15}^*$, esto NO es una tarea fácil en general, para números más grandes $N$. Este es el quid de la cuestión del problema de la factorización y la razón por la que necesitamos un ordenador cuántico. Veremos por qué a medida que avancemos con el resto del cuaderno.

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

La clave para encontrar factores $p$ y $q$ tales que $N=pq$ se reduce a 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 hallar los factores $p$ y $q$? Analicemos ahora el razonamiento. Dado $x^2 \equiv 1 \bmod N$ que, eso significa que $x^2 - 1 \equiv 0 \bmod N$. En otras palabras, $x^2 - 1$ es un múltiplo de $N$. Por lo tanto, para algún entero $l$,

$x^2 - 1 = l N$

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

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

A partir de nuestras hipótesis iniciales sabemos que $x \not\equiv \pm 1 \bmod N$, por lo que $N$ no se divide uniformemente ni en $x+1$ ni $x-1$ en. Por lo tanto, los dos factores de $N$, $p$ y, $q$ deben dividirse cada uno en $x-1$ y $x+1$. O bien $p$ es un factor de $x-1$ y $q$ es un factor de $x+1$, o viceversa. Por lo tanto, 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 fácil que se puede realizar, por ejemplo, utilizando el algoritmo de Euclides.

Comprueba tu comprensión

Puede resultar complicado comprender cada paso de la lógica anterior, así que intente aplicarla con un ejemplo. Utilice $N=15$ y $x=11$. En primer lugar, compruebe que $x^2 \equiv 1 \text{mod}(N)$ y $x \not\equiv \pm 1 \bmod N$. A continuación, continúe verificando cada paso. Por último, calcula $\text{GCD}(11\pm1,15)$ y comprueba 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í que, ¡encontramos nuestros factores de $15$!

El algoritmo

Ahora que hemos visto cómo encontrar un número entero $x$ tal que nos $x^2 \equiv 1\bmod N$ ayuda a factorizar $N$, podemos repasar el algoritmo de Shor. Básicamente, se trata de encontrar $x$ :

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

• Calcular $\text{GCD}(a, N)$ de forma clásica.
  • Si $\text{GCD}(a, N) > 1$, ya has encontrado un factor. Alto.
  • De lo contrario, continúe.

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

3. Comprueba si el pedido es par.

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

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

• Comprueba que $x \not\equiv 1 \pmod N$ y $x \not\equiv -1 \pmod N$.
  • Si $x \equiv \pm 1 \pmod N$, vuelve al paso 1 y elige uno nuevo $a$.
• De lo contrario, calcula los mcd para extraer los factores:

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

5. Factorizar recursivamente si es necesario.

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

Basándonos en este procedimiento, podría no resultar obvio por qué se necesita un ordenador cuántico para completar esta tarea. Es necesario porque el paso 2, encontrar el orden del $a$ módulo $N$, es clásicamente un problema muy difícil. La complejidad aumenta exponencialmente con el número $N$. Pero con un ordenador cuántico, solo tenemos que utilizar la estimación de fase cuántica para resolverlo. El paso 4, hallar el MCD de dos números enteros, es en realidad algo bastante fácil de hacer de forma clásica. Por lo tanto, el único paso que realmente necesita la potencia de un ordenador cuántico es el paso de búsqueda de órdenes. Decimos que el problema del factoraje «se reduce» al problema de encontrar el orden.

La parte difícil: encontrar el pedido

Ahora veremos cómo podemos utilizar un ordenador cuántico para la búsqueda. En primer lugar, aclaremos qué entendemos por «orden» Por supuesto, ya te he explicado lo que significa matemáticamente el orden: es el primer entero distinto $r$ de cero tal que $a^r = 1 \pmod N.$ Pero veamos si podemos entender un poco mejor este concepto.

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

¿Notas algo? ¡Son funciones periódicas! ¡Y el orden $r$ es el mismo que el período! Por lo tanto, encontrar el orden equivale a encontrar el período.

Las computadoras cuánticas son muy adecuadas para hallar el período de las funciones. Para ello, podemos utilizar una subrutina algorítmica denominada «estimación de fase cuántica». En el módulo anterior hablamos sobre QPE y su relación con la transformada de Fourier cuántica. Para obtener información detallada, consulte el módulo QFT o la lección de John Watrous sobre estimación de fase cuántica en su curso sobre algoritmos cuánticos. Ahora repasaremos los puntos principales del procedimiento:

En la estimación de fase cuántica (QPE), comenzamos con un operador unitario $U$ y un estado propio de ese operador unitario $|\psi\rangle$. A continuación, utilizamos la QPE para aproximar el valor propio correspondiente, que, dado que el operador es unitario, tendrá la forma $e^{2\pi i \theta}$. Por lo tanto, hallar el valor propio equivale a hallar el valor de $\theta$ en la función periódica. El circuito tiene el siguiente aspecto:

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

En el algoritmo de Shor, utilizamos QPE en el operador unitario $M_a$ :

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

Aquí, $|y\rangle$ denota un estado de base computacional del registro multiqubit, donde el valor binario de los qubits corresponde al entero $y$. Por ejemplo, si $N=15$ y $y = 2$, entonces $|y\rangle$ se representa mediante el estado de base de cuatro $|0010\rangle$ qubits, ya que se necesitan cuatro qubits para codificar números hasta 15. (Si este concepto le resulta desconocido, consulte el módulo introductorio Qiskit en las aulas para refrescar sus conocimientos sobre la codificación binaria de los estados cuánticos)

Ahora, necesitamos averiguar un estado propio de esta unidad. 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 nuevamente al $|1\rangle$ estado. Por ejemplo, con $a = 3$ y $N = 35$ :

Así, 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 los estados propios de $M_a$. (Hay más estados propios además de estos. Pero solo nos interesan los que tienen la forma anterior)

Comprueba tu comprensión

Encuentre un estado propio 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 $r=4$. Los estados propios que nos interesan serán una superposición igual de todos los estados que se han repetido 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 nuestro estado cuántico en uno de estos estados propios (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 valor propio correspondiente, $\omega_j = e^{2 \pi i \theta_j}$ donde $\theta_j = \frac{j}{r}$. A continuación, podremos determinar el orden $r$ mediante la sencilla ecuación:

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

Pero recuerde, dije que se trata de $\theta_j$* estimaciones* de QPE, 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 tengamos, mejor $m$ será la estimación. En los problemas al final de la lección, se te pedirá que determines el mínimo $m$ 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 la preparación del estado propio $|\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 hacerlo sin saber ya qué $r$ es. La lógica es circular. Necesitamos una forma de estimar el valor propio sin inicializar el estado propio.

En lugar de comenzar con un estado propio de $M_a$, podemos preparar el estado inicial en el estado $n$ de -qubit correspondiente a $|1\rangle$ en binario (como en ) $|000...01\rangle$. Aunque este estado en sí mismo obviamente no es un estado propio de $M_a$, es una superposición sobre todos los estados propios $|\psi_k\rangle$ :

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

Comprueba tu comprensión

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

• Respuesta

  Los cuatro estados propios 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 estados propios de la forma indicada anteriormente, el algoritmo QPE estima simultáneamente cada uno de los $\theta_k$ correspondientes a estos estados propios. Por lo tanto, la medición de los qubits $m$ de control al final dará como resultado una aproximación al valor $k/r$ donde $k \in \{0,1,2,...,r-1\}$ es uno de los valores propios elegidos al azar. Si repetimos este circuito varias veces y obtenemos algunas muestras con diferentes valores de $k$, rápidamente podremos deducir $r$.

Implementar en Qiskit

Como mencionamos anteriormente, nuestro hardware no está en condiciones de factorizar números tan grandes como RSA1024. Vamos a factorizar un número pequeño para demostrar cómo funciona el algoritmo. Para esta demostración, utilizaremos una versión simplificada del código presentado en el tutorial del algoritmo de Shor. Si desea obtener más detalles, visite el tutorial.

Ejecutaremos el algoritmo utilizando nuestro marco estándar para resolver problemas cuánticos, denominado marco de patrones Qiskit. Esto consta de cuatro pasos:

1. Asignación de su problema a un circuito cuántico
2. Optimizar el circuito para que se ejecute en hardware cuántico
3. Ejecuta tu circuito en el ordenador cuántico
4. Procesar posteriormente las mediciones

1. Mapa

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

En primer lugar, debemos construir el circuito que implementará la unidad de multiplicación modular. $M_a$ Esta es, en realidad, la parte más complicada de toda la implementación y puede requerir un gran esfuerzo computacional, dependiendo de cómo se haga. Para ello, haremos un poco de trampa: sabemos que estamos empezando en el estado $|1\rangle$, y por una pregunta anterior,

Por lo tanto, construiremos una unidad que realice las operaciones correctas en estos cuatro estados, pero que deje todos los demás estados tal cual. Esto es hacer trampa porque estamos utilizando nuestro conocimiento del orden de $2\bmod 15$ para simplificar el unitario. Si realmente estuviéramos tratando de factorizar un número cuyos factores nos fueran desconocidos, no podríamos hacerlo.

Comprueba tu comprensión

Con tu conocimiento de cómo el $M_2$ operador 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 se puede realizar con un simple SWAP. $M_2|0001\rangle$ se consigue intercambiando los estados de los qubits $0$ y $1$. $M_2|0010\rangle$ se consigue intercambiando los estados de los qubits $1$ y $2$. Y así sucesivamente. Por lo tanto, podemos descomponer la $M_2$ matriz 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 que queremos en 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 codificar 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

A continuación, creamos el $M_2$ operador:

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)

Output:

El algoritmo QPE utiliza una puerta $U$ controlada. Ahora que tenemos un $M_2$ circuito, 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)

Output:

Ahora tenemos nuestra puerta $U$ controlada. Pero para ejecutar el algoritmo de estimación de fase cuántica, necesitaremos controlado $U^2$, controlado $U^4$, hasta controlado $U^{2^{m-1}}$, donde $m$ es el número de qubits utilizados para estimar la fase. Cuantos más qubits, más precisa será la estimación de fase. Utilizaremos qubits $m=8$ de control para nuestro procedimiento de estimación de fase. Por lo tanto, necesitamos:

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)

Output:

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

Dado que $a^{2^k} \bmod N = 1$ para $k \ge 2$, todos los operadores correspondientes ( $M_8$ y superiores) son equivalentes a la identidad. Por lo tanto, 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$ (por lo tanto, $2^k = 4$ ), cada potencia posterior del operador es la identidad. En general, para números más grandes $N$ 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 se considera un ejemplo simplificado : los números pequeños permiten atajos que no funcionarían en 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)

Output:

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)

Output:

Ahora, podemos juntarlo todo para encontrar el orden de $2\bmod 15$ con un circuito cuántico, utilizando 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)

Output:

2. Optimizar

Ahora que hemos mapeado nuestro circuito, el siguiente paso es optimizarlo para que se ejecute en un ordenador cuántico concreto. Primero tenemos que cargar el backend.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

Si no dispone de tiempo en su cuenta o desea utilizar un simulador por cualquier motivo, puede ejecutar la celda siguiente para configurar un simulador que imitará el dispositivo cuántico que hemos seleccionado anteriormente:

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)

Output:

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))

Output:

Vemos cuatro picos claros en 00000000, 01000000, 10000000 y 11000000, con algunos recuentos en otras cadenas de bits debido al ruido en el ordenador cuántico. Ignoraremos estos y mantendremos solo los cuatro dominantes imponiendo un umbral: solo los recuentos 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. Postprocesamiento

En el caso del algoritmo de Shor, gran parte del algoritmo se ejecuta de forma clásica. Por lo tanto, pondremos el resto en el paso de «posprocesamiento», después de haber obtenido nuestras mediciones del ordenador cuántico. Cada una de las mediciones anteriores se puede convertir en números enteros que, tras dividirlos por $2^m$, son nuestras aproximaciones para $\frac{k}{r}$, donde $k$ es aleatorio cada vez.

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} ***")

Output:

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 completar el módulo, es posible que te sorprenda una nueva apreciación de la genialidad de Peter Shor al haber ideado un algoritmo tan inteligente. Pero esperamos que también hayas alcanzado un nuevo nivel de comprensión de su engañosa simplicidad. Aunque el algoritmo pueda parecer impresionantemente (o intimidantemente) complejo, si lo desglosas en cada paso lógico y lo sigues lentamente, tú también podrás ejecutar el algoritmo de Shor.

Aunque aún estamos lejos de utilizar este algoritmo para factorizar números como RSA1024, nuestros ordenadores cuánticos mejoran cada día y, una vez que se alcance un umbral denominado «tolerancia a fallos», algoritmos como estos no tardarán en llegar. ¡Es un momento emocionante para aprender sobre la computación cuántica!

Problemas

Conceptos fundamentales:

• Los sistemas criptográficos modernos se basan en la dificultad clásica de factorizar números enteros grandes.
• La aritmética modular —incluidas las estructuras $\mathbb{Z}_N$ y $\mathbb{Z}_N^*$ — proporciona la base matemática para el algoritmo de Shor.
• El problema de factorizar un número entero $N$ puede reducirse al problema de hallar el orden de un número módulo $N$.
• La búsqueda de orden cuántico utiliza técnicas de estimación de fase cuántica para determinar el periodo 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 del orden cuántico y, a continuación, calcula de forma clásica los factores 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 se puede ejecutar de manera eficiente en cualquier ordenador cuántico moderno.
3. El algoritmo de T/F Shor utiliza 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 correcta del algoritmo de Shor siempre garantiza los factores correctos.

Respuesta breve:

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

Problemas desafiantes:

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

2. Siguiendo el procedimiento que hemos descrito aquí para factorizar 15, ahora intenta factorizar 21.