algoritmo de shor

Algoritmo cuántico para factorización de números enteros

El algoritmo de Shor es un algoritmo cuántico para encontrar los factores primos de un número entero. Fue desarrollado en 1994 por el matemático estadounidense Peter Shor . ^{[1] [2]} Es uno de los pocos algoritmos cuánticos conocidos con aplicaciones potenciales convincentes y una fuerte evidencia de aceleración superpolinomial en comparación con los algoritmos clásicos (es decir, no cuánticos) más conocidos. ^[3] Por otro lado, factorizar números de importancia práctica requiere muchos más qubits de los disponibles en el futuro próximo. ^[4] Otra preocupación es que el ruido en los circuitos cuánticos pueda socavar los resultados, ^[5] requiriendo qubits adicionales para la corrección de errores cuánticos .

Shor propuso múltiples algoritmos similares para resolver el problema de factorización, el problema de logaritmos discretos y el problema de búsqueda de períodos. El "algoritmo de Shor" generalmente se refiere a su algoritmo de resolución de factorización, pero también puede referirse a cada uno de los tres. El algoritmo de logaritmo discreto y el algoritmo de factorización son instancias del algoritmo de búsqueda de períodos, y los tres son instancias del problema de subgrupos ocultos .

En una computadora cuántica, para factorizar un número entero , el algoritmo de Shor se ejecuta en tiempo polinómico , lo que significa que el tiempo necesario es polinómico en , el tamaño del número entero dado como entrada. ^[6] Específicamente, se necesitan puertas cuánticas de orden usando multiplicación rápida, ^[7] o incluso utilizando el algoritmo de multiplicación asintóticamente más rápido conocido actualmente debido a Harvey y Van Der Hoven, ^[8] demostrando así que el problema de factorización de enteros se puede resolver eficientemente. en una computadora cuántica y, por lo tanto, pertenece a la clase de complejidad BQP . Esto es significativamente 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 subexponencial : . ^[9] ${\displaystyle N}$ ${\displaystyle \log N}$ ${\displaystyle O\!\left((\log N)^{2}(\log \log N)(\log \log \log N)\right)}$ ${\displaystyle O\!\left((\log N)^{2}(\log \log N)\right)}$ ${\displaystyle O\!\left(e^{1.9(\log N)^{1/3}(\log \log N)^{2/3}}\right)}$

Viabilidad e impacto

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 esquemas de criptografía de clave pública , como

• El esquema RSA
• El intercambio de claves de Finite Field Diffie-Hellman
• El intercambio de claves de la curva elíptica Diffie-Hellman ^[10]

RSA se basa en el supuesto de que factorizar números enteros grandes es computacionalmente intratable. Hasta donde se sabe, esta suposición es válida para computadoras clásicas (no cuánticas); No se conoce ningún algoritmo clásico que pueda factorizar números enteros en tiempo polinómico. Sin embargo, el algoritmo de Shor muestra que factorizar números enteros es eficiente en una computadora cuántica ideal, por lo que puede ser factible derrotar a RSA mediante la construcción de 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 computación cuántica. También ha facilitado la investigación sobre nuevos criptosistemas que sean seguros frente a las computadoras cuánticas, denominados colectivamente criptografía poscuántica .

Implementación física

Dadas las altas tasas de error de las computadoras cuánticas contemporáneas y la existencia de muy pocos qubits para utilizar la corrección de errores cuánticos , las demostraciones de laboratorio obtienen resultados correctos solo en una fracción de los intentos.

En 2001, el algoritmo de Shor fue demostrado por un grupo de IBM , que tuvo en cuenta , utilizando una implementación de RMN de una computadora cuántica con siete qubits. ^[11] Después de la implementación de IBM, dos grupos independientes implementaron el algoritmo de Shor utilizando qubits fotónicos , enfatizando que se observó un entrelazamiento de múltiples qubits al ejecutar los circuitos del algoritmo de Shor. ^{[12] [13]} En 2012, la factorización de se realizó con qubits de estado sólido. ^[14] Posteriormente, en 2012, se logró la factorización de. ^[15] En 2019, se intentó factorizar el número utilizando el algoritmo de Shor en un IBM Q System One , pero el algoritmo falló debido a la acumulación de errores. ^[16] Aunque las computadoras cuánticas han factorizado números más grandes utilizando otros algoritmos, ^[17] estos algoritmos son similares a la verificación clásica de factores por fuerza bruta, por lo que, a diferencia del algoritmo de Shor, no se espera que nunca funcionen mejor que los algoritmos de factorización clásicos. ^[18] ${\displaystyle 15}$ ${\displaystyle 3\times 5}$ ${\displaystyle 15}$ ${\displaystyle 21}$ ${\displaystyle 35}$

