Algoritmo di Shor

In aritmetica modulare e Quantum Computing , l'algoritmo di Shor è un quantum algoritmo progettato da Peter Shor nel 1994, che i fattori di un numero intero naturale N in O tempo e nello spazio . $((\ log N) ^ {3})$ $O (\ log N)$

Molti sistemi crittografici a chiave pubblica , come RSA , diventerebbero vulnerabili se l'algoritmo di Shor fosse mai implementato in un pratico computer quantistico . Un messaggio crittografato con RSA può essere decrittografato prendendo in considerazione la sua chiave pubblica N , che è il prodotto di due numeri primi . Allo stato attuale delle conoscenze, non esiste un algoritmo classico in grado di farlo in tempo per qualsiasi k , quindi, gli algoritmi classici noti diventano rapidamente poco pratici quando N aumenta, a differenza dell'algoritmo di Shor che può rompere l'RSA in tempo polinomiale. È stato anche esteso per attaccare molti altri sistemi crittografici a chiave pubblica. $O ((\ log N) ^ {k})$

Come la maggior parte degli algoritmi del computer quantistico, l'algoritmo di Shor è probabilistico: fornisce la risposta corretta con alta probabilità e la probabilità di fallimento può essere ridotta ripetendo l'algoritmo.

L'algoritmo di Shor è stato utilizzato nel 2001 da un gruppo dell'IBM , che ha scomposto 15 in 3 e 5, utilizzando un calcolatore quantistico a 7 qubit .

Procedura

Sia N un numero naturale dato. L'algoritmo di Shor è quello di trovare un'intera pagina tra 2 e divide N . ${\ sqrt N}$

Consiste di due elementi:

Una riduzione del problema di fattorizzazione in un problema di ricerca dell'ordine , che può essere eseguita su un computer classico.
Un algoritmo quantistico per risolvere il problema della ricerca dell'ordine.

Parte classica

Prendi un numero pseudocasuale a < N
Calcola MCD ( a , N ). Questo può essere fatto usando l'algoritmo di Euclide .
Se MCD ( a , N ) ≠ 1, allora è un fattore non banale di N , che fornisce una soluzione al problema.
Altrimenti, usa la subroutine Trova periodo (sotto) per trovare r , il periodo della funzione , cioè il più piccolo intero r per cui . ${\ displaystyle f: x \ mapsto a ^ {x} \ {\ mbox {mod}} \ N}$ $f (x + r) = f (x)$
Se r è dispari , torna al passaggio 1.
Se un r / 2 ≡ −1 (mod N ), torna al passaggio 1.
I fattori di N sono MCD (a r / 2 ± 1, N ), che risolve il problema.

Parte quantistica: subroutine di ricerca del periodo

Inizia con i registri di input e output di ogni registro 2 N qubit e inizializzali per: $N ^ {{- 1/2}} \ sum _ {x} \ sinistra | x \ destra \ rangle \ sinistra | 0 \ destra \ rangle$ dove x va da 0 a N - 1.
Costruisci f ( x ) come una funzione quantistica e applicala allo stato precedente, per ottenere $N ^ {{- 1/2}} \ sum _ {x} \ sinistra | x \ destra \ rangle \ sinistra | f (x) \ destra \ rangle$
Applicare la trasformata quantistica di Fourier al registro di ingresso. La trasformata quantistica di Fourier su N punti è definita da: $U _ {{QFT}} \ sinistra | x \ destra \ rangle = N ^ {{- 1/2}} \ sum _ {y} e ^ {{2 \ pi ixy / N}} \ sinistra | y \ destra \ rangle$ Che dà il seguente stato: $N ^ {{- 1}} \ sum _ {x} \ sum _ {y} e ^ {{2 \ pi ixy / N}} \ sinistra | y \ destra \ rangle \ sinistra | f (x) \ destra \ rangle$
Prendi una misura. Ciò fornisce un certo valore y nel registro di ingresso e nel registro di uscita. Poiché f è periodico, la probabilità di misurare un certo y è data da $f (x_ {0})$ $\ left | N ^ {{- 1}} \ sum _ {{x: \, f (x) = f (x_ {0})}} e ^ {{2 \ pi ixy / N}} \ right | ^ {2} = \ left | N ^ {{- 1}} \ sum _ {{b}} e ^ {{2 \ pi i (x_ {0} + rb) y / N}} \ right | ^ {2 }$ Il calcolo mostra che questa probabilità è maggiore quando yr / N è vicino a un numero intero.
Metti y / N in forma irriducibile ed estrai il denominatore r ′, che è un candidato per r .
Controlla se f ( x ) = f ( x + r ′). Se è così, è finita.
Altrimenti, ottieni più candidati per r utilizzando valori vicini a y o multipli di r ′. Se un altro candidato cammina, è finita.
Altrimenti, torna al passaggio 1 della routine.

Spiegazione dell'algoritmo

