Home
Introduzione al Quantum Computing

30 Agosto 2021

Introduzione al Quantum Computing

di

Cosa si intende per Quantum Computing e quali sono i suoi confini tra teoria dell’informazione classica, informatica e fisica quantistica? Proviamo a dare delle risposte.

Di che cosa parliamo

  1. Introduzione: un nuovo modo di sfruttare la natura
  2. Un po’ di storia
  3. Dal bit al qubit
  4. Algoritmi quantistici
  5. Che cosa ci riserva il futuro

1. Introduzione: un nuovo modo di sfruttare la natura

Molte tappe nella storia della tecnologia hanno comportato la scoperta di nuovi modi per sfruttare la natura: l’utilizzo di varie risorse fisiche come materiali, forze e sorgenti di energia ha fatto sì che l’uomo compisse progressi tecnologici sempre più grandi. Nel corso del Ventesimo secolo l’informazione è entrata a far parte della tecnologia, a partire dal momento in cui l’invenzione dei computer ha permesso di elaborare informazioni complesse all’esterno dei cervelli umani. La stessa storia dei calcolatori è intessuta di una sequenza di cambiamenti da un tipo di implementazione fisica ad un altro, dalle prime valvole ai circuiti integrati di oggi. Fino alle odierne tecniche più avanzate che ci consentono di costruire componenti di dimensioni inferiori al micron; e presto avremo chip ancora più ridotti, sino a raggiungere il punto in cui le porte logiche necessarie al funzionamento dei computer saranno costituite da pochi atomi ciascuna.

Iscriviti alla nostra newsletter

Sul piano degli atomi, la materia obbedisce alle regole della meccanica quantistica, molto differenti da quelle della fisica classica, che invece determinano le proprietà delle porte logiche convenzionali. Per questo motivo, se i computer dovranno diventare di dimensioni così ridotte nel prossimo futuro, una tecnologia completamente nuova dovrà sostituire ciò che utilizziamo ora. La tecnologia quantistica, però, può offrire molto di più della diminuzione delle dimensioni e dell’aumento delle prestazioni dei calcolatori: essa può aprire la strada a calcoli di un genere completamente nuovo, con algoritmi basati su principî quantistici, diversi da quelli a cui siamo abituati. Questa tecnologia prende il nome di Quantum Computing.

Il Quantum Computing nasce dall’unione tra teoria dell’informazione classica, informatica e fisica quantistica. La cosa che stupisce maggiormente è che teoria dell’informazione e meccanica quantistica si sposano in effetti molto bene, dando vita ad interessanti implicazioni.

Torna all’inizio.

2. Un po’ di storia

I fondamenti dell’informatica sono stati formulati più o meno contemporaneamente alla Teoria dell’informazione di Shannon, fatto che non deve essere considerato come mera coincidenza.

Il padre dell’informatica è probabilmente Alan Turing (1912-1954) e il suo profeta è Charles Babbage (1791-1871). Babbage, infatti, ha concepito gli elementi essenziali di un calcolatore moderno, nonostante ai suoi tempi non esistesse la tecnologia necessaria a realizzare praticamente le sue idee. È dovuto passare un intero secolo prima che l’Analytical Engine di Babbage fosse migliorata in quello che Turing ha descritto come la Universal Turing Machine, verso la metà degli anni Trenta. I più grandi meriti di Turing sono stati il chiarire con estrema precisione di che cosa debba essere capace una macchina per il calcolo e l’enfatizzare il ruolo del software e della programmazione, più ancora di quanto non avesse fatto il suo predecessore.

I moderni calcolatori elettronici non sono né macchine di Turing né motori di Babbage; ciononostante sono basati su principi molto simili e possiedono un potere computazionale equivalente. Senza scendere troppo nel dettaglio, vogliamo porre l’accento sul fatto che durante la storia dello sviluppo dei computer non vi è stato mai alcun sostanziale cambiamento dell’idea essenziale di calcolatore o di come esso operi. Tutti i miglioramenti sono quantificabili in termini di velocità e dimensioni. Ed ecco che cosa differenzia il Quantum Computing dall’informatica classica: la meccanica quantistica per la prima volta fa intravedere la possibilità di un cambiamento sostanziale dei computer e del loro modo di operare.

