Algorisme de Shor

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

Moltes criptografies de clau pública, com ara RSA, arribarien a ser obsoletes si l'algorisme de Shor és implementat alguna vegada en un ordinador quàntic pràctic. 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((logN)^k) per a cap k, de manera que arriben a ser ràpidament poc pràctics a mesura que s'augmenta N. Per contra, l'algorisme de Shor pot trencar RSA en temps polinòmic. També s'ha ampliat per atacar moltes altres criptografies de clau pública.

Com tots els algorismes de computació quàntica, l'algorisme de Shor és probabilístic: dona 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 d'IBM, que va descompondre 15 en els seus factors 3 i 5, utilitzant un ordinador quàntic amb 7 qubits.

Procediment

El problema que intenta solucionar l'algorisme de Shor és que, donat un nombre enter N, es troba un altre nombre enter p entre 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àssic.
2. Un algorisme quàntic per solucionar el problema de trobar l'ordre.

Part clàssica

1. Escolliu un nombre pseudo-aleatori a<N
2. Computa el mcd (a,N). Això es pot fer usant l'algorisme d'Euclides.

   Si el mcd (a,N) ≠ 1, llavors hi ha un factor no trivial de N, de manera que ja hem acabat.

   Si no, feu servir el subprograma per trobar el període (vegeu a baix) per trobar r, el període de la funció següent:

   $f(x)=a^{x}{\bmod {N}}$,

   és a dir, el nombre enter més petit r per al qual

   $f(x+r)=f(x)$, o $f(x+r)=a^{x+r}{\bmod {N}}=a^{x}{\bmod {N}}.$

3. Si r és senar, torneu al pas 1.
4. Si a^r/2 ≡ -1 (mod N), torneu al pas 1.
5. Els factors de N són el mcd(a ^r/2  ± 1,N). Acabem.

Per exemple: $N=15,a=7,r=4$, $gcd(7^{2}\pm 1,15)=gcd(49\pm 1,15)$, on $mcd(48,15)=3$, i $mcd(50,15)=5$.

Part quàntica: subprograma per trobar el període

Subrutina quàntica a l'algorisme de Shor.

Els circuits quàntics utilitzats per a aquest algorisme estan dissenyats especialment per a cada N i per a cada a aleatòria utilitzats a f(x) = a^x mod N. Donat un N, trobeu Q = 2^q tal que $N^{2}\leq Q<2N^{2}$, cosa que implica $Q/r>N$. Els registres qubit d'entrada i sortida han de contenir superposicions dels valors entre 0 i Q − 1, i per tant tenen q qubits cadascun. Si s'utilitza el que semblaria que fos el doble de qubits necessaris, es garanteix que hi ha com a mínim N x diferents que produeixen la mateixa f(x), també quan el període r s'acosta a N/2.

1. Comenceu amb un parell de registres qubits d'entrada i sortida amb log₂N qubits cadascun, i inicialitzeu-los a

   $Q^{-1/2}\sum _{x=0}^{Q-1}\left|x\right\rangle \left|0\right\rangle$

   On x va de 0 a Q- 1. Aquest estat inicial és una superposició de Q estats.

2. Construïu f(x) com a funció quàntica i apliqueu-la a l'estat esmentat, per obtenir

   $Q^{-1/2}\sum _{x}\left|x,f(x)\right\rangle .$

   Això encara és una superposició de Q estats.

