Algoritmo de Shor

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

algoritmo cuántico para la factorización entero

Algoritmo de Shor es un algoritmo de computadora cuántica para encontrar los factores primos de un número entero. Fue desarrollado en 1994 por el matemático estadounidense Peter Shor.

En una computadora cuántica, para factorizar un entero $N$ , el algoritmo de Shor funciona en tiempo polinomio, lo que significa que el tiempo tomado es polinomio en ${displaystyle log N}$ , el tamaño del entero dado como entrada. Específicamente, toma puertas cuánticas de orden ${displaystyle O!left((log N)^{2}(log log N)(log log log N)right)}$ usando la multiplicación rápida, o incluso ${displaystyle O!left((log N)^{2}(log log N)right)}$ utilizando el algoritmo de multiplicación asintomáticamente más rápido que se conoce actualmente debido a Harvey y Van Der Hoven, demostrando así que el problema de factorización entero puede ser resuelto eficientemente en un equipo cuántico y es consecuente en la clase de complejidad BQP. Esto es casi exponencialmente más rápido que el algoritmo de factorización clásica más eficiente, el sieve de campo de número general, que funciona en tiempo sub-exponencial: ${displaystyle O!left(e^{1.9(log N)^{1/3}(log log N)^{2/3}}right)}$ . La eficiencia del algoritmo de Shor se debe a la eficiencia de la transformación quantum Fourier, y a la exponencia modular por repetidos escuadrones.

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 criptográficos de clave pública, como

The RSA scheme
El intercambio de claves de Finite Field Diffie-Hellman
Elliptic Curve Diffie-Hellman intercambio clave

RSA se basa en la suposición de que la factorización de números enteros grandes es computacionalmente intratable. Por lo que se sabe, esta suposición es válida para las computadoras clásicas (no cuánticas); no se conoce ningún algoritmo clásico que pueda factorizar números enteros en tiempo polinomial. Sin embargo, el algoritmo de Shor muestra que la factorización de números enteros es eficiente en una computadora cuántica ideal, por lo que puede ser factible vencer a RSA construyendo una computadora cuántica grande. También fue un poderoso motivador para el diseño y la construcción de computadoras cuánticas y para el estudio de nuevos algoritmos de computadoras cuánticas. También ha facilitado la investigación sobre nuevos criptosistemas que son seguros desde las computadoras cuánticas, denominados colectivamente criptografía poscuántica.

En 2001, un grupo de IBM demostró el algoritmo de Shor. ${displaystyle 15}$ en ${displaystyle 3times 5}$ , utilizando una aplicación NMR de un equipo cuántico con $7$ Cubitos. Después de la implementación de IBM, dos grupos independientes implementaron el algoritmo de Shor usando qubits fotonicos, enfatizando que se observó un enredo multi-qubit al ejecutar los circuitos de algoritmos de Shor. En 2012, la factorización ${displaystyle 15}$ se realizó con codos de estado sólido. Más tarde, en 2012, la factorización ${displaystyle 21}$ se logró. En 2019 se intentó determinar el número ${displaystyle 35}$ usando el algoritmo de Shor en un sistema Q IBM One, pero el algoritmo falló debido a errores acumulativos. Aunque los números más grandes han sido factorizados por ordenadores cuánticos usando otros algoritmos, estos algoritmos son similares a la comprobación clásica de la fuerza bruta de factores, por lo que a diferencia del algoritmo de Shor, no se espera que puedan realizar mejor que los algoritmos de factorización clásica.

Procedimiento

El problema que estamos tratando de resolver es, dado un número compuesto $N$ , para encontrar un divisor no-trivial $N$ (un divisor estrictamente entre $1$ y $N$ ). Antes de intentar encontrar tal divisor, si hay alguna duda de si $N$ es compuesto o primo, uno puede utilizar algoritmos de prueba de primalidad relativamente rápido para verificar que $N$ es de hecho compuesto, aunque esto no es parte del algoritmo de Shor.