Cerchiamo di capire semplicemente in che termini ed in che modo.

Torna all’inizio.

3. Dal bit al qubit

La caratteristica fondamentale dell’informazione è la possibilità di essere codificata in un numero di modi virtualmente infinito. Ad esempio la frase italiana Alice è a casa mia ed il corrispettivo francese Alice est chez-moi contengono la stessa informazione, espressa in codici differenti. Comunque sia, ciò che accomuna tutti i modi di esprimere informazione è la necessità di strumenti fisici. Le parole parlate, infatti, sono costituite da fluttuazioni nella pressione dell’aria, quelle scritte da molecole di inchiostro su carta, persino gli stessi pensieri dipendono dai neuroni. Il motto dei ricercatori è pertanto: nessuna informazione senza la sua rappresentazione fisica!

I computer classici che tutti conosciamo utilizzano come unità di informazione di base il cosiddetto bit. Da un punto di vista prettamente fisico il bit è un sistema a due stati: può infatti essere indotto in uno dei due stati distinti rappresentanti due valori logici – no o sì, falso o vero, o semplicemente 0 o 1. In termini pratici, senza scendere nei dettagli implementativi, il bit viene realizzato utilizzando le proprietà dell’energia elettrica (assenza di carica o presenza di carica). Un bit di informazione può ovviamente venire rappresentato anche attraverso altri mezzi: ad esempio con due differenti polarizzazioni di luce o due differenti stati elettronici di un atomo. Ed è proprio quando arriviamo all’infinitamente piccolo che la meccanica quantistica entra in gioco, informandoci che se un bit può esistere in due stati distinti può anche esistere in una loro sovrapposizione coerente. Si tratta di un terzo stato, che non ha un analogo classico in generale, in cui l’atomo rappresenta entrambi i valori 0 e 1 contemporaneamente. Per aiutare a comprendere come una quantità fisica possa assumere due valori in contemporanea viene in genere illustrato un semplice esperimento di riflessione dei fotoni, che noi non tratteremo. Occupiamoci invece di ampliare ulteriormente il concetto di sovrapposizione di numeri.

Consideriamo un registro composto da tre bit fisici. Un registro 3-bit classico può contenere esattamente uno degli otto diversi numeri possibili: in altre parole esso può trovarsi in una delle otto possibili configurazioni 000, 001, 010, …, 111, rappresentazioni binarie dei numeri da 0 a 7. A differenza di ciò, un registro quantistico 3-qubit (come vengono chiamate le unità di informazione di base nel Quantum Computing, corrispettive del bit classico) è in grado di contenere fino a tutti e otto i numeri contemporaneamente in una sovrapposizione quantistica.

Il fatto che otto numeri differenti possano essere fisicamente presenti in contemporanea nello stesso registro è una diretta conseguenza delle proprietà dei qubit, e ha delle grandi implicazioni dal punto di vista della teoria dell’informazione. Se aggiungessimo più qubit al registro, la sua capacità di memorizzare informazioni crescerebbe in maniera esponenziale: quattro qubit possono immagazzinare fino a 16 numeri allo stesso tempo, ed in generale L qubit sono in grado di conservare 2L numeri contemporaneamente. Un registro 250-qubit, per capirci, composto essenzialmente di 250 atomi, sarebbe capace di memorizzare più numeri contemporaneamente di quanti siano gli atomi presenti nell’universo conosciuto. Un dato senza dubbio scioccante.

