Algoritmo de Shor

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 22 de junio de 2021; la verificación requiere 1 edición .

El algoritmo de Shor es un algoritmo de factorización cuántica (que descompone un número en factores primos) que le permite descomponer un número en el tiempo usando qubits lógicos . $METRO$ $O(\log ^{3}M)$ ${\ estilo de visualización O (\ log M)}$

El algoritmo de Shor fue desarrollado por Peter Shor en 1994 . Siete años después, en 2001 , su desempeño fue demostrado por un grupo de especialistas de IBM . El número 15 fue factorizado por 3 y 5 usando una computadora cuántica con 7 qubits .

Sobre el algoritmo

La importancia del algoritmo radica en el hecho de que con su ayuda (cuando se usa una computadora cuántica con varios miles de qubits lógicos) es posible descifrar sistemas criptográficos de clave pública . Por ejemplo, RSA usa una clave pública que es el producto de dos grandes números primos. Una forma de descifrar el cifrado RSA es encontrar los factores. Cuando son lo suficientemente grandes, esto es casi imposible de hacer usando los algoritmos clásicos conocidos . Los algoritmos de factorización probados deterministas clásicos más conocidos, como el método de forma cuadrática de Shanks y el algoritmo de Pollard-Strassen , requieren tiempo de orden. Además , el método de forma cuadrática de Shanks puede ejecutarse en tiempo de orden si la hipótesis de Riemann es verdadera . Entre los algoritmos probabilísticos, el líder de la factorización es un método de tamiz de campo numérico especial , que puede encontrar un divisor primo con una probabilidad de 1/2 en tiempo subexponencial . El algoritmo de Shor, utilizando las capacidades de las computadoras cuánticas, puede factorizar un número. no solo en tiempo polinomial, sino en un tiempo no mucho mayor que el tiempo de multiplicación de enteros (es decir, casi tan rápido como el propio cifrado). Por lo tanto, la implementación de una computadora cuántica escalable pondrá fin a la mayor parte de la protección criptográfica moderna. No se trata solo del esquema RSA, que se basa directamente en las complejidades de la factorización, sino también de otros esquemas similares que una computadora cuántica puede descifrar de manera similar. $METRO,$ $METRO.$ $METRO$ ${\ estilo de visualización M ^ {1/4}.}$ ${\ estilo de visualización M ^ {1/5}}$ $\exp \left(\left({\frac {32}{9}}\cdot \log M\right)^{1/3}\cdot (\log \log M)^{2/3} \Correcto).$

El algoritmo de Shor tiene un carácter probabilístico. La primera fuente de aleatoriedad está integrada en la reducción probabilística clásica de la factorización para encontrar el período de alguna función. La segunda fuente proviene de la necesidad de observar la memoria cuántica, que también da resultados aleatorios [1] .

Cómo funciona el algoritmo de Shor

La base del algoritmo de Shor: la capacidad de las unidades de información de las computadoras cuánticas -qubits- de tomar varios valores al mismo tiempo y estar en un estado de " entrelazamiento cuántico ". Por lo tanto, permite realizar cálculos en condiciones de economía de qubits. El principio de funcionamiento del algoritmo de Shor se puede dividir en 2 partes: la primera es la reducción clásica de la factorización para encontrar el período de una determinada función, la segunda es el hallazgo cuántico del período de esta función. Dejar:

METRO

- el número que queremos factorizar (no debe ser una potencia entera de un número impar);

norte

- el tamaño del registro de memoria que se utiliza (sin contar el volcado). El tamaño de bits de esta memoria es aproximadamente 2 veces el tamaño de . Más precisamente, ;

{\ estilo de visualización n = \ log _ {2} N}

METRO

M^{2}<N=2^{n}<2M^{2}

t

es un parámetro aleatorio tal que y (donde es el máximo común divisor ).

1<t<M

{\ estilo de visualización \ nombre del operador {gcd} (t, M) = 1}

{\ estilo de visualización \ nombre del operador {gcd}}

Tenga en cuenta que , , son fijos. El algoritmo de Shor utiliza una forma estándar de reducir el problema de expansión al problema de encontrar el período de una función para un número seleccionado al azar [2] . $t$ $norte$ $METRO$ $r$ $t$

La parte clásica del algoritmo

El mínimo tal que es el módulo de pedido $r$ $t^{r}\equiv 1\ {\mbox{mod}}\ M,$ $t$ $METRO.$

