Sfatiamo subito alcune frequenti errate convinzioni sui computer quantistici che ad oggi:

• non sono più veloci dei computer classici e non sappiamo se mai lo saranno
• non sono praticamente utili e non sappiamo se mai lo saranno
• non permettono di dotare una macchina di coscienza
• non aiutano con le intelligenze artificiali, anzi al momento è più vero il viceversa
• non calcolano in modo non deterministico

Come descriverò in questo articolo, esistono valide ragioni per ritenere che i computer quantistici abbiano effettivamente un vantaggio notevole rispetto ai computer classici. Tuttavia trovo affascinante il fatto che tutto si basi su una congettura non dimostrata e forse non dimostrabile. Come sempre, per capire veramente questo argomento c’è bisogno di arrivarci con un po’ di studio…

Recentemente ho notato sul Fediverse, ma anche nella vita reale, che girano affermazioni al limite del fattuale e molte altre proprio sbagliate per quanto riguarda, non tanto la struttura fisica dei computer quantistici, quanto il loro supposto vantaggio che li renderebbe incredibilmente più potenti degli attuali computer classici elettronici. Per questo vorrei fare un po’ di chiarezza per quanto riguarda questo ambito di ricerca, pur non essendo direttamente del campo, ma disponendo delle basi di teoria della complessità per affacciarmi a questo mondo, partendo da un punto di vista forse un po’ insolito. Per capirci non parlerò di qubit, entanglement quantistico, principio di indeterminazione di Heisenberg, effetti quantistici topologici e compagnia. Per questi temi vi lascio nelle mani del buon Barbascura, che ha fatto un ottimo video a riguardo. Purtroppo come spesso accade, anche questo concentrato sul versante fisico e meno su quello dell’informatica teorica e della teoria della complessità in particolare.
Proviamo a partire dalle basi.

L’idea che circola preponderante e che costituisce la premessa alla base dell’enorme sviluppo di questo campo di ricerca negli ultimi decenni, è sostanzialmente la possibilità di sfruttare i comportamenti quantistici di particelle elementari o altri oggetti fisici che porterebbero un vantaggio al calcolo di questo tipo di computer. In poche parole si riuscirebbero a fare calcoli così velocemente che oggi ce lo possiamo soltanto sognare.

Già questa premessa presenta delle lacune, ad esempio non si è specificato quali problemi verrebbero accelerati e di quanto. La realtà è molto più intricata di queste premesse. Capite bene che se partiamo con il piede sbagliato non possiamo arrivare molto lontano e se ci proviamo comunque, non faremo che raggiungere conclusioni sbagliate.

Per capire veramente quanto siano più “potenti” e vantaggiosi i computer quantistici non possiamo rinunciare ad alcuni concetti di base della teoria della complessità che dobbiamo rispolverare o imparare da zero.

Macchina di Turing

Partiamo con il concetto di Macchina di Turing o MdT per brevità. Si tratta di una macchina astratta, che non può esistere perché prevede un nastro semi-infinito, diviso in celle su cui una testina può muoversi seguendo delle regole o “il programma” come si direbbe oggi e scrivere o leggere il contenuto di una cella. L’informatica intera è nata da questo concetto e le teoria della calcolabilità e della complessità si basano su questo. Non mi metto a spiegarle in dettaglio, ma specifico che ne esistono diverse varianti. Qui ci interessano:

1. MdT deterministica (la base di riferimento, dove non specificato intendo questa variante), dato lo stesso input e lo stesso stato iniziale raggiunge sempre la stessa conclusione o stato finale nello stesso identico tempo o numero di passi, usando lo stesso spazio o numero di celle.
2. MdT non deterministica, analoga alla precedente, solo che il programma che la caratterizza ammette il raggiungimento di più stati diversi. In tal caso la macchina esegue “in parallelo” sequenze di computazione diverse; non appena una di queste sequenze raggiunge uno stato di accettazione, la macchina si arresta e accetta l’input. Se invece tutte le sequenze rifiutano l’input, allora la macchina rifiuta l’input. Questo tipo di macchina non modella affatto un computer quantistico, banalmente perché la fisica quantistica modella la realtà in modo probabilistico e questo modello non si basa sulla probabilità.
3. MdT probabilistica, una MdT non deterministica che invece di proseguire “in parallelo”, sceglie su quale arco di computazione procedere secondo una certa distribuzione di probabilità. Produce risultati stocastici, cioè dato lo stesso input e lo stesso stato iniziale, potrebbe comportarsi diversamente: finire prima o dopo, convergere o non convergere affatto, accettare o non accettare. È già molto più vicina alle fondamenta della meccanica quantistica, ma manca ancora qualcosa, per esempio non ho citato Hilbert.
4. MdT quantistica, simile alla precedente, solo che si basa su matrici di transizione, matrici che moltiplicate con le corrispondenti matrici che rappresentano una MdT probabilistica, forniscono una matrice di probabilità che rappresenta la macchina quantistica. L’insieme degli stati Q è sostituito con uno spazio di Hilbert (la matematica alla base della fisica quantistica si basa su questo concetto). Un giorno magari approfondirò anche degli spazi di Hilbert, ma ora finirei fuori tema.

