Quels sont les pics intéressants dans ce graphique après QFT (page 241) de la programmation d'ordinateurs quantiques?
Je lis Programming Quantum Computers en essayant de comprendre l'algorithme de Shor. J'y ai appris qu'on prépare un état$|x^i \bmod N\rangle$, puis appliquez le QFT à cet état. Le QFT change les amplitudes d'une superposition uniforme à de grandes amplitudes régulièrement espacées par la période de$x^i \bmod N$. Par exemple, voici un graphique des amplitudes après application du QFT avec$N = 35$. C'est à la page 241.

Le livre dit qu'il y a 12 pointes régulièrement espacées. Je vois beaucoup plus de 12 pointes régulièrement espacées. Dois-je compter uniquement les plus élevés et arrêter quand j'en ai compté 12? Mais n'est-ce pas subjectif? Comment pourrais-je comprendre que le nombre est vraiment 12 en regardant simplement ce graphique sans connaître la bonne réponse? (En d'autres termes, comment en tirer 12?)
Réponses
En regardant les graphiques que vous avez reproduits, le graphique de gauche montre l'évaluation de $2^x\bmod 35$ pour $x\in\{0,\dots 63\}$ tandis que le graphique de droite illustre l'amplitude de la transformée de Fourier discrète pour $\hat{x}\in\{0,\dots 63\}$. Le commentaire selon lequel il y a "12 pointes régulièrement espacées" indique que les maxima locaux du graphique de droite se répètent tous les$64/12=5.33$ valeurs.
Vous avez raison, vous n'avez pas accès à $\hat{x}$ d'une manière qui vous permet d'observer cette périodicité dans $\hat{x}$immédiatement; Cependant, ce que vous n'avez accès à un moyen d'échantillon$\hat{x}_i$ pour plusieurs $i$ d'une manière qui retourne $\hat{x}_i$ avec une probabilité donnée par le (carré de la) hauteur du respectif $\hat{x}_i$.
Par exemple, si vous exécutez l'exponentiation modulaire (graphique de gauche) suivie du QFT (graphique de droite) et échantillonnez le premier registre, vous obtiendrez probablement une valeur telle que $0$ avec une probabilité plus élevée que $5$, avec une probabilité plus élevée que $32$, avec une probabilité plus élevée que $11$, avec une probabilité plus élevée que $6$, etc.
À partir de ces échantillons respectifs de $\hat{x}_i$, vous pouvez exécuter les parties classiques (la partie de fraction continue) de l'algorithme de Shor pour en déduire qu'en effet, il y avait 12 pics régulièrement espacés dans $\hat{x}$, vous donnant la période de $12$ dans $2^x\bmod 35$. Il y a beaucoup de détails que j'oublie, mais le fait est que vous utilisez les échantillons de votre QFT comme entrées pour cette partie classique.