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 superpolinómica en comparación con los algoritmos clásicos (no cuánticos) más conocidos. ^[3] Por otro lado, la factorización de números de importancia práctica requiere muchos más qubits de los que estarán disponibles en el futuro cercano. ^[4] Otra preocupación es que el ruido en los circuitos cuánticos puede 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 del logaritmo discreto y el problema de búsqueda de períodos. El "algoritmo de Shor" generalmente se refiere al algoritmo de factorización, pero puede referirse a cualquiera de los tres algoritmos. El algoritmo del 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 del subgrupo oculto .

En una computadora cuántica, para factorizar un entero , el algoritmo de Shor se ejecuta en tiempo polinomial , lo que significa que el tiempo empleado es polinomial en . ^[6] Se necesitan puertas cuánticas de orden utilizando una 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 de manera eficiente en una computadora cuántica y, en consecuencia, está en la clase de complejidad BQP . Esto es significativamente más rápido que el algoritmo de factorización clásico conocido más eficiente, 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 operar 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 Diffie-Hellman de campo finito
• El intercambio de claves Diffie-Hellman de curva elíptica ^[10]

El algoritmo RSA se basa en el supuesto de que la factorización de números enteros grandes es computacionalmente intratable. Hasta donde se sabe, este supuesto es válido para 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 la factorización de números enteros es eficiente en una computadora cuántica ideal, por lo que puede ser factible derrotar al algoritmo 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 computadoras cuánticas. También ha facilitado la investigación sobre nuevos criptosistemas que son seguros frente a las computadoras cuánticas, colectivamente llamados criptografía poscuántica .

Implementación física

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

En 2001, un grupo de IBM demostró el algoritmo de Shor , que lo factorizó en , utilizando una implementación de RMN de una computadora cuántica con siete cúbits. ^[11] Después de la implementación de IBM, dos grupos independientes implementaron el algoritmo de Shor utilizando cúbits fotónicos , enfatizando que se observó un entrelazamiento de múltiples cúbits al ejecutar los circuitos del algoritmo de Shor. ^{[12] [13]} En 2012, se realizó la factorización de con cúbits de estado sólido. ^[14] Más tarde, en 2012, se logró la factorización de . ^[15] En 2016, se realizó nuevamente la factorización de utilizando cúbits de iones atrapados con una técnica de reciclaje. ^[16] 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. ^[17] Sin embargo, todas estas demostraciones han compilado el algoritmo haciendo uso del conocimiento previo de la respuesta, y algunas incluso han simplificado demasiado el algoritmo de una manera que lo hace equivalente a lanzar una moneda al aire. ^[18] Además, se han hecho intentos de utilizar computadoras cuánticas con otros algoritmos. ^[19] Sin embargo, 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 tengan un mejor rendimiento que los algoritmos de factorización clásicos. ^[20] ${\displaystyle 15}$ ${\displaystyle 3\times 5}$ ${\displaystyle 15}$ ${\displaystyle 21}$ ${\displaystyle 15}$ ${\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 lidiar con estos fenómenos no deseados (cuando haya más cúbits disponibles, la corrección de errores cuánticos puede ayudar). En 2023, Jin-Yi Cai demostró que, en presencia de ruido, el algoritmo de Shor falla asintóticamente casi con seguridad para semiprimos grandes que son productos de dos primos en la secuencia OEIS A073024. ^[5] Estos primos tienen la propiedad de tener un factor primo mayor que , y tienen una densidad positiva en el conjunto de todos los primos. Por lo tanto, se necesitará corrección de errores para poder factorizar todos los números con el algoritmo de Shor. ${\displaystyle p}$ ${\displaystyle p-1}$ ${\displaystyle p^{2/3}}$

Algoritmo

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

Para lograr esto, el algoritmo de Shor consta de dos partes:

1. Una reducción clásica del problema de factorización al problema de búsqueda de 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

Es posible un algoritmo de factorización completo si podemos factorizar de manera eficiente números arbitrarios en solo dos números enteros mayores que 1, ya que si o no son primos, 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 verificar de manera eficiente si es par, en cuyo caso 2 es trivialmente un factor. Supongamos, por lo tanto, que es impar para el resto de esta discusión. Después, podemos utilizar algoritmos clásicos eficientes para verificar si es una potencia prima . ^[21] Para potencias primas, existen algoritmos de factorización clásicos eficientes, ^[22] 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 entero aleatorio . Un posible divisor no trivial de se puede encontrar calculando , 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 termina y el otro factor no trivial es . Si no se identificó un factor no trivial, eso significa que y la elección de son coprimos , por lo que está contenido en el grupo multiplicativo de números enteros módulo , que tiene un inverso multiplicativo módulo . Por lo tanto, tiene un orden multiplicativo módulo , lo que significa ${\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 a}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle a}$ ${\displaystyle r}$ ${\displaystyle N}$

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

