Algoritme de Shor

En computació quàntica, el algoritme de Shor és un algoritme quàntic para descompondre en factors un número N en temps O((log N)³) i espai O(logN), aixina nomenat per Peter Shor.

L'algoritme de Shor és un procediment que permet trobar factors d'un número d'una manera eficient. L'implementació d'este algoritme es pot portar a terme de manera clàssica o utilisant circuits quàntics (que no han segut duts a la pràctica encara). Esta última implementació és (per supost) la més convenient quan es desija trobar l'orde, un paràmetro molt necessari a l'hora de trobar els factors primers d'un cert número.

Moltes criptografia de clau pública, tals com RSA, aplegarien a ser obsoletes si l'algoritme de Shor és implementat alguna volta en una computadora quàntica pràctica. Un mensage sifrat en RSA pot ser dessifrat descomponent en factors la clau pública N, que és el producte de dos número primo. Els algoritmes clàssics coneguts no poden fer açò en temps O((log N)^k) per a cap k, aixina que apleguen a ser ràpidament poc pràctics a mida que s'aumenta N. Pel contrari, l'algoritme de Shor pot trencar RSA en temps polinòmic. També s'ha ampliat per a atacar moltes atres criptografia públiques.

Com tots els algoritmes de computació quàntica, l'algoritme de Shor és provabilístic: dona la resposta correcta en alta provabilitat, i la provabilitat de fallo pot ser disminuïda repetint l'algoritme.

L'algoritme de Shor va ser aplicat en la pràctica en 2001 per un grup en IBM, que va descompondre 15 en els seus factors 3 i 5, usant una computadora quàntica en 7 qubits.

Procediment

El problema que intenta solucionar l'algoritme de Shor és que, donat un número entero N, intentem trobar un atre número entero p entre 1 i N que dividixca N.

L'algoritme de Shor consistix en dos parts:

Una reducció del problema de descompondre en factors al problema de trobar l'orde, que es pot fer en una computadora clàssica.
Un algoritme quàntic per a solucionar el problema de trobar el periodo.

Part clàssica

Trie un número pseudo-aleatori a < N.
Compute el mcd(a, N). Açò es pot fer usant l'algoritme de Euclides.

Si el mcd(a, N) ≠ 1, llavors és un factor no trivial de N, aixina que terminem.

Si no, utilise el subprograma per a trobar el periodo (vore avall) per a trobar r, el periodo de la funció següent:

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

és dir l'número entero més chicotet r per al qual

$f (x + r) = f (x)$ .
Si r és impar, vaja de nou al pas 1.
Si a^r/2 ≡ -1 (mod N), vaja de nou al pas 1.
Els factors de N són el mcd(a^r/2 ± 1, N). Terminem.

Part quàntica: subprograma per a trobar el periodo

Comence en un parell de registres qubits d'entrada i eixida en log₂N qubits cada u, i inicialícelos a #: $N^{- 1 / 2} \sum_{x = 0}^{N - 1} | x ⟩ | 0 ⟩$

Construïxca f(x) com a funció quàntica i aplique-la a l'estat antedicho, per a obtindre
$N^{- 1 / 2} \sum_{x = 0}^{N - 1} | x ⟩ | f (x) ⟩$
Aplique la transformada quàntica de Fourier al registre d'entrada. La transformada quàntica de Fourier en N punts es definix com:
$U_{Q F T} | x ⟩ = N^{- 1 / 2} \sum_{y} e^{2 π i x y / N} | y ⟩$

Lo que nos deixa en l'estat següent:

$N^{- 1} \sum_{x} \sum_{y} e^{2 π i x y / N} | y ⟩ | f (x) ⟩$

Realise una medició. Obtenim un cert resultat i en el registre d'entrada i f(x₀) en el registre d'eixida. Este pas no és necessari, ya que, d'acort en el principi de medició en diferit, el resultat serà el mateix al final de l'algoritme independentment de que es realise una medició. No obstant, per raons de simplificació a l'hora d'entendre l'algoritme, inclourem este pas. ya que f és periòdica, la provabilitat de medir cert i ve donada per #: $N^{- 1} {| \sum_{x : f (x) = f (x_{0})} e^{2 π i x y / N} |}^{2} = N^{- 1} {| \sum_{b} e^{2 π i (x_{0} + r b) y / N} |}^{2}$