El algoritmo de Shor consta de dos partes:

Una reducción, que puede hacerse en una computadora clásica, del problema de factorización al problema de la determinación del orden.
Un algoritmo cuántico para resolver el problema de determinación de pedidos.

El objetivo del algoritmo es encontrar una raíz cuadrada no-trivial $b$ de $1$ modulo $N$ que es diferente de $1$ y ${displaystyle -1}$ , porque entonces

{displaystyle b^{2}-1=(b+1)(b-1)=mN}

para un entero no cero $m$ que nos da dos divisores distintos ${displaystyle gcd(N,b+1)}$ y ${displaystyle gcd(N,b-1)}$ de $N$ . Esta idea es similar a otros algoritmos de factorización, como el tamiz cuadrático, y una explicación más detallada se puede encontrar en la sección Explicación a continuación. Antes de comenzar el algoritmo, es imperativo comprobar $N$ para ser extraño (otros $2$ es un divisor) y no ser cualquier poder de un entero (otros que el entero es un divisor), para garantizar la existencia de una raíz cuadrada no-trivial $b$ de $1$ modulo $N$ .

A su vez, encontrar tal $b$ se reduce a encontrar un elemento $a$ como parámetro en una función de entero, tal que la función tiene un período uniforme con una determinada propiedad adicional (como se explica a continuación, se requiere que la condición del Paso 6 de la parte clásica no se mantenga). El algoritmo cuántico se utiliza para encontrar el período de elementos elegidos aleatoriamente $a$ , como este es un problema difícil en un ordenador clásico.

Parte clásica

