Fattorizzazione in Numeri Primi: Algoritmi Classici e Algoritmo Quantistico di Shor

Questo capitolo introduce la computazione quantistica e la descrizione delle sue principali componenti. Inoltre, verranno analizzati alcuni elementi della meccanica quantistica, necessari per comprendere la computazione quantistica, come la sovrapposizione degli stati, la misurazione, il parallelismo quantistico e l'entanglement.

Tutto questo per intendere nel miglior modo possibile il capitolo successivo che tratterrà un algoritmo quantistico per la fattorizzazione in numeri primi. La computazione quantistica è un nuovo paradigma di calcolo basato da una recente fisica nata agli inizi del secolo scorso: la sica o meccanica quantistica.

Tale fisica, a differenza di quella classica, riesce a descrivere quello che accade a livello microscopico, ad esempio cosa succede all'interno di un atomo. La computazione classica, come descritto nel primo capitolo, è basata sull'astrazione della macchina di Turing deterministica.

Tale modello rende la computazione non reversibile, cioè non si ha la possibilità di risalire ai vari step di computazione: da un passo specifico o anche da quello finale di una determinata computazione fino a ritornare al passo iniziale. È importante sottolineare che la meccanica quantistica è reversibile e questo implica che anche la computazione su cui si basa deve esserlo, a differenza della computazione classica.

In particolare non si ha come modello computazionale un sistema irreversibile come la macchina di Turing deterministica ma un modello reversibile di nome: macchina di Turing quantistica. In questo campo ci sono stati molti sviluppi negli ultimi decenni e quelli che
seguono sono tra i più importanti.

. C. Bennett nel 1973 mostrò che la computazione poteva essere fatta in maniera reversibile attraverso la costruzione di una macchina di Turing reversibile.
. Qualche anno dopo R. Feynman osservò che era impossibile simulare in modo efficiente un sistema quantistico in un computer classico. Inoltre propose un nuovo modello per un computer quantistico con la capacità di effettuare una tale simulazione.
. Nello stesso anno T. Tooli introdusse la porta reversibile che prende il suo nome.
. Nel 1985 D. Deutsch dimostrò l'universalità del computer quantistico descrivendo una macchina di Turing quantistica universale.