El orden es el periodo de la función donde $r$ $f(x)=t^{x}\ {\mbox{mod}}\ M,$ ${\ estilo de visualización x = 0,1,2,...,N-1.}$

Si puede calcularse eficientemente como una función de , entonces uno puede encontrar su propio divisor en el tiempo acotado por un polinomio con probabilidad para cualquier fijo . $r$ $t$ $METRO$ ${\ estilo de visualización \ log _ {2} M}$ $\geqslant 1-M^{{-m}}$ $metro$

Supongamos que para un periodo dado es par y satisface la condición $t$ $r$ $(r\equiv 0\ {\mbox{mod}}\ 2)$

t^{\frac {r}{2}}\no \equiv -1\ {\mbox{mod}}\ M.

Después

{\ estilo de visualización \ nombre del operador {gcd} (t ^ {\ frac {r} {2}} + 1, M)}

— propio divisor La función es computable en tiempo polinomial.

METRO.

{\ estilo de visualización \ nombre del operador {gcd}}

La probabilidad de que se cumpla esta condición donde es el número de primos impares distintos , por tanto, en este caso. Por lo tanto, es probable que se encuentre un buen valor en los intentos. El cálculo más largo en un intento es el cálculo [3] [4] . $\geqslant 1-{\frac {1}{2^{k-1))},$ $k$ $METRO$ $\geqslant {\frac {1}{2}}$ $t$ $\geqslant 1-M^{{-m}}$ ${\ estilo de visualización O (\ log M)}$ $t^{\frac{r}{2}}$

La parte cuántica del algoritmo

Para implementar la parte cuántica del algoritmo, el circuito computacional es un registro cuántico y . Inicialmente, cada uno de ellos consta de un conjunto de qubits en un estado booleano cero $2$ $X$ $Y$ ${\ estilo de visualización | 0 \ rangle.}$

El registro se usa para colocar los argumentos de la función El registro (auxiliar) se usa para colocar los valores de la función con el periodo a calcular. $X$ $X$ ${\ estilo de visualización f (x).}$ $Y$ $f(x)$ $r$

La computación cuántica consta de 4 pasos [5] :

primer paso En el primer paso utilizando la operación de Walsh-Hadamard, que es una transformación del qubit usando el operador, el estado inicial del registro se traduce en una superposición equiprobable de todos los estados booleanos . El segundo registro permanece en el estado Como resultado, se obtiene el siguiente estado para el sistema de dos registros: $H={\frac {1}{\sqrt {2))}{\begin{bmatriz}1&1\\1&-1\end{bmatriz)),$ $|0\ángulo\$ $X$ $norte$ $Y$ ${\ estilo de visualización | 0 \ rangle.}$ ${\frac {1}{\sqrt {N}}}\sum \limits _{x=0}^{N-1}|x,0\rangle .$

Segundo paso . Sea una transformación unitaria que se traduce en En el segundo paso se aplica una transformación unitaria al sistema de dos registros. Esto da como resultado el siguiente estado del sistema: $U_{f}$ $|x,0\ángulo$ ${\ estilo de visualización | x, f (x) \ rangle.}$

{\frac {1}{\sqrt {N))}\sum \limits _{x=0}^{N-1}|x,0\rangle \quad {\xrightarrow {U_{f)) }\quad {\frac {1}{\sqrt {N}}}\sum \limits _{x=0}^{N-1}|x,t^{x}\ {\mbox{mod}}\ M\ángulo ,

es decir, se forma una cierta relación entre los estados de ambos registros.

Tercer paso . Una transformada cuántica de Fourier es una transformación unitaria de un estado de un registro cuántico descrito por un vector de estado bidimensional de la forma en otro estado $norte$ $\sum \limits _{x=0}^{N-1}f(x)|x\rangle ,$ $\sum \limits _{k=0}^{N-1}{\tilde {f}}(k)|k\rangle \ :$

\mathrm {QFT} _{N}:\sum \limits _{x=0}^{N-1}f(x)|x\rangle \ \Rightarrow \sum \limits _{k=0} ^{N-1}{\tilde {f}}(k)|k\rangle \ ,

donde la amplitud de la transformada de Fourier tiene la forma

f(x)

{\tilde {f}}(k)={\frac {1}{N}}\sum \limits _{x=0}^{N-1}\exp(2\pi \ i\ kx /N)f(x).

