INFORMATICA

Calcolo quantistico, nuova frontiera. Ma ancora per pionieri

I risultati raggiunti da Google danno per la prima volta una spallata ai “limiti” posti dal calcolo digitale classico. Ma rimangono in campo i nodi primari sul fronte dell’applicabilità: indicando alla ricerca la necessità di approfondire lo sfruttamento dell’enorme potenza di calcolo disponibile sui sistemi tradizionali

06 Mag 2020
Massimo Bernaschi

Istituto Applicazioni del Calcolo. Consiglio Nazionale delle Ricerche


Lo studio del calcolo quantistico sta registrando nuove vette raggiunte. Ma c’è ancora molto da fare per sviluppare algoritmi più efficienti e alternativi per i computer, digitali e quantistici.

Quantum computing, “gol” di Google

Dopo l’articolo pubblicato su Nature il 23 ottobre (“Quantum supremacy using a programmable superconducting processor”) che aveva già considerevolmente aumentato l’attenzione del pubblico sull’evoluzione di quelli che vengono comunemente chiamati “computer quantistici“, Google ha annunciato di aver eseguito sul proprio computer quantistico la più grande simulazione di chimica quantistica mai realizzata, riproducendo il comportamento di una lunga catena di atomi di idrogeno.

Sono entrambi risultati sicuramente interessanti, ma è importante non farsi prendere troppo dall’entusiasmo perché siamo ancora lontani dal poter “sostituire” i calcolatori digitali tradizionali come qualcuno cerca di far credere.

Capita di leggere che i computer quantistici sono in grado di provare simultaneamente tutte le possibili soluzioni ad un dato problema e selezionare quella “giusta”. Questa affermazione (sbagliata) si basa su un’interpretazione non corretta del principio della sovrapposizione quantistica per cui un’entità può essere “contemporaneamente” in due stati (0 e 1 oppure x e y, non fa differenza). Quella che bisognerebbe considerare, invece, è l’interferenza quantistica.

Ciò che un computer quantistico può fare (sotto opportune condizioni non facili da realizzare) è “combinare” (in inglese il termine è interfere ma la traduzione letterale non rende l’idea) dei “percorsi” computazionali in modo che i percorsi che porterebbero a risposte sbagliate si cancellino tra di loro, mentre i percorsi che portano alla risposta giusta si rafforzano.

Cos’è il percorso computazionale

Per comprendere cosa vuol dire percorso computazionale, immaginiamo di avere un calcolo classico che deve prendere ad ogni passo una decisione tra due possibilità (alto-basso, destra-sinistra, etc). La prima possibilità ha probabilità p di essere quella giusta e la seconda probabilità 1-p (p è compreso tra 0 ed 1). La scelta deve essere ripetuta ad ogni passo. Viene abbastanza naturale rappresentare questa situazione con il tipico “albero” decisionale (Figura 1), in cui i nodi colorati di verde corrispondono ad una risposta giusta e quelli colorati di rosso ad una risposta sbagliata.

Figura 1: Un percorso computazionale con la tipica forma ad albero

La profondità dell’albero rappresenta il numero di scelte (istruzioni). Da notare che c’è più di un cammino che porta alle risposte giuste, così come ci sono più cammini che portano alle risposte sbagliate. Ogni cammino ha una certa probabilità di essere eseguito (chi è un po’ familiare con la probabilità intuisce che è il prodotto delle probabilità ad ogni passo) e la probabilità di arrivare, ad esempio, alla soluzione corretta che corrisponde al quarto nodo dall’alto (il terzo verde) è data dalla somma delle probabilità di tutti i cammini che arrivano a quel nodo (è facile controllare che ce ne sono più di uno).

Infine, la probabilità di arrivare al risultato corretto è la somma delle probabilità di arrivare ad uno qualunque dei nodi verdi. Nel caso quantistico, la differenza è che le transizioni sono regolate da ampiezze, non dalle probabilità e le ampiezze possono essere sia positive sia negative (a rigore sono numeri complessi ma per questa descrizione va benissimo considerare solo numeri reali positivi e negativi).

Il paradigma delle “ampiezze”

La prima volta che si sente parlare di ampiezze negative si rimane sicuramente perplessi. Sembra assurdo, perché verrebbe da pensare che ci possa essere, per analogia, una probabilità pari -25% di vincere una lotteria. In realtà il tutto è meno esotico di quanto possa sembrare. Nel mondo classico se un evento ha N possibili esiti, possiamo assegnare ad ogni esito una certa probabilità di verificarsi.

