Algoritmo di fattorizzazione di Shor

L'algoritmo di fattorizzazione di Shor è un algoritmo ideato da Peter Shor nel 1994 per risolvere il problema della fattorizzazione dei numeri interi in numeri primi.

Su un computer quantistico questo algoritmo ha una complessità computazionale BQP (Bounded error Quantum Polynomial time): i fattori primi vengono trovati con un margine d'errore arbitrariamente piccolo in "tempo polinomiale" nella[non chiaro] lunghezza del numero intero da fattorizzare.

Procedura

L'algoritmo di Shor consiste di due passi:

  1. Una riduzione, che può essere eseguita su un computer classico, del problema di fattorizzazione a un problema di calcolo dell'ordine.
  2. La risoluzione, tramite un algoritmo quantistico del problema del calcolo dell'ordine.

Riduzione del problema

Voce da controllare
Questa voce o sezione sull'argomento matematica è ritenuta da controllare.
Motivo: La parte sui periodi è completamente sbagliata, da come è scritta la definizione risulta una funzione costante dopo l'intero t

Sia n {\displaystyle n} il numero da fattorizzare. Il problema di fattorizzarlo in fattori primi si può ridurre a massimo log(n) problemi di fattorizzazione binaria in numeri non per forza primi.

Viene scelto un numero a < n {\displaystyle a<n} tale che a {\displaystyle a} sia coprimo con n {\displaystyle n} : il massimo comun divisore tra i due vale dunque 1.

Si definisce una successione sugli interi positivi k {\displaystyle k} :

f ( k ) ≡ a k ( mod n ) {\displaystyle f(k)\equiv a^{k}{\pmod {n}}}

tale che uno dei termini della successione è uguale a 1, e i seguenti si ripetono in modo periodico, ossia

f ( k + t ) = f ( k ) , {\displaystyle f(k+t)=f(k),}

per gli interi k > r {\displaystyle k>r} e per un dato periodo t {\displaystyle t} , dove r {\displaystyle r} è il più piccolo intero per cui f ( r ) ≡ a r ≡ 1 ( mod n ) {\displaystyle f(r)\equiv a^{r}\equiv 1{\pmod {n}}} , e si dice ordine moltiplicativo di a {\displaystyle a} modulo n {\displaystyle n} . È anche uguale al periodo della successione.

Se r {\displaystyle r} è pari, almeno un fattore di n {\displaystyle n} si trova tra i due numeri:

  • M C D ( a r / 2 + 1 , n ) , {\displaystyle \mathrm {MCD} (a^{r/2}+1,n),}
  • M C D ( a r / 2 − 1 , n ) , {\displaystyle \mathrm {MCD} (a^{r/2}-1,n),}

infatti

a r ≡ 1 ( mod n ) , {\displaystyle a^{r}\equiv 1{\pmod {n}},}
( a r / 2 ) 2 − 1 ≡ 0 ( mod n ) , {\displaystyle (a^{r/2})^{2}-1\equiv 0{\pmod {n}},}
( a r / 2 + 1 ) ( a r / 2 − 1 ) ≡ 0 ( mod n ) . {\displaystyle (a^{r/2}+1)(a^{r/2}-1)\equiv 0{\pmod {n}}.}

Ad esempio con n = 143 , {\displaystyle n=143,} e scegliendo a = 21 , {\displaystyle a=21,} l'ordine è 4 {\displaystyle 4} , infatti f ( 4 ) ≡ 21 4 ≡ 1 ( mod 143 ) {\displaystyle f(4)\equiv 21^{4}\equiv 1{\pmod {143}}} .

Si ha

( 21 4 / 2 − 1 ) ( 21 4 / 2 + 1 ) ≡ 0 ( mod 143 ) , {\displaystyle (21^{4/2}-1)(21^{4/2}+1)\equiv 0{\pmod {143}},}

da cui segue che 440 ⋅ 442 ≡ 0 ( mod 143 ) {\displaystyle 440\cdot 442\equiv 0{\pmod {143}}} .

I M C D {\displaystyle \mathrm {MCD} } tra i due termini e n {\displaystyle n} sono i candidati fattori primi:

M C D ( 440 , 143 ) = 11 , {\displaystyle \mathrm {MCD} (440,143)=11,}
M C D ( 442 , 143 ) = 13 , {\displaystyle \mathrm {MCD} (442,143)=13,}

che sono effettivamente i fattori di n {\displaystyle n} , 11 e 13.

Calcolo dell'ordine

