Computación Cuántica: el Algoritmo de Shor

Trabajo Fin de Grado Computación Cuántica: el Algoritmo de Shor. Santiago Iglesias González 29 de Julio, 2022 UNIVERSIDAD DE SANTIAGO DE COMPOSTELA GRADO DE MATEMÁTICAS Trabajo Fin de Grado Computación Cuántica: el Algoritmo de Shor. Santiago Iglesias González Julio, 2022 UNIVERSIDAD DE SANTIAGO DE COMPOSTELA Trabajo propuesto Área de Conocimiento: Álgebra Título: Computación Cuántica: el Algoritmo de Shor. Breve descripción del contenido En este trabajo se hará una introducción a la computación cuántica explotando la analogía entre las funciones booleanas y las transformaciones unitarias en un espacio de Hilbert. Como aplicación se dará una descripción del algoritmo de factorización en primos de número enteros desarrollado por Shor. Recomendaciones Haber superado las materias de Área de Álgebra del Grado en Matemáticas. Tener conocimientos de los algoritmos clásicos y de su formalización en términos de funciones booleanas. Otras observaciones iii Índice Resumen viii Introducción xi 1. Cuestiones preliminares 1 1.1. Números naturales y cadenas binarias . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Notaciónasintótica................................... 3 2. Preliminares de álgebra lineal 5 2.1. EspaciosdeHilbert................................... 5 2.2. Producto: usual, tensorial y vectorial . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3. Matrices......................................... 7 2.4. Espacios complejos y producto escalar . . . . . . . . . . . . . . . . . . . . . . . . 9 3. Sistema RSA: claves pública y privada 11 4. Funciones binarias, bits cuánticos y factibilidad 15 4.1. Funcionesbinarias ................................... 15 4.1.1. Conceptos generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.1.2. Funciones binarias factibles . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.2. Representación cuántica de argumentos binarios . . . . . . . . . . . . . . . . . . . 18 4.3. Factibilidadcuántica.................................. 19 v vi ÍNDICE 4.4. Circuitos y matrices cuánticas : Hadamard y U1(α)................ 20 4.4.1. Introducción .................................. 20 4.4.2. Matrices de Hadamard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.4.3. Matrices U1(α)................................ 22 5. Transformada Cuántica de Fourier (QFT) 23 5.1. Definición y principales propiedades . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.2. Transformación a circuito cuántico . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.3. Calcular el periodo de una función . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6. El algoritmo de Shor 33 6.1. Descripción del algoritmo: pasos y ejemplo de aplicación . . . . . . . . . . . . . . 33 6.2. Principal aplicación y eficiencia del algoritmo . . . . . . . . . . . . . . . . . . . . 37 Bibliografía 39 xiv INTRODUCCIÓN Capítulo 1 Cuestiones preliminares 1.1. Números naturales y cadenas binarias En este capítulo, hablaremos de los números naturales y su representación como cadenas binarias de unos y ceros, fundamentales en la computación debido al establecimiento de roles contrarios en la informática: encendido/apagado o cargado/descargado, donde cada uno de estos estados es representado por un bit diferente (0 para el apagado y 1 para el encendido). Recordemos que una cadena binaria es un conjunto de bits cuyos elementos solo pueden tomar dos valores: 0 o 1. Con estas cadenas podemos realizar operaciones simples: el tamaño de una cadena es el número de bits presentes en la misma, y si xeyson cadenas binarias, entonces xy es la concatenación de ambas cadenas. Ejemplo 1.1. Si x=01 ey=11101, entonces el resultado de concatenar ambas cadenas es el siguiente: xy=0111101. Esta operación de concatenación la podemos entender como una operación interna para las cadenas binarias, pero en este caso no utilizaremos un símbolo explícitamente. Por otro lado, hablaremos del producto interior binario: si xeyson cadenas de longitud m; entonces x•y representa dicho producto y está definido de la siguiente manera: x•y=x1y1⊕···⊕xmym En este caso, el símbolo ⊕denota el OR exclusivo (únicamente es verdadero cuando ambos valores difieren; es decir, cuando uno es 0 y el otro es 1 o viceversa) [9]. Una vez comentadas estas primeras cuestiones, lo siguiente que debemos conocer es cómo pasar de un número natural a una cadena binaria y viceversa, ya que en ciertos casos será más útil utilizar una forma que otra. Esta correspondencia es muy importante en la computación, y más concretamente en los algoritmos cuánticos. 1 2 1. Cuestiones preliminares A continuación, mostramos los procesos que nos permiten pasar de una forma a otra: Un número m∈Nadmite una única representación en forma de cadena binaria: m= 2n−1xn−1+···+ 2x1+x0, donde cada xi, con i∈ {1, . . . , n −1}, es un bit (0 o 1) y en el que xn−1= 0. Ejemplo 1.2. El número 9se representaría en binario como 1001 (23·1+22·0+21·0+20·1 = 8+0+0+1=9). En el otro sentido, podemos emplear la cadena binaria xn−1. . . x1x0 para denotar el número natural 2n−1xn−1+···+ 2x1+x0. De esta manera, la cadena 101010 representa el número natural 25+ 23+ 21= 32 + 8 + 2 = 42. Surge la necesidad de fijar dichas representaciones de tal manera que sean únicas. Para ello, es necesario conocer la longitud de las cadenas; ya que en otro caso, no sabríamos, por ejemplo, ¿que cadena representaría al número 0: si 0 o 00 o 000 y así en adelante? Para resolver este problema, lo que podemos hacer es especificar la correspondencia unívocamente entre los números naturales y las cadenas de longitud n, que son de la forma {0,1}n. Si hacemos esto, vemos que ahora el número natural 0 se corresponde de manera única con la cadena binaria 0···0, que presenta n ceros. Además, las cadenas binarias se pueden usar para representar los diferentes subconjuntos de un conjunto. Para ilustrarlo, veamos el siguiente ejemplo: Ejemplo 1.3. Denotemos por A={1,2,3}nuestro conjunto. Entonces, 000 se corresponde con el conjunto vacío, 011 se asocia con el subconjunto B={2,3}, 110 con el subconjunto C={1,2}, 111 con el conjunto Ay así sucesivamente. 1.2. Notación asintótica 3 1.2. Notación asintótica Una cuestión muy importante a tener en cuenta en los algoritmos es el orden de complejidad, que representa la cantidad de recursos (temporales) que necesita un algoritmo para resolver un problema y por tanto permite determinar la eficiencia del mismo [5]. A continuación, introduciremos un par de definiciones relacionadas con el orden de complejidad de los algoritmos: Definición 1.4. Dos funciones s(n)yt(n)definidas en Nson asintóticamente equivalentes si l´ımn→∞ s(n) t(n)= 1. Definición 1.5. Dadas dos funciones s, t :N−→ Rtenemos que: s(n)=O(t(n)) si existen constantes c, d ∈Ntales que, ∀n, s(n)≤c·t(n) + d. s(n) = Ω(t(n)) si t(n) = O(s(n)). s(n) = Θ(t(n)) si s(n) = O(t(n)) ys(n) = Ω(t(n)), siendo O(t(n)) el límite superior asintótico; que es una medida de la mayor cantidad de tiempo que podría tardar el algoritmo en completarse, Ω(t(n)) el límite inferior asintótico, que es una medida de la menor cantidad de tiempo que podría tardar el algoritmo en completarse y por último, Θ(t(n)) representa el tiempo real de ejecución del algoritmo [8]. De esta forma, estas definiciones serán utilizadas más adelante para estudiar el orden de complejidad de los algoritmos y procesos involucrados en nuestro estudio. 4 1. Cuestiones preliminares Capítulo 2 Preliminares de álgebra lineal En este capítulo fijaremos notaciones y recordaremos resultados y definiciones de álgebra lineal que utilizaremos posteriormente. 2.1. Espacios de Hilbert En primer lugar, recordemos que un espacio de Hilbert real es un espacio euclidiano, que se denota por HNsiendo Nla dimensión de dicho espacio y cuyos elementos ason vectores reales de dimensión N, que se representan de la siguiente manera: a=       a1 a2 . . . aN        En él, están definidas las siguientes operaciones: Suma de vectores: si aybson vectores del espacio; su suma a+btambién pertenece al espacio y está definida como: a+b=    a1 . . . aN    +    b1 . . . bN    =    a1+b1 . . . aN+bN     5 6 2. Preliminares de álgebra lineal El producto de un vector a∈HNy un escalar c∈R, es el vector ca c·a=c    a1 . . . aN    =    c·a1 . . . c·aN    . El producto escalar de dos vectores ayb∈HNque se suponen escogidos de una base ortonormal es a·b=at·b= N X i=1 aibi. La norma de un vector a∈HNse define como: ∥a∥=X k a2 k 1 2 =√at·a. En el caso de que nuestro espacio sea únicamente de dos dimensiones, la norma del vector a a="a1 a2# es la longitud del vector en el plano: pa2 1+a2 2. Por último, recordemos que un vector unitario es aquel cuya norma es 1. 2.2. Producto: usual, tensorial y vectorial El producto cartesiano H1×H2entre un espacio de Hilbert de dimensión m, que denotaremos por H1con otro espacio de Hilbert de dimensión n, denotado por H2es el espacio de Hilbert de dimensión m+nobtenido concatenando vectores del espacio H1con vectores del espacio H2. De modo más preciso, si ξ1={e1, . . . , em}es una base ortonormal de H1yξ2={e′ 1, . . . , e′ n}es una base ortonormal de H2, los elementos de H1×H2están identificados en la base ortonormal ξ12 ={e1, . . . , em, e′ 1, . . . , e′ n}por vectores de Rn+m. Por otro lado, el producto tensorial de ambos espacios, denotado por H1⊗H2es un espacio de Hilbert de dimensión n·mcon base ortonormal asociada ξ1⊗ξ2={ei⊗e′ j, i ∈ {1, . . . , m}, j ∈ {1, . . . , n}}. El producto tensorial de dos vectores a∈H1,b∈H2es el vector c=a⊗bdeterminado en coordenadas respecto a la base ξ1⊗ξ2por la expresión cij =aibj a partir de las coordenadas de aen ξ1y las de ben ξ2. Por tanto, utilizando la base ξ1⊗ξ2el espacio H1×H2se identifica con Rnm. 2.3. Matrices 7 Estos vectores se utilizan en computación cuántica para denotar estados cuánticos puros y se dividen en dos grupos: Vectores separables: son aquellos vectores que son el resultado del producto tensorial realizado sobre otros dos vectores. Ejemplos: los vectores e00 oe11. Vectores entrelazados: son aquellos vectores que no se pueden escribir como el producto tensorial de otros dos vectores. Ejemplos: la combinación lineal de los vectores anteriores 1 √2(e00 +e11)es entrelazado. Así, los vectores que forman la base del espacio H1⊗H2son separables, pero esto no es cierto en general para las combinaciones lineales de los mismos. Por último, recordemos también que el producto escalar de dos vectores reales a∈Rmy b∈Rmviene dado por: ⟨a,b⟩= m X k=1 akbk. 2.3. Matrices Las matrices representan operadores lineales en los espacios de Hilbert. Podemos sumarlas, multiplicarlas y aplicarlas sobre vectores. Recordemos también la notación básica de matrices y su aplicación sobre vectores con el siguiente ejemplo. Asumiremos sin mencionarlo que las matrices tienen las dimensiones adecuadas para realizar las operaciones indicadas. Ejemplo 2.1. U V a =b Esto significa que en primer lugar aplicamos la matriz Vsobre el vector acuyo resultado es un vector al que a continuación se le aplica la matriz Udando como resultado el vector b. Por otro lado, la matriz INdenota la matriz identidad de dimensión N×N, y cualquier matriz se representará como U[ij], la entrada correspondiente a la fila iy columna jde la matriz U. Recordemos también que en un lenguaje matricial diremos que una aplicación es lineal si verifica las siguientes propiedades: U(α·a) = αU a. U(a+b) = U a +U b. Además, diremos también que si Ues una matriz, entonces Ukdenota la k-ésima potencia de la matriz U. Recordemos también diferentes tipos de matrices muy utilizadas en diferentes contextos. 8 2. Preliminares de álgebra lineal Definición 2.2. Denotaremos por UTa la matriz traspuesta de U, es decir UT[i, j] = U[j, i] El producto escalar de dos vectores de HNse obtiene respecto a una base ortonormal mediante la expresión matricial ⟨a,b⟩=atb. Definición 2.3. Diremos que Ues una matriz inversible si existe una matriz Vque verifica: V U =U V =I Tal matriz Vsi existe, entonces es única y se denota por V=U−1. Definición 2.4. Diremos que Ues una matriz unitaria si verifica que: UTU=I es decir, si su inversa coincide con su traspuesta. Definición 2.5. Diremos que Ues una matriz de permutación si es una matriz cuadrada y que presenta todo ceros en cada fila y columna excepto un único 1. Todas las matrices de permutación son unitarias. Las matrices unitarias preservan la distancia euclidiana, como veremos en el siguiente lema [1]: Lema 2.6. Si Ues una matriz unitaria real y aes un vector real, entonces ∥U a∥=∥a∥. Demostración. El resultado se obtiene: ∥U a∥2=⟨U a,U a⟩= (U a)tU a =atUtU a =⟨a,a⟩=∥a∥2(2.1) 2.4. Espacios complejos y producto escalar 9 2.4. Espacios complejos y producto escalar Muchos algoritmos cuánticos (en especial el algoritmo base de este documento, el de Shor) presentan una parte de computación clásica, basada en las nociones de álgebra vistas, pero también presenta una parte de computación cuántica, basada en espacios vectoriales complejos. Como en los espacios reales, en los espacios complejos utilizaremos matrices y vectores complejos para representar la información, cuyas operaciones sobre ambas son similares al caso real excepto la transposición y el producto escalar. Para poder entender ambas operaciones, es necesario definir la operación conjugación: si z=x+iy, con z∈C,x, y ∈Rei=√−1, entonces el conjugado de z(se denota por z) es x−iy. Definición 2.7. Sea Uuna matriz compleja de dimensiones n×n. Entonces, Ves la matriz adjunta de Usi: V[i, j] = U[j, i] es decir, Ves la matriz conjugada ytraspuesta de U. Se denota por V=U∗. Definición 2.8. Una matriz compleja Ude dimensiones n×nes una matriz unitaria si verifica que U∗U=I es decir, si la matriz adjunta de Ucoincide con su inversa. Recordemos la definición del producto escalar hermitiano y sus propiedades, además de señalar también sus diferencias respecto al caso real. El producto entre los vectores ayb∈Cestá definido de la siguiente manera ⟨a,b⟩= m X k=0 akbk(2.2) y determinado por las siguientes propiedades: ⟨a+b,c⟩=⟨a,c⟩+⟨b,c⟩,∀a,b,c∈C. ⟨αa,b⟩=α⟨a,b⟩,∀α∈Cy∀a,b∈C. ⟨b,a⟩=⟨a,b⟩,∀a,b∈C. ⟨a,a⟩>0,∀a∈Ccon a= 0. En otras palabras, un producto escalar hermitiano es una forma bilineal simétrica con forma cuadrática real y definida positiva. Esta definición generaliza el caso real, ya que también cumple la definición 2.2, de modo que para nuestros propósitos tiene sentido unificar en la misma noción los espacios de Hilbert reales y complejos. 16 4. Funciones binarias, bits cuánticos y factibilidad f(1,0) = 0,f(0,1) = 0 yf(1,1) = 1), la OR (f(0,0) = 0,f(1,0) = 1,f(0,1) = 1 yf(1,1) = 1) o la XOR (f(0,0) = 0,f(1,0) = 1,f(0,1) = 1 yf(1,1) = 0). A continuación mostraremos las 3 últimas operaciones comentadas en el caso de estar trabajando en un espacio de dimensión mayor que 2. En ese caso, definimos AND:f(x1, . . . , xn)=1⇔si xi= 1,∀i∈ {1, . . . , n}. OR:f(x1, . . . , xn) = 1 ⇔si ∃i∈ {1, . . . , n}tal que xi= 1. XOR:f(x1, . . . , xn)=1⇔si el número de índices i∈ {1, . . . , n}tales que xi= 1 es impar. De hecho, estas operaciones binarias se pueden aplicar en pares de cadenas bit a bit. Para ilustrarlo, si xeyson cadenas binarias de dimensión n, entonces x⊕yes igual a: z= (x1⊕y1, . . . , xn⊕yn) Igual que en el ejemplo anterior, podemos definir también las operaciones AND yOR bit a bit para el caso de dos cadenas binarias de igual longitud. Es importante recordar que no son lo mismo que las funciones descritas anteriormente, no son operaciones en ndimensiones, si no que son la aplicación de noperaciones binarias, dónde cada operación de las anteriores conecta el i-ésimo bit de xcon el i-ésimo bit de ypara cada i. De esta manera, el producto interior binario se define aplicando primero la función AND bit a bit y después a cada uno de esos resultados se les aplica la función XOR tal y como se muestra a continuación: x•y=XOR(x1∧y1, . . . , xn∧yn) En casos como el de la operación x⊕y, diremos que tenemos un circuito de npuertas binarias que computan la función binaria f:{0,1}r−→ {0,1}n, siendo r= 2nyfdefinida por f(x, y) = x⊕y. Una vez llegados a este punto, es importante comentar que dichas funciones binarias se representan mediante puertas lógicas, y estas se interconectan formando circuitos para obtener la salida deseada según los parámetros de entrada. Es lógico pensar que a mayor número de puertas en el circuito, mayor esfuerzo deberá ser realizado por el circuito para poder computar el resultado requerido y por tanto, mayor tiempo necesitará para poder calcular el valor final. Además, dichos circuitos deben de cumplir la siguiente propiedad: únicamente se pueden utilizar operaciones básicas y éstas solamente se pueden aplicar a valores calculados previamente. De esta manera, podemos construir circuitos que computen cualquier función que deseemos. El problema radica en la eficiencia que podemos conseguir para poder crear dichos circuitos. Relacionado con esta cuestión, hablaremos a continuación de las nociones de factibilidad de las funciones binarias, que nos permitirán afirmar de manera objetiva el grado en el que una función binaria puede ser computada eficientemente o no. 4.1. Funciones binarias 17 4.1.2. Funciones binarias factibles Existen distintos niveles de complejidad en los que podemos encuadrar a las funciones binarias. Dichos niveles pueden ser definidos gracias a la Ingeniería Informática: por ejemplo, las funciones AND yOR son computables en un número lineal de pasos, y por tanto su orden de complejidad es O(n), mientras que existen otras cuyo orden en exponencial, esto es, O(nm) con m∈N. Para visualizar esta circunstancia de la diferencia entre los órdenes de complejidad, consideremos la tabla de verdad para la operación XOR exclusiva binaria: x y x ⊕y 0 0 0 0 1 1 1 0 1 1 1 0 Cuadro 4.1: Tabla de verdad de la operación XOR-exclusiva binaria La tabla representa la salida que produce la función OR-exclusiva según los datos de entrada utilizados por la función. En general, una función binaria f(x1, . . . , xn)se define mediante una tabla de verdad que tiene de tamaño 2nfilas (una por cada posible combinación de los datos de entrada). Como es lógico, la dificultad radica en que a medida que aumenta el número de datos de entrada; el número de filas presentes en la tabla de verdad aumenta de manera exponencial. De esta manera, la representación de funciones binarias como tabla de verdad siempre es posible, pero no factible; debido a que las tablas asociadas a funciones con un gran de número de entradas serían demasiado largas para poder representarlas. Como últimos contenidos de esta sección, comentaremos los conceptos de familia [fi] = {f1, . . . , fr} de funciones binarias y la factibilidad de las mismas. En primer lugar, cada familia [fi]de cadenas binarias representa el conjunto formado por cada una de las funciones fique toman nidatos de entrada. De esta manera, la familia [fi]determina una única función que actúa sobre cadenas de todas las longitudes consideradas; esto es: f:{0,1}n−→ {0,1}n, con n=n1+··· +nr generalizando también la dimensión de la salida generada por la función considerada. Una vez comentada esta cuestión, podemos indicar ya la definición de factibilidad: Definición 4.1. Una familia de funciones [fi] = {f1, . . . , fr}es factible si cada una de las funciones fies computable mediante circuitos de puertas lógicas de orden de complejidad nO(1). 18 4. Funciones binarias, bits cuánticos y factibilidad 4.2. Representación cuántica de argumentos binarios En primer lugar, denotaremos por |x⟩=|xnxn−1···x0⟩=|xn⟩⊗|xn−1⟩⊗···⊗|x0⟩al qubit x siendo xi∈ {0,1}con i∈ {1,··· , n}las coordenadas binarias de un número binario x. Ahora, sea N= 2n. Entonces, cada vector básico en un espacio de Hilbert de dimensión Nse corresponde con una cadena binaria de dimensión n. El esquema de codificación estándar asigna a cada índice j∈ {0, . . . , n −1}la cadena binaria de nbits que representa dicho índice en notación binaria, añadiendo ceros al principio si es necesario. De esta manera, para poder representar una función binaria cualquiera (y=f(x1, . . . , xn)) necesitaremos n+ 1 coordenadas binarias, lo que implica 2N= 2 ·2n= 2n+1 coordenadas matriciales. Realmente, lo que estamos computando es la función: F(x1, . . . , xn, z)=(x1, . . . , xn, z ⊕f(x1, . . . , xn)) Una propiedad importante de esta función es que es invertible, y además la inversa es ella misma. Veámoslo: F(F(x1, . . . , xn, z)) = F(x1, . . . , xn, z ⊕y) = (x1, . . . , xn,(z⊕y)⊕y)=(x1, . . . , xn, z)(4.1) La segunda propiedad importante es que tenemos una matriz de permutación Pfde dimensión 2N×2Nque se describe fácilmente: el único 1 de cada fila x1x2. . . xnzestá en la columna x1x2. . . xnb, donde b=z⊕f(x1, . . . , xn). Sin embargo, este es el caso en el que la salida de la función fes solamente un bit. Generalmente, si la función fpresenta mvalores de salida (y1, . . . , ym), entonces la función Fse aplica de la siguiente manera: F(x1, . . . , xn, z1, . . . , zm) = (x1, . . . , xn, z1⊕y1, . . . , zm⊕ym) Por lo tanto, la matriz Pfsigue siendo una matriz de permutación, pero ahora tiene dimensión 2n+m×2n+m. Por otro lado, es importante comentar también lo que sucede en los casos en los que necesitamos h“bits de ayuda” para poder calcular la función f. Con este esquema, utilizando el sistema de computación clásica de “filas y columnas”, toda nuestra información está contenida en n′= n+m+hfilas con la entrada xsituada en la primera columna. De esta forma, cada fila representa un qubit, abreviatura de bit cuántico; mientras que las hfilas de ayuda se conocen como qubits auxiliares. Estos qubits auxiliares se utilizan porque en la computación cuántica es necesario igualar la dimensión del conjunto de datos de entrada al de los datos de salida. Como es lógico, escribir una matriz de dimensión 2n′×2n′solo para una permutación no es factible. Esta razón es suficiente para pensar utilizar los operadores Pfcomo piezas de código. Realmente, estos qubits son coordenadas de las cadenas binarias que representan los índices de estos programas. Dichas cadenas tienen dimensión n′, y sus índices 1, . . . , n′es lo que denotamos por coordenadas cuánticas. Por lo tanto, nuestro siguiente paso será determinar cuáles son las operaciones factibles dentro de la computación cuántica; que es lo que trataremos a continuación. 4.3. Factibilidad cuántica 19 4.3. Factibilidad cuántica Un algoritmo cuántico lo que hace es aplicar una serie de matrices unitarias a un vector inicial. Ante la pregunta de si es posible aplicar cualquier matriz unitaria que deseemos, la respuesta obviamente es no; debido a que los algoritmos cuánticos están diseñados para ser eficientes, y es por esta razón por la que debe de haber una restricción en las matrices que pensamos utilizar. Antes de seguir, recordemos ciertas particularidades de las matrices Pf: El diseño de Pfno depende de la complejidad de la función binaria f. Aunque empleemos operaciones simples (como por ejemplo la AND(x1, x2, . . . , xn), dicha matriz seguirá siendo demasiado grande para poderla computar de manera factible. Por lo tanto, esta circunstancia nos permite plantear varias dudas: ¿Cómo podemos distinguir operaciones básicas factibles? ¿Qué debemos usar como variables de nuestras funciones? ¿Si tenemos un vector de tamaño 2n, cuántas variables necesitaremos? La respuesta a estas preguntas se basa en darse cuenta que si conseguimos mantener el número kde argumentos de cualquier operación como una constante, entonces 2kpermanecerá constante. Así, podremos utilizar matrices de dimensión 2k×2kque aplicaremos sobre solo algunos argumentos. Estos argumentos no deben confundirse con las coordenadas 0, . . . , N −1de los espacios de Hilbert. Por otro lado, las coordenadas cuánticas empiezan siendo nombradas como x1, x2, . . . , xnigual que las cadenas binarias de entrada y se extienden para representar también los bits de salida de la función y los bits acompañantes que ya comentamos anteriormente. Una vez entendidas estas cuestiones, la noción de factibilidad en matrices unitarias no es más que la extensión natural de la misma aplicada sobre circuitos binarios. Cualquier matriz unitaria Bde dimensión 2k×2k, siendo kconstante y k≤3es factible. Este tipo de matrices operan en cualquier subconjunto de kcoordenadas cuánticas, dejando sin tocar el resto de n′−kcoordenadas. A continuación, supongamos que Ues una matriz unitaria cualquiera de dimensión N×N. Entonces, diremos que es factible si existe una manera sencilla de crearla empleando matrices básicas, que son el resultado de realizar el producto tensorial entre una matriz By matrices identidad aplicadas sobre las demás coordenadas cuánticas. Técnicamente, estamos suponiendo que Upertenece a la familia infinita [Un]parametrizada por n, siendo cada matriz U∈ Un constructible mediante nO(1) matrices básicas. Una vez comentado lo anterior, mostraremos a continuación la definición de que una computación cuántica sea factible: 20 4. Funciones binarias, bits cuánticos y factibilidad Definición 4.2. Una computación cuántica Cen squbits es factible si: C=UtUt−1. . . U1, donde cada Uicon i∈ {1, . . . , t}es una operación factible, y donde sytestán acotados por un polinomio de grado el número nde qubits de entrada. 4.4. Circuitos y matrices cuánticas : Hadamard y U1(α) 4.4.1. Introducción Los circuitos cuánticos permiten representar el proceso de aplicar una serie de transformaciones cuánticas a un conjunto de datos de entrada para generar un conjunto de datos de salida. Dichos circuitos se pueden representar mediante matrices unitarias y las transformaciones que se llevan a cabo son las denominadas puertas cuánticas. Un ejemplo de un circuito de este tipo se presenta en la siguiente imagen: Figura 4.1: Ejemplo de circuito cuántico De esta manera, podemos observar como se representa un circuito cuántico: las lineas horizontales (similares a las de un pentagrama) representan las entradas x1, . . . , xn(en nuestro ejemplo n= 2). Por otro lado, el recuadro con la H representa una de las puertas cuánticas (en este caso la de Hadamard, que veremos en la siguiente subsección), y la línea vertical representa el origen (o control) en el punto negro situado en la línea 1 y el objetivo en la segunda de una puerta cuántica (en este caso la CN OT ) que no se muestra explícitamente. Así, para obtener el resultado tras aplicar el circuito a los bits de entrada se realiza la composición de las puertas cuánticas involucradas, de la misma manera que se hace un producto de matrices. En nuestro ejemplo, el resultado se obtendría al realizar el producto de matrices CN OT ·H. 4.4. Circuitos y matrices cuánticas : Hadamard y U1(α)21 Una vez indicado como funcionan y se escriben los circuitos cuánticos, pasaremos a comentar en las dos siguientes subsecciones los dos tipos de puertas cuánticas que tenemos que saber para poder comprender los pasos previos al algoritmo de Shor (debido a que van a ser usadas durante el proceso de determinar el periodo de nuestra función tras emplear la Transformada Cuántica de Fourier). Estas puertas son las denominadas puertas (o matrices) de Hadamard y las matrices U1(α). A continuación, pasemos a comentar cada una de ellas: 4.4.2. Matrices de Hadamard Consideraremos en nuestro caso que N= 2npara cierto n∈N. Así: Definición 4.3. La matriz de Hadamard HNde orden Nestá definida recursivamente por H2=Hy para N≥4: HN:=HN/2⊗H=1 √2"HN/2HN/2 HN/2−HN/2# También podemos utilizar H1=h1icomo base y de esta manera tendríamos: H2=1 √2"H1H1 H1−H1#=1 √2"1 1 1−1#,H4=1 √2"H2H2 H2−H2#=1 2       1111 1−1 1 −1 1 1 −1−1 1−1−1 1       . Esta definición recursiva nos muestra las características más importantes de este tipo de matrices. Por ejemplo, implica que en general; HN=1 √NA, donde Aes una matriz cuyas únicas entradas son +1 y−1. Por otro lado, este tipo de matrices solo existen si su orden es 1, 2 o un múltiplo de 4. Veamos por qué: Demostración. Dos filas cualquiera de una matriz de Hadamard de dimensión n×nson ortogonales. Para una matriz formada por 1y−1, significa que dos filas cualquiera difieren exactamente en la mitad de sus valores, lo cual es imposible cuando nes un número impar. Cuando n= 2(mod 4), dos filas que son ortogonales a una tercera fila no pueden ser ortogonales entre sí. Por tanto, juntando todo lo anterior: podemos afirmar que una matriz de Hadamard n×nsolo puede existir si n∈ {1,2,4k}, siendo k∈N. 22 4. Funciones binarias, bits cuánticos y factibilidad 4.4.3. Matrices U1(α) Definición 4.4. La matriz U1(α)realiza un control sobre una rotación en el ángulo especificado (α). Así, podemos definir este tipo de matrices de la siguiente manera: U1(α)(x) =    |0⟩,si x=|0⟩ eiα|1⟩,si x=|1⟩ Para el caso de un qubit de entrada de dimensión 2 (|x⟩=|x1x0⟩), esta matriz es de la forma: U1(α)(x) = "1 0 0eiα#(4.2) Por tanto, un control en este caso no es más que la identidad si la entrada es el qubit 0 o aplicar una rotación de ángulo αsi la entrada es el qubit 1. Capítulo 5 Transformada Cuántica de Fourier (QFT) Pasamos entonces a comentar los detalles detrás de la Transformada Cuántica de Fourier (QFT, siglas de Quantum Fourier Transform). En primer lugar, definiremos este tipo de matrices. Después, veremos su representación como un circuito cuántico de puertas lógicas y en la última sección de este capítulo explicaremos el principal uso que tiene dicha transformada en el algoritmo de Shor: calcular el periodo de una función. 5.1. Definición y principales propiedades Definición 5.1. Sea N= 2ny sea ω=e2πi/N , denominada habitualmente como la raíz principal N-ésima de la unidad. Entonces, la matriz QFT (FN) de dimensión N×Nes la matriz FN=1 √N             1 1 1 1 . . . 1 1ω ω2ω3. . . ωN−1 1ω2ω4ω6. . . ωN−2 1ω3ω6ω9. . . ωN−3 . . .. . ..... . . 1ωN−1ωN−2ωN−3. . . ω             ,(5.1) es decir, la matriz que tiene en el lugar (i, j)el valor FN[i, j] = ωij mod N . A continuación, mostraremos el enunciado y la demostración de una de las propiedades fundamentales de este tipo de matrices. Proposición 5.2. Las matrices QFT son unitarias. 23 24 5. Transformada Cuántica de Fourier (QFT) Demostración. Veamos que F F ∗=F∗F=I. Así, para un elemento Fij de F F ∗, tenemos que Fij =1 N N−1 X k=0 ωjkω−rk. En el caso en el que j=r(elementos de la diagonal) , tendremos que sus elementos (Fii) serán de la forma Fii =1 N N−1 X k=0 ωkiω−ki =1 N N−1 X k=0 ωki−ki =1 N N−1 X k=0 1 = 1 N·N= 1,∀i∈ {0, . . . , N −1} Por tanto, si a continuación conseguimos ver que el resto de elementos Fij = 0 con i=j habremos concluido. Entonces, puesto que si i=jentonces ω0=ωj−i= 1 es otra raíz N-ésima de la unidad. Por tanto Fij =1 N N−1 X k=0 ωk 0=1−ωN 0 1−ω0 = 0. 5.2. Transformación a circuito cuántico El objetivo principal de aplicar la Transformada Cuántica de Fourier es transformar la base computacional en la base de Fourier, entendiendo como base computacional aquella que permite formar los números en binario, mientras que la base de Fourier trabaja con estados en superposición. Para ello, es necesario convertir la expresión anterior 5.1 en un circuito cuántico, así que pasemos a ver dicho proceso. Antes de empezar, recordemos que N= 2nyω=e2πi/N . También, recordemos que el qubit |x⟩ se puede representar mediante |xn−1xn−2. . . x1x0⟩y que a su vez esta expresión es equivalente a|xn−1⟩⊗|xn−2⟩⊗ . . . |xn1⟩⊗|x0⟩. Recordemos también que todo número natural xpresenta su correspondiente expresión en número binario como x= n−1 X k=0 xk·2k(5.2) Partimos entonces de nuestra expresión que transforma el qubit |x⟩en 1 √NPN−1 y=0 ωxy|y⟩. Haciendo operaciones, tendremos que se da la siguiente igualdad (que demostraremos a continuación): 1 √N N−1 X y=0 ωxy|y⟩= (|0⟩+e2πix/2|1⟩) | {z } xn−1 ⊗(|0⟩+e2πix/22|1⟩) | {z } xn−2 ⊗···⊗(|0⟩+e2πix/2n|1⟩) | {z } x0 (5.3) 5.2. Transformación a circuito cuántico 25 Una vez llegado a este punto, lo que nos interesa es trabajar con las coordenadas binarias del número xy no con él directamente. Por tanto, aplicando 5.2, tendremos que la expresión 5.3 es equivalente a: (|0⟩+e2πi(x0 2+  x1+  2x2+  ...)|1⟩)⊗(|0⟩+e2πi(x0 4+x1 2+  x2+  ...)|1⟩)⊗···⊗(|0⟩+e2πi(x0 2n+x1 2n−1+x2 2n−2+···+xn−1 2)|1⟩). (5.4) Como podemos ver, el último qubit de la expresión anterior 5.4 presenta la interacción de todos los demás; ya que en el resto de casos podemos prescindir de los elementos de la forma e2mπi con m∈ {1, . . . , n}, ya que siempre van a ser 1, y por tanto solo tendremos en cuenta los elementos de la forma xk 2jcon k∈ {0, . . . , n −1}yj∈ {1, . . . , n}. Hemos visto como podemos escribir nuestra expresión de la Transformada Cuántica de Fourier en una expresión equivalente más manejable para poder representarla como un circuito de puertas cuánticas. Sin embargo, antes de visualizar y explicar como sería nuestro circuito; nos quedó pendiente demostrar el por qué se da la igualdad 5.3. Veámoslo: Demostración. Escribiendo ycomo su correspondiente forma en número binario, tenemos que (∗) = 1 √N N−1 X y=0 ωxy|y⟩=1 √N N−1 X y=0 e2πix Pn−1 k=0 yk·2k 2n|y⟩,(5.5) además (utilizando que ea+b=ea·eb) (∗) = 1 √N N−1 X y=0 e2πix Pn−1 k=0 yk·2k 2n|y⟩=1 √N N−1 X y=0 n−1 Y k=0 e2πix yk 2n−k|y⟩.(5.6) A continuación, recordemos que por definición: |y⟩=|yn−1yn−2. . . y0⟩. Por tanto N−1 X y=0 |y⟩= 1 X yn−1=0 1 X yn−2=0 ··· 1 X y0=0 |yn−1yn−2. . . y0⟩ De esta manera, el cambio que realizaremos a continuación es el siguiente (∗) = 1 X yn−1=0 ··· 1 X y0=0 1 √N n−1 Y k=0 e2πix yk 2n−k|yn−1. . . y0⟩= 1 X yn−2=0 ··· 1 X y0=0 (1 √N n−2 Y k=0 e2πix yk 2n−k|0yn−2. . . y0⟩+1 √N n−2 Y k=0 e2πix yk 2n−ke2πix/2|1yn−2. . . y0⟩). (5.7) La segunda igualdad de 5.7 se verifica porque estamos escribiendo esta suma de forma explícita, primero yn−1= 0 y luego yn−1= 1. Si nos fijamos también y recordando que |ab⟩=|a⟩⊗|b⟩, podemos extraer factor común. 32 5. Transformada Cuántica de Fourier (QFT) Una vez hecha esta medición para conseguir que el primer qubit colapse hacia donde nos interese (no utilizaremos el resultado de esta primera medición), aplicaremos a x0, x1yx2la QFT y una vez aplicada, medimos la salida generada por esta función. Es esta medición la que nos dará siempre un múltiplo de M p, y al obtener varios valores de estos múltiplos; podremos aplicar el máximo común divisor y despejando pcomo en la expresión 5.15, obtendremos el periodo de la función; que es lo que queríamos desde un principio. Capítulo 6 El algoritmo de Shor Llegados al último capítulo del documento y tras haber comentado todos los preliminares necesarios para poder entender el algoritmo de Shor, explicitaremos los pasos en los que se divide el algoritmo y también presentaremos algunos aspectos importantes del mismo: división en parte clásica y cuántica, y eficacia respecto a la computación actual. 6.1. Descripción del algoritmo: pasos y ejemplo de aplicación El algoritmo en sí se divide en dos partes: una parte cuántica, que es la que hemos visto sobre todo en este documento, que consiste en encontrar el periodo de una función, y después una parte clásica, que emplea el resultado del periodo calculado en la anterior fase para poder descomponer un número en factores primos, objetivo final de nuestro algoritmo. La parte cuántica es fundamental, ya que aunque se pueda determinar el periodo de una función mediante un método clásico; este sería mucho más costoso, porque habría que evaluar demasiados puntos para poder llevar a cabo dicho cálculo y convertiría el algoritmo en impráctico. Antes de empezar con la explicación, debemos conocer un par de conceptos que serán empleados en el algoritmo. El primero de ellos es la llamada raíz cuadrada no trivial módulo (N), que definiremos a continuación: Definición 6.1. Diremos que x∈Nes una raíz cuadrada no trivial módulo (N)si x2= 1(mod N)yx∈(2, N −2) Ejemplo 6.2. 5 es una raíz cuadrada no trivial módulo (8), ya que el resto de dividir 52= 25 entre 8 es 1 y además 5∈(2,6). El otro concepto que definiremos es el denominado orden de un natural módulo (N): 33 34 6. El algoritmo de Shor Definición 6.3. El orden de m∈Nmódulo (N) es el menor entero r∈Ztal que mr= 1(mod N). Ejemplo 6.4. 10 es el orden de 7 módulo (11); ya que 710 = 1(mod 11) y7j= 1(11) con j∈ {1,...,9}. Tras haber comentado estos dos conceptos, pasamos a ver los resultados en los que se sustenta fundamentalmente la teoría aplicada en nuestro algoritmo. Lema 6.5. Dado un número Nproducto de 2 números primos distintos pyq, encontrar la raíz cuadrada no trivial módulo (N) es equivalente a encontrar pyq. Demostración. Sea N=p·q. Recordemos que por definición, si xes una raíz cuadrada no trivial módulo (N) esto quiere decir que x2= 1(mod N)y además que x∈(2, N −2). Así: x2= 1(mod N) =⇒x2−1 = 0(mod N) =⇒(x−1)·(x+1) = 0(mod N) =⇒(x−1)·(x+1) = k·N. (6.1) Entonces, y recordando que N=p·q, nuestro objetivo será demostrar que pes un factor de (x−1) y que qlo es de (x+ 1) o bien que pes un factor de (x+ 1) yqlo es de (x−1). Para ver esto, utilizaremos que x∈(2, N −2) y así x−1< N yx+1 < N. Por tanto, ni x−1ni x+ 1 pueden ser múltiplos de N; ya que para ser múltiplos deben ser mayores o iguales que N. Como Nes producto de dos factores primos, la única opción posible es que uno de los factores, supongamos psea factor de (x−1) y que el otro qlo sea de (x+ 1). Por último, calculando el mcd de cada uno de los términos x+ 1 yx−1respecto de N, se tiene que mcd(x−1, N) = py que mcd(x+ 1, N) = q. De esta manera, si somos capaces de calcular la raíz cuadrada no trivial módulo (N), también podremos calcular los factores primos a emplear en la factorización utilizada en el algoritmo de Shor. ¿Cómo podemos encontrar dicha raíz cuadrada no trivial x? Para ello, debemos darnos cuenta que la siguiente función f(i) = xi(mod N)con i∈Nes periódica, donde su periodo es exactamente el orden de xmódulo (N), cuya definición vimos antes. De esta forma, la idea detrás del algoritmo se basa en escoger un valor dentro del intervalo (2, N −2), construimos la función f(i) = xi(mod N)y calculamos el periodo. Si el periodo obtenido es 2, ya hemos terminado; puesto que si el periodo de esa función es 2 hemos encontrado una raíz cuadrada no trivial, tal y como queríamos. 6.1. Descripción del algoritmo: pasos y ejemplo de aplicación 35 En general, realmente nos vale con encontrar cualquier periodo par, ya que si por ejemplo tenemos un periodo p= 6; es decir, nuestra función es x6(mod N), realmente esta expresión es equivalente a (x3)2(modN), y de esta forma nuestra raíz cuadrada no trivial sería x3. Por último, solo nos queda saber como debemos de escoger este valor dentro del intervalo (2, N−2) para poder obtener un periodo par. Pero, a priori esta decisión es azarosa, ¿cómo podemos asegurarnos de escoger un valor adecuado? Pues aquí es donde entra en juego el segundo resultado que utilizaremos, pero antes de verlo enunciaremos y demostraremos un lema que es necesario para poder demostrar nuestro resultado. Lema 6.6. Sea N∈Nimpar. Entonces, al menos la mitad de los elementos de (Z/NZ)×tiene orden par. Demostración. Supongamos que el orden rde xes impar. Entonces, (−x)r= (−1)rxr= (−1)r=−1(mod N). Por tanto, −xdebe tener orden 2r, que es par. De esta manera, al menos la mitad de los elementos de (Z/NZ)×tiene orden par. Ahora sí, pasamos enunciar y demostrar el segundo resultado fundamental para el algoritmo de Shor: Lema 6.7. Sea N∈Nimpar con descomposición en factores primos N=pα1 1···pαm m. Sea además un número al azar x∈(2, N −2) coprimo con Nyrsu orden. Entonces, la probabilidad de que al mismo tiempo rsea par y xr 2=−1(mod N)) es mayor o igual que 1−(1 2)m Demostración. Por el Teorema chinés de los restos, escoger un x∈(Z/NZ)×al azar es equivalente a escoger xi∈(Z/pei iZ)×para cada pide manera aleatoria, con i∈ {1, . . . , m}tal que xi=x(mod N). Sea ahora rel orden de xy sea riel orden de cada xi. En particular, xr/2= 1(mod N). De esta manera, lo que queremos ver es lo mostrado en el enunciado, que la probabilidad de que rsea par o que xr/2= 1(mod N)es mayor o igual que 1−(1 2)m. Como los primos p1, . . . , pmson distintos, se tiene que r= mcm (r1, r2, . . . , rm), donde mcm denota el mínimo común múltiplo. Supongamos que res impar. Entonces, esto solo sucederá si y solo si cada uno de los rison impares. Aplicando el Lema 6.6 anterior, sabemos que cada ries impar con una probabilidad de al menos 1 2. Entonces, res impar con una probabilidad de al menos (1 2)m. 36 6. El algoritmo de Shor Ahora, supongamos que res par. En este caso aún debemos comprobar si no se da el caso en el que xr/2=±1(mod N). Aplicando el Teorema chinés de los restos, esta situación solo pasa cuando xr/2=±1(mod pei i),∀pi. La probabilidad de escoger un xtal que cumpla alguno de los dos casos anteriores es 2·2−m= 2−m+1, y combinando ambas probabilidades obtenemos una probabilidad de éxito de al menos (1 −2−k)(1 −2−k+1)≥1−3·2−k. De esta manera, escogiendo pocos números podemos asegurar con una probabilidad elevada que alguno de ellos presentará un periodo par. Para ilustrar todo lo explicado en este capítulo hasta ahora, proponemos el siguiente ejemplo de aplicación del algoritmo de Shor: Ejemplo 6.8. Trataremos de descomponer el número 33 en factores primos. Para ello, seleccionamos en primer lugar un número al azar en el intervalo (2,31); por ejemplo, el número 10. Ahora, vemos que 102= 100 = 1(mod 33); y por tanto 10 es una raíz cuadrada no trivial módulo (33). Por lo tanto, aplicando el lema 6.5, tendremos que los factores primos de 33 serán el mcd(10 −1,33) = mcd(9,33) = 3 por un lado y el mcd(10 + 1,33) = mcd(11,33) = 11 por el otro. Por tanto, los factores primos de 33 son 3 y 11. Ya hemos visto todos los pasos necesarios para poder explicar de manera completa el algoritmo de Shor y un ejemplo sencillo de aplicación del mismo. Para terminar, en la última sección comentaremos brevemente cuestiones referidas a la eficiencia del algoritmo. 6.2. Principal aplicación y eficiencia del algoritmo 37 6.2. Principal aplicación y eficiencia del algoritmo Como vimos en el capítulo 3, el sistema RSA constituye una de las bases en las que se sustenta la criptografía actual, y vimos en su caso la importancia de los números primos. De esta manera, la principal aplicación del algoritmo de Shor no es otra que la criptografía. Este algoritmo es tan poderoso que si se consiguiera implementar en un ordenador cuántico podría terminar con la criptografía actual; debido a que la factorización de primos necesaria para poder determinar las claves pública y privada presenta orden de complejidad exponencial empleando la criptografía clásica; mientras que el orden de complejidad empleando el algoritmo de Shor y la computación cuántica es polinómico, siendo radicalmente superior en velocidad al caso clásico. De esta manera, este algoritmo conseguiría en muchísimo menos tiempo encontrar la factorización en primos de cada número resultado de la encriptación correspondiente, de tal manera que los sistemas actuales de contraseñas y seguridad serían muy vulnerables a esta solución. Este aumento de rapidez respecto al caso clásico se debe al empleo del algoritmo cuántico basado en los capítulos 4 y 5, que permiten encontrar el periodo de la función evaluada en muchos menos intentos que en el caso clásico, que al necesitar muchos más puntos dificulta y ralentiza la labor de dicho algoritmo. Pese al principal inconveniente que acabamos de comentar respecto a la brecha de seguridad que se puede generar si se consigue desarrollar este algoritmo; viene también acompañado de buenas noticias: el algoritmo de Shor puede suponer una nueva base para un sistema de encriptación cuántica mucho más seguro que el actual y que permita mantener la seguridad y la privacidad de los usuarios en la red en cualquiera de sus ámbitos. Aún nos queda mucho por aprender de la computación cuántica, pero estoy seguro de que de la misma forma en la que se ha descubierto y estudiado este algoritmo, aparecerán muchos más que nos permitirá a los usuarios navegar de la manera más cómoda y segura posible en la nueva era de la computación cuántica que se avecina en los próximos años. 38 6. El algoritmo de Shor Bibliografía [1] Lipton, Richard J. y Regan, Kenneth W.: Quantum Algorithms via Linear Algebra, The MIT Press, 1ªEd. (2014). [2] Scherer, Wolfgang: Mathematics of Quantum Computing: An Introduction, Springer, 1ªEd. (2019). [3] Shor, Peter W.: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM J. Comput.,26(5), 1997, 1484–1509. Referencias webgráficas: [4] Guillermo Alonso. Playlist de vídeos de los pasos necesarios para entender el algoritmo de Shor.https://www.youtube.com/playlist?list= PLhYoqmIacCv9IryISV7HhsXucZAUL2WGb. Visitada el 20 de julio del 2022. [5] José Vicente Álvarez Bravo. Definición de orden de complejidad de un algoritmo. Enlace: https://www2.infor.uva.es/~jvalvarez/docencia/tema5.pdf. Visitado el 2 de julio del 2022. [6] Tomás Domínguez. Matrices de Hadamard. Enlace: https://idus.us.es/bitstream/ handle/11441/43427/Matrices%20de%20Hadamard.pdf?sequence=1&isAllowed=y. Visitado el 15 de julio del 2022. [7] Fang Xi Lin. Shor’s Algorithm and the Quantum Fourier Transform. Enlace: https://cpb-us-w2.wpmucdn.com/u.osu.edu/dist/7/36891/files/2019/05/ Fangxi-LinMcGillShorsQuantumFactoringDiscreteLogAlgorithms.pdf. Visitado el 20 de julio de 2022. [8] Abhishek Yadav, traducido por Acervo Lima. Diferencias entre los diferentes órdenes de complejidad de un algoritmo. Enlace: https://es.acervolima.com/ diferencia-entre-big-oh-big-omega-y-big-theta/. Visitado el 2 de julio del 2022. 39 40 BIBLIOGRAFÍA [9] Varios autores. Definición del OR-exclusivo. Enlace: https://en.wikipedia.org/wiki/ Exclusive_or. Visitado el 2 de julio del 2022. [10] Varios autores. El algoritmo de Shor. Enlace: https://es.wikipedia.org/wiki/ Algoritmo_de_Shor. Visitado el 20 de julio del 2022.