Non so se avete mai sentito parlare dell’algoritmo di fattorizzazione di Shor. Nel 1994 Peter Shor definì un algoritmo di fattorizzazione di un numero che, implementato su un computer quantistico, completa il compito in un tempo polinomiale rispetto alla dimensione del numero stesso. Occhei, il risultato è quasi certamente corretto: come sappiamo nel mondo quantistico certezze non ce ne possono essere: ma la probabilità di errore può essere resa piccola a piacere.

Questo risultato, se avessimo un computer quantistico funzionante, distruggerebbe tutti gli algoritmi di crittografia che si basano sulla difficoltà della fattorizzazione, come RSA: infatti gli algoritmi classici di fattorizzazione hanno una complessità che cresce esponenzialmente con la dimensione del numero, e quindi è molto più semplice moltiplicare due numeri primi grandi che partire dal prodotto e arrivare ai due numeri. E in effetti nel 2001 ci fu il primo computer quantistico che riuscì a fattorizzare 15 con l’algoritmo di Shor. Non molto, ma un punto di partenza.

È passato quasi un quarto di secolo. I computer quantistici sono diventati sempre più grandi. Eppure non si è ancora riusciti a fattorizzare 21. Craig Gidney spiega il perché. Qui sopra vedete il circuito logico usato per la fattorizzazione di 15. Ci sono sei porte entangling da due qubit e due porte di Toffoli (quelle con due pallini neri in verticale), ciascuna delle quali corrisponde a sei porte entangling. Con i tre rivelatori finali si ha un totale di 21 porte entangling. Non riporto il disegno di un circuito ottimizzato per la fattorizzazione di 21: se volete divertirvi guardatelo nell’articolo. Dico solo che ha 191 porte CNOT e 369 porte di Toffoli, per un totale di 2405 entangling: due ordini di grandezza in più! Insomma, quello che si guadagna in velocità di esecuzione si perde con gli interessi in complessità.

Ma la parte più divertente, almeno per me, è questo articolo, sempre di Gidney, che fattorizza i numeri fino a 255 e nota come per numeri così piccoli l’algoritmo è così stabile che funziona anche usando un generatore di numeri casuali anziché collassare lo stato quantistico! Insomma, possiamo ancora stare tranquilli per un po’ di tempo…