Elija un número aleatorio $<math alttext="{displaystyle 1<a1.a.N{displaystyle 1 se hizo realidad <img alt="{displaystyle 1<a$ .
Computación ${displaystyle K=gcd(a,N)}$ , el mayor divisor común $a$ y $N$ . Esto puede hacerse usando el algoritmo de Euclidean.
Si ${displaystyle Kneq 1}$ , entonces $K$ es un factor notrivial $N$ Así que hemos terminado.
De lo contrario, utilice la subrutina de determinación del período cuántico (bajo) para encontrar $r$ , que denota el período de la siguiente función:
${displaystyle f(x)=a^{x}({bmod {N}}).}$
Equivalentemente, $r$ es el entero positivo más pequeño que satisfice ${displaystyle a^{r}equiv 1({bmod {N}}}$ ).
Si $r$ es extraño, luego vuelve al paso 1.
Si ${displaystyle a^{r/2}=-1{bmod {N}}}$ Luego vuelve al paso 1.
De lo contrario, ambos ${displaystyle gcd(a^{r/2}+1,N)}$ o ${displaystyle gcd(a^{r/2}-1,N)}$ son factores notriviales $N$ Así que hemos terminado.

Por ejemplo: Dado ${displaystyle N=15}$ , ${displaystyle a=7}$ , y ${displaystyle r=4}$ , es decir, ${displaystyle {bmod {(}}1,15)={bmod {(}}7^{4},15)={bmod {(}}7^{8},15),}$ tenemos ${displaystyle gcd(7^{2}pm 1,15)=gcd(49pm 1,15)}$ , donde ${displaystyle gcd(48,15)=3}$ y ${displaystyle gcd(50,15)=5}$ . Para $N$ que es un producto de dos primos distintos, $p$ y $q$ , ${displaystyle varphi (N)=(p-1)(q-1)}$ , que para ${displaystyle N=15}$ es $8$ , y $r$ divideciones $8$ .

Parte cuántica: subrutina de búsqueda de período

Subroutina cuántica en el algoritmo de Shor

Los circuitos cuánticos utilizados para este algoritmo son personalizados diseñados para cada elección de $N$ y cada elección del azar $a$ que tienen la relación ${displaystyle f(x)=a^{x}{bmod {N}}}$ . Valor dado $N$ , un valor ${displaystyle Q=2^{q}}$ es elegido tal que $<math alttext="{displaystyle N^{2}leq QN2≤ ≤ Q.2N2{displaystyle N^{2}leq Qse2N^{2}<img alt="{displaystyle N^{2}leq Q$ . Tal valor $Q$ implica que $N}" xmlns="http://www.w3.org/1998/Math/MathML">Qr■N{displaystyle {dfrac {} {}} {fn}}} {fn}} {fn}} {fn}}} {fn}}}}}}} {fnK}}}} {fn}}}}}}}} {fn}}}}}}}}}}N}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4f4e972c4f4ec458f417429d60174678f0218040" style="vertical-align: -1.838ex; width:7.837ex; height:5.343ex;"/>$ . Los registros de bits de entrada y salida almacenarán superposiciones de valores de ${displaystyle 0 }$ a ${displaystyle Q-1}$ . Por lo tanto, estos registros tienen $q$ cada uno. Usando lo que podría parecer ser el doble de cubitos como garantías necesarias que hay al menos $N$ diferentes valores de $x$ que producen lo mismo $f(x)$ , incluso como el período $r$ enfoques ${displaystyle {dfrac {N}{2}}}$ . A continuación se utiliza la notación de punta de sujetador para denotar estados cuánticos.

Proceda de la siguiente manera:

Initialize the registers to
${displaystyle {frac {1}{sqrt {Q}}}sum _{x=0}^{Q-1}|xrangle =left({frac {1}{sqrt {2}}}sum _{x_{1}=0}^{1}|x_{1}rangle right)otimes cdots otimes left({frac {1}{sqrt {2}}}sum _{x_{q}=0}^{1}|x_{q}rangle right).}$

where $otimes$ denotes the tensor product.
This initial state is a superposition of $Q$ states, and is obtained by generating $q$ independent qubits, each an equal superposition of ${displaystyle 0 }$ and $1$ states. We can accomplish this by initializing the qubits to the zero-position, and then applying a Hadamard gate to each of the $q$ qubits, where ${displaystyle 2^{q}=Q}$ . This process is called the Hadamard transform.
Construct $f(x)$ as a quantum function and apply it to the above state, to obtain
${displaystyle U_{f}|x,0^{n}rangle =|x,f(x)rangle }$

${displaystyle U_{f}{frac {1}{sqrt {Q}}}sum _{x=0}^{Q-1}|x,0^{n}rangle ={frac {1}{sqrt {Q}}}sum _{x=0}^{Q-1}|x,f(x)rangle }$
Note: ${displaystyle f(x)=a^{x}{bmod {N}}}$ . This is still a superposition of $Q$ states. However, the ${displaystyle q+n}$ qubits, i.e, the $q$ input qubits and $n$ ( ${displaystyle >{log _{2}}(N)}$ ) output qubits, are now entangled or not separable, as the state cannot be written as a tensor product of states of individual qubits. Importantly, the value containing the $r$ we are looking for is now stored in the phase of the input qubits $x$ as a result of "phase kickback", where using qubits as control inputs to unitary gates alters the relative phase of the control qubits.
Apply the inverse quantum Fourier transform to the input register. This transform (operating on a superposition of Q = 2 q {displaystyle Q=2^{q}} ${displaystyle Q=2^{q}}$ states) uses a Q {displaystyle Q} $Q$ -th root of unity such as ω = e 2 π i Q {displaystyle omega =e^{frac {2pi i}{Q}}} ${displaystyle omega =e^{frac {2pi i}{Q}}}$ to distribute the amplitude of any given | x ⟩ {displaystyle |xrangle } $| x rangle$ state equally among all Q {displaystyle Q} $Q$ of the | y ⟩ {displaystyle |yrangle } ${displaystyle |yrangle }$ states, and to do so in a different way for each different x {displaystyle x} $x$ . We thus obtain
${displaystyle {U_{operatorname {QFT} }}(|xrangle)={frac {1}{sqrt {Q}}}sum _{y=0}^{Q-1}omega ^{xy}|yrangle.}$
This leads to the final state
${displaystyle {frac {1}{Q}}sum _{x=0}^{Q-1}sum _{y=0}^{Q-1}omega ^{xy}|y,f(x)rangle.}$
Now, we reorder this sum as
${displaystyle {frac {1}{Q}}sum _{z=0}^{N-1}sum _{y=0}^{Q-1}left[sum _{xin {0,ldotsQ-1};~f(x)=z}omega ^{xy}right]|y,zrangle.}$
This is a superposition of many more than Q {displaystyle Q} $Q$ states, but many fewer than Q 2 {displaystyle Q^{2}} ${displaystyle Q^{2}}$ states, as there are fewer than Q {displaystyle Q} $Q$ distinct values of z = f ( x ) {displaystyle z=f(x)} ${displaystyle z=f(x)}$ . Let
- ${displaystyle omega =e^{frac {2pi i}{Q}}}$ be a $Q$ -th root of unity,
- $r$ be the period of $f$ ,
- ${displaystyle x_{0}}$ be the smallest of the ${displaystyle xin {0,ldotsQ-1}}$ for which ${displaystyle f(x)=z}$ (we have ${displaystyle x_{0}<r}$ ), and
- write ${displaystyle m-1=leftlfloor {frac {Q-x_{0}-1}{r}}rightrfloor }$
- $b$ indexes these $x$ , running from ${displaystyle 0 }$ to ${displaystyle m-1}$ , so that ${displaystyle x_{0}+rb<Q}$ .
Then ω r y {displaystyle omega ^{ry}} ${displaystyle omega ^{ry}}$ is a unit vector in the complex plane ( ω {displaystyle omega } $omega$ is a root of unity, and r {displaystyle r} $r$ and y {displaystyle y} $y$ are integers), and the coefficient of 1 Q | y , z ⟩ {displaystyle {dfrac {1}{Q}}left|y,zrightrangle } ${displaystyle {dfrac {1}{Q}}left|y,zrightrangle }$ in the final state is
${displaystyle sum _{xin {0,ldotsQ-1};~f(x)=z}omega ^{xy}=sum _{b=0}^{m-1}omega ^{(x_{0}+rb)y}=omega ^{x_{0}y}sum _{b=0}^{m-1}omega ^{rby}.}$
Each term in this sum represents a different path to the same result, and quantum interference occurs — constructive when the unit vectors ω r y b {displaystyle omega ^{ryb}} ${displaystyle omega ^{ryb}}$ point in nearly the same direction in the complex plane, which requires that ω r y {displaystyle omega ^{ry}} ${displaystyle omega ^{ry}}$ point along the positive real axis.
Perform a measurement. We obtain some outcome $y$ in the input register and some outcome $z$ in the output register. As $f$ is periodic, the probability of measuring some state ${displaystyle |y,zrangle }$ is given by
${displaystyle mathrm {Pr} (|y,zrangle)=left|{frac {1}{Q}}sum _{xin {0,ldotsQ-1};~f(x)=z}omega ^{xy}right|^{2}={frac {1}{Q^{2}}}left|sum _{b=0}^{m-1}omega ^{(x_{0}+rb)y}right|^{2}={frac {1}{Q^{2}}}|omega ^{x_{0}y}|^{2}left|sum _{b=0}^{m-1}omega ^{bry}right|^{2}}$

${displaystyle ={frac {1}{Q^{2}}}left|sum _{b=0}^{m-1}omega ^{bry}right|^{2}={frac {1}{Q^{2}}}left|{frac {omega ^{mry}-1}{omega ^{ry}-1}}right|^{2}={frac {1}{Q^{2}}}{frac {sin ^{2}({frac {pi mry}{Q}})}{sin ^{2}({frac {pi ry}{Q}})}}}$
Analysis now shows that this probability is higher the closer the unit vector ${displaystyle omega ^{ry}}$ is to the positive real axis, or the closer ${displaystyle {dfrac {yr}{Q}}}$ is to an integer. Unless $r$ is a power of $2$ , it will not be a factor of $Q$ .
Since y r Q {displaystyle {frac {yr}{Q}}} ${displaystyle {frac {yr}{Q}}}$ is close to some integer c {displaystyle c} $c$ , the known value y Q {displaystyle {dfrac {y}{Q}}} ${displaystyle {dfrac {y}{Q}}}$ is close to the unknown value c r {displaystyle {dfrac {c}{r}}} ${displaystyle {dfrac {c}{r}}}$ . Performing [classical] continued fraction expansion on y Q {displaystyle {dfrac {y}{Q}}} ${displaystyle {dfrac {y}{Q}}}$ allows us to find approximations d s {displaystyle {dfrac {d}{s}}} ${displaystyle {dfrac {d}{s}}}$ of it that satisfy two conditions:
1. ${displaystyle s<N}$ .
2. ${displaystyle left|{dfrac {y}{Q}}-{dfrac {d}{s}}right|<{dfrac {1}{2Q}}}$ .
Given these multiple conditions (and assuming d s {displaystyle {dfrac {d}{s}}} ${displaystyle {dfrac {d}{s}}}$ is irreducible), s {displaystyle s} $s$ is very likely to be the appropriate period r {displaystyle r} $r$ , or at least a factor of it.
Check (classically) if ${displaystyle f(x)=f(x+s)Leftrightarrow a^{s}equiv 1{bmod {N}}}$ . If so, then we are done.
Otherwise, (classically) obtain more candidates for $r$ by using multiples of $s$ , or by using other $s$ with ${displaystyle {dfrac {d}{s}}}$ near ${displaystyle {dfrac {y}{Q}}}$ . If any candidate works, then we are done.
Otherwise, try again starting from step 1 of this subroutine.

Explicación del algoritmo

El algoritmo se compone de dos partes. La primera parte del algoritmo convierte el problema de factorización en el problema de encontrar el período de una función y puede implementarse de manera clásica. La segunda parte encuentra el período utilizando la transformada cuántica de Fourier y es responsable de la aceleración cuántica.

Raíz cuadrada no trivial de [1 módulo N]

El algoritmo de Shor se acerca a encontrar una raíz cuadrada no-trivial $1$ modulo $N$ ; Es decir, una solución

{displaystyle b^{2}equiv 1{bmod {N}}}

Donde ${displaystyle bnot equiv pm 1{bmod {N}}}$ .

If such $b$ existe, afirmamos que ${displaystyle d=gcd(b-1,N)}$ es un factor adecuado $N$ , es decir, ${displaystyle dneq 1,N}$ . De hecho, si

${displaystyle d=N}$ , entonces $N$ divideciones $b-1$ Así que ${displaystyle bequiv 1{bmod {N}}}$ , que va en contra de la construcción de $b$ . Si, por otro lado, ${displaystyle d=gcd(b-1,N)=1}$ , entonces por la identidad de Bézout, hay enteros ${displaystyle u,v}$ tales que

{displaystyle (b-1)u+Nv=1.}

Multiplicar ambos lados por ${displaystyle b+1}$ , obtenemos

{displaystyle (b^{2}-1)u+N(b+1)v=b+1.}

As $N$ divideciones ${displaystyle b^{2}-1}$ , encontramos que $N$ divideciones ${displaystyle b+1}$ Así que ${displaystyle bequiv -1{bmod {N}}}$ , nuevamente contradiciendo la construcción de $b$ .

Por lo tanto, $d$ es el factor adecuado requerido $N$ . Del mismo modo, puede probarse que ${displaystyle gcd(b+1,N)}$ es también un factor adecuado $N$ .

Para tal raíz cuadrada no-trivial $1$ modulo $N$ para existir, notar que ${displaystyle -1equiv 1{bmod {2}}}$ , y para cualquier poder de una prima extraña ${displaystyle N=p^{n}}$ , no hay raíz cuadrada no-trivial $1$ modulo $N$ Para cualquier ${displaystyle (b+1)(b-1)=mp^{n},}$ o ${displaystyle b-1}$ o ${displaystyle b+1}$ tiene que ser un múltiple de ${displaystyle N=p^{n}}$ .

Por lo tanto, para que el algoritmo de Shor funcione, necesitamos $N$ para ser extraño (otros $2$ es un divisor) y no ser cualquier poder de una prima extraña (otros que el primo es un divisor). Podemos comprobar que no hay raíces enteros ${displaystyle {sqrt[{k}]{N}}}$ para ${displaystyle 2leq kleq {log _{3}}(N)}$ , y si $N$ no es un poder de ningún entero, no es un poder de ninguna prima extraña. Aquí, el límite superior para el entero $k$ que necesitamos comprobar es determinado por ${displaystyle {sqrt[{k}]{N}}geq 3}$ , desde $N$ para ser extraño, ${displaystyle {sqrt[{k}]{N}}}$ no puede ser $2$ . Este cheque, sin embargo, no puede descartar que $N$ puede ser un principio extraño en sí mismo, que sólo puede ser descartado por algoritmos de prueba de primalidad.

Dado que $N$ es extraño y no cualquier poder de una prima extraña, basado en el teorema fundamental de la aritmética, podemos asumir que $N$ es el producto de dos enteros coprime más grande que $2$ () ${displaystyle N=n_{1}n_{2}}$ y $2,,gcd(n_{1},n_{2})=1}" xmlns="http://www.w3.org/1998/Math/MathML">n1,n2■2,gcd()n1,n2)=1{displaystyle n_{1},n_{2}]2,,gcd(n_{1},n_{2})=1}2,,gcd(n_{1},n_{2})=1}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9ace1c0f382cbb16276248de906f6e03640b48d2" style="vertical-align: -0.838ex; width:27.103ex; height:2.843ex;"/>$ ). De las cuatro combinaciones de elegir más signo y signo menos en las ecuaciones enteros ${displaystyle x=m_{1}n_{1}pm 1=m_{2}n_{2}pm 1}$ , basado en el teorema restante chino y $2}" xmlns="http://www.w3.org/1998/Math/MathML">n1,n2■2{displaystyle No.2}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f2438439d5af04ba5dca712ba3dc5c4964d28e31" style="vertical-align: -0.671ex; width:10.193ex; height:2.509ex;"/>$ , hay al menos cuatro raíces cuadradas distintas $1$ modulo $N$ , y por lo tanto existen al menos dos raíces cuadradas distintas no-triviales. De hecho, son las soluciones a ${displaystyle b'=m_{1}n_{1}+1=m_{2}n_{2}-1}$ y ${displaystyle b''=m_{1}n_{1}-1=m_{2}n_{2}+1}$ .