Classi di complessità

Ora che abbiamo ben in mente il concetto astratto di Macchina di Turing e alcune delle sue varianti più rilevanti in questo contesto, possiamo introdurre e definire alcune delle principali classi di complessità:

1. PTIME o semplicemente P, ovvero la classe di problemi risolvibili in tempo polinomiale, cioè una MdT impiega al più f(n) passi rispetto al suo dato di input grande n. Qui vivono i problemi “facili” per cui esistono algoritmi che richiedono “poco” tempo per essere calcolati.
2. NPTIME o semplicemente NP, ovvero la classe di problemi che possono essere verificati (data la soluzione stabilire se è corretta) in tempo polinomiale, ma di cui potrebbe non esistere una soluzione calcolabile in tempo polinomiale. Dato che anche i problemi in P possono essere banalmente verificati in tempo polinomiale, possiamo dire che P è un sottoinsieme di NP (ma attenzione che non sappiamo se P = NP!). In alternativa NP è la classe di problemi risolvibili in tempo polinomiale da una MdT non deterministica (la MdT deterministica che simula la MdT non deterministica impiega “esponenzialmente molto più tempo”). Qui vivono i problemi “difficili” (in realtà anche quelli “facili”, perché P è contenuta in NP).
3. BPP, o Bounded-error Probabilistic Polynomial time, ovvero la classe di problemi risolvibili da una MdT probabilistica in tempo polinomiale con una probabilità di errore di 1/3 per tutte le istanze del problema. Qui vivono i problemi “difficili” che diventano “facili” se accettiamo 1/3 di probabilità di errore (più tutti quelli “facili” perché P è contenuta in BPP, ma non è stato ancora dimostrato se BPP = P).
4. Finalmente, la classe BQP, o Bounded-error Quantum Polynomial time, ovvero la classe dei problemi risolvibili da una MdT quantistica in tempo polinomiale con una probabilità di errore di 1/3 per tutte le istanze. Qui vivono i problemi “difficili” che diventano “facili” se usiamo un computer quantistico ed accettiamo 1/3 di probabilità di errore (più tutti quelli “facili” perché, come prima, P è contenuta in BQP, ma non sappiamo se BQP = P).

Possiamo già decifrare una buona parte di questo apparentemente complicatissimo ed esoterico diagramma di Venn.

Giusto per dare un riferimento un po’ più solido, aggiungo che la classe PP è definita in modo del tutto equivalente a BPP, solo che ci accontentiamo di una probabilità di errore più alta: fino a meno di 1/2; mentre sulla classe PSPACE che contiene tutte le altre aggiungo una breve digressione: PSPACE è la classe di problemi che per essere risolti richiedono uno spazio polinomiale, cioè se ho un input grande n, la MdT può usare al più f(n) celle, dove f è una funzione polinomiale. Qui vivono tutti i problemi per cui esistono algoritmi che “non occupano troppo spazio”.

Osservando il funzionamento di una MdT si potrebbe notare che non può essere che impieghi un numero di passi superiore al numero di celle utilizzate, altrimenti la macchina andrebbe in loop e non terminerebbe mai (escludiamo questo caso), quindi lo spazio necessario a risolvere un problema decidibile limita il tempo. Questa osservazione fa si che tutte le classi definite prima siano contenute nella classe PSPACE. Esistono una marea di altre classi, sia che contengono PSPACE, sia contenute in PSPACE, sia completamente disgiunte che ovviamente non cito neppure perché probabilmente ho già esagerato con i dettagli.

Nel diagramma riportato sopra non compare la classe NP: questo è dovuto al fatto che non conosciamo ancora quale sia la relazione tra BQP e NP: non sappiamo se BQP è incluso in NP, se NP è incluso in BQP oppure se nessuna delle precedenti è vera. Per ora conosciamo problemi che stanno in BQP che non stanno in NP e viceversa.

La situazione è esemplificata dal diagramma qua sotto.

