Algorisme de Shor

De Viquipèdia
Dreceres ràpides: navegació, cerca

L'algorisme de Shor és un algorisme quàntic per descompondre en factors un nombre N en temps O ((log N) 3) i espai O (logN), així nomenat per Peter Shor.

Moltes criptografia de clau pública, com ara RSA, arribarien a ser obsoletes si l'algorisme de Shor és implementat alguna vegada en una ordinador quàntica pràctica. Un missatge xifrat amb RSA pot ser desxifrat descomponent en factors la clau públicaN, que és el producte de dos nombres primers. Els algorismes clàssics coneguts no poden fer-ho en temps O ((logN) k) per a capk, de manera que arriben a ser ràpidament poc pràctic a mesura que s'augmentaN. Per contra, l'algorisme de Shor pot 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 qubits.

Procediment[modifica | modifica el codi]

El problema que intenta solucionar l'algorisme de Shor és que, donat un nombre enter N, es troba un altre nombre enterpentre 1 i N que divideixi N.

L'algorisme de Shor consisteix en dues parts:

  1. Una reducció del problema de descompondre en factors al problema de trobar l'ordre, que es pot fer en un ordinador clàssica.
  2. Un algorisme quàntic per solucionar el problema de trobar l'ordre.

Part clàssica[modifica | modifica el codi]

  1. Escolliu un nombre pseudo-aleatoria<N
  2. Computa el mcd (a,N). Això es pot fer usant el algorisme d'Euclides.
    Si el mcd (a,N) ≠ 1, llavors és un factor no trivial deN, de manera que vam acabar.
    Si no, feu servir el subprograma per trobar el període (vegeu a baix) per trobarr, el període de la funció següent:
     F (x) = a^x \ \mbox{mod}\N ,
    És a dir el nombre enter més petitrper al qual
     F (x+r) = f (x) .
  3. Sirés senar, vagi de nou al pas 1.
  4. Siar/2 ≡ -1 (modN), vagi de nou al pas 1.
  5. Els factors deNsón el mcd (a r/2 ± 1,N). Acabem.

Part quàntica: subprograma per trobar el període[modifica | modifica el codi]

  1. Comenceu amb un parell de registres qubits d'entrada i sortida amb log 2 Nqubits cada un, i inicialícelos a
     N^{-1/2}\sum_x \left|x \right \rangle \left|0 \right \rangle
    Onxva de 0 aN- 1.
  2. Construeixif(x) com a funció quàntica i apliqui l'estat esmentat, per obtenir
     N^{-1/2}\sum_x \left|x \right \rangle \left|f (x) \right \rangle
  3. Apliqui la transformada de Fourier quàntica al registre d'entrada. La transformada de Fourier quàntica enNpunts es defineix com:
     U_{QFT} \left|x \right \rangle
= N^{-1/2}\sum_y i^{2 \pi ixy/N} \left|i \right \rangle
    El que ens deixa en l'estat següent:
     N^{-1}\sum_x \sum_y i^{2 \pi ixy/N} \left|i \right \rangle \left|f (x) \right \rangle
  4. Feu una mesura. Obtenim un cert resultatien el registre d'entrada if(x 0 ) en el registre de sortida. Com quefés periòdica, la probabilitat de mesurar certive donada per
     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
    L'anàlisi mostra ara que com més alta és aquesta probabilitat, més l'ir/Nés proper a un nombre enter.
  5. Converteixi ai/Nen una fracció irreductible, i extraieu el denominadorr', que és un candidat ar.
  6. Comproveu sif(x) =f(x+r'). Si és així acabem.
  7. Si no, obtingui més candidats arusant valors propersi, o múltiples der'. Si qualsevol candidat compleix les condicions, vam acabar.
  8. Si no, vagi de nou al pas 1 del subprograma.

Explicació de l'algorisme[modifica | modifica el codi]

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.

Obtenció de factors a partir del període[modifica | modifica el codi]

Els nombres enters menors queNi coprimer s ambNformen un grup finit sota multiplicació mòdulN, que es denota típicament (Z/NZ) × . Per al final del pas 3, tenim un nombre enteraen aquest grup. Com que el grup és finit,aha de tenir un ordre finitr, el nombre enter positiu més petit tal que

 A^r \equiv 1 \ \mbox{mod}\N. \,

Per tant,N|(ar - 1). Suposeu que podem obtenirr, i és parell. Llavors

 A^r - 1 = (a^{r/2}- 1) (a^{r/2}+1) \equiv 0 \ \mbox{mod}\N
 \Rightarrow N \|(a^{r/2}- 1) (a^{r/2}+1). \,

rés el nombre enter positiumés petittal quear ≡ 1, així queNno pot dividir (ar/2 - 1). SiNtampoc divideix (ar/2 +1), llavorsNha de tenir un factor comú no trivial amb (ar/2 - 1) i (ar/2 +1).

Prova: Per simplicitat, denoti (ar/2 - 1) i (ar/2 +1)oivrespectivament. N|uv, despréskN=uvper a un cert nombre enter k. Suposeu que el mcd (o,N) = 1, aleshoresmu+nN= 1 per a certs nombres entersmin(aquesta és una propietat del màxim comú divisor .) Multiplicant ambdós costats perv, trobem queMKN+nvN=v, desprésN|v. Per contradicció, mcd (o,N) ≠ 1. Per un argument similar, mcd (v,N) ≠ 1.

Això ens proveeix d'una factorització de N. SiNés el producte de dos primers, aquesta és l'única factorització possible.

II. Trobar el període[modifica | modifica el codi]

L'algorisme, per trobar el període de Shor, es basa radicalment en la capacitat d'una 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 polinòmic En logN.

  1. 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).
  2. Implementar la funciófcom una transformada quàntica. Per assolir això, Shor utilitzar exponenciació per quadrats per a la seva transformació modular de l'exponenciació.
  3. 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 ((logN) 2 ) portes.

Després de totes aquestes transformacions una mesura donarà una aproximació al períoder. Per simplicitat assumeixi que hi ha unaital queir/Nés un nombre enter. Llavors la probabilitat de mesurariés 1. Per veure això notem que

 I^{2 \pi i b ir/N}= 1

per a tots els nombres entersb. Per tant la suma que ens dóna la probabilitat de la mesuraiseràN/rja quebpresa aproximadamentN/rvalors i així la probabilitat és1/r. Hi har,itals queir/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.

Vegeu també[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]