Obtención de factores del periodo

Los enteros menos que $N$ y coprime con $N$ la forma grupo multiplicativo de enteros modulo $N$ , que es un grupo abeliano finito $G$ . El tamaño de este grupo es dado por ${displaystyle varphi (N)}$ . Al final del paso 3, tenemos un entero $a$ en este grupo. Como el grupo es finito, $a$ debe tener una orden finita $r$ , que es el más pequeño número positivo tal que

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

Esta es la orden $r$ del subgrupo cíclico finitoa. ${displaystyle (mathbb {Z} _{N})^{times }}$ , que es el más pequeño número positivo $r$ para la cual ${displaystyle a^{x+r}{bmod {N}}equiv a^{x}{bmod {N}}}$ . Desde $a$ y $N$ son coprime, por el teorema totiente de Euler, $r$ debe existir, y dividir ${displaystyle varphi (N)}$ , donde $varphi$ denota la función totiente de Euler.

Por lo tanto, $N$ divideciones ${displaystyle a^{r}-1}$ (también escrito ${displaystyle Nmid a^{r}-1}$ ). Supongamos que somos capaces de obtener $r$ y eso es incluso. (Si) $r$ es extraño, entonces por paso 5, tenemos que reiniciar el algoritmo con un número aleatorio diferente $a$ ) Ahora ${displaystyle bequiv a^{r/2}{bmod {N}}}$ es una raíz cuadrada $1$ modulo $N$ que es diferente de $1$ . Esto es porque $r$ es el orden de $a$ modulo $N$ Así que ${displaystyle a^{r/2}not equiv 1{bmod {N}}}$ , o el orden de $a$ en este grupo sería ${displaystyle {dfrac {r}{2}}}$ . Si ${displaystyle a^{r/2}equiv -1{bmod {N}}}$ , entonces por paso 6, tenemos que reiniciar el algoritmo con un número aleatorio diferente $a$ .