En el plano bidimensional , la transformada de Fourier corresponde a una rotación de los ejes de coordenadas de 90°, lo que conduce a la transformación de la escala en la escala . En el tercer paso, se realiza la transformada de Fourier en el estado del primer registro, y resulta

x,k

X

k

{\frac {1}{N}}\sum \limits _{x=0}^{N-1}\sum \limits _{k=0}^{N-1}\exp(2\ pi \ i \ kx/N)|k,t^{x}\ {\mbox{mod}}\ M\rangle .

Cuarto paso . En el cuarto paso, el primer registro se mide en relación con la proyección ortogonal de la vista: $X$

|0,0\rangle \otimes I,\quad |1,1\rangle \otimes I,\quad \dots,\quad |N-1,N-1\rangle \otimes I,

donde es el operador de identidad en el espacio de Hilbert del segundo registro .

yo

Y

Como resultado, resulta con probabilidad [6] $|k,t^{k}\ {\mbox{mod}}\ M\rangle \$

\left|{\frac {1}{N}}\sum \limits _{x:\ t^{x}\equiv t^{k}\ {\mbox{mod}}\ M}\exp (2\pi\i\kx/N)\right|^{2}.

El resto de la ejecución se ejecuta en una computadora clásica:

Encuentre la mejor aproximación (desde abajo) a con denominador ${\frac{k}{N}}\$ $r'<M<{\sqrt {N}}:$ $\left|{\frac {k}{N}}\ -{\frac {d'}{r'}}\right|<{\frac {1}{2N}}.$

Intentemos en el papel : $r'$ $r$
- Si , entonces se debe calcular $r'\equiv 0\ {\mbox{mod}}\ 2$ $\operatorname {gcd} (t^{\frac {r'}{2}}\pm 1,M).$
- Si es impar o si es par, pero no se encuentra ningún divisor propio , entonces debe repetir la ejecución nuevamente con el mismo . En caso de falla, cambie y comience una nueva ejecución del algoritmo [3] [4] . $r'$ $r'$ $METRO$ $O(\log \log M)$ $t$ $t$

Hasta cierto punto, la determinación del período de una función mediante la transformada de Fourier es similar a la medición de las constantes de la red cristalina mediante difracción de rayos X o de neutrones. Para determinar el periodo , no se requiere calcular todos los valores, en este sentido, el problema es similar al problema de Deutsch , en el que es importante conocer no todos los valores de la función, sino solo algunos de sus valores . propiedades [6] . ${\ estilo de visualización r,}$ ${\ estilo de visualización f \ izquierda (x \ derecha).}$

Hallar el periodo de una función en el algoritmo

Sea una función con periodo desconocido $F$ ${\ estilo de visualización r:}$

F:|x,0\rangle \ \rightarrow |x,f(x)\rangle \ f:Z\rightarrow Z_{2^{m}}\ r<2^{n}.

Para determinar el periodo se requieren dos registros con tamaños y qubits, los cuales inicialmente deben estar en el estado ${\ estilo de visualización r,}$ $2n$ $metro$ ${\ estilo de visualización | 0,0 \ ángulo.}$

En la primera etapa, se realiza una superposición unilateral de todos los vectores base del primer registro utilizando un operador de la siguiente forma: $tu$

U|0,0\rangle \ =\sum \limits _{i=0}^{N-1}c_{i}|i,0\rangle \

, donde y

|c_{i}|={\frac{1}{\sqrt {N))}

{\ estilo de visualización N = 2^{2n}.}

Aquí se utiliza la pseudotransformación de Hadamard . Aplicando al estado actual, obtenemos: $H_{1}={\begin{bmatriz}2&1\\1&1\end{bmatriz}}$ $F$

|\psi \rangle =FH_{1}|0,0\rangle =F{\frac {1}{2^{n))}\sum \limits _{i=0}^{N-1 }|i,0\rangle ={\frac {1}{2^{n}}}\sum \limits _{i=0}^{N-1}|i,f(i)\rangle .

Midiendo el segundo registro con el resultado donde lleva al estado a ${\ Displaystyle k = f (s),}$ ${\ estilo de visualización s<r,}$

|\psi '\rangle =\sum \limits _{j=0}^{[N/r]-1}c_{j}'|rj+s,k\rangle ,\qquad

dónde

c_{j}'=\left[{\frac {N}{r}}\right]^{-1/2}.