In termini pratici, però, quando misuriamo il contenuto di un registro siamo in grado di vedere solamente uno dei numeri della sovrapposizione: ciò rappresenta sicuramente un problema nel caso di quantistica applicata a problemi tradizionali molto semplici. Ma nel caso in cui dovessimo effettuare un calcolo quantistico più complesso, che consista di più passaggi e pertanto più operazioni sui registri, il vero vantaggio del Quantum Computing inizierebbe a manifestarsi: quando un registro contiene una sovrapposizione di molti numeri differenti, infatti, un calcolatore quantistico è in grado di effettuare operazioni matematiche su tutti loro contemporaneamente, allo stesso costo in termini computazionali dell’operazione eseguita su uno solo dei numeri. Ed il risultato sarà a sua volta una sovrapposizione coerente di più numeri. In altre parole: è possibile eseguire un massiccio calcolo parallelo ad un costo computazionale irrisorio rispetto a quello richiesto dai computer tradizionali, che avrebbero bisogno per compiere la stessa operazione di ripetere il calcolo 2L volte o di poter contare su 2L processori paralleli.

In breve, ecco riassunto quello che ci offre un calcolatore quantistico: un enorme guadagno di risorse computazionali come tempo e memoria, anche se solamente per certi tipi di operazione.

Torna all’inizio.

4. Algoritmi quantistici

Cerchiamo ora di fare luce sulle possibili applicazioni dei calcolatori quantistici. Come abbiamo accennato, le leggi della fisica ci permettono di leggere un solo risultato da un registro, anche se esso contiene 2L numeri differenti: per questo motivo il Quantum Computing non ci porta un vantaggio immediato in termini di conservazione dell’informazione. Sapendo però che grazie ad una proprietà dei quanti molto importante nota con il nome di quantum interference siamo in grado di ottenere un risultato finale singolo che dipende logicamente da tutti i 2L risultati intermedi, possiamo comprendere gli algoritmi che sono stati introdotti dai ricercatori.

Consideriamo ad esempio l’algoritmo scoperto da Lov Grover dei Bell Labs della AT&T, che realizza una ricerca in una lista non ordinata di N elementi in radice di N passi. È lampante per chi non sia totalmente digiuno di informatica che un algoritmo del genere è impossibile da realizzare con le tecniche classiche. Pensiamo, ad esempio, di dover ricercare un numero di telefono specifico all’interno di un elenco contenente un milione di elementi, ordinati alfabeticamente: è ovvio che nessun algoritmo classico possa migliorare il metodo di ricerca a forza bruta che consiste nella semplice scansione degli elementi fino a quando non si trova quello che ci interessa. Gli accessi alla memoria richiesti nel caso medio saranno pertanto 500.000, che è dello stesso di grandezza di N (O(N), come viene espresso in notazione matematica). Un computer quantistico è invece in grado di esaminare tutti gli elementi simultaneamente, nel tempo di un singolo accesso alla memoria: se fosse programmato per stampare semplicemente il risultato a questo punto, però, non costituirebbe un miglioramento rispetto all’algoritmo classico, perché solamente uno sul milione dei percorsi di calcolo effettuati conterrà l’elemento a cui siamo interessati, e per conoscerlo dovremo per forza di cose ispezionarli tutti.

Se però lasciamo l’informazione quantistica ricavata all’interno del calcolatore senza misurarla, possiamo applicarvi direttamente un’altra operazione che automaticamente andrà ad influire su altri percorsi (comunemente chiamati universi). In questo modo l’informazione riguardante l’elemento ricercato viene diffusa, attraverso la quantum interference, ad altri universi. Si è verificato che se questa operazione che genera interferenza viene ripetuta radice di N volte (nel nostro caso 1000), l’informazione che ci interessa sarà accessibile attraverso la misurazione con una probabilità di 0,5: in altre parole, si sarà diffusa in più della metà degli universi possibili. Pertanto ulteriori ripetizioni dell’algoritmo ci permetteranno di trovare il risultato che ci interessa con una probabilità molto prossima ad 1. Nonostante l’algoritmo di Grover sia uno strumento estremamente versatile e potente, in pratica la ricerca in un database fisico sarà difficilmente una delle sue applicazioni fondamentali, almeno fino a quando la memoria classica resterà molto più economica di quella quantistica. Per queste ragioni, il campo in cui questo algoritmo dà il meglio di sé è sicuramente quello della ricerca algoritmica, nella quale i dati non sono conservati in memoria, ma sono generati al volo da un programma: pensiamo ad esempio ad un calcolatore quantistico programmato per giocare a scacchi, che utilizzi l’algoritmo di Grover per investigare tutte le possibili mosse a partire da una determinata configurazione della scacchiera.

