Home
Introduzione al Quantum Computing

01 Luglio 2002

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 processare 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 di 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 della velocità di clock dei calcolatori: essa può aprire la strada a calcoli di un genere completamente nuovo, con algoritmi basati su principi quantistici diversi da quelli a cui siamo abituati. Questa nuova 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 la Teoria dell’Informazione e la 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 una mera coincidenza.

Il padre dell’Informatica è probabilmente Alan Turing (1912-1954), ed 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 2 stati: può infatti essere indotto in uno dei due stati distinti rappresentanti 2 valori logici – no o sì, falso o vero, o semplicemente 0 o 1. In termini pratici, senza scendere nei dettagli implementatitivi, 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 2 differenti polarizzazioni di luce o 2 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 2 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 2 valori in contemporanea viene in genere illustrato un semplice esperimento di riflessione dei fotoni, che noi non tratteremo, limitandoci a segnalarlo tra i Riferimenti. Occupiamoci invece di ampliare ulteriormente il concetto di sovrapposizione di numeri.

Consideriamo un registro composto da 3 bit fisici. Un registro a 3-bit classico può contenere esattamente uno degli 8 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 composto da 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 8 i numeri contemporaneamente in una sovrapposizione quantistica.

Il fatto che 8 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: 4 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 di 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 è 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 1 milione di elementi, ordinati alfabeticamente: è ovvio che nessun algoritmo classico più 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 (che comunemente vengono chiamati “universi”). In questo modo l’informazione riguardante l’elemento ricercato è 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 il misuramento 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 da’ 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 recentemente fatto notare, inoltre, un’altra importantissima applicazione dell’algoritmo di Grover è nel campo della crittanalisi, per attaccare schemi crittografici classici come il Data Encryption Standard (DES) con un approccio a forza bruta. Crackare il DES fondamentalmente richiede una ricerca tra tutte le 256 = 7 x 106 possibili chiavi. Un computer classico, potendo esaminarne ad esempio 1 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 4 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 fino ad ora il numero più grande che è stato fattorizzato, nel corso di una “gara” tra matematici, aveva 129 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 al momento 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 è al momento 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 costruita un’engine quantistica per la fattorizzazione, tutti i sistemi crittografici a chiave asimmetrica diverranno completamente insicuri.

Probabilmente questo momento è ancora lontano, 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 delle semplici porte logiche quantistiche, che come nel caso delle porte classiche sono dei semplici devices 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 è quello di 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 sub-microscopici 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 provenienti dall’esterno.

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”. Solo nel 1996 sono stati realizzati due documenti di Calderbank e Shor, e indipendentemente Steane, che hanno stabilito i principi 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 fatti successivamente nell’opera di generalizzazione di queste idee: in particolare, un importante sviluppo c’è stato 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 principi della meccanica quantistica garantiscono la conservazione dell’informazione, in modo che se essa arriva a destinazione si può essere sicuri che non è andata da nessun’altra parte (in altre parole, non è stata intercettata). Di conseguenza, l’intero problema delle chiavi compromesse, che riempie da secoli gli annali della storia dello spionaggio, è 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. Recentemente, però, l’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 a 7-qubit e fattorizzato il numero 15 nei suoi fattori primi 3 e 5. Nonostante l’apparente semplicità, si tratta del calcolo quantistico più complesso mai effettuato fino ad ora, e lascia ben sperare per gli sviluppi futuri di questa affascinante materia di studio.

Torna all’inizio.

Vuoi rimanere aggiornato?
Iscriviti alla nostra newletter

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.

Corsi che potrebbero interessarti

Tutti i corsi
Big_Data_Analytics-home Corso Online

Big Data Analytics: iniziare bene

Credi che i Big Data siano una grande opportunità ma pensi che spesso se ne parli a sproposito? Excel ti sta stretto e vorresti fare di più? Andrea De Mauro ti aiuta a fare chiarezza e ti insegna a muovere i primi passi nell'analisi dei Big Data.

con Andrea De Mauro


Libri che potrebbero interessarti

Tutti i libri

VBA dal problema alla soluzione

Lavorare meglio con Excel imparando a programmare da zero

33,90

49,89€ -32%

28,41

29,90€ -5%

19,99

di Francesco Borazzo, Angelo Rolfo

Docker

Sviluppare e rilasciare software tramite container

33,90

49,89€ -32%

28,41

29,90€ -5%

19,99

di Serena Sensini

Software Licensing & Data Governance

Tutelare e gestire le creazioni tecnologiche

21,90

29,89€ -27%

18,91

19,90€ -5%

9,99

di Simone Aliprandi


Articoli che potrebbero interessarti

Tutti gli articoli