Sappiamo tutti che stiamo vivendo una meravigliosa era scientifica! È in corso una transizione sociale, dominata da due pilastri principali: le transizioni ecologiche e digitali. Nella transizione digitale, dovremo fare i conti con il cosiddetto calcolo “quantistico”. Inevitabile, ne parliamo (giustamente) come di una rivoluzione scientifica e tecnica e di un vero e proprio cambio di paradigma. Essendo il computer quantistico un’estensione del computer “classico”, è quindi necessario prendere i concetti chiave dell’informatica e dar loro la loro “versione” quantistica. In questa prospettiva, dobbiamo definire cos’è un algoritmo quantistico.
Il classico algoritmo
La parola “algoritmo” , usata un po’ male in questi ultimi anni, perde un po’ della sua sostanza originaria. Da Euclide a Google passando per Al-Khwârizmî (dal cui nome deriva la parola algoritmo), l’algoritmo è l’antidoto alla risoluzione di un problema formulato utilizzando la matematica. Nel suo famoso articolo del 1936, Alan Turing lega l’algoritmica alla nozione di “calcolabilità“, cioè la possibilità di calcolare sotto forma di algoritmi, considerati di conseguenza come oggetti matematici “reali” che assumono la forma di una sequenza finita e univoca di istruzioni e operazioni per risolvere una classe di problemi.
Un algoritmo diventa quindi un metodo generale per risolvere un tipo di problema; e l’informatica teorica diventa una branca della matematica.
Un certo numero di qualificatori permette di caratterizzare un algoritmo: efficienza, performance, complessità. (Ci limitiamo qui a queste poche nozioni). L’efficienza si misura in particolare dal suo tempo di calcolo, dal suo consumo di RAM (assumendo che ogni istruzione abbia un tempo di esecuzione costante), dalla precisione dei risultati ottenuti (ad esempio con l’uso di metodi probabilistici), o anche dalla sua scalabilità (la sua capacità da parallelizzare efficacemente). Si dirà efficiente se utilizza con parsimonia le risorse a sua disposizione, ovvero il tempo della CPU, la RAM e (oggetto di recenti ricerche) il consumo di energia elettrica. Infine, la complessità consente di prevedere il tempo di calcolo necessario per portare a completamento un algoritmo, in funzione della quantità di dati da elaborare.
Gli algoritmi possono essere essenzialmente raggruppati in 3 famiglie:
- fondamentale: hanno compiti perfettamente ben definiti, i cui risultati sono facilmente verificabili
- ottimizzazione: cercano di identificare parametri o una configurazione che massimizza o minimizza un valore (esempio: trovare il percorso più breve tra due punti)
- crittografici: hanno lo scopo di garantire la sicurezza delle comunicazioni e delle transazioni
Prima di stabilire l’estensione quantistica di un algoritmo, ricordiamo i vantaggi del calcolo quantistico.
Il principio del calcolo quantistico
L’informatica classica si basa fondamentalmente sull’elaborazione di segnali binari, vale a dire basata su due stati.
Lo stato di uno switch o di un bit in memoria è 0 o 1: un registro a n bit equivale quindi a n valori. Il calcolo convenzionale elaborerà ciascuno di questi valori in modo lineare, uno dopo l’altro, quindi ci vorrà del tempo di elaborazione.
Nella meccanica quantistica, i paradigmi cambiano profondamente. Tre aspetti della meccanica quantistica sono alla base della possibilità di fare calcolo quantistico: dualità onda/particella, sovrapposizione di stati ed entanglement.
Per la loro natura ondulatoria/particellare, le particelle quantistiche sono descritte da probabilità che si evolvono nel tempo e nello spazio. Inoltre, hanno la capacità di trovarsi in un cosiddetto stato “sovrapposto“: sia un piccolo 0 che un piccolo 1. Quindi, un qubit (la versione quantistica del bit tradizionale) ha due stati “di esistenza“, denominati (per convenzione e per analogia con il bit classico) ❘0> e ❘1> (si pronuncia: ket 0 e ket 1). Mentre un bit classico è digitale e ha sempre il valore di 0 o 1, lo stato di un qubit è una sovrapposizione quantistica lineare dei suoi due stati base (cioè è simultaneamente ❘0> e ❘ 1>). Se invece proviamo ad osservarlo, troveremo poi uno 0 o un 1: l’osservazione ha cambiato lo stato della particella scegliendo tra i due. Un qubit osservato si comporta quindi come un bit classico. Infine, attraverso l’entanglement, possiamo far vivere due particelle quantistiche come una “coppia” e rendere interdipendente il loro stato quantistico. Questo è molto utile per cercare di seguire e comprendere l’evoluzione di un qubit.
Con un registro di n qubit, abbiamo quindi 2n valori contemporaneamente, che possono essere archiviati tutti contemporaneamente (mentre il calcolo convenzionale può memorizzare solo un valore alla volta). Se riusciamo a fare calcoli con tali supporti, riusciamo in qualche modo a fare tutti i calcoli contemporaneamente, come se stessimo realizzando 2n calcoli paralleli. Ad esempio, se n=3, un computer quantistico sarà in grado di elaborare 8 diversi stati quantistici, e quindi 8 calcoli contemporaneamente. Se ogni calcolo durasse un secondo, un computer quantistico avrebbe quindi bisogno solo di 1 secondo per eseguirli (mentre un computer classico avrebbe avuto bisogno di 8 secondi, poiché dovrebbe elaborare ogni calcolo uno dopo l’altro). (Nota: questo è solo un esempio semplificato per illustrare il punto, non calcoli o operazioni effettive.)
Alla fine, potrebbe esserci solo uno di questi calcoli che è riuscito, ed è il suo risultato che ci interessa. La difficoltà è isolarlo. L’arte degli algoritmi quantistici è quindi quella di cancellare giudiziosamente tutti i calcoli che non hanno avuto successo.
L’algoritmo quantistico
Nell’informatica classica, un programma per computer consiste in una sequenza di istruzioni eseguite in sequenza. A livello microscopico, queste istruzioni risultano dall’elaborazione di bit da parte di porte logiche.
Nell’informatica quantistica, le porte diventano quantistiche, il che cambia la natura intrinseca dell’elaborazione delle istruzioni. È quindi necessario ripensare alla natura della formulazione degli algoritmi, che, per estensione, diventano quantistici.
In questa fase, il principio di sovrapposizione specifico della fisica quantistica consente di applicare questi diversi passaggi a una sovrapposizione arbitraria degli stati base, o anche alla loro somma completa. Poiché la lettura del registro fornisce solo un valore di 0 o 1 per ogni bit (ricordiamo che un qubit osservato si blocca in un determinato stato e si comporta come un bit convenzionale), ovvero uno degli stati di base del registro, tutto nell’algoritmica quantistica consiste nel concentrare l’evoluzione verso gli stati che danno una/la soluzione del problema ricercato.
Un computer quantistico non è quindi solo una macchina universale che risolverebbe tutti i problemi più velocemente di un computer convenzionale. Piuttosto, è una macchina in grado di risolvere efficacemente alcuni problemi al di fuori della portata delle macchine convenzionali, utilizzando una metodologia completamente diversa. Il gioco consiste quindi nel confrontare la complessità di un problema da un punto di vista classico e quantistico: se un algoritmo può essere risolto in modo classico con una complessità ben definita, allora può essere risolto anche nel modello quantistico con un uguale o minore complessità.
Le capacità degli algoritmi quantistici sono direttamente legate al numero di qubit… ma non solo. Aumentare il loro numero è utile solo se l’“ambiente” quantistico viene mantenuto nonostante gli inevitabili processi di decoerenza. Un’altra particolarità del qubit rispetto a un bit classico è che non può essere duplicato a causa delle leggi della fisica quantistica.
Alcuni famosi algoritmi quantistici
Ma quali problemi interessanti possono essere affrontati con il calcolo quantistico? Tutti problemi di predizione e controllo di sistemi complessi, come finanza, meteorologia, salute, energia, ma anche la fisica quantistica stessa!
L’algoritmo di Shor, il primo algoritmo quantistico riconosciuto come tale, spiega come fattorizzare grandi numeri in fattori primi in modo efficiente. Non sappiamo come farlo con l’informatica classica. Gli algoritmi che conosciamo richiedono un tempo esponenziale. Inoltre, gran parte della crittografia (molto usata nella nostra vita quotidiana) si basa sul fatto che non sappiamo come fattorizzare rapidamente un numero primo. Questo problema di fattorizzazione può essere risolto nel modello quantistico con l’algoritmo di Shor. Ovviamente, affinché questo diventi fattibile nella pratica, sarebbe necessario saper costruire un computer quantistico che manipoli qualche migliaio di qubit. Non ci siamo ancora. L’algoritmo di Shor è stato utilizzato nel 2001 da un gruppo dell’IBM, che ha calcolato 15 in 3 e 5, utilizzando un computer quantistico a 7 qubit! Il numero 21 che è stato preso in considerazione su un processore quantistico IBM. Una prova che l’algoritmo funziona!
L’algoritmo di Grover è un altro noto algoritmo quantistico. Consente di cercare uno o più elementi che soddisfano un determinato criterio tra N elementi non classificati. Il problema viene risolto con una complessità minore rispetto a un algoritmo classico.
La corsa all’algoritmo quantistico è iniziata. E se combiniamo i vantaggi dell’Intelligenza Artificiale con la potenza del calcolo parallelo quantistico (una disciplina chiamata Quantum Machine Learning), avremo raggiunto i limiti della potenza di calcolo? Se la questione dell’algoritmo “intelligente” viene risolta a poco a poco, resterà allora da risolvere la questione etica degli algoritmi, al fine di quantificarne l’impatto sociale e politico.
Autore
Waleed Mouhali, ECE Paris
