El algoritmo de Shor

A partir de 2026, debido a las altas tasas de error de las computadoras cuánticas y al número limitado de cúbits físicos disponibles para la corrección de errores cuánticos , las demostraciones de laboratorio del algoritmo de Shor obtienen resultados correctos en solo una fracción de los intentos, y solo han tenido éxito con semiprimos pequeños .

En 2001, el algoritmo de Shor fue demostrado por un grupo en IBM , que factorizó${\displaystyle 15}$en${\displaystyle 3\times 5}$, utilizando una implementación de RMN de una computadora cuántica con siete cúbits. ^{[ 10 ]} Después de la implementación de IBM, dos grupos independientes implementaron el algoritmo de Shor utilizando cúbits fotónicos . ^{[ 11 ] [ 12 ]} En 2012, la factorización de${\displaystyle 15}$se realizó con cúbits de estado sólido. ^{[ 13 ]} Posteriormente, en 2012, la factorización de${\displaystyle 21}$se logró. ^{[ 14 ]} En 2016, la factorización de${\displaystyle 15}$Se realizó nuevamente utilizando cúbits de iones atrapados. ^{[ 15 ]} Sin embargo, ninguna de estas demostraciones cumple con los requisitos del algoritmo de Shor: compilan el circuito utilizando conocimiento previo de la solución, y algunas incluso han simplificado demasiado el algoritmo de tal manera que lo hacen equivalente a lanzar una moneda. ^{[ 16 ]}

Un algoritmo de factorización completo es posible si podemos factorizar eficientemente cualquier número arbitrario.${\displaystyle N}$en solo dos números enteros${\displaystyle p}$y${\displaystyle q}$mayor que 1, ya que si alguno de los dos${\displaystyle p}$o${\displaystyle q}$Si no son primos, entonces el algoritmo de factorización se puede ejecutar sobre ellos hasta que solo queden primos.

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

Si esos casos sencillos no producen un factor no trivial de${\displaystyle N}$El algoritmo procede a manejar el caso restante. Elegimos un número entero aleatorio.${\displaystyle 2\leq a<N{.}}$Un posible divisor no trivial de${\displaystyle N}$se puede encontrar mediante computación${\displaystyle \gcd(a,N)}$, lo cual se puede hacer de forma clásica y eficiente utilizando el algoritmo euclidiano . Si esto produce un factor no trivial (que significa${\displaystyle \gcd(a,N)\neq 1}$), el algoritmo está terminado y el otro factor no trivial es${\displaystyle N/\gcd(a,N)}$. Si no se identificó un factor no trivial, entonces esto significa que${\displaystyle N}$y la elección de${\displaystyle a}$son coprimos , por lo tanto${\displaystyle a}$está contenido en el grupo multiplicativo de enteros módulo${\displaystyle N}$, teniendo un inverso multiplicativo módulo${\displaystyle N}$. De este modo,${\displaystyle a}$tiene un orden multiplicativo${\displaystyle r}$módulo${\displaystyle N}$, significado

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

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

La subrutina cuántica encuentra${\displaystyle r}$. Se puede observar por la congruencia que${\displaystyle N}$divide${\displaystyle a^{r}-1}$, escrito${\displaystyle N\mid a^{r}-1}$Esto se puede factorizar utilizando la diferencia de cuadrados :$${\displaystyle N\mid (a^{r/2}-1)(a^{r/2}+1).}$$Dado que hemos factorizado la expresión de esta manera, el algoritmo no funciona para números impares.${\displaystyle r}$(porque${\displaystyle a^{r/2}}$debe ser un número entero), lo que significa que el algoritmo tendría que reiniciarse con un nuevo${\displaystyle a}$Por lo tanto, en adelante podemos asumir que${\displaystyle r}$es par. No puede ser el caso que${\displaystyle N\mid a^{r/2}-1}$, ya que esto implicaría${\displaystyle a^{r/2}\equiv 1{\bmod {N}}}$, lo cual implicaría contradictoriamente que${\displaystyle r/2}$sería el orden de${\displaystyle a}$, que ya estaba${\displaystyle r}$. En este punto, puede que sea o no el caso que${\displaystyle N\mid a^{r/2}+1}$. Si${\displaystyle N}$no divide${\displaystyle a^{r/2}+1}$, entonces esto significa que podemos encontrar un factor no trivial de${\displaystyle N}$Calculamos .$${\displaystyle d=\gcd(N,a^{r/2}-1).}$$Si${\displaystyle d=1}$, entonces${\displaystyle N\mid a^{r/2}+1}$era cierto, y un factor no trivial de${\displaystyle N}$no se puede lograr desde${\displaystyle a}$y el algoritmo debe reiniciarse con un nuevo${\displaystyle a}$. De lo contrario, hemos encontrado un factor no trivial de${\displaystyle N}$, siendo el otro${\displaystyle N/d}$y el algoritmo ha terminado. Para este paso, también es equivalente a calcular${\displaystyle \gcd(N,a^{r/2}+1)}$; producirá un factor no trivial si${\displaystyle \gcd(N,a^{r/2}-1)}$no es trivial, y no lo será si es trivial (donde${\displaystyle N\mid a^{r/2}+1}$).