3. Apliqueu la transformada de Fourier quàntica al registre d'entrada. Aquesta transformada (que opera sobre una superposició d'una potència de dos Q = 2^q estats) utilitza una arrel de la unitat Q^ena tal que $\omega =e^{2\pi i/Q}$ per a distribuir l'amplitud de qualsevol estat $\left|x\right\rangle$ donat igualment entre tots els Q dels estats $\left|y\right\rangle$, i per a fer-ho d'una forma diferent per a cada x diferent.

   La transformada de Fourier quàntica en N punts es defineix com:

   $U_{QFT}\left|x\right\rangle =Q^{-1/2}\sum _{y}e^{2\pi ixy/Q}\left|y\right\rangle$

   $U_{QFT}\left|x\right\rangle =Q^{-1/2}\sum _{y}\omega ^{xy}\left|y\right\rangle$

   Això porta a l'estat final:

   $Q^{-1}\sum _{x}\sum _{y}\omega ^{xy}\left|y,f(x)\right\rangle .$

   Ara reordenem aquesta suma com a

   $Q^{-1}\sum _{z}\sum _{y}\left|y,z\right\rangle \sum _{x:\,f(x)=z}\omega ^{xy}.$

   Això és una superposició de molts més de Q estats, però molts menys de Q² estats, perquè hi ha menys de Q valors distints de $z=f(z)$. Siguin

   • $\omega =e^{2\pi i/Q}$ una arrel Q^ena de la unitat,
   • r el període de f,
   • x₀ la x més petita que compleix f(x) = z (tenim x₀ < r), i
   • b indexa aquestes x, anant des de 0 fins a $\lfloor (Q-x_{0}-1)/r\rfloor$ de manera que $x_{0}+rb<Q.$

   Llavors $\omega ^{ry}$ és un vector unitari en el pla complex ($\omega$ és una arrel de la unitat i r i y són enters), i el coeficient de $Q^{-1}\left|y,z\right\rangle$ en l'estat final és

   $\sum _{x:\,f(x)=z}\omega ^{xy}=\sum _{b}\omega ^{(x_{0}+rb)y}=\omega ^{x_{0}y}\sum _{b}\omega ^{rby}.$

   Cada terme d'aquesta suma representa un camí diferent cap al mateix resultat, i ocorre una interferència quàntica—constructiva quan els vectors unitaris $\omega ^{ryb}$ apunten en gairebé la mateixa direcció en el pla complex, cosa que requereix que $\omega ^{ry}$ apunti al llarg de l'eix real positiu.

4. Efectueu una mesura. Obtenim un cert resultat y en el registre d'entrada i f(x₀) en el registre de sortida. Com que f és periòdica, la probabilitat de mesurar cert y ve donada per

   $\left|Q^{-1}\sum _{x:\,f(x)=f(x_{0})}\omega ^{xy}\right|^{2}=Q^{-2}\left|\sum _{b}\omega ^{(x_{0}+rb)y}\right|^{2}=Q^{-2}\left|\sum _{b}\omega ^{bry}\right|^{2}.$

   L'anàlisi mostra ara que aquesta probabilitat és més alta com més proper és el vector unitari $\omega ^{ry}$ 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.

5. Com que $yr/Q$ é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:
   • A: s<N
   • B: |y/Q - d/s| < 1/2Q.

   Donades aquestes condicions (i suposant que d/s és una fracció irreduïble), és molt probable que s sigui el període apropiat r, o com a mínim en sigui un factor.

6. Comproveu (de forma clàssica) si $f(x)=f(x+s)\Leftrightarrow a^{r}\equiv 1{\pmod {N}}$. Si és així, ja estem.
7. Si no, obteniu més candidats a r usant múltiples de s, or usant altres s on d/s s'acosti a y/Q. Si qualsevol candidat compleix les condicions, ja estem.
8. Si no, aneu de nou al pas 1 del subprograma.

Explicació de l'algorisme

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 implementar de forma clàssica. La segona part troba 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

Els nombres enters menors que N i coprimers amb N formen un grup abelià finit sota multiplicació mòdul N, que es denota típicament (Z/NZ)^×. La mida la dona la Funció φ d'Euler. 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

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

Per tant, N és divisor d'a^r - 1 (es pot escriure com a N|(a^r - 1)). Suposeu que podem obtenir r, i és parell (si és imparell, vegeu el pas 5). Llavors

$a^{r}-1=(a^{r/2}-1)(a^{r/2}+1)\equiv 0\ {\mbox{mod}}\mathbb {N}$

$\Rightarrow N|(a^{r/2}-1)(a^{r/2}+1).\,$

r és el nombre enter positiu més petit tal que a^r ≡ 1, així que N no pot dividir (a^r/2 - 1). Si N tampoc divideix (a^r/2 +1), llavors N ha de tenir un factor comú no trivial amb (a^r/2 - 1) i (a^r/2 +1).