Los análisis teóricos del algoritmo de Shor suponen una computadora cuántica libre de ruido y errores. Sin embargo, las implementaciones prácticas a corto plazo tendrán que hacer frente a estos fenómenos no deseados (cuando haya más qubits disponibles, la corrección de errores cuánticos puede ayudar). En 2023, Jin-Yi Cai estudió el impacto del ruido y concluyó que existe una clase especial de números (productos de dos primos de A073024, que son densos en los semiprimos), el algoritmo de Shor no puede factorizar dichos números en presencia de ruido. ^[5] Por lo tanto, será necesaria la corrección de errores para poder factorizar todos los números con el algoritmo de Shor.

Algoritmo

El problema que intentamos resolver es: dado un número compuesto impar , encontrar sus factores enteros ${\displaystyle N}$ .

Para lograrlo, el algoritmo de Shor consta de dos partes:

1. Una reducción clásica del problema de factoring al problema de encontrar orden . Esta reducción es similar a la utilizada para otros algoritmos de factorización , como la criba cuadrática .
2. Un algoritmo cuántico para resolver el problema de búsqueda de orden.

Reducción clásica

Un algoritmo de factorización completo es posible si somos capaces de factorizar eficientemente arbitrario en solo dos números enteros mayores que 1, ya que si alguno de ellos o no es primo, entonces el algoritmo de factorización puede, a su vez, ejecutarse en ellos hasta que solo queden primos. ${\displaystyle N}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle q}$

Una observación básica es que, utilizando el algoritmo de Euclides , siempre podemos calcular el MCD entre dos números enteros de manera eficiente. En particular, esto significa que podemos comprobar eficientemente si es par, en cuyo caso 2 es trivialmente un factor. Supongamos entonces que esto es extraño para el resto de esta discusión. Posteriormente, podemos utilizar algoritmos clásicos eficientes para comprobar si es una potencia prima . ^[19] Para potencias primas, existen algoritmos de factorización clásicos eficientes, ^[20] por lo tanto, el resto del algoritmo cuántico puede asumir que no es una potencia prima. ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle N}$

Si esos casos fáciles no producen un factor no trivial de , el algoritmo procede a manejar el caso restante. Elegimos un número entero aleatorio . Se puede encontrar un posible divisor no trivial de mediante computación , lo que se puede hacer de manera clásica y eficiente utilizando el algoritmo euclidiano . Si esto produce un factor no trivial (es decir , ), el algoritmo finaliza y el otro factor no trivial es . Si no se identificó un factor no trivial, entonces eso significa que y la elección de son coprimos . Aquí, el algoritmo ejecuta la subrutina cuántica, que devolverá el orden de , es decir ${\displaystyle N}$ ${\displaystyle 2\leq a<N}$ ${\displaystyle N}$ ${\displaystyle \gcd(a,N)}$ ${\displaystyle \gcd(a,N)\neq 1}$ ${\textstyle {\frac {N}{\gcd(a,N)}}}$ ${\displaystyle N}$ ${\displaystyle a}$ ${\displaystyle r}$ ${\displaystyle a}$

${\displaystyle a^{r}\equiv 1{\bmod {N}}.}$

La subrutina cuántica requiere que y sean coprimos, ^[2] lo cual es cierto ya que en este punto del algoritmo no se produjo un factor no trivial de . Se puede ver en la congruencia que divide , escrita . Esto se puede factorizar usando diferencia de cuadrados : ${\displaystyle a}$ ${\displaystyle N}$ ${\displaystyle \gcd(a,N)}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle a^{r}-1}$ ${\displaystyle N\mid a^{r}-1}$

