Aide sur l'algorithme d'affacturage de Shor

27

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 xqui 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 j,xkmodN .

De là, nous pouvons trouver les convergentes de la fraction j2q , les convergentes sont des valeurs possibles de l'ordrer. Ici, essayons-nous simplement tous les convergents<Net si nous ne trouvons pasrcomme 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.

Callum
la source
21
@Peter Shor pourrait même vous aider avec celui-ci.
Dave Clarke
1
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 j j = 2 q k / r 2 q k / r < N r j 2 q rj,xkmodNjjj=2qk/r2qk/r<Nrj2qr
Callum

Réponses:

47

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? r . < N rj/2qr.<Nr

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.rrr

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 / r k / r j / 2 q ( j + 1 ) / 2 q jkk/rk/rj/2q(j+1)/2qj

Peter Shor
la source
33
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. xr=2tjProb(j)=12q×([2qk1r]+1)|a=0[2qk1r]e2πirja/2q|2xr=2t k0=0,,r-1j=k02qrk0=0,,r11j12t
Callum
3
Si , alors en effet toutes les valeurs possibles de auront une probabilité égale de . j 1 / 2 tr=2tj1/2t
Peter Shor,