¿Cuáles son los picos interesantes en este gráfico posterior a QFT (página 241) de Programación de computadoras cuánticas?
Estoy leyendo Programación de ordenadores cuánticos para intentar comprender el algoritmo de Shor. Allí aprendí que preparamos un estado$|x^i \bmod N\rangle$, luego aplique QFT a este estado. El QFT cambia las amplitudes de una superposición uniforme a grandes amplitudes espaciadas uniformemente por el período de$x^i \bmod N$. Por ejemplo, aquí hay un gráfico de las amplitudes después de aplicar el QFT con$N = 35$. Eso está en la página 241.

El libro dice que hay 12 picos espaciados uniformemente. Veo más de 12 picos espaciados uniformemente. ¿Debo contar solo los más altos y detenerme cuando haya contado 12? ¿Pero no es eso subjetivo? ¿Cómo me daría cuenta de que el número es realmente 12 con solo mirar este gráfico sin saber la respuesta correcta? (En otras palabras, ¿cómo saco 12 de esto?)
Respuestas
Mirando los gráficos que ha reproducido, el gráfico de la izquierda muestra la evaluación de $2^x\bmod 35$ por $x\in\{0,\dots 63\}$ mientras que el gráfico de la derecha ilustra la amplitud de la transformada discreta de Fourier para $\hat{x}\in\{0,\dots 63\}$. El comentario de que hay "12 picos espaciados uniformemente" indica que los máximos locales del gráfico de la derecha se repiten cada$64/12=5.33$ valores.
Estás en lo correcto, no tienes acceso a $\hat{x}$ de una manera que le permita observar esta periodicidad en $\hat{x}$inmediatamente; sin embargo, a lo que sí tiene acceso es a una forma de probar$\hat{x}_i$ para múltiples $i$ de una manera que vuelve $\hat{x}_i$ con probabilidad dada por el (cuadrado de la) altura del respectivo $\hat{x}_i$.
Por ejemplo, si tuviera que ejecutar la exponenciación modular (gráfico de la izquierda) seguido del QFT (gráfico de la derecha) y muestrear el primer registro, es probable que obtenga un valor como $0$ con mayor probabilidad que $5$, con mayor probabilidad que $32$, con mayor probabilidad que $11$, con mayor probabilidad que $6$etc.
A partir de estos respectivos muestreos de $\hat{x}_i$, puede ejecutar las porciones clásicas (la porción de fracción continua) del algoritmo de Shor para deducir que, de hecho, hubo 12 picos espaciados uniformemente en $\hat{x}$, dándote el período de $12$ en $2^x\bmod 35$. Hay muchos detalles que me olvido, pero el punto es que usa las muestras de su QFT como entradas a esta parte clásica.