y es el entero positivo más pequeño que satisface esta congruencia. ${\displaystyle r}$

La subrutina cuántica encuentra . Se puede ver a partir de la congruencia que divide a , escrito . Esto se puede factorizar usando diferencia de cuadrados : Dado que hemos factorizado la expresión de esta manera, el algoritmo no funciona para impares (porque debe ser un entero), lo que significa que el algoritmo tendría que reiniciarse con un nuevo . De aquí en adelante, por lo tanto, podemos suponer que es par. No puede ser el caso de que , ya que esto implicaría , lo que implicaría contradictoriamente que sería el orden de , que ya era . En este punto, puede o no ser el caso de que . Si no es cierto que , entonces eso significa que podemos encontrar un factor no trivial de . Calculamos Si , entonces eso significa que era cierto, y un factor no trivial de no se puede lograr a partir de , y el algoritmo debe reiniciarse con un nuevo . De lo contrario, hemos encontrado un factor no trivial de , siendo el otro , y el algoritmo está terminado. Para este paso, también es equivalente a calcular ; Producirá un factor no trivial si no es trivial, y no lo producirá si es trivial (donde ). ${\displaystyle r}$ ${\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 replantea brevemente de la siguiente manera: sea impar y no una potencia prima. Queremos obtener dos factores no triviales de . ${\displaystyle N}$ ${\displaystyle N}$

1. Elige un número al azar . ${\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 hemos terminado. ${\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, vuelva al paso 1. ${\displaystyle r}$
6. Calcular . Si no es trivial, el otro factor es y ya está. De lo contrario, volver 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 unas cuantas 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 muy alta de éxito si se utiliza una reducción más avanzada. ^[23] ${\displaystyle N}$

Subrutina de búsqueda de orden cuántico

El objetivo de la subrutina cuántica del algoritmo de Shor es, dados los números enteros coprimos y , encontrar el orden de módulo , que es el número entero positivo más pequeño tal que . Para lograr esto, 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 , es decir, . El tamaño del primer registro determina qué tan precisa es la aproximación que produce el circuito. Se puede demostrar que el uso de qubits brinda 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 denotar estados cuánticos y para denotar el producto tensorial , en lugar del AND 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 n=\left\lceil {\log _{2}N}\right\rceil }$ ${\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 unitario que representa 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 este codifican información sobre el período, y se puede ver 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 entero aleatorio de la forma para 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 a partir de la medición de los estados cuánticos de salida y recuperar el período. ${\displaystyle r}$

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

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 unitario y estado propio tal que , envía estados de entrada a estados de salida cercanos a , donde es un entero cercano a . En otras palabras, envía cada estado propio de a un estado cercano al valor propio asociado. Para los fines de la búsqueda de orden cuántico, empleamos esta estrategia utilizando el unitario definido por la acción La acción de sobre los estados con no es crucial para el funcionamiento del algoritmo, pero debe incluirse para garantizar que la transformación general sea una puerta cuántica bien definida. Implementar el circuito para la estimación de fase cuántica con requiere poder implementar eficientemente las puertas . Esto se puede lograr mediante la exponenciación modular , que es la parte más lenta del algoritmo. La puerta así definida satisface , lo que implica inmediatamente que sus valores propios son las raíces -ésimas de la unidad . Además, cada valor propio tiene un vector propio de la forma , y estos vectores propios son tales que ${\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}}}$$ ${\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}^{j}}$ ${\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 desprende 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 entonces el 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 alcanza su pico alrededor de , con . Esta probabilidad se puede hacer arbitrariamente cercana a 1 utilizando cúbits 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 la fase cuántica da como resultado la evolución. Al medir el primer registro, ahora tenemos una probabilidad equilibrada para encontrar cada , cada uno dando una aproximación entera a , que se puede dividir por para obtener una aproximación decimal para . ${\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 da la mejor aproximación de fracción para la aproximación medida a partir del circuito, para y coprimos y . La cantidad de qubits en el primer registro, , que determina la precisión de la aproximación, garantiza que, dada la mejor aproximación a partir de la superposición de se midió ^[2] (lo que se puede hacer arbitrariamente probable usando bits adicionales y truncando la salida). Sin embargo, mientras que y son coprimos, puede ser el caso de que y no sean coprimos. Debido a eso, y puede haber perdido algunos factores que estaban en y . Esto se puede remediar volviendo a ejecutar la subrutina de búsqueda de orden cuántico una cantidad arbitraria de veces, para producir una lista de aproximaciones de fracción donde es la cantidad de veces que se ejecutó la subrutina. Cada una tendrá diferentes factores eliminados porque el circuito (probablemente) habrá medido múltiples valores posibles diferentes de . Para recuperar el valor real, podemos tomar el mínimo común múltiplo de cada uno : El mínimo común múltiplo será el orden del entero original con alta probabilidad. En la práctica, una sola ejecución de la subrutina de búsqueda de orden cuántico es suficiente en general si se utiliza un posprocesamiento más avanzado. ^[25] ${\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}}}$$ ${\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}}}}$$ ${\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}$

