Mr. Q #4: Peter Shor e l'applicazione killer del computer quantistico

Anche se con imperdonabile ritardo, ecco il post che mette la parola fine a questa serie di interventi sulla computazione quantistica.
Avevo interrotto il post precedente introducendo (con l'inatteso aiuto dei Genesis) il concetto di entanglement tra qubit: due registri (o, più astrattamente, due stati quantici), apparentemente non legati tra di loro da una relazione di causa-effetto, risultano "aggrovigliati", in modo tale che se uno assume un certo valore allora l'altro sarà vincolato ad assumere un valore ben preciso e non altri.
Così, se due qubit assumono lo stato di sovrapposizione |00> + |11>, andando a misurare i valori potremmo trovare i valori 00 e 11, ma mai 01 o 10. Lo stato |00> + |11> è quindi una sovrapposizione "aggrovigliata", o entangled; in altri termini, questo stato non può essere fattorizzato in due stati indipendenti (|0> + |1>)(|0> + |1>).
L'entanglement è la chiave della potenza della computazione quantistica. Grazie a porte come la C-NOT descritta nel post precedente, gli studiosi sono riusciti a costruire circuiti quantistici in grado di sfruttare i fenomeni quantistici (come l'entanglement) per eseguire calcoli complessi in modo più efficiente rispetto ai modelli computazionali classici.

Nel 1985, il già ricordato fisico inglese David Deutsch pubblicò un articolo fondamentale, intitolato "Quantum theory, the Church-Turing principle and the universal quantum computer", nel quale forniva una prima dimostrazione delle possibilità computazionali insite nei sistemi quantistici.

Nove anni dopo, un informatico teorico americano, Peter Shor, propose una sorprendente applicazione del modello di calcolo quantistico: un metodo per calcolare i fattori primi di un numero, eseguibile in modo efficiente con un computer quantistico.
Com'è noto, ogni numero naturale può essere espresso come prodotto di più numeri primi, e per ogni numero esiste un solo modo di fattorizzarlo (a meno dell'ordine dei fattori): questo fatto è talmente basilare che assume l'altisonante nome di "teorema fondamentale dell'aritmetica". Ora, se prendiamo un numero molto grande, formato ad esempio da centinaia di cifre, e proviamo a determinare i suoi fattori primi, scopriamo che il problema è molto difficile, e potrebbe richiedere anni o secoli per essere risolto, anche disponendo di un computer molto potente.
Perché? Semplicemente perché i metodi più efficienti che sono stati scoperti per eseguire questo calcolo non sono, in generale, molto migliori del metodo più "stupido" possibile, quello basato sulla cosiddetta "forza bruta": provare a dividere il numero di partenza per tutti i numeri ad esso inferiori finché se ne trova qualcuno che è un divisore esatto, e ripetere l'operazione con il risultato della divisione.
Nel 1994, invece, Shor dimostrò che, potendo utilizzare un computer quantistico, con tutto il suo armamentario di porte come la C-NOT, le sovrapposizioni quantiche, l'entanglement e così via, era possibile implementare un algoritmo di fattorizzazione molto più veloce di quelli classici.
Il lavoro di Shor era squisitamente teorico, in quanto nel 1994 non esistevano computer quantistici reali (e oggi la situazione non è profondamente mutata): ma agli studiosi apparve subito evidente l'importanza del risultato dell'informatico statunitense. Molti di voi sanno che la sicurezza dei sistemi di crittografia che proteggono i nostri dati su internet (ad esempio i numeri delle carte di credito usate nelle transazioni sulla rete) si basa sulla difficoltà di fattorizzare grandi numeri.
Il ragionamento che venne fatto all'indomani della pubblicazione dell'articolo di Shor, era quindi il seguente: "se qualcuno domani costruisse un computer quantistico e ci facesse girare l'algoritmo di Shor, tutti i sistemi di sicurezza della rete crollerebbero come un castello di carte, e forse la finanza internazionale farebbe la stessa fine."

L'algoritmo di Shor si candidò immediatamente come l'"applicazione killer" della computazione quantistica; eppure, pochi anni prima lo stesso Deutsch si era mostrato scettico a proposito della possibilità di escogitare un algoritmo quantistico efficiente per la fattorizzazione di grandi numeri.

Shor riuscì sorprendentemente in questa "missione impossibile", dimostrando al tempo stesso che il computer quantistico, da innocente giocattolo teorico, interessante solo per i ricercatori e per i matematici, poteva trasformarsi in una bomba dalle conseguenze inimmaginabili nel campo della sicurezza informatica.
Ad oggi, gli sforzi compiuti nella realizzazione pratica del computer quantistico non hanno ancora portato al risultato finale, per cui la bomba di Shor non è ancora esplosa; tuttavia, i continui progressi nella teoria del calcolo quantistico promettono sempre livelli di potenza computazionale sempre crescenti.
Nessuno sa se un giorno, più o meno lontano, potremo utilizzare, sulla nostra scrivania, un computer quantistico al posto dell'attuale computer "classico"; ma è fuori di dubbio che la ricerca teorica svolta fin qui sull'argomento ha svelato l'esistenza di un mondo affascinante che mette assieme due settori apparentemente lontani come l'informatica e la fisica quantistica, e che fino a pochi decenni fa era completamente sconosciuto.