Individuare l'ordine è un problema di cui non si conosce una soluzione deterministica efficiente con un computer classico. L'introduzione di Peter Shor è quella di un algoritmo quantistico in grado di fornire l'ordine r {\displaystyle r} in "tempo polinomiale" nella[non chiaro] lunghezza di n {\displaystyle n} . L'algoritmo utilizza la codifica e l'estrazione di informazioni (tramite la trasformata di Fourier quantistica) dalle fasi relative tra gli stati quantistici (qubit), proprietà che non ha un equivalente classico.

Esistono diverse versioni dell'algoritmo. Quella presentata da Shor nel 1994 è la seguente:

  1. Si considerino due registri, di q {\displaystyle q} e m {\displaystyle m} qubit. Il primo sia inizializzato alla rappresentazione binaria di | 0 ⟩ {\displaystyle |0\rangle } , ossia | 0 ⟩ ⊗ q {\displaystyle |0\rangle ^{\otimes q}} . Il secondo a | 1 ⟩ {\displaystyle |1\rangle } , rappresentato su m {\displaystyle m} cifre come | 0 ⟩ ⊗ m − 1 | 1 ⟩ {\displaystyle |0\rangle ^{\otimes m-1}|1\rangle } .
  2. Sul primo registro si opera una porta di Hadamard a q {\displaystyle q} qubit. Il primo registro si trova così in uno stato ( | 0 ⟩ + | 1 ⟩ ) ⊗ q {\displaystyle (|0\rangle +|1\rangle )^{\otimes q}} (si omettono le normalizzazioni). Si può osservare che questo stato è la sovrapposizione uniforme di tutti gli stati che codificano per numeri x < 2 q {\displaystyle x<2^{q}} .
  3. Il primo registro controlla l'azione di U a x {\displaystyle U_{a}^{x}} sul secondo. L'operatore si definisce come U a | y ⟩ = | y a ( mod n ) ⟩ {\displaystyle U_{a}|y\rangle =|ya{\pmod {n}}\rangle } .
    L'operatore U a {\displaystyle U_{a}} è una radice r {\displaystyle r} -esima dell'unità, dove r {\displaystyle r} è l'ordine moltiplicativo di a {\displaystyle a} modulo n {\displaystyle n} , ha quindi autovalori del tipo e 2 π i k r {\displaystyle e^{2\pi i{\frac {k}{r}}}} per 0 ≤ k < r {\displaystyle 0\leq k<r} . Si può mostrare che la sovrapposizione omogenea degli autostati è esattamente lo stato | 1 ⟩ {\displaystyle |1\rangle } . Far controllare l'azione di U a x {\displaystyle U_{a}^{x}} allo stato del primo registro, in sovrapposizione di tutti gli x < 2 q {\displaystyle x<2^{q}} fa in modo che le fasi e 2 π i k r {\displaystyle e^{2\pi i{\frac {k}{r}}}} compaiano nello stato finale.
  4. La trasformata di Fourier quantistica estrae queste fasi e le rende misurabili in base computazionale sul primo registro.

Diverse ripetizioni dell'algoritmo forniscono varie stime di k r {\displaystyle {\tfrac {k}{r}}} , da cui si può riconoscere r {\displaystyle r} . Il k {\displaystyle k} misurato ad ogni esecuzione è casuale, tra tutti quelli minori di r {\displaystyle r} : da solo può risultare fuorviante (ad esempio se divide r {\displaystyle r} ).

Efficienza

L'algoritmo presentato ha complessità di ordine log 2 ⁡ N ⋅ log ⁡ log ⁡ N ⋅ log ⁡ log ⁡ log ⁡ N {\displaystyle \log ^{2}N\cdot \log \log N\cdot \log \log \log N} . La restante parte della fattorizzazione, espressa sopra, è comune agli algoritmi classici ed è già efficiente: l'accelerazione che l'algoritmo di Shor dà al problema del calcolo dell'ordine, quindi, rende efficiente l'intero algoritmo di fattorizzazione.

L'algoritmo, tuttavia, non è deterministico, ed ha una probabilità di successo minore di 1: si può comunque ripeterne l'iterazione per abbassare la soglia d'errore.

Implementazione

Non esiste una macchina quantistica scalabile che implementi la versione descritta dell'algoritmo di Shor. Versioni compilate, ossia ridotte per casi specifici, sono invece già state eseguite: ad esempio su sistemi ottici lineari, dove i qubit sono codificati nella polarizzazione dei fotoni.

Bibliografia

  • (EN) Peter Shor, Algorithms for quantum computation: Discrete log and factoring, in Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, Santa Fe, IEEE Computer Society Press, novembre 1994, pp. 124-134.
  • (EN) Phillip Kaye, Raymond Laflamme, Michele Mosca, Finding-Orders, in An introduction to quantum computing, Oxford, Oxford University Press, 2007, ISBN 978-0-19-857049-3.

Voci correlate

  Portale Fisica
  Portale Informatica