Elección del 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, donde es la aproximación más precisa de la fase a partir de la estimación de fase) permitirá recuperar el valor real de . ${\displaystyle 2n+1}$ ${\displaystyle |k\rangle }$ ${\textstyle k/2^{2n+1}}$ ${\displaystyle r}$

Cada medida anterior en el algoritmo de Shor representa una superposición de números enteros que se aproximan a . Sea 1 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, entonces el algoritmo de fracciones continuas ejecutado en recuperará tanto como . ${\displaystyle j}$ ${\displaystyle r}$ ${\displaystyle n}$ $${\displaystyle \left\vert {\frac {j}{r}}-\phi \right\vert \leq {\frac {1}{2r^{2}}}}$$ ${\displaystyle \phi }$ ${\textstyle {\frac {j}{\gcd(j,\;r)}}}$ ${\textstyle {\frac {r}{\gcd(j,\;r)}}}$

^[3] Como la cadena de bits óptima a partir de la estimación de fase es precisa hasta por bits, lo que implica que el algoritmo de fracciones continuas recuperará y (o con su máximo común divisor eliminado). ${\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 preprocesamiento/posprocesamiento clásico. Existen varios enfoques para construir y optimizar circuitos para la exponenciación modular. El enfoque más simple y (actualmente) más práctico es imitar los 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 futuras optimizaciones. ^{[26] [27]} Los circuitos reversibles suelen utilizar el orden de puertas para qubits. Las técnicas alternativas mejoran asintóticamente el recuento 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. ${\displaystyle n^{3}}$ ${\displaystyle n}$

Cálculo de períodos y logaritmos discretos

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

Algoritmo de Shor para logaritmos discretos

Dado un grupo con orden y generador , supongamos que sabemos que , para algún , y deseamos calcular , que es el logaritmo discreto : . Consideremos el grupo abeliano , donde cada factor corresponde a la suma modular de valores. Ahora, consideremos 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 es, como el algoritmo de búsqueda de factores, debido a Peter Shor y ambos se implementan creando una superposición mediante el uso de puertas de Hadamard, seguido de la implementación como una transformada cuántica, seguida finalmente por una transformada cuántica de Fourier. ^[3] Debido a esto, el algoritmo cuántico para calcular el logaritmo discreto también se conoce ocasionalmente como "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 adición, 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 polinomial. ^[3] ${\displaystyle G}$ ${\displaystyle G}$

Véase también

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

Referencias

1. Shor, PW (1994). "Algoritmos para computación cuántica: logaritmos discretos y factorización". Actas del 35.° Simposio anual sobre fundamentos de la informática . págs. 124-134. doi :10.1109/sfcs.1994.365700. ISBN . 978-0-8186-6580-6.
2. Shor, Peter W. (octubre de 1997). "Algoritmos de tiempo polinomial para factorización prima y logaritmos discretos en una computadora cuántica". Revista SIAM de informática . 26 (5): 1484–1509. arXiv : quant-ph/9508027 . doi :10.1137/S0097539795293172. 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.). Cambridge University Press. ISBN 978-1-107-00217-3Archivado (PDF) del original el 11 de julio de 2019. Consultado el 24 de abril de 2022 .
4. Gidney, Craig; Ekerå, Martin (2021). "Cómo factorizar enteros RSA de 2048 bits en 8 horas usando 20 millones de qubits ruidosos". Quantum . 5 : 433. arXiv : 1905.09749 . Bibcode :2021Quant...5..433G. doi :10.22331/q-2021-04-15-433. S2CID  162183806.
5. Cai, Jin-Yi (2024). "El algoritmo de Shor no factoriza números enteros grandes en presencia de ruido". Science China Information Sciences . 67 (7). arXiv : 2306.10072 . doi :10.1007/s11432-023-3961-3.
6. Véase también tiempo pseudopolinomial .
7. Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John (agosto de 1996). "Redes eficientes para factorización cuántica". 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.
8. Harvey, David; van der Hoeven, Joris (marzo de 2021). "Multiplicación de enteros en tiempo O (n log n)" (PDF) . Anales de Matemáticas . 193 (2). doi :10.4007/annals.2021.193.2.4.
9. "Tamiz de campo numérico". wolfram.com . Consultado el 23 de octubre de 2015 .
10. Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter , Kristin E. (2017). "Estimaciones de recursos cuánticos para calcular logaritmos discretos de curva elíptica". En Takagi, Tsuyoshi; Peyrin, Thomas (eds.). Avances en criptología – ASIACRYPT 2017 – 23.ª Conferencia internacional sobre la teoría y las 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 . Notas de clase en informática. Vol. 10625. Springer. págs. 241–270. arXiv : 1706.06752 . doi :10.1007/978-3-319-70697-9_9. ISBN . 978-3-319-70696-2.
11. Vandersypen, Lieven MK; Steffen, Matthias; Breyta, Gregory; Yannoni, Costantino S.; Sherwood, Mark H.; Chuang, Isaac L. (diciembre de 2001). "Realización experimental del algoritmo de factorización cuántica de Shor utilizando resonancia magnética nuclear". Nature . 414 (6866): 883–887. arXiv : quant-ph/0112176 . Código Bibliográfico :2001Natur.414..883V. doi :10.1038/414883a. PMID  11780055.
12. Lu, Chao-Yang; Browne, Daniel E.; Yang, Tao; Pan, Jian-Wei (19 de diciembre de 2007). "Demostración de una versión compilada del algoritmo de factorización cuántica de Shor utilizando cúbits fotónicos". Physical Review Letters . 99 (25): 250504. arXiv : 0705.1684 . Código Bibliográfico :2007PhRvL..99y0504L. doi :10.1103/PhysRevLett.99.250504. PMID  18233508.
13. Lanyon, BP; Weinhold, TJ; Langford, NK; Barbieri, M.; James, DFV; Gilchrist, A.; White, AG (19 de diciembre de 2007). "Demostración experimental de una versión compilada del algoritmo de Shor con entrelazamiento cuántico". Physical Review Letters . 99 (25): 250505. arXiv : 0705.1398 . Código Bibliográfico :2007PhRvL..99y0505L. doi :10.1103/PhysRevLett.99.250505. PMID  18233509.
14. Lucero, Erik; Barends, Rami; Chen, Yu; Kelly, Julian; Mariantoni, Matteo; Megrant, Anthony; O'Malley, Peter; Sank, Daniel; Vainsencher, Amit; Wenner, James; White, Ted; Yin, Yi; Cleland, Andrew N.; Martinis, John M. (2012). "Computing prime factors with a Josephson phase qubit quantum processing". Nature Physics . 8 (10): 719. arXiv : 1202.5707 . Bibcode :2012NatPh...8..719L. doi :10.1038/nphys2385. S2CID  44055700.
15. Martín-López, Enrique; Martín-López, Enrique; Laing, Anthony; Lawson, Thomas; Alvarez, 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 usando reciclaje de cúbits". Nature Photonics . 6 (11): 773–776. arXiv : 1111.4147 . Código Bibliográfico :2012NaPho...6..773M. doi :10.1038/nphoton.2012.259. S2CID  46546101.
16. Monz, Thomas; Nigg, Daniel; Martinez, Esteban A.; Brandl, Matthias F.; Schindler, Philipp; Rines, Richard; Wang, Shannon X.; Chuang, Isaac L.; Blatt, Rainer (4 de marzo de 2016). "Realización de un algoritmo Shor escalable". Science . 351 (6277): 1068–1070. arXiv : 1507.08852 . Bibcode :2016Sci...351.1068M. doi :10.1126/science.aad9480. PMID  26941315. S2CID  17426142.
17. Amico, Mirko; Saleem, Zain H.; Kumph, Muir (8 de julio de 2019). "Estudio experimental del algoritmo de factorización de Shor utilizando IBM Q Experience". Physical Review A . 100 (1): 012305. arXiv : 1903.00768 . Código Bibliográfico :2019PhRvA.100a2305A. doi :10.1103/PhysRevA.100.012305. S2CID  92987546.
18. Smolin, John A.; Smith, Graeme; Vargo, Alexander (julio de 2013). "Simplificando excesivamente la factorización cuántica". Nature . 499 (7457): 163–165. arXiv : 1301.7007 . Bibcode :2013Natur.499..163S. doi :10.1038/nature12290. PMID  23846653.
19. Karamlou, Amir H.; Simon, 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 Quantum Information . 7 (1): 156. arXiv : 2012.07825 . doi :10.1038/s41534-021-00478-z.
20. "Computación cuántica: motte-and-baileys". Shtetl-Optimized . 2019-12-28 . Consultado el 2021-11-15 .
21. Bernstein, Daniel (1998). "Detección de potencias perfectas en tiempo esencialmente lineal". Matemáticas de la computación . 67 (223): 1253–1283. doi :10.1090/S0025-5718-98-00952-1.
22. por ejemplo, calculando las primeras raíces de , por ejemplo, con el método de Newton y comprobando cada resultado entero en busca de primalidad ( prueba de primalidad AKS ). ${\displaystyle \log _{2}(N)}$ ${\displaystyle N}$
23. Ekerå, Martin (junio de 2021). "Sobre la factorización completa y eficiente de cualquier número entero en una sola ejecución de un algoritmo de búsqueda de orden". Procesamiento de información cuántica . 20 (6): 205. arXiv : 2007.10044 . Bibcode :2021QuIP...20..205E. doi : 10.1007/s11128-021-03069-1 .
24. Kitaev, A. Yu (1995). "Medidas cuánticas y el problema del estabilizador abeliano". arXiv : quant-ph/9511026 .
25. Ekerå, Martin (mayo de 2024). "Sobre la probabilidad de éxito de la búsqueda de orden cuántico". ACM Transactions on Quantum Computing . 5 (2): 1–40. arXiv : 2201.07791 . doi : 10.1145/3655026 .
26. Markov, Igor L.; Saeedi, Mehdi (2012). "Circuitos cuánticos optimizados de manera constante para multiplicación y exponenciación modular". Información y computación cuántica . 12 (5–6): 361–394. arXiv : 1202.6614 . Código Bibliográfico :2012arXiv1202.6614M. doi :10.26421/QIC12.5-6-1. S2CID  16595181.
27. Markov, Igor L.; Saeedi, Mehdi (2013). "Factorización de números cuánticos más rápida mediante 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. S2CID  2246117.
28. Bernstein, Daniel J.; Heninger, Nadia; Lou, Paul; Valenta, Luke (2017). "RSA postcuántico". Criptografía postcuántica . Apuntes de clase en informática. Vol. 10346. págs. 311–329. doi :10.1007/978-3-319-59879-6_18. ISBN 978-3-319-59878-9.