Come Gilles Brassard dell’Università di Montreal ha fatto notare, inoltre, un’altra importantissima applicazione dell’algoritmo di Grover si trova nel campo della crittanalisi, per attaccare schemi crittografici classici come il Data Encryption Standard (DES) con un approccio a forza bruta. Craccare il DES fondamentalmente richiede una ricerca tra tutte le 256 = 7 x 106 possibili chiavi. Un computer classico, potendo esaminarne ad esempio un milione al secondo, impiegherebbe migliaia di anni a scoprire quella corretta; un computer quantistico che utilizzi l’algoritmo di Grover, invece, ci metterebbe meno di quattro minuti.

Per qualche strana coincidenza, molte delle caratteristiche superiori dei calcolatori quantistici hanno applicazioni nel campo della crittologia. Oltre all’algoritmo di ricerca di Grover che abbiamo appena visto, c’è quello scoperto nel 1994 da Peter Shor (un altro ricercatore dei Bell Labs) per la fattorizzazione efficiente di numeri interi grandi. In questo caso la differenza di performance tra gli algoritmi quantistici e quelli classici è ancora più spettacolare.

I matematici sono convinti (anche se di fatto la cosa non è mai stata dimostrata in maniera rigorosa) che la fattorizzazione di un numero intero con N cifre decimali sia particolarmente pesante in termini computazionali: per portare a termine l’operazione, qualsiasi computer classico ha bisogno di un numero di passi che cresce esponenzialmente con N. Questo significa che aggiungendo una semplice cifra al numero da fattorizzare, il tempo necessario a compiere l’operazione si moltiplica per un fattore fisso. Per rendere meglio l’idea, basti pensare che prima del Quantum Computing il numero più grande che è stato fattorizzato aveva 232 cifre. Nessuno è in grado di concepire la possibilità di fattorizzare numeri di migliaia di cifre con i metodi classici: il calcolo richiederebbe più volte l’età stimata dell’universo. In contrasto, i calcolatori quantistici possono fattorizzare numeri di migliaia di cifre in una frazione di secondo, ed il tempo di esecuzione cresce solamente secondo il cubo del numero delle cifre (e non esponenzialmente come nel caso dell’algoritmo classico).

La cosa più interessante è che sulla difficoltà di calcolo dell’operazione di fattorizzazione si basa la sicurezza di quelli che sono i metodi di cifratura più utilizzati ed universalmente riconosciuti come inattaccabili: stiamo parlando in particolar modo del sistema RSA (Rivest, Shamir e Adleman). Tale algoritmo crittografico è largamente impiegato per proteggere le comunicazioni più riservate e le transazioni bancarie, che si avvalgono di uno schema crittografico a chiave asimmetrica (la crittografia a chiave pubblica è stata scoperta originariamente da Ellis e Cocks del GCHQ inglese). Quando dovesse essere costruito un engine quantistico per la fattorizzazione, tutti i sistemi crittografici a chiave asimmetrica diverranno completamente insicuri.

Questo momento non è ancora giunto, ma di fatto le recenti scoperte ci fanno capire che è ora di pensare ad altri metodi crittografici, in previsione di quello che ci può riservare il futuro.

Torna all’inizio.

5. Che cosa ci riserva il futuro

In linea di principio siamo già in grado di costruire un calcolatore quantistico: cominciamo con semplici porte logiche quantistiche, che come nel caso delle porte classiche sono semplici device in grado di eseguire un’operazione elementare su uno o due qubit. Ovviamente esse differiscono dalle loro controparti classiche, perché sono in grado di operare su sovrapposizioni quantistiche. Tali porte dovranno poi essere collegate in reti, per poter operare come un computer.