Prova: Per simplicitat, denotem (a^r/2 - 1) i (a^r/2 +1) o i v, respectivament. N|uv, per tant 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 (això és una propietat del màxim comú divisor). Multiplicant ambdós costats per v, trobem que MKN+nvN=v, i per tant N|v. Per contradicció, mcd(o,N) ≠ 1. Per un argument similar, mcd(v,N) ≠ 1.

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

Trobar el període

Per trobar el període, l'algorisme de Shor depèn totalment de la capacitat d'un ordinador quàntic 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.

Però 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. Si no fos pel teorema de no-clonació, podríem començar mesurant f(x) sense mesurar x, i llavors fer unes quantes còpies de l'estat resultant (que és una superposició d'estats que tenen tots la mateixa f(x)). Mesurar x en aquests estats proporcionaria diferents valors de x que donarien la mateixa f(x), i obtindríem el període. Però com que no podem fer còpies exactes d'un estat quàntic, aquest mètode no funciona. Per tant hem de transformar acuradament la superposició a un altre estat que retorni la resposta correcta amb alta probabilitat. Això s'aconsegueix utilitzant la transformada de Fourier quàntica.

Shor va haver de solucionar així tres "problemes d'implementació". Tots tres havien de tenir una implementació "ràpida", o sigui, que s'havien d'executar amb un nombre de portes quàntiques que sigui polinòmic en $\log N$.

1. Crear una superposició d'estats. Això es pot fer aplicant portes Hadamard a tots els qubits del registre d'entrada. Un enfocament alternatiu seria utilitzar la transformada de Fourier quàntica (vegeu a sota).
2. Implementar la funció f com una transformada quàntica. Per assolir això, Shor va utilitzar exponenciació per quadrats per a la seva transformació modular de l'exponenciació. És important de fer notar que aquest pas és més difícil d'implementar que la transformada de Fourier quàntica, perquè requereix qubits auxiliars, i força més portes per aconseguir-ho.
3. Realitzar una transformada de Fourier quàntica. Usant portes de rotació controlada i portes Hadamard, Shor va dissenyar un circuit per a la transformada de Fourier quàntica (amb Q = 2^q) que utilitza només $q(q-1)/2=O((\log Q)^{2})$ portes.

Després de totes aquestes transformacions una mesura donarà una aproximació al període r. Per simplicitat assumiu que hi ha una y tal que yr/Q és un nombre enter. Llavors la probabilitat de mesurar i és 1. Per veure-ho notem que

$e^{2\pi ibyr/Q}=1$

per a tots els nombres enters b. Per tant la suma el quadrat de la qual ens dona la probabilitat de la mesura y serà Q/r ja que b pren aproximadament Q/r valors i així la probabilitat és $1/r^{2}$. Hi ha r y tals que yr/Q és un nombre enter, i també r possibilitats per $f(x_{0})$, per tant la suma de les probabilitats és 1.

Nota: una altra manera d'explicar l'algorisme de Shor és observant que és precisament l'algorisme de valoració de fase quàntica disfressat.

Coll d'ampolla

El coll d'ampolla de l'algorisme de Shor és l'exponenciació modular quàntica, que és molt més lenta que la transformada de Fourier quàntica, i el pre- i post-processament de la part clàssica. Hi ha diferents maneres de construir i optimitzar circuits per a l'exponenciació modular. La més senzilla, i (actualment) la més pràctica és simular els circuits aritmètics convencionals amb portes reversibles, començant amb sumadors en onada (ripple-carry). Si es coneix la base i el mòdul de l'exponenciació, es faciliten optimitzacions addicionals. Els circuits reversibles utilitzen típicament de l'ordre de $n^{3}$ portes per $n$ qubits. Hi ha tècniques alternatives que milloren asimptòticament el nombre de portes utilitzant transformades de Fourier quàntiques, però no són competitives amb menys de 600 qubits degut a les constants elevades.

Vegeu també

• Anell factorial.

Enllaços externs

• 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:
• Quantum Computation and Quantum Information, Michael A. Nielsen, Isaac L. Chuang, Cambridge University Press, 2000 Arxivat 2005-10-17 a Wayback Machine. Un llibre de textos general en computació quàntica:(en anglès)
• Explicació molt didàctica sobre criptografia i l'algorisme de Shor a YouTube (anglès)