Algorisme de Shor: diferència entre les revisions

Contingut suprimit Contingut afegit
moltes fórmules malament
arreglades les fórmules de la primera part a partir de l'anglesa
Línia 45:
#: Això porta a l'estat final:
#:<math> Q^{-1} \sum_x \sum_y \omega^{x y} \left|y, f(x)\right\rangle.</math>
#:Ara reordenem aquesta suma com a
#:<math> Q^{-1} \sum_{z} \sum_y \left|y, z\right\rangle \sum_{x:\, f(x)=z} \omega^{x y}.</math>
#:Això és una superposició de molts més de ''Q'' estats, però molts menys de ''Q''<sup>2</sup> estats, perquè hi ha menys de ''Q'' valors distints de <math>z = f(z)</math>. Siguin
Línia 60:
</math>
#: L'anàlisi mostra ara que aquesta probabilitat és més alta com més proper és el vector unitari <math>\omega^{ry}</math> a l'eix positiu real, o com més proper sigui ''yr/Q'' a un enter. Si r no és potència de 2, no serà un factor de Q.
# Com que <math>yr/Q</math> és proper a algun enter ''c'', el valor conegut ''y''/''Q'' és proper al valor desconegut ''c''/''r''. Si fem una expansió [clàssica] en [[fracció contínua]] sobre ''y/Q'' podrem trobar-ne aproximacions ''d/s'' que satisfacin dues condicions:
# Convertiu a ''i/N'' en una [[fracció irreductible]], i extraieu el denominador ''r''', que és un candidat a ''r''.
#* A: s<N
# Comproveu si ''f''(''x'') =''f''(''x''+''r'''). Si és així acabem.
#* B: |y/Q - d/s| < 1/2Q.
# Si no, obteniu més candidats a ''r'' usant valors propers ''i'', o múltiples de ''r'''. Si qualsevol candidat compleix les condicions, vam acabar.
#: Donades aquestes condicions (i suposant que ''d''/''s'' és una [[fracció irreductible]]), és molt probable que ''s'' sigui el període apropiat ''r'', o com a mínim en sigui un factor.
# Comproveu (de forma clàssica) si <math>f(x) = f(x + s) \Leftrightarrow a^r \equiv 1 \pmod{N}</math>. Si és així, ja estem.
# Si no, obteniu més candidats a ''r'' usant valorsmúltiples propersde ''is'', oor múltiplesusant dealtres ''rs'' on ''d/s'' s'acosti a ''y''/''Q''. Si qualsevol candidat compleix les condicions, vamja acabarestem.
# Si no, aneu de nou al pas 1 del subprograma.