Al crescere del numero delle porte quantistiche nella rete, però, ci imbattiamo rapidamente in alcuni problemi pratici molto seri. Più qubit sono coinvolti, più diventa complesso gestire l’interazione che genera la quantum interference. A parte le difficoltà derivanti dal dover lavorare a livello di singolo atomo e singolo fotone, uno dei problemi più importanti è impedire che anche l’ambiente venga modificato dalle interazioni che generano le sovrapposizioni quantistiche. Più componenti vi sono, più si fa probabile che l’informazione quantistica si diffonda all’esterno del computer per perdersi nell’ambiente, compromettendo i risultati del calcolo. Questo processo prende il nome di decoerenza, e per evitarlo gli ingegneri devono riuscire a produrre sistemi submicroscopici nei quali i qubit si influenzano l’un l’altro, ma sono completamente separati dall’ambiente esterno.

Per lo stesso motivo, è immediato osservare che gli effetti della quantum interference che rendono realizzabili algoritmi come quello di Shor sono estremamente fragili: i computer quantistici sono molto sensibili alle interferenze.

Ed è a questo punto che entra in gioco la nuova Teoria dell’informazione quantistica, nata dal connubio tra Teoria dell’informazione classica e Quantum Computing: è infatti possibile, combinando elementi delle due discipline, realizzare calcolatori quantistici molto meno sensibili alle interferenze esterne, grazie a quella che viene chiamata quantum error correction. Nel 1996 sono stati realizzati due documenti di Calderbank e Shor, e indipendentemente Steane, che hanno stabilito i principî generali con cui il quantum information processing può essere utilizzato per combattere una vasta gamma di interferenze in un sistema quantistico. Molti progressi sono stati compiuti successivamente nell’opera di generalizzazione di queste idee: in particolare, un importante sviluppo si è verificato con la dimostrazione effettuata da Shor e Kitaev che la correzione degli errori può avere luogo anche quando le stesse operazioni correttive sono imperfette. Questi metodi conducono ad un concetto di Quantum Computing fault tolerant. Se la correzione degli errori in sé non garantisce un calcolo quantistico accurato, poiché non può combattere tutti i tipi di interferenza, il fatto che sia possibile rappresenta comunque uno sviluppo significativo che ci fa ben sperare per il futuro. Un’altra importante implicazione del connubio tra meccanica quantistica e teoria dell’informazione, derivante direttamente dalle proprietà di base dei sistemi quantistici applicate alla pratica, è la quantum cryptography. La crittografia quantistica comprende numerose idee, tra le quali la più interessante (e la più seguita) è la quantum key distribution. Si tratta di un metodo molto ingegnoso secondo il quale gli stati quantistici trasmessi sono utilizzati per eseguire una comunicazione molto particolare: creare in due locazioni separate una coppia di sequenze di bit randomiche identiche, impedendone l’intercettazione da terze parti. Si nota subito come questo possa rivelarsi molto utile nel caso dello scambio di chiavi crittografiche per cifrari simmetrici, operazione che necessita di un canale assolutamente sicuro. La caratteristica fondamentale è che i principî della meccanica quantistica garantiscono la conservazione dell’informazione, in modo che se essa arriva a destinazione si può essere sicuri che non sia andata da nessun’altra parte (in altre parole, non sia stata intercettata). Di conseguenza, l’intero problema delle chiavi compromesse, che riempie da secoli gli annali della storia dello spionaggio, viene evitato completamente avvalendosi della struttura del mondo naturale e delle sue leggi.

Tra gli effetti del Quantum Computing che più rischiano di influenzare il nostro futuro, uno dei più interessanti è sicuramente la rivoluzione del concetto stesso di dimostrazione matematica. Quando abbiamo a che fare con computer classici, infatti, possiamo descrivere matematicamente con facilità le operazioni da essi compiute. In questo modo siamo in grado di fornire una prova della correttezza del calcolo svolto che soddisfi la definizione classica:

