Ayuda del algoritmo de factorización de Shor

Tengo un pequeño problema para comprender completamente los pasos finales del algoritmo de factorización de Shor.

Dada una que queremos factorizar, elegimos una aleatoria que tiene el orden . $N$ $x$ $r$

El primer paso consiste en configurar los registros y aplicar el operador Hadamard. El segundo paso se aplica un operador lineal. El tercer paso se mide el segundo registro (creo que este paso se puede realizar más tarde). El cuarto paso, la transformada discreta de Fourier se aplica al primer registro. Luego medimos el primer registro.

Aquí es donde estoy un poco brumoso:

Obtenemos una medida en la forma . $\mid j , x^k \textrm{mod} N \rangle$

A partir de esto podemos encontrar los convergentes de la fracción , los convergentes son posibles valores del orden . Aquí, ¿simplemente intentamos todos los convergentes y si no encontramos como uno de los convergentes, simplemente comenzamos de nuevo? $\frac{j}{2^q}$ $r$ $< N$ $r$

Además, ¿cómo difiere la probabilidad de los posibles valores ? Por lo que veo, todos deberían tener la misma probabilidad, pero el documento de Shor dice que este no es el caso. $j$

Solo un poco confundido ya que algunos periódicos parecen decir cosas diferentes.

Gracias.

quantum-computing Callum
fuente

@ Peter Shor podría incluso ayudarte con este.

Dave Clarke

Desde que hice estas preguntas, creo que lo entiendo mejor. Para aclarar para aquellos que están interesados, obtenemos una medida en la forma

∣ j, x^{k} \mod N ⟩

$\mid j , x^k \mod N \rangle$ donde todo lo que necesitamos es la

j

$j$ . El valor

j

$j$ se puede escribir como

j = 2^{q} k / r

$j= 2^q k/ r$ dividiendo entre

2^{q}

$2^q$ obtenemos

k / r

$k/r$ y de esto podemos encontrar sus convergentes, el denominador

< N

$< N$ de un convergente es un posible valor de

r

$r$ , si No es el algoritmo se ejecuta de nuevo. La probabilidad de encontrar

j

$j$ se basa en una suma que depende del valor de

2^{q}

$2^q$ y cuál es el período

r

$r$ .

Callum

Respuestas:

A partir de esto podemos encontrar los convergentes de la fracción , los convergentes son valores posibles del orden Aquí, ¿simplemente intentamos todos los convergentes y si no encontramos como uno de los convergentes, simplemente comenzamos de nuevo? $j/2^q$ $r.$ $<N$ $r$

Tú podrías; el algoritmo funciona bastante rápido si lo haces. Si desea reducir el número esperado de pasos cuánticos, también puede hacer otras pruebas; por ejemplo, debe verificar si es un pequeño múltiplo de uno de los convergentes. Pero si no encuentra después de estas pruebas extendidas, debe comenzar de nuevo. $r$ $r$

Además, ¿cómo difiere la probabilidad de los posibles valores ? Por lo que veo, todos deberían tener la misma probabilidad, pero el documento de Shor dice que este no es el caso. $j$

No sé si puedo ayudarte más con esto, porque no me has dado suficiente información para que te diga por qué estás confundido. La probabilidad de cada valor de en la fracción es (casi) la misma. Sin embargo, dependiendo de exactamente dónde cae entre los valores adyacentes de y , las probabilidades de los valores específicos de difieren. $k$ $k/r$ $k/r$ $j/2^q$ $(j+1)/2^q$ $j$

Peter Shor
fuente

Me gusta cómo te refieres al papel como "papel de Shor" :)

Suresh Venkat

Estoy un poco inseguro sobre cómo funciona la probabilidad, eso es todo. ¿Tengo razón al decir que . En los ejemplos que he visto, ha habido una simetría en la distribución de probabilidad sobre el punto medio del eje , ¿es este siempre el caso? Supongamos que , ¿significa esto que para todos los valores posibles de , donde , todos tendrán la misma probabilidad de ? Gracias.

Prob (j) = \frac{1}{2^{q} \times ([\frac{2^{q} - k - 1}{r}] + 1)} | \sum_{a = 0}^{[\frac{2^{q} - k - 1}{r}]} e^{- 2 π i r j a / 2^{q}} |^{2}

$\textrm{Prob} (j) = \frac{1}{2^q \times ([ \frac{2^q - k -1}{r}]+1)} \Bigg| \sum^{[ \frac{2^q - k -1}{r}]}_{a=0} e^{ -2 \pi i rja/2^q } \Bigg| ^2$

x

$x$

r = 2^{t}

$r= 2^t$

j = \frac{k_{0} 2^{q}}{r}

$j= \frac{ k_0 2^q}{r}$

k_{0} = 0, \dots, r - 1

$k_0 = 0, \cdots , r-1$

j

$j$

\frac{1}{2^{t}}

$\frac{1}{2^t}$

Callum

Si , entonces todos los valores posibles de tendrán una probabilidad igual de 1/2 .

r = 2^{t}

$r=2^t$

j

$j$

1 / 2^{t}

$1/2^t$

Peter Shor