Finalmente, debemos golpear a un $a$ de orden $r$ dentro $G$ tales que ${displaystyle bequiv a^{r/2}not equiv pm 1{bmod {N}}}$ . Esto es porque tal $b$ es una raíz cuadrada $1$ modulo $N$ de otros $1$ y ${displaystyle -1}$ , cuya existencia está garantizada por el teorema restante chino, como el número impar $N$ no es un poder primario.

Encontrar el período

El algoritmo de búsqueda de períodos de Shor se basa en gran medida en la capacidad de una computadora cuántica para estar en muchos estados simultáneamente.

Los físicos llaman a este comportamiento una "superposición" de estados. Para calcular el período de una función $f$ , evaluamos la función en todos los puntos simultáneamente.

La física cuántica no nos permite acceder directamente a toda esta información. Una medición sólo dará uno de todos los valores posibles, destruyendo a todos los demás. Si no fuera por el teorema de no cerrar, primero podríamos medir $f(x)$ sin medición $x$ , y luego hacer unas cuantas copias del estado resultante (que es una superposición de estados que todos tienen la misma $f(x)$ ). Medición $x$ sobre estos estados proporcionaría diferentes $x$ valores que dan el mismo $f(x)$ , conduce al período. Debido a que no podemos hacer copias exactas de un estado cuántico, este método no funciona. Por lo tanto, tenemos que transformar cuidadosamente la superposición a otro estado que devolverá la respuesta correcta con alta probabilidad. Esto se logra por la transformación cuántica Fourier.