El algoritmo reformulado brevemente es el siguiente:${\displaystyle N}$ser impar, y no una potencia prima. Queremos generar dos factores no triviales de${\displaystyle N}$.

1. Elige un número al azar${\displaystyle 1<a<N}$.
2. Calcular${\displaystyle K=\gcd(a,N)}$, el máximo común divisor de${\displaystyle a}$y${\displaystyle N}$.
3. Si${\displaystyle K\neq 1}$, entonces${\displaystyle K}$es un factor no trivial de${\displaystyle N}$, siendo el otro factor el${\displaystyle N/K}$y hemos terminado.
4. De lo contrario, utilice la subrutina cuántica para encontrar el orden.${\displaystyle r}$de${\displaystyle a}$.
5. Si${\displaystyle r}$Si es extraño, vuelva al paso 1.
6. Calcular${\displaystyle g=\gcd(N,a^{r/2}+1)}$. Si${\displaystyle g}$no es trivial, el otro factor es${\displaystyle N/g}$Y listo. De lo contrario, vuelva al paso 1.

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.${\displaystyle N}$con una probabilidad de éxito muy alta si se utiliza una reducción más avanzada. ^{[ 19 ]}

El objetivo de la subrutina cuántica del algoritmo de Shor es, dados los enteros coprimos${\displaystyle N}$y${\displaystyle 1<a<N}$para encontrar el orden${\displaystyle r}$de${\displaystyle a}$módulo${\displaystyle N}$, el entero positivo más pequeño${\displaystyle r}$de tal manera que${\displaystyle a^{r}\equiv 1{\pmod {N}}}$Para lograr esto, el algoritmo de Shor utiliza un circuito cuántico que involucra dos registros. El segundo registro utiliza${\displaystyle n}$cúbits, donde${\displaystyle n}$es el entero más pequeño tal que${\displaystyle N\leq 2^{n}}$, es decir,${\displaystyle n=\left\lceil {\log _{2}N}\right\rceil }$El tamaño del primer registro determina la precisión de la aproximación que produce el circuito. Se puede demostrar que utilizando${\displaystyle 2n}$Los cúbits proporcionan la precisión suficiente para encontrar${\displaystyle r}$El circuito cuántico exacto depende de los parámetros.${\displaystyle a}$y${\displaystyle N}$, que definen el problema. La siguiente descripción del algoritmo utiliza la notación bra-ket para denotar estados cuánticos y${\displaystyle \otimes }$para denotar el producto tensorial .

El algoritmo consta de dos pasos principales:

1. Utilice la estimación de fase cuántica con matriz unitaria.${\displaystyle U}$representando la operación de multiplicar por${\displaystyle a}$(módulo${\displaystyle N}$), y estado de entrada${\displaystyle |0\rangle ^{\otimes 2n}\otimes |1\rangle }$(donde el segundo registro es${\displaystyle |1\rangle }$hecho de${\displaystyle n}$cúbits). Los valores propios de este${\displaystyle U}$codificar información sobre el período y${\displaystyle |1\rangle }$se puede ver que es escribible como una suma de sus autovectores. Gracias a estas propiedades, la etapa de estimación de fase cuántica da como resultado un entero aleatorio de la forma${\displaystyle {\frac {j}{r}}2^{2n}}$para aleatorio${\displaystyle j=0,1,...,r-1}$.
2. Utilice el algoritmo de fracciones continuas para extraer el período.${\displaystyle r}$a partir 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.

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 Alexei Kitaev . ^{[ 20 ]}

Estimación de fase cuántica