L'algoritmo è composto da due parti. La prima parte trasforma il problema della fattorizzazione in un problema di trovare il periodo di una funzione e può essere implementata in modo classico. La seconda parte trova il periodo utilizzando la trasformata quantistica di Fourier ed è responsabile dell'accelerazione quantistica.

Ottieni fattori dal periodo

Gli interi minori di N e primi con N formano un gruppo finito dotato della moltiplicazione modulo N , che è tipicamente denotata ( Z / N Z ) × . La fine del passaggio 3 rende possibile determinare un intero a in questo gruppo. Poiché il gruppo è finito, a ha (secondo il teorema di Eulero ) un ordine finito r , definito come il più piccolo intero positivo tale che

a ^ {r} \ equiv 1 \ {\ mbox {mod}} \ N

Pertanto, N | ( a r - 1). Supponiamo che sia possibile determinare r , e che sia pari . Allora

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

, da dove

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

r è il più piccolo numero intero positivo tale che N divide ( a r - 1), quindi N non può dividere ( a r / 2 - 1). Se anche N non divide ( a r / 2 + 1), allora N deve avere un fattore comune non banale con ciascuno di ( a r / 2 - 1) e ( a r / 2 + 1).

Dimostrazione: denotano ( un r / 2 - 1) e ( a r / 2 + 1) u e v rispettivamente. N | uv , quindi kN = uv per un numero intero k . Supponiamo che MCD ( u , N ) = 1; quindi mu + nN = 1 per alcuni numeri interi m e n ( identità di Bézout ). Moltiplicando su entrambi i lati per v , troviamo che mkN + nvN = v , quindi N | v . Per contraddizione, MCD ( u , N ) ≠ 1. Con un argomento simile, MCD ( v , N ) ≠ 1.

Ciò fornisce una fattorizzazione N . Se N è il prodotto di due numeri primi, è l' unica possibile fattorizzazione.

Trova il periodo

L'algoritmo di ricerca del periodo di Shor è fortemente correlato alla capacità di un computer quantistico di trovarsi in molti stati contemporaneamente. I fisici chiamano questo comportamento una " sovrapposizione " di stati. Per calcolare il periodo di una funzione f , valutiamo la funzione in tutti i suoi punti contemporaneamente.

Eppure la fisica quantistica non ci consente di accedere direttamente a tutte le informazioni. Una misurazione fornirà solo uno di tutti i valori possibili mentre distruggerà tutti gli altri. Quindi dobbiamo trasformare attentamente la sovrapposizione in un altro stato che restituirà la risposta corretta con alta probabilità. Ciò è ottenuto dalla trasformata quantistica di Fourier .

Shor ha quindi dovuto risolvere tre problemi di "implementazione". Tutti loro sono state attuate "rapido", il che significa che possono essere realizzate con un numero di porte logiche quantistiche che è polinomiale in . $\ log N$

Crea una sovrapposizione di stati. Questo può essere fatto applicando le porte Hadamard a tutti i qubit nel registro di input. Un altro approccio potrebbe essere quello di utilizzare la trasformata quantistica di Fourier (vedi sotto).
Implementa la funzione f come trasformazione quantistica. Per ottenere ciò, Shor ha utilizzato l' elevazione al quadrato per la sua trasformazione a esponenziazione modulare.
Esegui una trasformazione quantistica di Fourier. Utilizzando le porte UNControlled e le porte qubit a rotazione singola, Shor ha progettato un circuito per la trasformata quantistica di Fourier che utilizza solo porte. $O ((\ log N) ^ {2})$

Dopo tutte queste trasformazioni, una misurazione fornirà un'approssimazione del periodo r . Per semplificare, assicuriamoci che esista un y tale che yr / N sia un numero intero. Allora la probabilità di misurare y è 1. Per vedere questo, nota che quindi per tutti gli interi b . Pertanto, la somma che ci dà la probabilità di misurare y sarà N / r poiché b assume globalmente valori N / r e quindi la probabilità è 1 / r . Esiste r y tale che yr / N sia un numero intero quindi le probabilità sommano 1. $e ^ {{2 \ pi ibyr / N}} = 1 \,$

Nota: un altro modo per spiegare l'algoritmo di Shor è notare che è solo l' algoritmo di stima della fase quantistica sotto mentite spoglie.

Note e riferimenti

(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato “ Algoritmo di Shor ” ( vedi la lista degli autori ) .

(in) Michael Ross, " IBM's Test-Tube Quantum Computer Makes History " su www-03.ibm.com ,19 dicembre 2001(accessibile il 1 ° agosto 2016 ) .

Appendici

Bibliografia

(en) Peter W. Shor, Algoritmi in tempo polinomiale per la fattorizzazione in fattori primi e logaritmi discreti su un computer quantistico . " Quant-ph / 9508027 " , testo liberamente accessibile, su arXiv .
(en) Michael A. Nielsen e Isaac L. Chuang, Quantum Computation and Quantum Information , Cambridge University Press, 2000Un libro generalista sull'informatica quantistica

link esterno

Una spiegazione dell'algoritmo di Shor, senza calcoli, il blog di Scott Aaronson