Revisió del 19:39, 19 abr 2010 modifica Mcapdevila (discussió \| contribucions) 185.518 edits Cap resum de modificació ← Edició anterior		Revisió del 23:27, 21 jul 2010 modifica desfés Bestiasonica (discussió \| contribucions) 244.771 edits Cap resum de modificació Edició següent →
Línia 1: El L'''' algorisme de Shor ''' és un [[algoritme]] [[Computació quàntica\|quàntic]] per [[Factorització\|descompondre en factors]] un nombre '' N '' en temps [[Cota superior asimptòtica\|O]] ((log N) <sup> 3 </sup>) i espai O (log '' N ''), així nomenat per [[Peter Shor]]. Moltes [[Criptografia asimètrica\|criptografia de clau pública]], com ara [[RSA]], arribarien a ser obsoletes si l'algorisme de Shor és implementat alguna vegada en una [[Computació quàntica\|ordinador quàntica]] pràctica. Un missatge xifrat amb RSA pot ser desxifrat descomponent en factors la clau pública '' N '', que és el producte de dos nombres primers. Els algorismes clàssics coneguts no poden fer-ho en temps O ((log '' N '') <sup> '' k '' </sup>) per a cap '' k '', així que arriben a ser ràpidament poc pràctic a mesura que s'augmenta '' N '' . Per contra, l'algorisme de Shor pot [[Problemes RSA\|trencar RSA]] en [[temps polinòmic]]. També s'ha ampliat per atacar moltes altres criptografia públiques. Com tots els algorismes de [[computació quàntica]], l'algorisme de Shor és probabilístic: dóna la resposta correcta amb alta probabilitat, i la probabilitat d'error pot ser disminuïda repetint l'algorisme. L'algorisme de Shor va ser demostrat en [[2001]] per un grup en [[IBM]], que descompondre 15 en els seus factors 3 i 5, utilitzant un ordinador quàntica amb 7 [[qubit]] s. == Procediment == El problema que intenta solucionar l'algorisme de Shor és que, donat un [[nombre enter]] '' N '', ~~intentem~~es ~~trobar~~troba un altre nombre enter '' p '' entre '' 1 '' i '' N '' que divideixi '' N ''.▼ ▲El problema que intenta solucionar l'algorisme de Shor és que, donat un [[nombre enter]] '' N '', intentem trobar un altre nombre enter '' p '' entre '' 1 '' i '' N '' que divideixi '' N ''. L'algorisme de Shor consisteix en dues parts: Linha 16 ⟶ 15: === Part clàssica === # Escolliu un nombre pseudo-aleatori '' a '' <'' N ''▼ # Computa el [[màxim comú divisor\|mcd]] (''a'',''N''). Això es pot fer usant el [[algorisme d'Euclides]].</li> ▲# Escolliu un nombre pseudo-aleatori '' a '' <'' N '' #: ~~Computa~~Si el ~~[[màxim comú divisor\|~~mcd]] ('' a '', '' N ''). ~~Això~~≠ es1, ~~pot~~llavors ~~fer~~és ~~usant~~un elfactor ~~[[algorisme~~no dtrivial de'~~Euclides]]~~'N'', així que vam acabar. </liLi> #: Si no, feu servir el subprograma per trobar el període (veure a baix) per trobar '' r '', el [[Nombre diari\|període]] de la funció següent:▼ ~~#: Si el mcd ('' a '', '' N '') ≠ 1, llavors és un factor no trivial de '' N '', així que vam acabar. </Li>~~ ▲#: Si no, feu servir el subprograma per trobar el període (veure a baix) per trobar '' r '', el [[Nombre diari\|període]] de la funció següent: #: <math> F (x) = a^x \ \mbox{mod}\N </math>, #: És a dir el nombre enter més petit '' r '' per al qual #: <math> F (x+r) = f (x) </math>. # Si '' r '' és senar, vagi de nou al pas 1. # Si '' a '' <sup> '' r ''/2 </sup> ≡ -1 (mod '' N ''), vagi de nou al pas 1. # Els factors de '' N '' són el mcd (a <sup> '' r ''/2 </sup> ± 1, '' N ''). Acabem. === Part quàntica: subprograma per trobar el període === # Comenceu amb un parell de registres [[Qubit\|qubits]] d'entrada i sortida amb log <sub> 2 </sub> '' N '' qubits cada un, i inicialícelos a #: <math> N^{-1/2}\sum_x \left\|x \right \rangle \left\|0 \right \rangle </math> #: On '' x '' va de 0 a '' N '' - 1. # Construeixi '' f '' ('' x '') com a funció quàntica i apliqui l'estat esmentat, per obtenir #: <math> N^{-1/2}\sum_x \left\|x \right \rangle \left\|f (x) \right \rangle </math> # Apliqui la [[transformada de Fourier]] quàntica al registre d'entrada. La transformada de Fourier quàntica en '' N '' punts es defineix com: #: <math> U_{QFT} \left\|x \right \rangle = N^{-1/2}\sum_y i^{2 \pi ixy/N} \left\|i \right \rangle </math> #: El que ens deixa en l'estat següent: #: <math> N^{-1}\sum_x \sum_y i^{2 \pi ixy/N} \left\|i \right \rangle \left\|f (x) \right \rangle </math> # Feu una mesura. Obtenim un cert resultat '' i '' en el registre d'entrada i '' f '' ('' x '' <sub> 0 </sub>) en el registre de sortida. Com que '' f '' és periòdica, la probabilitat de mesurar cert '' i '' ve donada per #: <math> N^{-1} \left\|\sum_{x: \, f (x) = f (x_0)}i^{2 \pi ixy/N}\right\|^2 = N^{-1} \left\|\sum_{b}i^{2 \pi i (x_0+rb) i/N}\right\|^2 </Math> #: L'anàlisi mostra ara que com més alta és aquesta probabilitat, més l''' ir ''/'' N '' és proper a un nombre enter. # Converteixi a '' i/N '' en una [[fracció irreductible]], i extraieu el denominador '' r '' ', que és un candidat a '' r ''. # Comproveu si '' f '' ('' x '') = '' f '' ('' x ''+'' r '' '). Si és així acabem. # Si no, obtingui més candidats a '' r '' usant valors propers '' i '', o múltiples de '' r '' '. Si qualsevol candidat compleix les condicions, vam acabar. # Si no, vagi de nou al pas 1 del subprograma. Linha 54 ⟶ 52: L'algorisme es compon de dues parts. La primera part de l'algorisme converteix el problema de descompondre en factors en el problema de trobar el període d'una funció, i es pot implentat clàssicament. La segona part ha el període utilitzant la [[transformada de Fourier]] quàntica, i és responsable de l'acceleració quàntica. === I. Obtenció de factors a partir del període === Els nombres enters menors que '' N '' i [[coprimer]] s amb '' N '' formen un [[grup (matemàtiques)\|grup]] [[finit]] sota multiplicació [[Aritmètica modular\|mòdul]] '' N '', que es denota típicament (''' Z '''/'' N '' ''' Z ''') <sup> × </sup>. Per al final del pas 3, tenim un nombre enter '' a '' en aquest grup. Com que el grup és finit, '' a '' ha de tenir un ordre finit '' r '', el nombre enter positiu més petit tal que▼ ▲Els nombres enters menors que '' N '' i [[coprimer]] s amb '' N '' formen un [[grup (matemàtiques)\|grup]] [[finit]] sota multiplicació [[Aritmètica modular\|mòdul]] '' N '', que es denota típicament (''' Z '''/'' N '' ''' Z ''') <sup> × </sup>. Per al final del pas 3, tenim un nombre enter '' a '' en aquest grup. Com que el grup és finit, '' a '' ha de tenir un ordre finit '' r '', el nombre enter positiu més petit tal que : <math> A^r \equiv 1 \ \mbox{mod}\N. \, </math> Per tant, '' N ''\|('' a '' <sup> '' r '' </sup> - 1). Suposeu que podem obtenir '' r '', i és parell. Llavors : <math> A^r - 1 = (a^{r/2}- 1) (a^{r/2}+1) \equiv 0 \ \mbox{mod}\N </math> : <math> \Rightarrow N \\|(a^{r/2}- 1) (a^{r/2}+1). \, </Math> '' r '' és el nombre enter positiu '' més petit '' tal que '' a '' <sup> '' r '' </sup> ≡ 1, així que '' N '' no pot dividir ('' a '' <sup> '' r ''/2 </sup> - 1). Si '' N '' tampoc divideix ('' a '' <sup> '' r ''/2 </sup>+1), llavors '' N '' ha de tenir un factor comú no trivial amb ('' a '' <sup> '' r ''/2 </sup> - 1) i ('' a '' <sup> '' r ''/2 </sup>+1). ''' Prova: ''' Per simplicitat, denoti ('' a '' <sup> '' r ''/2 </sup> - 1) i ('' a '' <sup> '' r ''/2 </sup>+1) '' o '' i '' v '' respectivament. '' N ''\|'' uv '', després '' kN '' = '' uv '' per a un cert nombre enter '' k ''. Suposeu que el mcd ('' o '', '' N '') = 1, aleshores '' mu ''+'' nN '' = 1 per a certs nombres enters '' m '' i '' n '' (aquesta és una propietat del [[màxim comú divisor]] .) Multiplicant ambdós costats per '' v '', trobem que '' MKN ''+'' nvN '' = '' v '', després '' N ''\|'' v ''. Per contradicció, mcd ('' o '', '' N '') ≠ 1. Per un argument similar, mcd ('' v '', '' N '') ≠ 1. Això ens proveeix d'una factorització de '' N ''. Si '' N '' és el producte de dos primers, aquesta és la '' única '' factorització possible. === II. Trobar el període === L'algorisme, per trobar el període de Shor, es basa radicalment en la capacitat d'una [[Computació quàntica\|ordinador quàntica]] d'estar en molts estats simultàniament. Els físics anomenen aquest comportament [[superposició quàntica]]. Per computar el període d'una funció '' f '', avaluem la funció en tots els punts simultàniament. No obstant això, la física quàntica no permet que tinguem accés a tota aquesta informació directament. Un [[mesurament quàntic]] donarà només un de tots els valors possibles, destruint tots els altres. Per tant hem de transformar acuradament la superposició a un altre estat que retorni la resposta correcta amb alta probable. Això és aconseguit utilitzant la [[transformada de Fourier]] quàntica. 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]] En log '' N ''. # 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ó. # Realitzar una [[transformada de Fourier]] quàntica. Usant portes controlades NOT i portes d'una sola rotació de [[qubit]], Shor va dissenyar un circuit per a la transformada de Fourier quàntica que utilitza exactament ((log '' N '') <sup> 2 </sup>) portes. 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> I^{2 \pi i b ir/N}= 1 </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 '' presa aproximadament '' N/r '' valors i així la probabilitat és '' 1/r ''. Hi ha '' r '', '' i '' tals que '' ir/N '' és un nombre enter, després la suma de les probabilitats és 1. Nota: una altra manera d'explicar l'algorisme de Shor és observant que és precisament el [[algorisme de valoració de fase quàntica]] disfressat. == ~~Referències~~Vegeu també == * [[Anell factorial]]. == Enllaços externs== ~~Preprint del paper original de Peter Shor:~~ * [http://www.arxiv.org/abs/quant-ph/9508027 '' Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer '', Peter W. Shor] (en anglès)Preprint del paper original de Peter Shor:▼ * [http://www.qinfo.org/qcqi '' Quantum Computation and Quantum Information '', Michael A. Nielsen, Isaac L. Chuang, Cambridge University Press, 2000] Un llibre de textos general en [[computació quàntica]]:(en anglès)▼ ▲* [http://www.arxiv.org/abs/quant-ph/9508027 '' Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer '', Peter W. Shor] (en anglès) ~~Un llibre de textos general en computació quàntica:~~ ▲* [http://www.qinfo.org/qcqi '' Quantum Computation and Quantum Information '', Michael A. Nielsen, Isaac L. Chuang, Cambridge University Press, 2000] (en anglès) ~~== Vegeu també ==~~ * [[Computació quàntica]] * [[Domini de factorització única]] [[Categoria: Algorismes\|Shor]] [[ar:خوارزمية شوور]]

Algorisme de Shor: diferència entre les revisions