L'anàlisis mostra ara que quant més alta és esta provabilitat, tant més el yr/N és propenc a un número entero.
Convertixca a i/N en una fracció irreducible, i extraga el denominador r ', que és un candidat a r.
Comprove si f(x) = f(x + r '). Si és aixina terminem.
Si no, obtinga més candidats a r usant valors propencs a i, o múltiples de r '. Si qualsevol candidat complix les condicions, terminem.
Si no, vaja de nou al pas 1 del subprograma.

Explicació de l'algoritme

L'algoritme es compon de dos parts. La primera part de l'algoritme convertix el problema de descompondre en factors en el problema de trobar el periodo d'una funció, i es pot implementar clásicamente. La segona part troba el periodo usant la transformada de Fourier quàntica, i és responsable de l'acceleració quàntica.

I. El problema de la factorización.

Siga $N \in ℕ$ . Llavors, trobar un factor $x \in ℕ$ , és trobar una solució per a l'equació:

m o d (x^{r}, N) = 1 (*)

A l'hora d'intentar abordar este problema, existixen un parell de teoremes que són útils:

Teorema 1

Siga $N \in ℕ$ , i siga $x$ una solució de l'equació (*) (solució no trivial) a on és clar $1 < x ⩽ N$ . Llavors: O $m c d (x + 1, N)$ o $m c d (x - 1, N)$ és un factor no trivial del número $N$ ("mcd" significa el màxim comú divisor).^[1]

Teorema 2

Siga $N \in ℕ$ impar en descomposició en factors primers $N = p_{1}^{α_{1}} \cdot ... \cdot p_{m}^{α_{m}}$ . Siga ademés $y \in ℕ$ (aleatori) que és coprimo en $N$ ( $1 < y ⩽ N - 1$ ) i $r$ l'orde d'eixe número entero, és dir, aquell $r$ tal que: $m o d (y^{r}, N) = 1$ . (D'este últim pas, açò és, trobar r, s'encarrega el circuit quàntic corresponent). Llavors:

$P r o b (r par \land m o d (y^{\frac{r}{2}}, N) \neq - 1) \geq 1 - (\frac{1}{2})^{m}$

En estes dos teoremes en ment, ya es pot escomençar a plantejar la seqüència en la que està basada l'algoritme d'factorización de Shor.

Notes:

La notació que s'utilisa és, en tot moment coherent, en el sentit de que les variables que apareixen en les teoremes i fòra d'ells o en qualsevol atre context d'a continuació són les mateixes.

Per un atre costat, la relació que presenten les variables $x$ i $y$ és: $y = x^{\frac{r}{2}}$ . Com es va a poder vore en la següent secció.^[1]

II. L'algoritme de Shor.

Este algoritme servix per a factorizar número entero de gran tamany. S'exponen i es comenten totes les fases d'este algoritme. En tot moment, l'algoritme va a tornar un factor del número $N$ que es desija descompondre. Els tres primers casos corresponen a una implementació clàssica, en el sentit de que no és necessària la presència de cap circuit quàntic. Corresponen per tant a l'eliminació de casos de tipo trivial o que una implementació clàssica pot realisar en suficientment bona eficiència.

1) Si $N$ és parell.

En efecte, la primera comprovació que es realisa al número és el cas trivial de que la seua última sifra siga un número par. En tal cas, l'algoritme torna 2, i el programa podrà continuar en $\frac{N}{2}$ .

2) $N$ és de la forma $a^{b}$ .

La següent fase, és implementar una comprovació per als número entero $a$ majors o iguals a 1 i números $b$ majors o iguals a 2. S'ha de tindre en conte este tipo de números per a que (com es vorà en el pas 4) en utilisar la teorema 2 la provabilitat d'obtindre un bon candidat a factor siga més alta del 75%. En este cas, l'algoritme, torna el factor a.

3) Procediment aleatori.

Es pren un número $y$ tal que $1 < y ⩽ N - 1$ . Si $m c d (y, N) > 1$ , llavors el programa torna precisament este número. Açò es fa solament per a comprovar si el número elegit compartix factors en $N$ . En cas que els dos números siguen coprimos se seguix en el següent pas de la série.

En este punt, donat l'número natural $y$ anterior, s'utilisen els algoritmes d'estimació de fase i en concret d'orde, per a trobar precisament $r$ (l'orde). Estos algoritmes com es pot vore en els enllaços, depenen de l'implementació del circuit quàntic en qüestió.

4) Càlcul de $r$ i aplicació de les teoremes.

Com ya es va dir abans, partim de que es coneix l'orde. Ara, s'apliquen les teoremes anteriors per a intentar trobar este factor.

La primera part d'este últim pas, consistix en la comprovació de si es complixen els requisits que la teorema 2 impon per a assegurar una alta provabilitat. Açò ya es va fer en els procediments anteriors, puix se sap que; $N$ és impar, té a lo manco dos factors primers distints $y$ és coprimo en $N$ . Baixe estes condicions, és possible assegurar que existix una alta provabilitat de que el número $x$ siga no trivial, açò és: $m o d (y^{\frac{r}{2}}, N) \neq - 1$

i que per supost

r

és parell.

I havent comprovat açò, s'està en disposició d'aplicar la teorema 1 puix es complixen a la seua volta totes les condicions necessàries per a poder aplicar-ho i d'esta forma obtindre en alta provabilitat un factor de $N$ . Be $m c d (x + 1, N)$ o $m c d (x - 1, N)$ .

Com es veu tot este procés depén d'una certa provabilitat d'èxit. Si en algun punt l'algoritme falla, comença de nou.^[1]^[2]^[3]

III. Obtenció de factors a partir del periodo

