Algorithme de Shor: que faire après avoir lu deux fois le résultat du QFT?
J'ai demandé comment identifier la période en regardant un tracé de transformée de Fourier . La réponse semble être d'exécuter la transformée de Fourier plusieurs fois en obtenant plusieurs valeurs associées à des probabilités élevées décrites par le graphique. Donc, toujours en utilisant la même image, supposons que je la lise deux fois et que j'aie les valeurs | 5> et | 11>. Ce sont les pics les plus élevés (après le premier plus haut de | 0>.) Comment pourrais-je calculer la période 12 sur 5 et 11? Pouvez-vous montrer un exemple du calcul?
Une tentative de solution . En lisant l'article de Peter Shor (à la page 320), nous constatons que son$q$ est $q=64$ici dans notre exemple. Shor dit que nous pouvons obtenir une fraction$d/r$ dans les termes les plus bas (où $r = 12$ ici) en arrondissant $c/q$ à la fraction la plus proche ayant un dénominateur inférieur à $n=35$ici. Notre possible$c$ Voici $5$ et $11$.
Essayons ça. Après le QFT, nous avons$c = 5$ et nous avons $q = 64$. Alors on obtient$5/64 = 0.078125$ et nous voulons arrondir cela à la fraction la plus proche ayant un dénominateur plus petit que $35$. Pour$5/64$, Je trouve la fraction continue $[0,12,1,4]$. (J'ai vérifié que$5/64 = 1/(12 + 1/(1 + 1/4))$, donc c'est correct.) Maintenant, à partir de cette fraction continue (sous forme de liste), j'obtiens la séquence de fractions suivante: $1/4, 5/4, 64/5, 5/64$. (Je ne suis pas sûr de ce que je fais.) Peut-être$5$est la malchance? Mais, non, essayer la même chose avec$11$ produira également $11/64$. Donc, même si je sais comment calculer l'algorithme de fraction continue, je ne sais pas quoi en faire. Je vais devoir regarder Hardy et Wright, chapitre X.
Réponses
Il s'agit de la partie fraction continue de l'algorithme, étape 5 sur Wikipédia. Ce que vous avez mesuré est$y$ tel que $\frac{yr}{Q}\approx c$, où $c$ est un entier inconnu, $r$ est la période cachée (dans ce cas 12), et $Q=64$est la taille du QFT. Cela signifie que$\frac{y}{Q}\approx \frac{c}{r}$. Pour$y=5$, on a $\frac{5}{64}\approx \frac{1}{12}$, et pour $y=11$, on a $\frac{11}{64}\approx \frac{2}{12}$. Voilà donc la relation entre les valeurs mesurées et la période.
Comment pouvons-nous trouver la période à partir de ces valeurs, cependant (puisque nous ne savons pas $c$ ou alors $r$)? Avec des fractions continues. Une fraction continue pour un nombre$x$ est défini récursivement, avec $a_0=x$, puis avec $b_n=\lfloor a_n\rfloor$, et $a_n=\frac{1}{a_{n-1}-b_{n-1}}$. Appliqué à ce problème avec$x=\frac{5}{64}$, on a
$$ a = (\frac{5}{64},\frac{64}{5},\frac{5}{4},4,0,\dots)$$ $$ b = (0,12,1,4,0,\dots)$$
À partir de là, nous pouvons reconstruire des approximations, et le dénominateur de ces approximations sera probablement la période. La page wikipedia sur les fractions continues explique que nous obtenons une série de fractions approximatives$\frac{h_n}{k_n}$, où nous définissons un numérateur $h_n=b_nh_{n-1}+h_{n-2}$ et dénominateur $k_n=b_nk_{n-1}+k_{n-2}$, avec des valeurs initiales $h_{-1}=1$, $h_{-2}=0$, $k_{-1}=0$, et $k_{-2}=1$. Cela donne deux séquences:
$$h = (0, 1, 0, 1, 1, 5)$$ $$ k = (1,0, 1, 12, 13, 64)$$
ce qui donne trois fractions approximatives: $\frac{1}{12}$, $\frac{1}{13}$, et $\frac{5}{64}$. Le dernier est celui avec lequel nous avons commencé et est inutile car 64 est trop grand (la période doit être inférieure à 35, après tout). Le premier est la période réelle.
Je ne sais pas grand-chose sur les fractions continues mais je pense que ces approximations convergent très rapidement vers la fraction originale. Donc, en pratique, je pense que vous vérifieriez simplement chaque dénominateur dans la séquence des fractions approximatives (dans ce cas, à la fois 12 et 13) car (a) il ne devrait pas y avoir autant de fractions approximatives, et (b) les étapes finales de Shor algorithme sont si peu coûteux.