El algoritmo de Shor es un algoritmo informático cuántico de tiempo polinomial para la factorización de enteros . [1] De manera informal, resuelve el siguiente problema: Dado un número entero, encuentra sus factores primos . Fue inventado en 1994 por el matemático estadounidense Peter Shor .
En una computadora cuántica, factorizar un número entero , El algoritmo de Shor se ejecuta en tiempo polinomial (el tiempo necesario es polinomio en , el tamaño del número entero dado como entrada). [2] Específicamente, toma puertas cuánticas de ordenutilizando la multiplicación rápida, [3] demostrando así que el problema de factorización de enteros puede resolverse de manera eficiente en una computadora cuántica y, en consecuencia, se encuentra en la clase de complejidad BQP . Esto es casi exponencialmente más rápido que el algoritmo de factorización clásico más eficiente conocido, el tamiz de campo numérico general , que funciona en tiempo sub-exponencial :. [4] La eficiencia del algoritmo de Shor se debe a la eficiencia de la transformada cuántica de Fourier y la exponenciación modular por cuadraturas repetidas . [5]
Si una computadora cuántica con una cantidad suficiente de qubits pudiera funcionar sin sucumbir al ruido cuántico y otros fenómenos de decoherencia cuántica , entonces el algoritmo de Shor podría usarse para romper los esquemas de criptografía de clave pública , como el esquema RSA ampliamente utilizado . RSA se basa en la suposición de que factorizar números enteros grandes es computacionalmente intratable. Hasta donde se sabe, esta suposición es válida para las computadoras clásicas (no cuánticas); no se conoce ningún algoritmo clásico que pueda factorizar números enteros en tiempo polinomial. Sin embargo, el algoritmo de Shor muestra que factorizar enteros es eficiente en una computadora cuántica ideal, por lo que puede ser factible derrotar a RSA construyendo una computadora cuántica grande. También fue un poderoso motivador para el diseño y la construcción de computadoras cuánticas y para el estudio de nuevos algoritmos de computadoras cuánticas. También ha facilitado la investigación sobre nuevos criptosistemas que son seguros de las computadoras cuánticas, denominados colectivamente criptografía post-cuántica .
En 2001, un grupo de IBM demostró el algoritmo de Shor , que tuvo en cuenta dentro , utilizando una implementación de RMN de una computadora cuántica conqubits. [6] Después de la implementación de IBM, dos grupos independientes implementaron el algoritmo de Shor usando qubits fotónicos , enfatizando que se observó un entrelazamiento de múltiples qubits al ejecutar los circuitos del algoritmo de Shor. [7] [8] En 2012, la factorización dese realizó con qubits de estado sólido. [9] Además, en 2012, la factorización dese logró, estableciendo el récord del mayor entero factorizado con el algoritmo de Shor. [10] En 2019 se intentó factorizar el número 35 utilizando el algoritmo de Shor en un IBM Q System One , pero el algoritmo falló debido a la acumulación de errores. [11] Sin embargo, las computadoras cuánticas han calculado números mucho mayores utilizando otros algoritmos, específicamente el recocido cuántico . [12]
Procedimiento
El problema que estamos tratando de resolver es, dado un número compuesto , para encontrar un divisor no trivial de (un divisor estrictamente entre y ). Antes de intentar encontrar tal divisor, se pueden usar algoritmos de prueba de primalidad relativamente rápidos para verificar que es de hecho compuesto.
Nosotros necesitamos ser extraño (de lo contrario es un divisor) y no debe ser ninguna potencia de un primo (de lo contrario, ese primo es un divisor), por lo que debemos verificar que no haya raíces enteras por .
Por tanto, podemos suponer que es el producto de dos enteros coprimos mayores que. Se deduce del teorema del resto chino que hay al menos cuatro raíces cuadradas distintas de modulo (ya que hay dos raíces para cada ecuación modular). El objetivo del algoritmo es encontrar una raíz cuadrada de modulo que es diferente de y , porque entonces
para un número entero distinto de cero que nos da los divisores no triviales y de . Esta idea es similar a otros algoritmos de factorización , como el tamiz cuadrático .
A su vez, encontrar tal se reduce a encontrar un elemento de período par con una cierta propiedad adicional (como se explica a continuación, se requiere que la condición del Paso 6 de la parte clásica no se mantenga). El algoritmo cuántico se utiliza para encontrar el período de elementos elegidos al azar., ya que este es un problema difícil en una computadora clásica.
El algoritmo de Shor consta de dos partes:
- Una reducción, que se puede hacer en una computadora clásica, del problema de factorización al problema de encontrar órdenes .
- Un algoritmo cuántico para resolver el problema de búsqueda de pedidos.
Parte clásica
- Elige un número aleatorio .
- Calcular , el máximo común divisor de y . Esto se puede hacer usando el algoritmo euclidiano .
- Si , entonces este número es un factor no trivial de, así que hemos terminado.
- De lo contrario, use la subrutina de búsqueda de períodos cuánticos (a continuación) para encontrar , que denota el período de la siguiente función:
- Si es impar, luego vuelva al paso 1.
- Si , luego vuelva al paso 1.
- De lo contrario, ambos y son factores no triviales de , así que hemos terminado.
Por ejemplo: dado , , y , tenemos , dónde y . Para que es un producto de dos primos distintos, y , El valor de es solo , que para es , y divide .
Parte cuántica: subrutina de búsqueda de períodos
Los circuitos cuánticos utilizados para este algoritmo están diseñados a medida para cada elección de y cada elección del azar utilizado en . Dado, encontrar tal que , lo que implica que . Los registros qubit de entrada y salida deben contener superposiciones de valores de a y también lo han hecho qubits cada uno. El uso de lo que podría parecer el doble de qubits de los necesarios garantiza que hay al menos diferentes valores de que producen lo mismo , incluso cuando el período enfoques .
Proceder de la siguiente:
- Inicializar los registros para
dónde denota el producto tensorial .
Este estado inicial es una superposición de estados, y se obtiene fácilmente generando qubits independientes , cada uno una superposición de y estados. Podemos lograr esto inicializando los qubits en la posición cero y luego aplicando la puerta Hadamard en paralelo a cada uno de los qubits, donde . - Construir como una función cuántica y aplicarlo al estado anterior, para obtener
- Aplicar la transformada cuántica de Fourier inversa al registro de entrada. Esta transformada (operando sobre una superposición de estados) usa un -ésima raíz de la unidad como para distribuir la amplitud de cualquier Estado igualmente entre todos de El estados, y hacerlo de una manera diferente para cada . Así obtenemos
- ser un -ésima raíz de la unidad,
- ser el periodo de ,
- ser el mas pequeño de los para cual (tenemos ), y
- escribir
- indexa estos , corriendo desde a , así que eso .
- Realice una medición. Obtenemos algún resultado en el registro de entrada y algún resultado en el registro de salida. Como es periódica, la probabilidad de medir algún estado es dado por
- Desde está cerca de un número entero , el valor conocido está cerca del valor desconocido . Realización de expansión de fracción continua [clásica] en nos permite encontrar aproximaciones de ella que satisfacen dos condiciones: Dadas estas múltiples condiciones (y asumiendo es irreductible ), es muy probable que sea el período apropiado , o al menos un factor de ello.
- .
- .
- Compruebe (clásicamente) si . Si es así, hemos terminado.
- De lo contrario, (clásicamente) obtenga más candidatos para mediante el uso de múltiplos de , o usando otro con cerca . Si algún candidato funciona, hemos terminado.
- De lo contrario, vuelva a intentarlo a partir del paso 1 de esta subrutina.
Explicación del algoritmo
El algoritmo se compone de dos partes. La primera parte del algoritmo convierte el problema de factorización en el problema de encontrar el período de una función y puede implementarse de manera clásica. La segunda parte encuentra el período utilizando la transformada cuántica de Fourier y es responsable de la aceleración cuántica.
Obtención de factores del período
Los enteros menores que y coprime conforman el grupo multiplicativo de números enteros módulo norte {\ Displaystyle N} , que es un grupo abeliano finito . El tamaño de este grupo viene dado por. Al final del paso 3, tenemos un número enteroen este grupo. Como el grupo es finito, debe tener un orden finito , que es el entero positivo más pequeño tal que
Por lo tanto, divide (también escrito ). Supongamos que podemos obtenery eso es parejo. (Si es impar, luego en el paso 5, tenemos que reiniciar el algoritmo con un número aleatorio diferente ) Ahora es una raíz cuadrada de modulo que es diferente de . Esto es porque es el orden de modulo , entonces , o bien el orden de en este grupo estaría . Si, luego en el paso 6, tenemos que reiniciar el algoritmo con un número aleatorio diferente .
Eventualmente, debemos alcanzar un de orden en tal que . Esto se debe a que tal es una raíz cuadrada de modulo otro que y , cuya existencia está garantizada por el teorema del resto chino, como no es un poder primordial.
Afirmamos que es un factor adecuado de , es decir, . De hecho, si, luego divide , así que eso , que va en contra de la construcción de . Si, por otro lado,, luego por la identidad de Bézout , hay enteros tal que
Multiplicar ambos lados por , obtenemos
Como divide , encontramos eso divide , así que eso , contradiciendo de nuevo la construcción de .
Por lo tanto, es el factor adecuado requerido de .
Encontrar el período
El algoritmo de búsqueda de períodos de Shor se basa en gran medida en la capacidad de una computadora cuántica para estar en muchos estados simultáneamente.
Los físicos llaman a este comportamiento una " superposición " de estados. Para calcular el período de una función, evaluamos la función en todos los puntos simultáneamente.
Sin embargo, la física cuántica no nos permite acceder a toda esta información directamente. Una medición arrojará solo uno de todos los valores posibles, destruyendo todos los demás. Si no fuera por el teorema de no clonación , primero podríamos medir sin medir , y luego hacer algunas copias del estado resultante (que es una superposición de estados que tienen el mismo ). Medición en estos estados proporcionaría diferentes valores que dan lo mismo , lo que lleva al período. Debido a que no podemos hacer copias exactas de un estado cuántico , este método no funciona. Por lo tanto, tenemos que transformar cuidadosamente la superposición a otro estado que devolverá la respuesta correcta con alta probabilidad. Esto se logra mediante la transformada cuántica de Fourier .
Por tanto, Shor tuvo que resolver tres problemas de "implementación". Todos ellos tuvieron que implementarse "rápido", lo que significa que se pueden implementar con una serie de puertas cuánticas que es polinomial en.
- Crea una superposición de estados. Esto se puede hacer aplicando puertas Hadamard a todos los qubits en el registro de entrada. Otro enfoque sería utilizar la transformada cuántica de Fourier (ver más abajo).
- Implementar la función como una transformación cuántica. Para lograr esto, Shor usó cuadratura repetida para su transformación de exponenciación modular. Es importante señalar que este paso es más difícil de implementar que la transformada cuántica de Fourier, ya que requiere qubits auxiliares y sustancialmente más puertas para lograrlo.
- Realice una transformada cuántica de Fourier. Mediante el uso de puertas de rotación controladas y puertas de Hadamard, Shor diseñó un circuito para la transformada cuántica de Fourier (con) que usa solo puertas. [14]
Después de todas estas transformaciones, una medición arrojará una aproximación al período . Para simplificar, suponga que hay un tal que es un entero. Entonces la probabilidad de medir es . Para ver esto, notamos que entonces
para todos los enteros . Por tanto, la suma cuyo cuadrado nos da la probabilidad de medir estarán , como toma aproximadamente valores y, por tanto, la probabilidad es . Existen posibles valores de tal que es un número entero, y también posibilidades para , entonces las probabilidades suman .
Nota: Otra forma de explicar el algoritmo de Shor es señalando que es solo el algoritmo de estimación de fase cuántica disfrazado.
El cuello de botella
El cuello de botella del tiempo de ejecución del algoritmo de Shor es la exponenciación modular cuántica , que es mucho más lenta que la transformada cuántica de Fourier y el pre y posprocesamiento clásico. Hay varios enfoques para construir y optimizar circuitos para potenciación modular. El enfoque más simple y (actualmente) más práctico es imitar circuitos aritméticos convencionales con puertas reversibles , comenzando con sumadores de acarreo de ondas . Conocer la base y el módulo de exponenciación facilita más optimizaciones. [15] [16] Los circuitos reversibles se utilizan normalmente en el orden de puertas para qubits. Las técnicas alternativas mejoran asintóticamente los recuentos de puertas mediante el uso de transformadas cuánticas de Fourier , pero no son competitivas con menos de 600 qubits debido a las altas constantes.
Logaritmos discretos
Dado un grupo Con orden y generador , supongamos que sabemos que , para algunos y deseamos calcular , que es el logaritmo discreto :. Considere el grupo abeliano, donde cada factor corresponde a la suma modular de valores. Ahora, considere la función
Esto nos da un problema de subgrupo oculto abeliano , comocorresponde a un homomorfismo de grupo . El kernel corresponde a los múltiplos de. Entonces, si podemos encontrar el kernel, podemos encontrar.
Ver también
- GEECM , un algoritmo de factorización que se dice que "a menudo es mucho más rápido que el de Shor" [17]
- Algoritmo de Grover
Referencias
- ^ Shor, PW (1994). "Algoritmos de computación cuántica: logaritmos discretos y factorización". Actas 35º Simposio Anual sobre Fundamentos de las Ciencias de la Computación . Computación IEEE. Soc. Presione: 124-134. doi : 10.1109 / sfcs.1994.365700 . ISBN 0818665807.
- ^ Véase también tiempo pseudopolinomial .
- ^ Beckman, David; Chari, Amalavoyal N .; Devabhaktuni, Srikrishna; Preskill, John (1996). "Redes eficientes para factorización cuántica" (PDF) . Physical Review A . 54 (2): 1034–1063. arXiv : quant-ph / 9602016 . Código Bibliográfico : 1996PhRvA..54.1034B . doi : 10.1103 / PhysRevA.54.1034 . PMID 9913575 .
- ^ "Tamiz de campo numérico" . wolfram.com . Consultado el 23 de octubre de 2015 .
- ^ Gidney, Craig. "Algoritmo de factorización cuántica de Shor" . Afirmaciones algorítmicas . Consultado el 28 de noviembre de 2020 .
- ^ Vandersypen, Lieven MK; Steffen, Matthias; Breyta, Gregory; Yannoni, Costantino S .; Sherwood, Mark H. y Chuang, Isaac L. (2001), "Realización experimental del algoritmo de factorización cuántica de Shor mediante resonancia magnética nuclear" (PDF) , Nature , 414 (6866): 883–887, arXiv : quant-ph / 0112176 , Código Bib : 2001Natur.414..883V , CiteSeerX 10.1.1.251.8799 , doi : 10.1038 / 414883a , PMID 11780055
- ^ Lu, Chao-Yang; Browne, Daniel E .; Yang, Tao & Pan, Jian-Wei (2007), "Demostración de una versión compilada del algoritmo de factorización cuántica de Shor utilizando qubits fotónicos" (PDF) , Physical Review Letters , 99 (25): 250504, arXiv : 0705.1684 , Bibcode : 2007PhRvL ..99y0504L , doi : 10.1103 / PhysRevLett.99.250504 , PMID 18233508
- ^ Lanyon, BP; Weinhold, TJ; Langford, NK; Barbieri, M .; James, DFV; Gilchrist, A. & White, AG (2007), "Demostración experimental de una versión compilada del algoritmo de Shor con entrelazamiento cuántico" (PDF) , Physical Review Letters , 99 (25): 250505, arXiv : 0705.1398 , Bibcode : 2007PhRvL .. 99y0505L , doi : 10.1103 / PhysRevLett.99.250505 , hdl : 10072/21608 , PMID 18233509
- ^ Lucero, Erik; Barends, Rami; Chen, Yu; Kelly, Julian; Mariantoni, Matteo; Megrant, Anthony; O'Malley, Peter; Se hundió, Daniel; Vainsencher, Amit; Wenner, James; White, Ted; Yin, Yi; Cleland, Andrew N .; Martinis, John M. (2012). "Cálculo de factores primos con un procesador cuántico de fase qubit de Josephson". Física de la naturaleza . 8 (10): 719. arXiv : 1202.5707 . Código Bibliográfico : 2012NatPh ... 8..719L . doi : 10.1038 / nphys2385 .
- ^ Martín-López, Enrique; Martín-López, Enrique; Laing, Anthony; Lawson, Thomas; Álvarez, Roberto; Zhou, Xiao-Qi; O'Brien, Jeremy L. (12 de octubre de 2012). "Realización experimental del algoritmo de factorización cuántica de Shor utilizando reciclaje de qubit". Nature Photonics . 6 (11): 773–776. arXiv : 1111.4147 . Código Bibliográfico : 2012NaPho ... 6..773M . doi : 10.1038 / nphoton.2012.259 .
- ^ Amico, Mirko; Saleem, Zain H .; Kumph, Muir (8 de julio de 2019). "Un estudio experimental del algoritmo de factorización de Shor en IBM Q" . Physical Review A . 100 (1): 012305. arXiv : 1903.00768 . doi : 10.1103 / PhysRevA.100.012305 . ISSN 2469-9926 .
- ^ Jiang, Shuxian; Britt, Keith A .; McCaskey, Alexander J .; Humilde, Travis S .; Kais, Sabre (5 de diciembre de 2018). "Recocido cuántico para la factorización prima" . Informes científicos . 8 (1): 17667. doi : 10.1038 / s41598-018-36058-z . ISSN 2045-2322 . PMC 6281593 . PMID 30518780 .
- ^ Autores de Qiskit. "Libro de texto de Qiskit: estimación de fase cuántica" . IBM . Consultado el 7 de noviembre de 2020 .
- ^ Shor 1999 , p. 14
- ^ Markov, Igor L .; Saeedi, Mehdi (2012). "Circuitos cuánticos optimizados para constantes para multiplicación y exponenciación modular". Computación e información cuántica . 12 (5–6): 361–394. arXiv : 1202.6614 . Código bibliográfico : 2012arXiv1202.6614M . doi : 10.26421 / QIC12.5-6-1 .
- ^ Markov, Igor L .; Saeedi, Mehdi (2013). "Factorización de números cuánticos más rápida a través de la síntesis de circuitos". Phys. Rev. A . 87 (1): 012310. arXiv : 1301.3210 . Código Bibliográfico : 2013PhRvA..87a2310M . doi : 10.1103 / PhysRevA.87.012310 .
- ^ Bernstein, Daniel J .; Heninger, Nadia ; Lou, Paul; Valenta, Luke (2017). "Post-Quantum RSA" (PDF) . Taller Internacional de Criptografía Post-Cuántica . Apuntes de conferencias en informática. 10346 : 311–329. doi : 10.1007 / 978-3-319-59879-6_18 . ISBN 978-3-319-59878-9. Archivado (PDF) desde el original el 20 de abril de 2017.
Otras lecturas
- Nielsen, Michael A. y Chuang, Isaac L. (2010), Computación cuántica e información cuántica, Edición del décimo aniversario , Cambridge University Press, ISBN 9781107002173.
- Phillip Kaye, Raymond Laflamme, Michele Mosca, Introducción a la computación cuántica , Oxford University Press, 2007, ISBN 0-19-857049-X
- "Explicación para el hombre de la calle" de Scott Aaronson , " aprobada " por Peter Shor. (Shor escribió: "¡Gran artículo, Scott! Ese es el mejor trabajo de explicar la computación cuántica al hombre de la calle que he visto"). En uno de los comentarios se presentó una metáfora alternativa para el QFT . Scott Aaronson sugiere las siguientes 12 referencias como lectura adicional (de "los 10 10 5000 tutoriales de algoritmos cuánticos que ya están en la web"):
- Shor, Peter W. (1997), "Algoritmos polinomiales de tiempo para factorización prima y logaritmos discretos en una computadora cuántica", SIAM J. Comput. , 26 (5): 1484–1509, arXiv : quant-ph / 9508027v2 , Bibcode : 1999SIAMR..41..303S , doi : 10.1137 / S0036144598347011. Versión revisada del artículo original de Peter Shor ("28 páginas, LaTeX. Esta es una versión ampliada de un artículo que apareció en las Actas del 35 ° Simposio Anual sobre Fundamentos de la Ciencia de la Computación, Santa Fe, NM, 20 de noviembre al 22 de 1994. Revisiones menores hechas en enero de 1996 ").
- Computación cuántica y algoritmo de Shor , página de algoritmos cuánticos de Matthew Hayward , 2005-02-17, imsa.edu, versión LaTeX2HTML del documento LaTeX original , también disponible como documento PDF o postscript .
- Computación cuántica y algoritmo de factorización de Shor , Ronald de Wolf, CWI y Universidad de Amsterdam, 12 de enero de 1999, documento posdata de 9 páginas.
- Algoritmo de factorización de Shor , notas de la conferencia 9 de Berkeley CS 294-2, de fecha 4 de octubre de 2004, documento posdata de 7 páginas.
- Capítulo 6 Computación cuántica , documento postscript de 91 páginas, Caltech, Preskill, PH229.
- Computación cuántica: un tutorial de Samuel L. Braunstein .
- Los estados cuánticos del algoritmo de Shor , por Neal Young, última modificación: martes 21 de mayo 11:47:38 1996.
- III. Rompiendo el cifrado RSA con una computadora cuántica: algoritmo de factorización de Shor , notas de la conferencia sobre computación cuántica, Universidad de Cornell, Física 481–681, CS 483; Primavera de 2006 por N. David Mermin. Última revisión del 28 de marzo de 2006, documento PDF de 30 páginas.
- Lavor, C .; Manssur, LRU; Portugal, R. (2003). "Algoritmo de Shor para factorizar enteros grandes". arXiv : quant-ph / 0303175 .
- Lomonaco, Jr. (2000). "Algoritmo de factorización cuántica de Shor". arXiv : quant-ph / 0010034 .Este artículo es una versión escrita de una conferencia de una hora sobre el algoritmo de factorización cuántica de Peter Shor. 22 páginas.
- Capítulo 20 Computación cuántica , a partir de la complejidad computacional: un enfoque moderno , borrador de un libro: con fecha de enero de 2007, Sanjeev Arora y Boaz Barak, Universidad de Princeton. Publicado como Capítulo 10 Computación cuántica de Sanjeev Arora, Boaz Barak, "Computational Complexity: A Modern Approach", Cambridge University Press, 2009, ISBN 978-0-521-42426-4
- Un paso hacia la computación cuántica: entrelazando 10 mil millones de partículas , de "Discover Magazine", con fecha del 19 de enero de 2011.
- Josef Gruska - Desafíos de Computación Cuántica también en Matemáticas ilimitados: 2001 y más allá , Editores Björn Engquist, Wilfried Schmid, Springer, 2001, ISBN 978-3-540-66913-5
enlaces externos
- Versión 1.0.0 de libquantum : contiene una implementación en lenguaje C del algoritmo de Shor con su biblioteca de computadora cuántica simulada, pero la variable de ancho en shor.c debe establecerse en 1 para mejorar la complejidad del tiempo de ejecución.
- PBS Infinite Series creó dos videos que explican las matemáticas detrás del algoritmo de Shor, " Cómo romper la criptografía " y " Hackear a velocidad cuántica con el algoritmo de Shor ".