Sulla base di un algoritmo rivoluzionario, i ricercatori propongono un modo per realizzare un circuito di fattorizzazione quantistica più piccolo e più tollerante al rumore per la crittografia
L'e-mail più recente che hai inviato è stata probabilmente crittografata utilizzando un metodo collaudato che si basa sull'idea che perfino il computer più veloce non sarebbe in grado di scomporre in modo efficiente un numero enorme in fattori. I computer quantistici, d'altro canto, promettono di decifrare rapidamente sistemi crittografici complessi che un computer classico potrebbe non essere mai in grado di svelare. Questa promessa si basa su un algoritmo di fattorizzazione quantistica proposto nel 1994 dal dottor Peter Shor (1), che ora è professore al MIT.
Ma nonostante i ricercatori abbiano fatto grandi passi avanti negli ultimi 30 anni, gli scienziati devono ancora costruire un computer quantistico sufficientemente potente da eseguire l'algoritmo di Shor.
Mentre alcuni ricercatori lavorano per costruire computer quantistici più grandi, altri hanno cercato di migliorare l'algoritmo di Shor in modo che potesse funzionare su un circuito quantistico più piccolo. Circa un anno fa, il dottor Oded Regev, informatico presso la New York University, ha proposto un importante miglioramento teorico (2). Il suo algoritmo potrebbe funzionare più velocemente, ma il circuito richiederebbe più memoria.
Sulla base di questi risultati, i ricercatori del MIT hanno proposto un approccio “best-of-both-worlds” che combina la velocità dell'algoritmo di Regev con l'efficienza di memoria di quello di Shor. Questo nuovo algoritmo è veloce quanto quello di Regev, richiede meno blocchi di costruzione quantistici noti come qubit e ha una tolleranza maggiore al rumore quantistico, il che potrebbe renderlo più fattibile da implementare nella pratica.
A lungo termine, questo nuovo algoritmo potrebbe guidare lo sviluppo di nuovi metodi di crittografia in grado di contrastare la potenza di decifrazione dei computer quantistici.
«Se mai venissero costruiti computer quantistici su larga scala, allora il factoring sarebbe un fallimento e dovremmo trovare qualcos'altro da usare per la crittografia. Ma quanto è reale questa minaccia? Possiamo rendere pratico il factoring quantistico? Il nostro lavoro potrebbe potenzialmente portarci un passo più vicini a un'implementazione pratica», afferma il dottor Vinod Vaikuntanathan (3), Ford Foundation Professor of Engineering, membro del Computer Science and Artificial Intelligence Laboratory (CSAIL) e autore senior di un articolo che descrive l'algoritmo (4).
L'autore principale della ricerca è il dottor Seyoon Ragavan, uno studente laureato del MIT Department of Electrical Engineering and Computer Science. La ricerca sarà presentata alla International Cryptology Conference del 2024.
Cracking della crittografia
Per trasmettere messaggi in modo sicuro su Internet, i provider di servizi come client di posta elettronica e app di messaggistica in genere si affidano a RSA, uno schema di crittografia (5) inventato dai ricercatori del MIT Ron Rivest, Adi Shamir e Leonard Adleman negli anni '70 (da cui il nome “RSA”). Il sistema si basa sull'idea che la scomposizione in fattori di un intero di 2.048 bit (un numero con 617 cifre) sia troppo difficile da eseguire per un computer in un lasso di tempo ragionevole.
Questa idea fu capovolta nel 1994 quando Shor, collaboratore all'epoca presso i Bell Labs, introdusse un algoritmo che dimostrò come un computer quantistico poteva fattorizzare abbastanza velocemente da violare la crittografia RSA.
«Quello è stato un punto di svolta. Ma nel 1994 nessuno sapeva come costruire un computer quantistico abbastanza grande. E siamo ancora piuttosto lontani da lì. Alcune persone si chiedono se saranno mai costruiti», afferma il professor Vaikuntanathan.
Si stima che un computer quantistico necessiterebbe di circa 20 milioni (6) di qubit per eseguire l'algoritmo di Shor. Al momento, i computer quantistici più grandi hanno circa 1.100 qubit.
Un computer quantistico esegue calcoli utilizzando circuiti quantistici, proprio come un computer classico utilizza circuiti classici. Ogni circuito quantistico è composto da una serie di operazioni note come porte quantistiche. Queste porte quantistiche utilizzano i qubit, che sono i più piccoli elementi costitutivi di un computer quantistico, per eseguire calcoli.
Ma le porte quantistiche introducono rumore, quindi avere meno porte migliorerebbe le prestazioni di una macchina. I ricercatori si sono sforzati di migliorare l'algoritmo di Shor in modo che potesse essere eseguito su un circuito più piccolo con meno porte quantistiche.
È esattamente ciò che il dottor Oded Regev ha fatto con il circuito proposto un anno fa.
«È stata una grande notizia perché è stato il primo vero miglioramento del circuito di Shor dal 1994», afferma Vaikuntanathan.
Il circuito quantistico proposto da Shor ha una dimensione proporzionale al quadrato del numero da fattorizzare. Ciò significa che se si dovesse fattorizzare un intero di 2.048 bit, il circuito avrebbe bisogno di milioni di porte.
Il circuito di Regev richiede significativamente meno porte quantistiche, ma ha bisogno di molti più qubit per fornire memoria sufficiente. Ciò presenta un nuovo problema.
Il dottor Vinod Vaikuntanathan ha sentito Oded Regev parlare dei suoi risultati in un workshop lo scorso agosto. Alla fine del suo intervento, Oded Regev ha posto una domanda: qualcuno potrebbe migliorare il suo circuito in modo che abbia bisogno di meno qubit? Vaikuntanathan e Ragavan hanno affrontato la questione.
Ping-pong quantistico
Per scomporre in fattori un numero molto grande, un circuito quantistico dovrebbe essere eseguito molte volte, svolgendo operazioni che implicano potenze di calcolo, come 2 alla potenza di 100.
Ma calcolare potenze così grandi è costoso e difficile da eseguire su un computer quantistico poiché i calcolatori quantistici possono eseguire solo operazioni reversibili. Elevare al quadrato un numero non è un'operazione reversibile, quindi ogni volta che un numero viene elevato al quadrato, è necessario aggiungere più memoria quantistica per calcolare il quadrato successivo.
I ricercatori del MIT hanno trovato un modo intelligente per calcolare gli esponenti usando una serie di numeri di Fibonacci (7). Questo metodo richiede una semplice moltiplicazione, che è reversibile, piuttosto che la quadratura. Il loro metodo necessita solo di due unità di memoria quantistica per calcolare qualsiasi esponente.
«È un po' come una partita a ping-pong, in cui si inizia con un numero e poi si rimbalza avanti e indietro, moltiplicandolo tra due registri di memoria quantistica», aggiunge Vaikuntanathan.
Hanno anche affrontato la sfida della correzione degli errori. «I circuiti proposti da Shor e Regev richiedono che ogni operazione quantistica sia corretta affinché il loro algoritmo funzioni», dice Vaikuntanathan. Ma le porte quantistiche prive di errori sarebbero irrealizzabili su una macchina reale.
Hanno superato questo problema utilizzando una tecnica per filtrare i risultati corrotti ed elaborare solo quelli corretti.
Il risultato finale è un circuito che è significativamente più efficiente in termini di memoria. Inoltre, la loro tecnica di correzione degli errori renderebbe l'algoritmo più pratico da implementare.
«Gli scienziati risolvono i due colli di bottiglia più importanti nel precedente algoritmo di fattorizzazione quantistica. Sebbene non sia ancora immediatamente pratico, il loro lavoro avvicina gli algoritmi di fattorizzazione quantistica alla realtà», aggiunge il professor Oded Regev (8).
In futuro, gli scienziati sperano di rendere il loro algoritmo ancora più efficiente e, un giorno, di utilizzarlo per testare la fattorizzazione su un circuito quantistico reale.
«La domanda fondamentale dopo questo lavoro è: ci avvicina davvero alla rottura della crittografia RSA? Non è ancora chiaro; questi miglioramenti al momento entrano in gioco solo quando gli interi sono molto più grandi di 2.048 bit. Possiamo spingere questo algoritmo e renderlo più fattibile di quello di Shor anche per interi a 2.048 bit?» conclude il dottor Seyoon Ragavan.
Questo lavoro è finanziato da una borsa di studio presidenziale Akamai, dalla US Defense Advanced Research Projects Agency, dalla National Science Foundation, dal MIT-IBM Watson AI Lab, da una borsa di studio per l'innovazione della Thornton Family Faculty Research e da un Simons Investigator Award.
Riferimenti:
(1) Peter Shor
(2) An Efficient Quantum Factoring Algorithm
(4) Space-Efficient and Noise-Robust Quantum Factoring
(5) A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
(6) How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
(8) Oded Regev
Descrizione foto: Peter Shor, il professore di matematica applicata di Morss, ha ricevuto quest'anno il James R. Killian, Jr. Faculty Achievement Award, che è l'onorificenza più alta che la facoltà dell'Istituto può conferire a uno dei suoi membri ogni anno accademico. Crediti: Jake Belcher.
Autore traduzione riassuntiva e adattamento linguistico: Edoardo Capuano / Articolo originale: Toward a code-breaking quantum computer