$${\displaystyle N\mid (a^{r/2}-1)(a^{r/2}+1)}$$

${\displaystyle r}$ ${\displaystyle a^{r/2}}$ ${\displaystyle a}$ ${\displaystyle r}$ ${\displaystyle N\mid a^{r/2}-1}$ ${\displaystyle a^{r/2}\equiv 1{\bmod {N}}}$ ${\textstyle {\frac {r}{2}}}$ ${\displaystyle a}$ ${\displaystyle r}$ ${\displaystyle N\mid a^{r/2}+1}$ ${\displaystyle N\mid a^{r/2}+1}$ ${\displaystyle N}$

$${\displaystyle d=\gcd(N,a^{r/2}-1)}$$

${\displaystyle d=1}$ ${\displaystyle N\mid a^{r/2}+1}$ ${\displaystyle N}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle N}$ ${\textstyle {\frac {N}{d}}}$ ${\displaystyle \gcd(N,a^{r/2}+1)}$ ${\displaystyle \gcd(N,a^{r/2}-1)}$ ${\displaystyle N\mid a^{r/2}+1}$

El algoritmo se reformula brevemente de la siguiente manera: sea impar y no una potencia primaria. Queremos generar dos factores no triviales de . ${\displaystyle N}$ ${\displaystyle N}$

1. Elija un número aleatorio . ${\displaystyle 1<a<N}$
2. Calcular , el máximo común divisor de y . ${\displaystyle K=\gcd(a,N)}$ ${\displaystyle a}$ ${\displaystyle N}$
3. Si , entonces es un factor no trivial de , siendo el otro factor y listo. ${\displaystyle K\neq 1}$ ${\displaystyle K}$ ${\displaystyle N}$ ${\textstyle {\frac {N}{K}}}$
4. De lo contrario, utilice la subrutina cuántica para encontrar el orden de . ${\displaystyle r}$ ${\displaystyle a}$
5. Si es impar, regrese al paso 1. ${\displaystyle r}$
6. Calcular . Si no es trivial, el otro factor es y terminamos. De lo contrario, regrese al paso 1. ${\displaystyle g=\gcd(N,a^{r/2}+1)}$ ${\displaystyle g}$ ${\textstyle {\frac {N}{g}}}$

Se ha demostrado que es probable que esto tenga éxito después de algunas ejecuciones. ^[2] En la práctica, una sola llamada a la subrutina de búsqueda de orden cuántico es suficiente para factorizar completamente con una probabilidad de éxito muy alta si se utiliza una reducción más avanzada. ^[21] ${\displaystyle N}$

Subrutina de búsqueda de orden cuántico

El objetivo de la subrutina cuántica del algoritmo de Shor es, dados enteros coprimos y , encontrar el orden del módulo , que es el entero positivo más pequeño tal que . Para lograrlo, el algoritmo de Shor utiliza un circuito cuántico que involucra dos registros. El segundo registro utiliza qubits, donde es el número entero más pequeño tal que . El tamaño del primer registro determina la precisión de la aproximación que produce el circuito. Se puede demostrar que el uso de qubits proporciona suficiente precisión para encontrar . El circuito cuántico exacto depende de los parámetros y que definen el problema. La siguiente descripción del algoritmo utiliza la notación bra-ket para indicar estados cuánticos y el producto tensorial , en lugar de OR lógico o XOR lógico . ${\displaystyle N}$ ${\displaystyle 1<a<N}$ ${\displaystyle r}$ ${\displaystyle a}$ ${\displaystyle N}$ ${\displaystyle a^{r}\equiv 1{\pmod {N}}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle N\leq 2^{n}}$ ${\displaystyle 2n+1}$ ${\displaystyle r}$ ${\displaystyle a}$ ${\displaystyle N}$ ${\displaystyle \otimes }$

El algoritmo consta de dos pasos principales:

