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…
Più traffico con i simulatori e più sono stupito di quanto poco si possa fare con i tali calcolatori se uno non è (davvero) capace. Senza considerare che se uno è (davvero) capace allora con i tali calcolatori risulta sempre che ci può fare poco.
Però sono anche convinto che non vedrò tanto presto dei paper che spiegano quello che ci si fa oggi in ambito di traffici satellitari, guerre di pace, ecc.
Ho presente il caso di chi ha ricevuto una notifica non trascurabile per aver accennato a un keylogger su smartphone che non esiste, figuriamoci se un giusto vantaggio patriottico può essere perso spiegando i calcoletti!
beh, mi pare ovvio che se ci sono così tanti paperi sul (non) funzionamento dei computer quantistici è proprio perché non funzionano, e quindi scriverci su non è pericoloso.
Pensare che funzionino davvero e quindi facciano scrivere quei paperi perché la gente non si metta a studiarli sul serio mi sembra un po’ troppo complottista.
Quanto non ci ho capito davvero nulla! Vale la pena approfondire per capire? Così, su due piedi, direi di no, viste le conclusioni che mi sembra di aver intuito (molto fumo e poco arrosto per ora)… :D
diciamo che io non ci perdo più tempo di quello che ho passato a scrivere questo post :-)