Shor tuvo que resolver tres problemas de "ejecución". Todos ellos tenían que ser implementados "rápido", lo que significa que pueden ser implementados con una serie de puertas cuánticas que es polinomio en ${displaystyle log N}$ .

Crear una superposición de estados. Esto se puede hacer aplicando las puertas de Hadamard a todos los bits en el registro de entrada. Otro enfoque sería utilizar la transformación quantum Fourier (ver más abajo).
Implementar la función $f$ como una transformación cuántica. Para lograrlo, Shor usó repetidos escuadras para su transformación modular de exponentes. Es importante señalar que este paso es más difícil de implementar que la transformación quantum Fourier, ya que requiere qubits auxiliares y sustancialmente más puertas para lograr.
Realizar un quantum Fourier transform. Mediante el uso de puertas de rotación controladas y puertas Hadamard, Shor diseñó un circuito para la transformación quantum Fourier (con ${displaystyle Q=2^{q}}$ ) que utiliza sólo ${displaystyle {dfrac {q(q-1)}{2}}=O!left((log Q)^{2}right)}$ Puertas.

Después de todas estas transformaciones, una medición dará una aproximación al período $r$ . Para la simplicidad asume que hay un $y$ tales que ${displaystyle {dfrac {yr}{Q}}}$ es un entero. Entonces la probabilidad de medir $y$ es $1$ . Para ver esto, notamos que entonces