Con il linguaggio della matematica possiamo scrivere una lista di numeri (un vettore) ognuno dei quali corrisponde alla probabilità di un esito. La somma di tutti i valori è uguale a 1 (copre tutte le possibilità). Tecnicamente si dice che la norma -1 del vettore deve essere uguale ad 1. Se abbiamo un bit, questo può valere uno, con probabilità p, oppure 0 con probabilità 1-p. Ma questa non è l’unica alternativa, si può utilizzare un’altra norma, la norma-2 definita come la somma dei quadrati. L’insieme delle coppie di numeri (chiamiamoli alfa e beta) la cui somma dei quadrati è uguale a uno forma un cerchio come quello della Figura 2.

WHITEPAPER
IoT Security: i fattori prioritari e i modelli da considerare nelle valutazioni dei rischi
IoT
Legal

Figura 2: il bit quantistico si trova su un punto della circonferenza

Il bit quantistico (spesso chiamato q-bit) è il bit a norma-2. Alfa è l’ampiezza che, quando è misurato, ritorni come valore zero (alfa al quadrato è la probabilità che torni come valore 0), mentre beta è l’ampiezza che, quando è misurato, ritorni come valore 1 (anche qui beta elevato al quadrato è la probabilità). Si può pensare di utilizzare come qbit anche un singolo elettrone. Un elettrone ha infatti una proprietà chiamata spin (spesso rappresentata come una rotazione) che può essere up (rotazione in senso orario) o down (rotazione in senso antiorario). Lo spin down può rappresentare uno zero e lo spin up un uno (ma sono solo convenzioni, non c’è un significato fisico).

Con una semplificazione un po’ ardita, si può dire che mentre non viene misurato, il q-bit può essere in un punto qualsiasi della circonferenza (si parla di quantum superposition). Quando viene misurato risulta 0 oppure 1. Se si combinano più qbit il numero di possibile superposizioni cresce esponenzialmente. Ma quando, alla fine, si misura lo stato, rimane sempre una sola combinazione e l’arte del calcolo quantistico sta nel fare in modo di massimizzare la probabilità che corrisponda alla risposta giusta. E qui torniamo al percorso computazionale.

Nel mondo quantistico, l’ampiezza di arrivare in un particolare nodo (cioè ad una soluzione) è data dalla somma delle ampiezze dei cammini che partono dalla radice dell’albero (il nodo a sinistra) ed arrivano a quel nodo ma, dato che possono essere sia positive sia negative, la somma può risultare effettivamente uguale a zero rendendo il nodo irraggiungibile. Si arriva quindi ad una situazione come quella descritta dalla Figura 3.

Figura 3: percorso computazionale quantistico con cammini che si cancellano o rafforzano

Le frecce rosse indicano transizioni che hanno ampiezza positiva, mentre le frecce blu indicano transizioni con ampiezza negativa. In realtà la cancellazione dei cammini non è perfetta (l’ampiezza non è esattamente zero) ma l’idea del calcolo quantistico è comunque di arrivare a fare in modo che i cammini con ampiezza uguale (o vicina) a zero corrispondano a quelli che portano alle risposte sbagliate.

Quelli che portano alle risposte giuste dovrebbero avere ampiezze che si combinano in maniera costruttiva (si amplificano). Quando poi si “misura” lo stato (si vede cioè dove si è arrivati), la probabilità di avere una risposta corretta è pari alla somma dei quadrati delle ampiezze che portano a quella risposta.

Si capisce quindi come non vengano provate tutte le possibili soluzioni contemporaneamente ma piuttosto vengono opportunamente selezionate le risposte potenzialmente corrette.

Quantum, i miti da sfatare

Per questo motivo, il computer quantistico non rende banale la soluzione di tutti i problemi difficili come quello classico del commesso viaggiatore (trovare il percorso migliore per visitare un certo numero di città minimizzando il tempo oppure qualche altra “misura di costo”).

Nel linguaggio tecnico si dice che non si conosce un modo per risolvere in maniera efficiente, con un computer quantistico, i problemi NP-hard.

Quello che un computer quantistico può fare in un caso come questo è offrire un miglioramento di un fattore 2. In altre parole, se per risolvere un problema con un computer digitale tradizionale servono 2 elevato alla N unità di tempo (da notare che già con N=256 questo è un numero enorme), con un computer quantistico sono sufficienti 2 elevato alla N/2 unità di tempo. Non che si tratti di un miglioramento trascurabile, ma il tempo rimane esponenziale (con N=256, il tempo scende a 2 elevato alla 128, che è circa 340000000000000000000000000000000000000!).

Ci sono, in effetti, problemi per cui si sa come fare in modo che il computer quantistico offra un miglioramento molto più spettacolare (il tempo di risoluzione non cresce più esponenzialmente). Il più famoso tra questi è la fattorizzazione dei numeri interi: trovare i numeri primi il cui prodotto è uguale ad un numero dato (i numeri primi sono quelli che sono divisibili solo per sé stessi e per uno). Ad esempio, 15 è il prodotto di 3 x 5. Quando il numero è molto grande (centinaia di cifre) trovare i numeri primi giusti (quelli il cui prodotto è uguale al numero dato) richiede un tempo enorme su un computer digitale tradizionale e questa difficoltà è alla base del funzionamento di sistemi per la crittografia come RSA.