Lectura adicional

• 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 978-1-107-00217-3.
• Kaye, Phillip; Laflamme, Raymond; Mosca, Michele (2006). Introducción a la computación cuántica . doi :10.1093/oso/9780198570004.001.0001. ISBN 978-0-19-857000-4.
• "Explicación para el hombre de la calle" de Scott Aaronson , "aprobada" por Peter Shor. (Shor escribió: "Excelente artículo, Scott. Es la mejor explicación que he visto sobre computación cuántica al hombre de la calle"). En uno de los comentarios se presentó una metáfora alternativa para la 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/S0036144598347011Versió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-22 de noviembre de 1994. Se realizaron revisiones menores en enero de 1996").
• Computación cuántica y el algoritmo de Shor, página de algoritmos cuánticos de Matthew Hayward, 17 de febrero de 2005, 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 Ámsterdam, 12 de enero de 1999, documento posdata de 9 páginas.
• Algoritmo de factorización de Shor, notas de la clase 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 2020-04-30 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 de 11:47:38 1996.
• III. Descifrado del cifrado RSA con un ordenador cuántico: algoritmo de factorización de Shor, apuntes sobre computación cuántica, Universidad de Cornell, Física 481-681, CS 483; primavera de 2006, por N. David Mermin. Última revisión: 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 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, Princeton University. 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 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 descifrar la criptografía" y "Hacking a velocidad cuántica con el algoritmo de Shor".
• Implementación completa del algoritmo de Shor con Classiq