Els número entero menors que N i coprimos en N formen un grup finito baix multiplicació mòdul N, que es denota típicament $ℤ_{N}^{*}$ . Per al final del pas 3, tenim un número entero a en este grup. ya que el grup és finito, a deu tindre un orde finito r, l'número entero positiu més chicotet tal que

a^{r} \equiv 1 mod N .

Per lo tant, N |(a^r - 1). Suponga que podem obtindre r, i és parell. Llavors

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

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

r és l'número entero positiu més menut tal que a ^r ≡ 1, aixina que N no pot dividir a (a ^r/2 - 1). Si N tampoc dividix (a^r/2 + 1), llavors N deu tindre un factor comú no trivial en (a^r/2 - 1) i (a ^r/2 + 1).

Prova: Per simplicitat, denote (a^r/2 - 1) i (a^r/2 + 1) o i v respectivament. N | uv, després kN = uv per a un cert número entero k. Suponga que el mcd(o, N) = 1; llavors mu + nN = 1 per a certs número entero m i n (esta és una propietat del màxim comú divisor). Multiplicant abdó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.

Açò nos proveïx d'una factorización de N. Si N és el producte de dos cosins, esta és la única factorización possible.

IV. Trobar el periodo

L'algoritme, per a trobar el periodo de Shor, es basa radicalment en la capacitat d'una computadora quàntica d'estar en molts estats simultàneament. Els físics criden a este comportament superposició quàntica. Per a computar el periodo d'una funció f, evaluem la funció en tots els punts simultàneament.

No obstant, la física quàntica no permet que tingam accés a tota esta informació directament. Una medició quàntica donarà solament un de tots els valors possibles, destruint tots els atres. Per lo tant tenim que transformar cuidadosadament la superposició a un atre estat que torne la resposta correcta en alta provabilitat. Açò és alcançat usant la transformada de Fourier quàntica.

Shor va tindre que solucionar aixina tres "problemes d'implementació". Tots varen tindre que ser implementats "ràpits", que significa eixecutar en un número de portes quàntiques que és polinòmic en logN.

Crear una superposició d'estats. Açò pot fer-se aplicant les portes de Hadamard a tots els qubits en el registre d'entrada. Un atre enfocament seria utilisar la transformada de Fourier quàntica (vore avall).
Implementar la funció f com una transformada quàntica. Per a alcançar açò, Shor va utilisar exponenciación per quadrats per a la seua transformació modular de la exponenciación.
Realisar 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 usa exactament ((logN)²) portes.

Despuix de totes estes transformacions una medició donarà una aproximació al periodo r. Per simplicitat assumixca que hi ha una i tal que yr/N és un número entero. Llavors la provabilitat de medir i és 1. Per a vore açò notem que

e^{2 π i b y r / N} = 1

per a tots els número entero b. Per lo tant la suma que nos dona la provabilitat de la medició i serà N/r posat que b pren aproximadament N/r valores i aixina la provabilitat és 1/r. Hi ha r, i tals que yr/N és un número entero, després la suma de les provabilitats és 1. Nota: una atra manera d'explicar l'algoritme de Shor és observant que és precisament l'algoritme quàntic d'estimació de fase disfrassat.

Vore també

Referències

↑ ^1,0 ^1,1 ^1,2 Nielsen, Michael A.; Chuang, {{{nom2}}} (2000). Quàntum computation and quàntum information, Cambridge University Press, p. pp233. OCLC 43641333. ISBN 0521632358.
↑ SIAM Review.41(2)
303–332.ISSN 0036-1445.doi:10.1137/s0036144598347011.
↑ «Una miqueta de computació quàntica. Algoritmes més comuns. Guillermo Morals Lluna». Archivat des d'el original, el 7 de decembre de 2010. Consultat el 29 de maig de 2018.

Referències

Este artícul conté una traducció derivada de «Algoritmo de Shor» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[:0-1] 1,0 ^1,1 ^1,2 Nielsen, Michael A.; Chuang, {{{nom2}}} (2000). Quàntum computation and quàntum information, Cambridge University Press, p. pp233. OCLC 43641333. ISBN 0521632358.

[2] SIAM Review.41(2)
303–332.ISSN 0036-1445.doi:10.1137/s0036144598347011.

[3] «Una miqueta de computació quàntica. Algoritmes més comuns. Guillermo Morals Lluna». Archivat des d'el original, el 7 de decembre de 2010. Consultat el 29 de maig de 2018.

[1]

[2]

[3]

Procediment

Part clàssica

Part quàntica: subprograma per a trobar el periodo

Explicació de l'algoritme

I. El problema de la factorización.

Teorema 1

Teorema 2

II. L'algoritme de Shor.

1) Si N és parell.

2) N és de la forma ab.

3) Procediment aleatori.

4) Càlcul de r i aplicació de les teoremes.

III. Obtenció de factors a partir del periodo

IV. Trobar el periodo

Vore també

Referències

Referències

1) Si $N$ és parell.

2) $N$ és de la forma $a^{b}$ .

4) Càlcul de $r$ i aplicació de les teoremes.