1. Utilice la estimación de fase cuántica con unidad que represente la operación de multiplicar por (módulo ) y el estado de entrada (donde el segundo registro está hecho de qubits). Los valores propios de esto codifican información sobre el período y se puede considerar que se pueden escribir como una suma de sus vectores propios. Gracias a estas propiedades, la etapa de estimación de fase cuántica da como salida un número entero aleatorio de la forma aleatorio . ${\displaystyle U}$ ${\displaystyle a}$ ${\displaystyle N}$ ${\displaystyle |0\rangle ^{\otimes 2n+1}\otimes |1\rangle }$ ${\displaystyle |1\rangle }$ ${\displaystyle n}$ ${\displaystyle U}$ ${\displaystyle |1\rangle }$ ${\displaystyle {\frac {j}{r}}2^{2n+1}}$ ${\displaystyle j=0,1,...,r-1}$
2. Utilice el algoritmo de fracciones continuas para extraer el período de los resultados de medición obtenidos en la etapa anterior. Este es un procedimiento para posprocesar (con una computadora clásica) los datos de medición obtenidos al medir los estados cuánticos de salida y recuperar el período. ${\displaystyle r}$

La conexión con la estimación de la fase cuántica no se discutió en la formulación original del algoritmo de Shor, ^[2] pero fue propuesta más tarde por Kitaev. ^[22]

Estimación de fase cuántica

Subrutina cuántica en el algoritmo de Shor

En general, el algoritmo de estimación de fase cuántica , para cualquier estado unitario y propio tal que , envía estados de entrada a estados de salida cercanos a , donde es un número entero cercano a . En otras palabras, envía cada estado propio de a un estado cercano al valor propio asociado. A los efectos de encontrar el orden cuántico, empleamos esta estrategia utilizando el unitario definido por la acción ${\displaystyle U}$ ${\displaystyle |\psi \rangle }$ ${\displaystyle U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle }$ ${\displaystyle |0\rangle |\psi \rangle }$ ${\displaystyle |\phi \rangle |\psi \rangle }$ ${\displaystyle \phi }$ ${\displaystyle 2^{2n+1}\theta }$ ${\displaystyle |\psi _{j}\rangle }$ ${\displaystyle U}$

$${\displaystyle U|k\rangle ={\begin{cases}|ak{\pmod {N}}\rangle &0\leq k<N,\\|k\rangle &N\leq k<2^{n}.\end{cases}}}$$

exponenciación modularraíces ${\displaystyle U}$ ${\displaystyle |k\rangle }$ ${\displaystyle N\leq k<2^{n}}$ ${\displaystyle U}$ ${\displaystyle U^{2^{j}}}$ ${\displaystyle U^{r}=I}$ ${\displaystyle r}$ ${\displaystyle \omega _{r}^{k}=e^{2\pi ik/r}}$ ${\displaystyle \omega _{r}^{k}}$ ${\textstyle |\psi _{j}\rangle =r^{-1/2}\sum _{k=0}^{r-1}\omega _{r}^{-kj}|a^{k}\rangle }$