Después de medir el estado, el primer registro consta solo de vectores base de la forma tal que para todo Por lo tanto, tiene un espectro homogéneo discreto. Es imposible obtener directamente el período o un múltiplo del mismo midiendo el primer registro, porque aquí hay una variable aleatoria. Aquí aplicamos la transformada discreta de Fourier de la forma $|\psi '\rango$ $|rj+s\ángulo$ $f(rj+s)=f(s)$ ${\ estilo de visualización j.}$ $r$ $s$

\mathrm {DFT:} |x\rangle \rightarrow {\frac {1}{\sqrt {N))}\sum \limits _{y=0}^{N-1}e^{{\ fracción {2\pi i}{N}}xy}|y\rangle

en el registro, ya que la probabilidad del espectro en el estado transformado es invariante con respecto al desplazamiento (solo se pueden transformar las fases, no los valores absolutos de las amplitudes).

|\psi ''\rangle =\mathrm {DFT} |\psi '\rangle =\sum \limits _{i=0}^{N-1}c_{i}''|i,k\ rango.

c_{i}''={\frac {\sqrt {r}}{N}}\sum \limits _{j=0}^{p-1}\exp \left({\frac {2 \pi i}{N}}i(jr+s)\right)={\frac {\sqrt {r}}{N}}e^{\varphi _{i}}\sum \limits _{j= 0}^{p-1}\exp \left({\frac {2\pi i}{N}}ijr\right),

donde y

\varphi _{i}=2\pi i{\frac {es}{N}}\quad

\quad p=\left[{\frac {N}{r}}\right].

Si es múltiplo de , entonces si es múltiplo de y en caso contrario. Incluso si no es una potencia de 2, el espectro muestra picos individuales con un período porque $N=2^{2n}$ $r$ $c_{i}''={\frac {e^{\varphi _{i))}{\sqrt {r))},$ $i$ ${\frac{N}{r)),$ $c_{i}''=0$ $r$ $|\psi ''\rango$ ${\frac{N}{r)),$

\lim _{n\to \infty }{\frac {1}{n}}\sum \limits _{k=0}^{n-1}e^{2\pi ik\alpha }={\begin {casos}1\ \ ,\alpha \in Z\\0\ \ ,\alpha \notin Z\\\end{casos}}

Para el primer registro se utilizan qubits cuando porque esto garantiza al menos elementos en la suma dada, y así el ancho de los picos será del orden $2n$ ${\ estilo de visualización r <2 ^ {n},}$ $2^{n}$ ${\ estilo de visualización O (1).}$

Si ahora calculamos el primer registro, obtenemos un valor cercano a donde se puede escribir como Esto se reduce a encontrar una aproximación donde para un número particular de un punto binario Para resolver este problema, se usan fracciones continuas. ${\ estilo de visualización c,}$ ${\frac {\lambda N}{r)),$ ${\ estilo de visualización \ lambda \ en Z_ {r}.}$ ${\frac {c}{N}}=c\cdot 2^{-2n}\approx {\frac {\lambda}{r)).$ ${\frac{a}{b)),$ $a,b<2^{n},$ $c\cdot 2^{-2n}.$

Dado que la forma de un número racional no es única, entonces u se define como si la probabilidad de que ambos números y sean primos fuera mayor que , por lo tanto, para que la probabilidad de éxito sea cercana a uno, solo se necesitan intentos [7] [5] . $\lambda$ $r$ ${\frac {a}{b}}={\frac {\lambda}{r)),$ ${\ estilo de visualización \ nombre del operador {gcd} (\ lambda, r) = 1.}$ $\lambda$ $r$ ${\ estilo de visualización {\ frac {1} {\ ln r}}$ $En)$

Logaritmo discreto

Otro problema matemático, el logaritmo discreto , a menudo utilizado para crear sistemas criptográficos asimétricos, también es vulnerable al algoritmo cuántico propuesto por Shor en el mismo artículo [8] .

Véase también

computadora cuántica

Notas

↑ Beckman, Chari, Devabhaktuni et al., 1996 .
↑ Valiev, 2004 , pág. 86-92.
↑ 12Feynman , 1986 .
↑ 12Feynman , 1982 .
↑ 12 Shor , 1997 .
↑ 1 2 Valiev, 2004 , pág. 81-92.
↑ Corto, 1994 .
↑ Shor P. Algorithms for Quantum Computation: Discrete Logarithms and Factoring // Foundations of Computer Science, Actas de 1994. , 35th Annual Symposium on - IEEE , 1994. - P. 124–134. - ISBN 0-8186-6580-7 - doi:10.1109/SFCS.1994.365700