{displaystyle e^{-{frac {2pi ibyr}{Q}}}=1}

para todos los enteros $b$ . Por lo tanto, la suma cuyo cuadrado nos da la probabilidad de medir $y$ será ${displaystyle {dfrac {Q}{r}}}$ , como $b$ las tomas duramente ${displaystyle {dfrac {Q}{r}}}$ valores y por lo tanto la probabilidad es ${displaystyle {dfrac {1}{r^{2}}}}$ . Hay $r$ valores posibles $y$ tales que ${displaystyle {dfrac {yr}{Q}}}$ es un entero, y también $r$ posibilidades de ${displaystyle f(x_{0})}$ , por lo que las probabilidades suma a $1$ .

La rutina de determinación del período puede considerarse una variación del algoritmo de estimación de fase cuántica más general para determinar el valor eigenvalo de un unitario correspondiente a un eigenvector. En el caso de la rutina de determinación del período utilizada en el Algoritmo de Shor, el módulo en cuestión es la multiplicación modular por el mod base elegido $N$ . Mientras que la base computacional $|1rangle$ no es un eigenvector de este unitario, es una superposición uniforme de su $r$ eigenvectores y por lo tanto la medición dará la fase del eigenvalue para uno de los eigenvectores. Puesto que no todas esas fases pueden utilizarse para extraer el período, es posible que sean necesarias los registros de la subrutina.

