Algorisme de Shor: diferència entre les revisions
Contingut suprimit Contingut afegit
Línia 88:
Això ens proporciona una factorització de ''N''. Si ''N'' és el producte de dos primers, aquesta és l'''única'' factorització possible.
===
Shor va haver de solucionar així tres "problemes d'implementació". Tots van haver de ser implementats "ràpids", que significa executar amb un nombre de portes quàntiques que és [[Temps polinòmic|polinòmic]]
# Crear una superposició d'estats. Això es pot fer aplicant les portes de Hadamard a tots els [[qubit]] s en el registre d'entrada. Un altre enfocament seria utilitzar la [[transformada de Fourier]] quàntica (vegeu a sota).
# Implementar la funció''f''com una transformada quàntica. Per assolir això, Shor utilitzar exponenciació per quadrats per a la seva transformació modular de l'exponenciació.
Línia 100:
Després de totes aquestes transformacions una mesura donarà una aproximació al període''r''. Per simplicitat assumeixi que hi ha una''i''tal que''ir/N''és un nombre enter. Llavors la probabilitat de mesurar''i''és 1. Per veure això notem que
: <math>
per a tots els nombres enters ''b''. Per tant la suma que ens dóna la probabilitat de la mesura ''i'' serà ''N/r'' ja que ''b''
== Vegeu també ==
| |||