Literatura

Feynman R. Simulación de física con computadoras (inglés) // Revista internacional de física teórica - Springer Science + Business Media , 1982. - Vol. 21, edición. 6/7.- Pág. 467-488. — ISSN 0020-7748 ; 1572-9575 - doi:10.1007/BF02650179
Feynman R. Computadoras mecánicas cuánticas (inglés) // Fundamentos de física / Gerard 't Hooft - Springer Science + Business Media , 1986. - Vol. 16, edición. 6.- Pág. 507-531. — ISSN 0015-9018 ; 1572-9516 - doi:10.1007/BF01886518
D B., AN C., S D., J P., Beckman D. , Chari A. N. , Devabhaktuni S. , Preskill J. Redes eficientes para la factorización cuántica // Phys . Rvdo. A - College Park, MD : Sociedad Estadounidense de Física , 1996. - vol. 54, edición. 2.- Pág. 1034-1063. — ISSN 2469-9926 ; 2469-9934 ; 2469-9942 - doi:10.1103/PHYSREVA.54.1034 - PMID:9913575 - arXiv:quant-ph/9602016
Shor P. Algorithms for Quantum Computation: Discrete Logarithms and Factoring (English) // Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on - IEEE , 1994. - P. 124–134. - ISBN 0-8186-6580-7 - doi:10.1109/SFCS.1994.365700
Algoritmos de tiempo polinomial Shor PW para factorización prima y logaritmos discretos en una computadora cuántica // Fundamentos de informática: publicaciones de conferencias. - 1997. - Pág. 1484-1509.
Valiev K. A. , Kokin A. A. Computadoras cuánticas: esperanzas y realidad. - Izhevsk: RHD, 2004. - 320 p.

Enlaces

Algoritmos Shor PW para computación cuántica: logaritmos discretos y factorización // Fundamentos de informática: publicaciones de conferencias. - 1994. - S. 124-134 . - ISBN 0-8186-6580-7 . -doi : 10.1109/ SFCS.1994.365700.

Algoritmos de tiempo polinomial Shor PW para factorización prima y logaritmos discretos en una computadora cuántica // Fundamentos de informática: publicaciones de conferencias. - 1997. - S. 1484-1509 .

Código fuente para un simulador de computadora cuántica en C++ y una implementación completa del algoritmo de Shor, incluido un esquema de exponenciación modular reversible, con una descripción detallada y diagramas de puertas cuánticas

Algoritmos cuánticos
Algoritmo de Shor algoritmo de Grover Algoritmo Deutsch-Yozhi problema feynman Algoritmo de Zalka-Wiesner recocido cuántico

informatica cuantica

Conceptos generales

comunicaciones cuánticas

canal cuántico
- red cuántica
criptografía cuántica
- Distribución de clave cuántica
Teletransportación de energía cuántica
teletransportación cuántica
Codificación cuántica ultradensa
LOCC
destilación cuántica

Algoritmos cuánticos

simulador cuántico
Algoritmo Deutsch-Yozhi
Algoritmo de Bernstein-Wazirani
algoritmo de Grover
Transformada cuántica de Fourier
Algoritmo de Shor
el problema de simon
Algoritmo de estimación de fase cuántica
Algoritmo de computación cuántica
recocido cuántico
Enfriamiento algorítmico
Algoritmo cuántico para resolver un sistema de ecuaciones lineales
ganancia de amplitud

Teoría de la complejidad cuántica

Modelos de computación cuántica

circuito cuántico
- puerta cuántica
Computadora cuántica unilateral
- grupo
Computación cuántica adiabática
Computadora cuántica topológica

Prevención de decoherencia

Corrección de errores cuánticos
Códigos de estabilización
Formalismo de estabilización
Código convolucional cuántico

Implementaciones físicas

óptica cuántica	Electrodinámica cuántica de cavitación Electrodinámica cuántica de contorno Computación cuántica basada en óptica lineal Protocolo KLM Muestreo bosónico
átomos superfríos	Computadora cuántica de iones absorbidos rejilla óptica
basado en la espalda	Computadora cuántica basada en resonancia magnética nuclear La computadora cuántica de Kane Computadora cuántica perdida - DiVincenzo centro NV
Computadoras cuánticas superconductoras	qubit de carga qubit de transmisión qubit de fase Transmón