Con il computer quantistico esiste, invece, in linea di principio, una procedura molto più efficiente (algoritmo di Shor) che quindi metterebbe a rischio quei sistemi di sicurezza. Ho usato il condizionale perché intanto la procedura è di tipo probabilistico (non è garantito che arrivi alla risposta giusta anche se, in caso di fallimento, si può ripetere, proprio perché è “efficiente”) ma soprattutto perché non esiste (per quanto se ne sappia ufficialmente) al momento un computer quantistico sufficientemente “stabile” da poterlo utilizzare in casi di interesse reale.

Il punto critico dei supercomputer

Si arriva così al punto veramente critico ma anche più interessante, almeno dal punto di vista della loro potenziale applicabilità, dei computer quantistici. Il problema, infatti, è che è molto difficile controllare (e quindi programmare) un computer quantistico a causa del fenomeno conosciuto come quantum decoherence che indica la perdita di coerenza necessaria per il calcolo quantistico (per permettere la cancellazione dei cammini che portano a risposte sbagliate ed il rafforzamento di quelli che portano alle risposte corrette).

Se il sistema/computer quantistico fosse perfettamente isolato, manterrebbe la coerenza indefinitamente ma  ovviamente, in questa configurazione, sarebbe impossibile interagire con il sistema e quindi diventerebbe praticamente inutile (possiamo vederlo come uno spiacevole effetto collaterale del famoso principio di indeterminazione di Heisenberg).

Il vero passo avanti del team di Google è stato riuscire a mantenere coerente un sistema composto da ben 53 qubit per un tempo sufficientemente lungo ad eseguire i calcoli (arrivando alla superposizione giusta) che hanno portato ai risultati annunciati nelle ultime settimane. In particolare, al raggiungimento di quella “quantum supremacy” che suona quasi prepotente.

Il termine, in realtà, non è stato inventato dai ricercatori di Google ma da John Preskill del Caltech che lo propose in un articolo di rassegna del 2012 che consiglio fortemente per la chiarezza e l’onestà intellettuale (John Preskill, Quantum computing and the entanglement frontier. Rapporteur Talk at the 25th Solvay Conference on Physics, Brussels https://doi.org/10.1142/8674, World Scientific, 2012). Nelle parole di Preskill, quantum supremacy significa poter eseguire compiti con sistemi quantistici “controllati” che vanno oltre ciò che può essere ottenuto con computer digitali tradizionali.

Dal punto di vista ingegneristico sicuramente un risultato notevole ma, al momento, il computer quantistico rimane soprattutto un interessante oggetto di ricerca avanzata. Attenzione, non solo tecnologica, ma anche di fisica di base. Alleviare il problema della perdita di coerenza richiede un approfondimento della nostra comprensione del passaggio di un sistema dallo stato in cui valgono la probabilità quantistica (che si basa sulle ampiezze) a quello in cui vale la probabilità classica.

La sfida della potenza di calcolo

Nell’attesa di computer quantistici alla portata di tutti, potremmo, anzi dovremmo, imparare a sfruttare meglio l’enorme potenza di calcolo comunque disponibile sui sistemi tradizionali. Algoritmi più efficienti ed implementazioni più attente permetterebbero di aumentare la frazione della potenza di calcolo effettivamente utilizzata rispetto a quella teoricamente disponibile, riducendo i tempi di esecuzione ed i consumi energetici che nei supercomputer sono ormai paragonabili a quelli di migliaia di case (MegaWatt). Per dare un’idea, molto spesso, riusciamo a sfruttare non più del 10-15% della capacità dei dispositivi digitali che ci circondano.

C’è molto da fare per sviluppare algoritmi più efficienti e alternativi per i computer (sia per quelli digitali sia per quelli quantistici). Ad esempio, c’è tutto un filone di ricerca che studia procedure crittografiche che possano risultare inattaccabili anche ad un computer quantistico oppure che sfruttino come un vantaggio le caratteristiche della meccanica quantistica. In particolare, la crittografia quantistica utilizza le proprietà della meccanica quantistica nella fase dello scambio della chiave di cifratura per evitare che questa possa essere intercettata da un attaccante senza che mittente e destinatario se ne accorgano. Insomma, l’eterna rincorsa tra chi vuole proteggere e chi vuole violare le comunicazioni forse non finirà neanche con i computer quantistici.

(Le figure e parte del testo sono ispirate all’ottimo lavoro di divulgazione svolto dal Professor Scott Aaronson dell’University of Texas).

@RIPRODUZIONE RISERVATA

Articolo 1 di 3