El cuello de botella

El cuello de botella de Shor es una exponencia modular cuántica, que es mucho más lenta que la transformación quantum Fourier y el procesamiento previo/post clásico. Hay varios enfoques para construir y optimizar circuitos para la exponencia modular. El enfoque más simple y (actualmente) más práctico es imitar los circuitos aritméticos convencionales con puertas reversibles, empezando por los aditivos de carga madura. Conocer la base y el módulo de exponencia facilita nuevas optimizaciones. Los circuitos reversibles suelen utilizar en el orden $n^{3}$ puertas para $n$ Cubitos. Técnicas alternativas mejorar asintomáticamente los recuentos de las puertas mediante transformaciones quantum Fourier, pero no son competitivos con menos de 600 codos debido a altas constantes.

Logaritmos discretos

Dado un grupo $G$ con orden $p$ y generador $g in G$ Supongo que sabemos que ${displaystyle x=g^{r}in G}$ , para algunos ${displaystyle rin mathbb {Z} _{p}}$ , y queremos computar $r$ , que es el logaritmo discreto: ${displaystyle r={log _{g}}(x)}$ . Considere el grupo abeliano ${displaystyle mathbb {Z} _{p}times mathbb {Z} _{p}}$ , donde cada factor corresponde a la adición modular de valores. Ahora, considere la función

{displaystyle fcolon 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, como $f$ corresponde a un homomorfismo grupal. El núcleo corresponde a los múltiples ${displaystyle (r,1)}$ . Así que, si podemos encontrar el núcleo, podemos encontrar $r$ . Existe un algoritmo cuántico para resolver este problema. Este algoritmo es, como el algoritmo de determinación de factores, debido a Peter Shor y ambos se implementan creando una superposición a través de las puertas de Hadamard, seguido de la implementación $f$ como una transformación cuántica, seguida finalmente por una transformación quantum Fourier. Debido a esto, el algoritmo cuántico para computar el logaritmo discreto también se denomina ocasionalmente "Shor's Algorithm".

El problema de búsqueda de pedidos también se puede considerar como un problema de subgrupo oculto. Para ver esto, considere el grupo de enteros bajo adición, y para un dado ${displaystyle ain mathbb {Z} }$ tal que: ${displaystyle a^{r}=1}$ , la función

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

Para cualquier grupo abeliano finito G, existe un algoritmo cuántico para resolver el subgrupo oculto para G en tiempo polinomial.

Contenido relacionado

Más resultados...