Algoritmo de Shor: ¿que hacer después de leer dos veces el resultado de QFT?
Me pregunté acerca de cómo identificar el periodo mirando una transformada de Fourier trama . La respuesta parece ser ejecutar la transformada de Fourier varias veces obteniendo múltiples valores asociados a las altas probabilidades descritas en el gráfico. Así que todavía usando la misma imagen, supongamos que la leo dos veces y obtengo los valores | 5> y | 11>. Estos son los picos más altos (después del primero más alto en | 0>.) ¿Cómo calcularía el período 12 de 5 y 11? ¿Puede mostrar un ejemplo del cálculo?
Un intento de solución . Al leer el artículo de Peter Shor (en la página 320), encontramos que su$q$ es $q=64$aquí en nuestro ejemplo. Shor está diciendo que podemos obtener una fracción$d/r$ en términos más bajos (donde $r = 12$ aquí) redondeando $c/q$ a la fracción más cercana que tenga un denominador menor que $n=35$aquí. Nuestro posible$c$ aquí está $5$ y $11$.
Probemos eso. Después del QFT, obtuvimos$c = 5$ y tenemos $q = 64$. Entonces obtenemos$5/64 = 0.078125$ y queremos redondear eso a la fracción más cercana que tenga un denominador menor que $35$. Para$5/64$, Encuentro la fracción continua $[0,12,1,4]$. (Lo comprobé$5/64 = 1/(12 + 1/(1 + 1/4))$, así que eso es correcto.) Ahora, de esta fracción continua (en forma de lista) obtengo la siguiente secuencia de fracciones: $1/4, 5/4, 64/5, 5/64$. (No estoy seguro de lo que estoy haciendo).$5$es mala suerte? Pero no, intentar lo mismo con$11$ también producirá $11/64$. Entonces, aunque sé cómo calcular el algoritmo de fracción continua, no sé qué hacer con él. Tendré que mirar a Hardy y Wright, Capítulo X.
Respuestas
Esta es la parte de fracción continua del algoritmo, paso 5 en Wikipedia. Lo que has medido es$y$ tal que $\frac{yr}{Q}\approx c$, dónde $c$ es un entero desconocido, $r$ es el período oculto (en este caso 12), y $Q=64$es el tamaño del QFT. Esto significa que$\frac{y}{Q}\approx \frac{c}{r}$. Para$y=5$, tenemos $\frac{5}{64}\approx \frac{1}{12}$, y para $y=11$, tenemos $\frac{11}{64}\approx \frac{2}{12}$. Entonces esa es la relación entre los valores medidos y el período.
Sin embargo, ¿cómo encontramos realmente el período a partir de esos valores (dado que no sabemos $c$ o $r$)? Con fracciones continuas. Una fracción continua de un número$x$ se define de forma recursiva, con $a_0=x$, luego con $b_n=\lfloor a_n\rfloor$, y $a_n=\frac{1}{a_{n-1}-b_{n-1}}$. Aplicado a este problema con$x=\frac{5}{64}$, tenemos
$$ a = (\frac{5}{64},\frac{64}{5},\frac{5}{4},4,0,\dots)$$ $$ b = (0,12,1,4,0,\dots)$$
A partir de esto, podemos reconstruir aproximaciones, y el denominador de estas aproximaciones probablemente será el período. La página de wikipedia sobre fracciones continuas explica que obtenemos una serie de fracciones aproximadas$\frac{h_n}{k_n}$, donde establecemos un numerador $h_n=b_nh_{n-1}+h_{n-2}$ y denominador $k_n=b_nk_{n-1}+k_{n-2}$, con valores iniciales $h_{-1}=1$, $h_{-2}=0$, $k_{-1}=0$, y $k_{-2}=1$. Esto da dos secuencias:
$$h = (0, 1, 0, 1, 1, 5)$$ $$ k = (1,0, 1, 12, 13, 64)$$
lo que da tres fracciones aproximadas: $\frac{1}{12}$, $\frac{1}{13}$, y $\frac{5}{64}$. El último es con el que empezamos y es inútil porque 64 es demasiado grande (el período debe ser menor que 35, después de todo). El primero es el período real.
No sé mucho sobre fracciones continuas, pero creo que estas aproximaciones convergen muy rápidamente a la fracción original. Entonces, en la práctica, creo que simplemente verificaría cada denominador en la secuencia de fracciones aproximadas (en este caso, 12 y 13) ya que (a) no debería haber tantas fracciones aproximadas, y (b) los pasos finales de Shor El algoritmo es tan económico.