Aide sur l'algorithme d'affacturage de Shor

J'ai un peu de mal à bien comprendre les dernières étapes de l'algorithme d'affacturage de Shor.

Étant donné un $N$ nous voulons factoriser, nous choisissons un aléatoire $x$ qui a l'ordre $r$ .

La première étape consiste à mettre en place les registres et à appliquer l'opérateur Hadamard. La deuxième étape consiste à appliquer un opérateur linéaire. La troisième étape, le deuxième registre est mesuré (je crois que cette étape peut être effectuée plus tard à la place). La quatrième étape de la transformée de Fourier discrète est appliquée au premier registre. Ensuite, nous mesurons le premier registre.

Voici où je suis un peu brumeux:

Nous obtenons une mesure sous la forme $\mid j , x^k \textrm{mod} N \rangle$ .

De là, nous pouvons trouver les convergentes de la fraction $\frac{j}{2^q}$ , les convergentes sont des valeurs possibles de l'ordre $r$ . Ici, essayons-nous simplement tous les convergents $< N$ et si nous ne trouvons pas $r$ comme l'un des convergents, recommençons-nous simplement?

De même, comment la probabilité des valeurs possibles $j$ diffère-t-elle? À leur avis, ils devraient tous avoir la même probabilité, mais le document de Shor dit que ce n'est pas le cas?

Juste un peu confus car certains articles semblent dire des choses différentes.

Merci.

quantum-computing Callum
la source

@Peter Shor pourrait même vous aider avec celui-ci.

Dave Clarke

Depuis que j'ai posé ces questions, je pense en avoir une meilleure compréhension. Pour clarifier pour ceux qui sont intéressés, nous obtenons une mesure sous la forme où tout ce dont nous avons besoin est le . La valeur peut être écrite comme en divisant par nous obtenons et de cela nous pouvons trouver ses convergents, le dénominateur d'un convergent est une valeur possible de , si ce n'est pas que l'algorithme est exécuté à nouveau. La probabilité de trouver est basée sur une somme qui dépend de la valeur de et de la période .

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

$\mid j , x^k \mod N \rangle$

j

$j$

j

$j$

j = 2^{q} k / r

$j= 2^q k/ r$

2^{q}

$2^q$

k / r

$k/r$

< N

$< N$

r

$r$

j

$j$

2^{q}

$2^q$

r

$r$

Callum

Réponses:

A partir de cela, nous pouvons trouver les convergents de la fraction , les convergents sont des valeurs possibles de l'ordre Ici, essayons-nous simplement tous les convergents et si nous ne trouvons pas comme l'un des convergents, recommençons-nous simplement? $j/2^q$ $r.$ $<N$ $r$

Vous pourriez; l'algorithme fonctionne assez rapidement si vous le faites. Si vous souhaitez réduire le nombre prévu d'étapes quantiques, vous pouvez également effectuer d'autres tests; par exemple, vous devez vérifier si est un petit multiple de l'un des convergents. Mais si vous ne trouvez pas après ces tests étendus, vous devez recommencer. $r$ $r$

De même, comment la probabilité des valeurs possibles diffère-t-elle? À leur avis, ils devraient tous avoir la même probabilité, mais le document de Shor dit que ce n'est pas le cas? $j$

Je ne sais pas si je peux vous aider davantage à ce sujet, parce que vous ne m'avez pas donné suffisamment d'informations pour que je puisse vous expliquer pourquoi vous êtes confus. La probabilité pour chaque valeur de dans la fraction est (presque) la même. Cependant, selon exactement où situe entre les valeurs adjacentes de et , les probabilités des valeurs spécifiques de diffèrent. $k$ $k/r$ $k/r$ $j/2^q$ $(j+1)/2^q$ $j$

Peter Shor
la source

J'aime la façon dont vous vous référez au papier comme "le papier de Shor" :)

Suresh Venkat

Je suis juste un peu incertain sur le fonctionnement de la probabilité, c'est tout. Ai-je raison de dire que . Dans les exemples que j'ai vus, il y a eu une symétrie sur la distribution de probabilité autour du point médian de l' axe des , est-ce toujours le cas? Supposons que , cela signifie- -il que pour toutes les valeurs possibles de , où , tous auront une probabilité égale de ? Merci.

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 , alors en effet toutes les valeurs possibles de auront une probabilité égale de .

r = 2^{t}

$r=2^t$

j

$j$

1 / 2^{t}

$1/2^t$

Peter Shor,