$${\displaystyle {\begin{aligned}{\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\psi _{j}\rangle &={\frac {1}{r}}\sum _{j=0}^{r-1}\sum _{k=0}^{r-1}\omega _{r}^{jk}|a^{k}\rangle \\&=|1\rangle +{\frac {1}{r}}\sum _{k=1}^{r-1}\left(\sum _{j=0}^{r-1}\omega _{r}^{jk}\right)|a^{k}\rangle =|1\rangle ,\end{aligned}}}$$

donde la última identidad se deriva de la fórmula de la serie geométrica , lo que implica . ${\textstyle \sum _{j=0}^{r-1}\omega _{r}^{jk}=0}$

El uso de la estimación de fase cuántica en un estado de entrada devolvería el número entero con alta probabilidad. Más precisamente, el circuito de estimación de fase cuántica envía a tal que la distribución de probabilidad resultante tiene un máximo alrededor de , con . Esta probabilidad se puede acercar arbitrariamente a 1 utilizando qubits adicionales. ${\displaystyle |0\rangle ^{\otimes 2n+1}|\psi _{j}\rangle }$ ${\displaystyle 2^{2n+1}j/r}$ ${\displaystyle |0\rangle ^{\otimes 2n+1}|\psi _{j}\rangle }$ ${\displaystyle |\phi _{j}\rangle |\psi _{j}\rangle }$ ${\displaystyle p_{k}\equiv |\langle k|\phi _{j}\rangle |^{2}}$ ${\textstyle k=2^{2n+1}j/r}$ ${\textstyle p_{2^{2n+1}j/r}\geq {\frac {4}{\pi ^{2}}}\approx 0.4053}$

Aplicando el razonamiento anterior a la entrada , la estimación de fase cuántica da como resultado la evolución ${\displaystyle |0\rangle ^{\otimes 2n+1}|1\rangle }$

$${\displaystyle |0\rangle ^{\otimes 2n}|1\rangle ={\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|0\rangle ^{\otimes 2n}|\psi _{j}\rangle \to {\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\phi _{j}\rangle |\psi _{j}\rangle .}$$

${\displaystyle 1/r}$ ${\displaystyle |\phi _{j}\rangle }$ ${\displaystyle 2^{2n+1}j/r}$ ${\displaystyle 2^{2n+1}}$ ${\displaystyle j/r}$

Algoritmo de fracción continua para recuperar el período.

Luego, aplicamos el algoritmo de fracciones continuas para encontrar números enteros y , donde se obtiene la mejor aproximación fraccionaria para la aproximación medida desde el circuito, para y coprimo y . El número de qubits en el primer registro, que determina la precisión de la aproximación, garantiza que ${\textstyle b}$ ${\textstyle c}$ ${\textstyle {\frac {b}{c}}}$ ${\textstyle b,c<N}$ ${\textstyle b}$ ${\textstyle c}$ ${\displaystyle 2n+1}$

$${\displaystyle {\frac {b}{c}}={\frac {j}{r}}}$$

^{[ cita necesaria ]} ${\textstyle |\phi _{j}\rangle }$ ${\textstyle b}$ ${\textstyle c}$ ${\textstyle j}$ ${\textstyle r}$ ${\textstyle b}$ ${\textstyle c}$ ${\textstyle j}$ ${\textstyle r}$

$${\displaystyle {\frac {b_{1}}{c_{1}}}_{\textstyle ,}\;{\frac {b_{2}}{c_{2}}}_{\textstyle ,}\ldots {\vphantom {\frac {b_{1}}{c_{1}}}}_{\textstyle ,}\;{\frac {b_{s}}{c_{s}}}}$$

mínimo común múltiplo ${\textstyle s}$ ${\textstyle c_{k}}$ ${\textstyle j}$ ${\textstyle r}$ ${\textstyle c_{k}}$

$${\displaystyle \mathrm {lcm} (c_{1},c_{2},\ldots ,c_{s})}$$

${\textstyle r}$ ${\textstyle a}$

Elegir el tamaño del primer registro

La estimación de fase requiere elegir el tamaño del primer registro para determinar la precisión del algoritmo, y para la subrutina cuántica del algoritmo de Shor, los qubits son suficientes para garantizar que la cadena de bits óptima medida a partir de la estimación de fase (es decir, dónde está la aproximación más precisa de la estimación fase a fase) permitirá recuperar el valor real de. ${\displaystyle 2n+1}$ ${\displaystyle |k\rangle }$ ${\textstyle k/2^{2n+1}}$ ${\displaystyle r}$

Cada medición anterior en el algoritmo de Shor representa una superposición de números enteros que se aproximan . Representemos el número entero más óptimo en . El siguiente teorema garantiza que el algoritmo de fracciones continuas se recuperará de : ${\displaystyle |\phi _{j}\rangle }$ ${\displaystyle 2^{2n+1}j/r}$ ${\displaystyle |k\rangle }$ ${\displaystyle |\phi _{j}\rangle }$ ${\displaystyle j/r}$ ${\displaystyle k/2^{2{n}+1}}$

Teorema  :  si y son números enteros de bits, y ${\displaystyle j}$ ${\displaystyle r}$ ${\displaystyle n}$

$${\displaystyle \left\vert {\frac {j}{r}}-\phi \right\vert \leq {\frac {1}{2r^{2}}}}$$

entonces el algoritmo de fracciones continuas que se ejecute recuperará tanto como . ${\displaystyle \phi }$ ${\textstyle {\frac {j}{\gcd(j,\;r)}}}$ ${\textstyle {\frac {r}{\gcd(j,\;r)}}}$

^[3] Como es la cadena de bits óptima a partir de la estimación de fase, tiene una precisión de bits. De este modo, ${\displaystyle k}$ ${\displaystyle k/2^{2{n}+1}}$ ${\displaystyle j/r}$ ${\displaystyle 2n+1}$

$${\displaystyle \left\vert {\frac {j}{r}}-{\frac {k}{2^{2n+1}}}\right\vert \leq {\frac {1}{2^{2{n}+1}}}\leq {\frac {1}{2N^{2}}}\leq {\frac {1}{2r^{2}}}}$$

${\displaystyle j}$ ${\displaystyle r}$

El cuello de botella

El cuello de botella en 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/postprocesamiento clásico. Existen varios enfoques para construir y optimizar circuitos para exponenciació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 ondulación . Conocer la base y el módulo de exponenciación facilita mayores optimizaciones. ^{[23] [24]} Los circuitos reversibles normalmente se utilizan en el orden de puertas para qubits. Las técnicas alternativas mejoran asintóticamente el número de puertas mediante el uso de transformadas cuánticas de Fourier , pero no son competitivas con menos de 600 qubits debido a las constantes elevadas. ${\displaystyle n^{3}}$ ${\displaystyle n}$

Hallazgo de períodos y logaritmos discretos.

Los algoritmos de Shor para el registro discreto y los problemas de búsqueda de orden son ejemplos de un algoritmo que resuelve el problema de búsqueda de período. ^{[ cita necesaria ]} . Los tres son ejemplos del problema de los subgrupos ocultos .

Algoritmo de Shor para logaritmos discretos

Dado un grupo con orden y generador , supongamos que sabemos que , para algunos , y queremos calcular , cuál es el logaritmo discreto : . Considere el grupo abeliano , donde cada factor corresponde a la suma modular de valores. Consideremos ahora la función ${\displaystyle G}$ ${\displaystyle p}$ ${\displaystyle g\in G}$ ${\displaystyle x=g^{r}\in G}$ ${\displaystyle r\in \mathbb {Z} _{p}}$ ${\displaystyle r}$ ${\displaystyle r={\log _{g}}(x)}$ ${\displaystyle \mathbb {Z} _{p}\times \mathbb {Z} _{p}}$

${\displaystyle f\colon \mathbb {Z} _{p}\times \mathbb {Z} _{p}\to G\;;\;f(a,b)=g^{a}x^{-b}.}$

Esto nos da un problema de subgrupo oculto abeliano , donde corresponde a un homomorfismo de grupo . El núcleo corresponde a los múltiplos de . Entonces, si podemos encontrar el núcleo, podemos encontrar . Existe un algoritmo cuántico para resolver este problema. Este algoritmo, al igual que el algoritmo de búsqueda de factores, se debe a Peter Shor y ambos se implementan creando una superposición mediante el uso de puertas de Hadamard, seguido de una transformación cuántica y, finalmente, una transformada cuántica de Fourier. ^[3] Debido a esto, el algoritmo cuántico para calcular el logaritmo discreto también se denomina ocasionalmente "algoritmo de Shor". ${\displaystyle f}$ ${\displaystyle (r,1)}$ ${\displaystyle r}$ ${\displaystyle f}$

El problema de búsqueda de orden también puede verse como un problema de subgrupo oculto. ^[3] Para ver esto, considere el grupo de números enteros bajo la suma, y ​​para un dado tal que: , la función ${\displaystyle a\in \mathbb {Z} }$ ${\displaystyle a^{r}=1}$

${\displaystyle f\colon \mathbb {Z} \to \mathbb {Z} \;;\;f(x)=a^{x},\;f(x+r)=f(x).}$

Para cualquier grupo abeliano finito , existe un algoritmo cuántico para resolver el subgrupo oculto en tiempo polinómico. ^[3] ${\displaystyle G}$ ${\displaystyle G}$

Ver también

• GEECM , un algoritmo de factorización que se dice que es "a menudo mucho más rápido que el de Shor" ^[25]
• algoritmo de Grover

Referencias

1. Corto, PW (1994). "Algoritmos para computación cuántica: logaritmos discretos y factorización". Actas del 35º Simposio Anual sobre Fundamentos de la Informática . Computación IEEE. Soc. Prensa. págs. 124-134. doi :10.1109/sfcs.1994.365700. ISBN 0818665807. S2CID  15291489.
2. Shor, Peter W. (octubre de 1997). "Algoritmos de tiempo polinómico para factorización prima y logaritmos discretos en una computadora cuántica". Revista SIAM de Computación . 26 (5): 1484-1509. arXiv : quant-ph/9508027 . doi :10.1137/S0097539795293172. ISSN  0097-5397. S2CID  2337707.
3. Nielsen, Michael A.; Chuang, Isaac L. (9 de diciembre de 2010). Computación cuántica e información cuántica (PDF) (7ª ed.). Prensa de la Universidad de Cambridge. ISBN 978-1-107-00217-3. Archivado (PDF) desde el original el 11 de julio de 2019 . Consultado el 24 de abril de 2022 .
4. Gidney, Craig; Ekerå, Martín (2021). "Cómo factorizar enteros RSA de 2048 bits en 8 horas utilizando 20 millones de qubits ruidosos". Cuántico . 5 : 433. arXiv : 1905.09749 . Código Bib : 2021Cantidad...5..433G. doi :10.22331/q-2021-04-15-433. S2CID  162183806.
5. cai, Jin-Yi (15 de junio de 2023). "El algoritmo de Shor no factoriza números enteros grandes en presencia de ruido". arXiv : 2306.10072 [cuántico-ph].
6. Véase también tiempo pseudopolinomial .
7. Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John (1996). "Redes eficientes para factoraje cuántico" (PDF) . Revisión física A. 54 (2): 1034–1063. arXiv : quant-ph/9602016 . Código bibliográfico : 1996PhRvA..54.1034B. doi :10.1103/PhysRevA.54.1034. PMID  9913575. S2CID  2231795.
8. Harvey, David; van Der Hoeven, Joris (2020). "Multiplicación de enteros en el tiempo O (n log n)". Anales de Matemáticas . doi : 10.4007/anales.2021.193.2.4. S2CID  109934776.
9. "Tamiz de campo numérico". wolfram.com . Consultado el 23 de octubre de 2015 .
10. Roetteler, Martín; Naehrig, Michael; Svore, Krysta M .; Lauter, Kristin E. (2017). "Estimaciones de recursos cuánticos para calcular logaritmos discretos de curvas elípticas". En Takagi, Tsuyoshi; Peyrin, Thomas (eds.). Avances en criptología - ASIACRYPT 2017 - 23.ª Conferencia internacional sobre teoría y aplicaciones de la criptología y la seguridad de la información, Hong Kong, China, 3 al 7 de diciembre de 2017, Actas, Parte II . Apuntes de conferencias sobre informática. vol. 10625. Saltador. págs. 241–270. arXiv : 1706.06752 . doi :10.1007/978-3-319-70697-9_9.
11. Vandersypen, Lieven MK; Steffen, Matías; Breyta, Gregorio; Yannoni, Costantino S.; Sherwood, Mark H. & 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 , Bibcode :2001Natur.414..883V, CiteSeerX 10.1.1.251.8799 , doi :10.1038/414883a, PMID  11780055, S2CID  4400832 
12. Lu, Chao-Yang; Browne, Daniel E.; Yang, Tao y 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, S2CID  5158195
13. 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, S2CID  10010619
14. Lucero, Erik; Barends, Rami; Chen, Yu; Kelly, Julián; Mariantoni, Mateo; Megant, Antonio; O'Malley, Peter; Se hundió, Daniel; Vainsencher, Amit; Wenner, James; Blanco, Ted; Yin, Yi; Cleland, Andrew N.; Martinis, John M. (2012). "Cálculo de factores primos con un procesador cuántico de qubit de fase Josephson". Física de la Naturaleza . 8 (10): 719. arXiv : 1202.5707 . Código bibliográfico : 2012NatPh...8..719L. doi : 10.1038/nphys2385. S2CID  44055700.
15. Martín-López, Enrique; Martín-López, Enrique; Laing, Antonio; 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 mediante reciclaje de qubits". Fotónica de la naturaleza . 6 (11): 773–776. arXiv : 1111.4147 . Código bibliográfico : 2012NaPho...6..773M. doi :10.1038/nphoton.2012.259. S2CID  46546101.
16. 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". Revisión física A. 100 (1): 012305. arXiv : 1903.00768 . doi :10.1103/PhysRevA.100.012305. ISSN  2469-9926. S2CID  92987546.
17. Karamlou, Amir H.; Simón, William A.; Katabarwa, Amara; Scholten, Travis L.; Peropadre, Borja; Cao, Yudong (28 de octubre de 2021). "Análisis del rendimiento de la factorización cuántica variacional en un procesador cuántico superconductor". npj Información cuántica . 7 (1): 156. arXiv : 2012.07825 . Código Bib : 2021npjQI...7..156K. doi :10.1038/s41534-021-00478-z. ISSN  2056-6387. S2CID  229156747.
18. "Motte-and-baileys de computación cuántica". Optimizado para Shtetl . 2019-12-28 . Consultado el 15 de noviembre de 2021 .
19. Bernstein, Daniel (1998). "Detección de poderes perfectos en un tiempo esencialmente lineal". Matemáticas de la Computación . 67 (223): 1253–1283. doi : 10.1090/S0025-5718-98-00952-1 . ISSN  0025-5718.
20. por ejemplo, calcular las primeras raíces de , por ejemplo, con el método de Newton y verificar la primalidad de cada resultado entero ( prueba de primalidad de AKS ). ${\displaystyle \log _{2}(N)}$ ${\displaystyle N}$
21. Ekerå, Martín (2021). "Sobre factorizar completamente cualquier número entero de manera eficiente en una sola ejecución de un algoritmo de búsqueda de pedidos". Procesamiento de información cuántica . 20 (6) 205: 1–14. arXiv : 2007.10044 . Código Bib : 2021QuiP...20..205E. doi : 10.1007/s11128-021-03069-1 . ISSN  1570-0755.
22. Kitaev, A. Yu (20 de noviembre de 1995). "Medidas cuánticas y el problema del estabilizador abeliano". arXiv : quant-ph/9511026 .
23. Markov, Igor L.; Saeedi, Mehdi (2012). "Circuitos cuánticos optimizados constantemente para multiplicación y exponenciación modulares". Información y Computación Cuántica . 12 (5–6): 361–394. arXiv : 1202.6614 . Código Bib : 2012arXiv1202.6614M. doi :10.26421/QIC12.5-6-1. S2CID  16595181.
24. Markov, Igor L.; Saeedi, Mehdi (2013). "Factorización de números cuánticos más rápida mediante síntesis de circuitos". Física. Rev. A. 87 (1): 012310. arXiv : 1301.3210 . Código Bib : 2013PhRvA..87a2310M. doi : 10.1103/PhysRevA.87.012310. S2CID  2246117.
25. Bernstein, Daniel J.; Heninger, Nadia ; Lou, Pablo; Valenta, Lucas (2017). "RSA post-cuántica" (PDF) . Criptografía poscuántica . Apuntes de conferencias sobre informática. vol. 10346. págs. 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. & 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ó "¡Excelente artículo, Scott! Es el mejor trabajo que he visto al explicar la computación cuántica al hombre de la calle"). 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 de tiempo polinomial 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 las Ciencias de la Computación, Santa Fe, Nuevo México, 20 de noviembre). 22, 1994. Revisiones menores realizadas 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 posdata.
• 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 lección 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 Archivado el 30 de abril de 2020 en Wayback Machine , documento posdata 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 conferencias sobre computación cuántica, Universidad de Cornell, Física 481–681, CS 483; Primavera de 2006 por N. David Mermin. Última revisión el 28 de marzo de 2006, documento PDF de 30 páginas.
• Lavor, C.; Manssur, LRU; Portugal, R. (2003). "Algoritmo de Shor para factorizar números 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 impartida sobre el algoritmo de factorización cuántica de Peter Shor. 22 páginas.
• Capítulo 20 Computación cuántica, de Computational Complexity: A Modern Approach , borrador de un libro: fechado en 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, "Complejidad computacional: un enfoque moderno", 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 Archivado el 20 de enero de 2011 en Wayback Machine , de "Discover Magazine", con fecha del 19 de enero de 2011.
• Josef Gruska - Desafíos de la computación cuántica también en matemáticas ilimitadas: 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".