Manca una introduzione al sottoinsieme dei problemi NP completi, problemi particolarmente “difficili” che caratterizzano la classe NP al punto che per risolvere un qualsiasi problema in NP si può pensare di prendere un algoritmo che risolve un problema NP completo e di costruire dei dati di input in modo che l’algoritmo simuli il problema di partenza. La soluzione potrà comunque essere verificata in tempo polinomiale.

Problemi aperti

Un problema di cui si parla moltissimo in ambito informatico è il problema di stabilire la relazione tra P e NP, che viene annoverato tra i 7 problemi per il Millennio, con premi in denaro per la risoluzione. Tuttavia esistono anche altri problemi, meno noti, ma non meno importanti:

• la relazione tra PSPACE e P (che include il problema precedente)
• la relazione tra BQP e NP

Vediamo alcune conseguenze eclatanti se si riuscissero a dimostrare alcune di queste ipotesi.

Se fosse che NP = BQP, o addirittura BQP contiene strettamente NP, cioè se si dimostrasse che è possibile ricondurre un problema NP completo ad un problema in BQP, allora i computer quantistici sarebbero delle bestie assurde, in grado di risolvere problemi oggi ritenuti intrattabili in tempi polinomiali, anche se con una probabilità di errore.

Più realisticamente, ma, in assenza di una dimostrazione, non più correttamente, si pensa che BQP sia in parte contenuto in NP, come mostra la linea tratteggiata nel diagramma precedente. In ogni caso sembra che si ottengano dei vantaggi notevoli con i computer quantistici, ma se si dimostrasse che NP = P? Sarebbe una notizia incredibile, di cui si parlerebbe ogni giorno, chiedendoci come avevamo fatto a non averci pensato prima. In questo caso, l’utilità dei computer quantistici verrebbe ridimensionata in base a cosa riusciremmo a dire delle altre classi: per esempio potrebbero rimanere utili per quei problemi che stanno fuori da NP (se esistono…).

E se P = NP = BQP? Anche questo sarebbe un grande sconvolgimento, infatti, i computer quantistici risulterebbero completamente inutili, in quanto un computer classico avrebbe accesso ad algoritmi polinomiali per tutti i problemi oggi contenuti in NP. Secondo gli studiosi della materia, ad oggi sembra molto improbabile che si dimostrino questi casi e, di nuovo, si propende per la gerarchia mostrata sopra.

Cosa calcolano meglio dei computer classici?

Ora che abbiamo delle basi di complessità assolutamente non rigorose, almeno a livello intuitivo possiamo ben capire alcuni dettagli non da poco.

Ad oggi si ritiene, ma non si è dimostrato, che l’applicazione dei computer quantistici ad alcuni problemi fuori da BPP, ma dentro BQP, ci consenta la risoluzione in tempo polinomiale di alcuni importanti problemi che i computer classici non possono raggiungere, secondo la teoria corrente. Gli algoritmi strettamente quantistici, infatti, non possono essere calcolati da computer classici, se non tramite una simulazione del comportamento quantistico. Per quanto ne sappiamo oggi, la simulazione ha un costo esponenziale, il che squalifica automaticamente l’algoritmo quantistico simulato sul computer classico dalla classe degli algoritmi polinomiali.

Per ricapitolare, i computer quantistici semplificano alcuni problemi (i problemi che appartengono a BQP) permettendo l’esecuzione di algoritmi quantistici che hanno una complessità inferiore rispetto ai corrispettivi algoritmi classici. Per questo il computer quantistico non esegue di per sé chissà quante operazioni al secondo in più rispetto ad un computer classico, soltanto riduce esponenzialmente il numero di operazioni richieste per risolvere i problemi che stanno in BQP, rendendoli risolvibili in tempi polinomiali.

Inolte, questa riduzione esponenziale si paga con un costo: il risultato del calcolo quantistico ha una probabilità di errore (la classe BQP fissa la probabiltà di errore arbitrariamente ad al più 1/3). Possiamo ridurre a piacere la probabilità di errore ripetendo più volte lo stesso calcolo e decidendo il risultato sulla base di un voto di maggioranza: più volte si ripete il calcolo e più piccola sarà la probabilità di errore. Anche ripetendo lo stesso calcolo, 10000 volte, il computer quantistico richiederà meno passi rispetto al computer classico, poiché quest’ultimo dovrà eseguire un algoritmo non quantistico, il che richiederà un numero esponenziale rispetto all’input di passi in più.

Algoritmi notevoli

Nel corso degli anni sono stati sviluppati diversi algoritmi quantistici che potrebbero avere anche profonde conseguenze, qualora trovassero applicazione pratica.