En general, el algoritmo de estimación de fase cuántica , para cualquier unitario${\displaystyle U}$y autoestado${\displaystyle |\psi \rangle }$de tal manera que${\displaystyle U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle }$, envía estados de entrada${\displaystyle |0\rangle |\psi \rangle }$para generar estados cercanos a${\displaystyle |\phi \rangle |\psi \rangle }$, dónde${\displaystyle \phi }$es una superposición de números enteros cercanos a${\displaystyle 2^{2n}\theta }$En otras palabras, envía cada autoestado${\displaystyle |\psi _{j}\rangle }$de${\displaystyle U}$a un estado que contiene información cercana al valor propio asociado. Para los fines de la búsqueda de orden cuántico, empleamos esta estrategia utilizando la unitaria definida por la acción$${\displaystyle U|k\rangle ={\begin{cases}|ak{\pmod {N}}\rangle &0\leq k<N,\\|k\rangle &N\leq k<2^{n}.\end{cases}}}$$La acción de${\displaystyle U}$en los estados${\displaystyle |k\rangle }$con${\displaystyle N\leq k<2^{n}}$no es crucial para el funcionamiento del algoritmo, pero debe incluirse para asegurar que la transformación general sea una puerta cuántica bien definida. Implementación del circuito para la estimación de fase cuántica con${\displaystyle U}$requiere poder implementar las puertas de manera eficiente${\displaystyle U^{2^{j}}}$Esto se puede lograr mediante la exponenciación modular , que es la parte más lenta del algoritmo.

La puerta así definida satisface${\displaystyle U^{r}=I}$, lo que implica inmediatamente que sus autovalores son los${\displaystyle r}$raíces de la unidad${\displaystyle \omega _{r}^{k}=e^{2\pi ik/r}}$. Además, cada valor propio${\displaystyle \omega _{r}^{j}}$tiene un vector propio de la forma${\textstyle |\psi _{j}\rangle =r^{-1/2}\sum _{k=0}^{r-1}\omega _{r}^{-kj}|a^{k}\rangle }$y estos autovectores son tales que$${\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 deduce de la fórmula de la serie geométrica , lo que implica${\textstyle \sum _{j=0}^{r-1}\omega _{r}^{jk}=0}$.

Utilizando la estimación de fase cuántica en un estado de entrada${\displaystyle |0\rangle ^{\otimes 2n}|\psi _{j}\rangle }$entonces devolvería el número entero${\displaystyle 2^{2n}j/r}$con alta probabilidad. Más precisamente, el circuito de estimación de fase cuántica envía${\displaystyle |0\rangle ^{\otimes 2n}|\psi _{j}\rangle }$a${\displaystyle |\phi _{j}\rangle |\psi _{j}\rangle }$de tal manera que la distribución de probabilidad resultante${\displaystyle p_{k}\equiv |\langle k|\phi _{j}\rangle |^{2}}$alcanza su punto máximo alrededor de${\displaystyle k=2^{2n}j/r}$, con${\displaystyle p_{2^{2n}j/r}\geq 4/\pi ^{2}\approx 0.4053}$Esta probabilidad se puede hacer arbitrariamente cercana a 1 utilizando cúbits adicionales.

Aplicando el razonamiento anterior a la entrada${\displaystyle |0\rangle ^{\otimes 2n}|1\rangle }$, la estimación de fase cuántica da como resultado la evolución$${\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 .}$$Al medir el primer registro, ahora tenemos una probabilidad equilibrada.${\displaystyle 1/r}$para encontrar cada${\displaystyle |\phi _{j}\rangle }$, cada uno de ellos dando una aproximación entera a${\displaystyle 2^{2n}j/r}$, que se puede dividir por${\displaystyle 2^{2n}}$para obtener una aproximación decimal para${\displaystyle j/r}$.

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 de Fourier cuántica y el preprocesamiento/postprocesamiento 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 circuitos aritméticos convencionales con puertas reversibles , comenzando con sumadores de acarreo en cascada . Conocer la base y el módulo de la exponenciación facilita optimizaciones adicionales. ^{[ 22 ] [ 23 ]} Los circuitos reversibles suelen usar del orden de${\displaystyle n^{3}}$puertas para${\displaystyle n}$cúbits. Las técnicas alternativas mejoran asintóticamente el número de compuertas mediante el uso de transformadas de Fourier cuánticas , pero no son competitivas con menos de 600 cúbits debido a las altas constantes.

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

${\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${\displaystyle f}$corresponde a un homomorfismo de grupo . El núcleo corresponde a los múltiplos de${\displaystyle (r,1)}$. Entonces, si podemos encontrar el núcleo, podemos encontrar${\displaystyle r}$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 Hadamard, seguido de la implementación.${\displaystyle f}$como una transformada cuántica, seguida finalmente por una transformada de Fourier cuántica. ^{[ 3 ]} Debido a esto, el algoritmo cuántico para calcular el logaritmo discreto también se conoce ocasionalmente como "algoritmo de Shor".

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

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

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