una sequenza di proposizioni ognuna delle quali è un assioma o deriva da proposizioni precedenti nella sequenza attraverso le regole standard di inferenza.

Con il Quantum Computing questa definizione non è più valida: d’ora in avanti una dimostrazione dovrà essere considerata come un processo (il calcolo stesso, e non una registrazione di tutti i suoi passaggi): in futuro è estremamente probabile che un calcolatore quantistico riesca a dimostrare teoremi attraverso metodi che un cervello umano (o un calcolatore classico) non è in grado nella maniera più assoluta di controllare, perché se la sequenza di proposizioni corrispondente alla dimostrazione intesa nel senso classico venisse stampata, la carta riempirebbe l’universo osservabile per molte volte. Riguardo alla realizzabilità di un calcolatore quantistico complesso, molti studiosi sono tutt’ora scettici. Nel 2001, però, IBM ha costruito un primo esempio di computer quantistico, con la prima implementazione funzionante dell’algoritmo di fattorizzazione di Shor. I ricercatori di IBM hanno realizzato un calcolatore 7-qubit e fattorizzato il numero 15 nei suoi fattori primi 3 e 5. Nonostante l’apparente semplicità, si era trattato del calcolo quantistico più complesso mai effettuato fino a quel momento.

Nel 2016 IBM ha installato un computer quantistico nel cloud e nel 2019 ne ha realizzato la prima versione commerciale. Sempre nel 2019 Google ha dichiarato, attraverso un articolo su Nature, di avere raggiunto la cosiddetta quantum supremacy, che consiste nell’avere effettivamente eseguito un’operazione impossibile da portare a termine in tempo ragionevole su un computer di architettura classica, utilizzando un calcolatore quantistico con 53 qubit.

IBM ha contestato la validità del risultato proclamato da Google, le cui premesse tecnologiche, dovunque sia la verità, sono comunque una testimonianza efficace dei grandi progressi compiuti dal Quantum Computing durante gli ultimi anni.

Un altro breakthrough è dell’estate 2021 e riguarda sempre Google, che in collaborazione con fisici di varie università ha annunciato la prima dimostrazione dell’esistenza possibile di un time crystal attraverso un computer quantistico. Un altro gruppo di ricerca, indipendente da Google, ha sostenuto nello stesso periodo di avere creato un time crystal fisico all’interno di un diamante.

Un time crystal è una forma alternativa di materia, teorizzata già da Richard Feynman nel 1982 ma mai attuata prima sperimentalmente, che grazie a effetti quantistici è stabile, ma intanto continua a cambiare struttura secondo un ciclo di cambiamento regolare nel tempo e, soprattutto, lo fa senza consumare energia, scavalcando a seconda legge della termodinamica.

Si tratta di un traguardo che non era mai stato raggiunto e il cui raggiungimento si deve probabilmente proprio alla possibilità di usare il Quantum Computing. Certamente la diffusione di massa dei computer quantistici, nonché uno sviluppo massiccio di applicazioni come avviene per i computer classici, è ancora lontano nel tempo; ma solo pochi anni la nozione di Quantum Computing apparteneva puramente alla teoria e forse oggi è il momento giusto per abbracciare una disciplina che potrebbe diventare di primaria importanza prima di quanto si possa pensare.

Torna all’inizio.

Immagine di apertura di FLY:D su Unsplash.

Iscriviti alla newsletter

Novità, promozioni e approfondimenti per imparare sempre qualcosa di nuovo

Gli argomenti che mi interessano:
Iscrivendomi dichiaro di aver preso visione dell’Informativa fornita ai sensi dell'art. 13 e 14 del Regolamento Europeo EU 679/2016.

Libri che potrebbero interessarti

Tutti i libri

Quantum Computing

Guida alla programmazione con Python e Q#

46,65

66,89€ -30%

37,91

39,90€ -5%

26,99

di Sarah Kaiser, Cassandra Granade