Algoritmo di Shor per la fattorizzazione in primi

Uno dei problemi appartenente a BQP (per quanto ne sappiamo oggi), è la fattorizzazione in fattori primi. Il migliore algoritmo classico noto è il General Number Field Sieve (GNFS) che ha una complessità sub-esponenziale (una funzione intermedia tra esponenziale e polinomiale). Prima degli anni ‘70, erano noti soltanto algoritmi esponenziali, pertanto il problema era relegato alla classe NP. Nel 1994 fu scoperto l’algoritmo di Shor, un algoritmo quantistico che risolve il problema in tempo polinomiale, spostando il problema in BQP.

Nel 2002 e nel 2012, l’algoritmo fu effettivamente implementato su veri computer quantistici e furono fattorizzati con successo i numeri 15 e 21 rispettivamente. Non fu possibile fattorizzare numeri più grandi a causa dell’accumulazione di errori quantistici.

Di recente è stato dimostrato che, a patto di avere un tasso di errori con un singolo qubit sufficientemente basso, l’affidabilità del calcolo complessiva può essere migliorata mediante un sistema di correzione degli errori quantistico. Sembra che per poter calcolare fattorizzazioni di numeri più grandi sia necessario un dispositivo dotato di questo sistema, che utilizzerebbe alcuni qubit aggiuntivi per implementare la funzionalità, aumentando il numero di qubit necessari per portare a termine il calcolo, il che rende l’intero successo di questo sforzo ingegneristico ancora più complesso ed articolato.

Per chi non era attento, lo ripeto: i più grandi numeri interi mai fattorizzati da computer quantistici sono 15 e 21. Questa è la potenza degli attuali computer quantistici.

Se l’algoritmo di Shor trovasse applicazione pratica, allora la stragrande maggioranza degli attuali sistemi crittografici risulterebbe compromessa. In particolare la sicurezza di RSA si basa sulla asimmetria nella difficoltà di trovare la scomposizione in fattori primi di numeri enormi, mentre, al contrario, semplici operazioni aritmetiche bastano a cifrare o decifrare un messaggio conoscendo la chiave.

L’algoritmo di Shor consentirebbe ad un attaccante di recuperare la chiave privata necessaria a decifrare il messaggio.

Algoritmo di Shor per il logaritmo discreto

Utilizzando un altro algoritmo sviluppato da Peter Shor, molto simile al precedente, è possibile risolvere il problema del logaritmo discreto usando un computer quantistico in tempo polinomiale.

Anche in questo caso verrebbero forzati molti sistemi crittografici quali lo scambio di chiavi crittografiche di Diffie-Hellman, alla base del protocollo TLS e HTTPS per il Web.

Simulazione di sistemi quantistici

Come ci si poteva aspettare, i computer quantistici eccellono nel simulare sistemi quantistici, mentre i computer classici arrancano non poco e già con 30 particelle elementari il calcolo è così complesso da diventare non trattabile nemmeno utilizzando super-computer.

Un utilizzo dei computer quantistici molto interessante che ci permetterà di simulare ampi sistemi di particelle e scoprire nuove cose su questo mondo a noi così poco affine della meccanica quantistica.

Polinomi di Jones

Questi polinomi servono nella teoria dei nodi per descrivere le proprietà dei nodi. Esiste un algoritmo quantistico in grado di trovare approssimazioni delle radici di un polinomio di Jones in tempo polinomiale.

Algoritmo HHL per la risoluzione di sistemi lineari di equazioni

HHL sta per Harrow Hassidim–Lloyd, gli inventori dell’algoritmo quantistico per la risoluzione di sistemi lineari di equazioni.

Trasformata di Fourier quantistica

Molti algoritmi quantistici ne fanno uso, come gli algoritmi di Shor introdotti in precedenza.

Conclusioni

Secondo la teoria della complessità attuale, si pensa che i computer quantistici abbiano un grande potenziale: quello di ingrandire la classe di problemi che riusciamo a risolvere in tempi umani, con risorse in spazio e tempo finiti. Alcuni di questi algoritmi quantistici potrebbero diventare importantissimi in futuro per far progredire velocemente interi campi di ricerca.

Per concludere, è giustificato il grande interesse verso questa branca di informatica che ancora una volta interseca fisica, matematica, probabilità, seppur sia necessario capirne pregi e difetti per metterne a frutto i risultati.

---

L’articolo termina qui, il prossimo uscirà un giorno scelto da una super-posizione di stati quantici. Alla prossima!