Scroll

Come ogni buona teoria che si rispetti, il punto di partenza è sempre un limite da superare.

In informatica, un computer è fondamentalmente una “macchina di Turing” ovvero un modello matematico che rappresenta ciò che un calcolatore programmabile può fare e quello che un calcolatore, oggi, può fare, è governato dalle leggi della fisica classica.

La questione principale del modello era stata posta da David Hilbert nei seguenti termini: «esiste sempre, almeno in linea di principio, un metodo meccanico (cioè una maniera rigorosa) attraverso cui, dato un qualsiasi enunciato matematico, si possa stabilire se esso sia vero o falso?».

La risposta è no.

Non è possibile sviluppare un algoritmo generale che stabilisca la veridicità di una qualsiasi affermazione, e questo perché in realtà il concetto stesso di “algoritmo” non è ben definito (oggi si usa proprio la macchina di Turing per definire tale concetto). Tuttavia, Alan Turing propose un modello matematico con cui verificare, per ogni singola affermazione, se sia possibile arrivare a stabilirla come vera o falsa.

Con la sua macchina infatti è possibile sviluppare algoritmi per ridurre una affermazione ai suoi componenti di base, cercando di verificarla, e vi sono due opzioni: o la macchina ad un certo punto termina l’algoritmo e fornisce una risposta, oppure l’algoritmo andrà avanti all’infinito (in una sorta di loop continuo, chiamato halting) senza mai fornire una risposta.

Una macchina di Turing utilizza come input-output un nastro su cui legge e scrive un valore alla volta, in una precisa cella del nastro, ed in ogni istante di tempo t la macchina avrà un preciso stato s che è il risultato dell’elaborazione. Ovviamente la macchina può eseguire alcune operazioni fondamentali: spostarsi di una cella avanti, spostarsi di una cella indietro, scrivere un simbolo nella casella attuale, cancellare il simbolo presente nella casella attuale, e fermarsi.

Un modello così rigido, che esegue operazioni elementari per tutto il tempo che si ritiene necessario, può di fatto svolgere qualsiasi tipo di calcolo concepibile. Tuttavia, così come Kurt Gödel aveva dimostrato che alcuni teoremi non si possono dimostrare senza cadere in un ciclo infinito , anche con la macchina di Turing non è detto che arrivi ad un risultato, perché alcuni calcoli non si possono portare a termine senza cadere in un processo infinito.

Come anticipato, per un normale calcolatore valgono le leggi della fisica classica, in particolare, i principi della termodinamica. Il primo principio stabilisce quali eventi siano possibili e quali no, il secondo principio stabilisce quali eventi siano probabili e quali no.

Il primo principio, espresso come definizione dell’energia interna di un sistema ci dice che l’energia interna di un sistema chiuso non si crea e non si distrugge, ma si trasforma ed il suo valore rimane dunque costante. Infatti, in un sistema isolato il calore ovvero l’energia interna può trasformarsi in lavoro e viceversa senza però sparire magicamente.

Il secondo principio (quello dell’entropia) definisce la direzione che qualsiasi evento deve seguire ovvero quella che fa aumentare l’entropia. L’entropia non può mai diminuire, al massimo può rimanere costante. In altre parole, l’enunciato del secondo principio della termodinamica si può riassumere con la nota frase “riscaldando un acquario si ottiene una zuppa di pesce, ma raffreddando una zuppa di pesce non si ottiene un acquario”.

Insomma, la maggioranza degli eventi termodinamici non è reversibile e questo vale anche per la macchina di Turing.

Cominciamo a pensare invece a cosa accadrebbe se il modello matematico di Turing fosse basato non più sulle leggi della fisica classica bensì su quelle della meccanica quantistica. Quest’ultima, senza scendere particolarmente nel dettaglio, consentirebbe alle operazioni eseguite dalla macchina di essere anche reversibili con l’ovvio vantaggio per la macchina “quantistica” di non cadere mai nell’halting problem.

Se la base dell’informatica classica è il bit, alla base dell’informatica quantistica troviamo il qubit o bit quantistico. Mentre il primo può assumere solamente un valore ben definito (“0” o “1”, “aperto” o “chiuso”, “acceso” o “spento”), il qubit può assumere anche valori sovrapposti. In base al Principio di indeterminazione di Heisenberg, un elemento quantistico, quale il qubit, non assumerà mai uno valore ben definito, ma avrà sempre stati sovrapposti e indeterminabili.

Nel celebre paradosso proposto da Erwin Schrödinger per spiegare la sua teoria, il gatto può essere contemporaneamente vivo o morto; nel caso degli elettroni questo principio impone che è impossibile determinare con certezza, nell’istante di tempo t, l’energia associata ad essi e contemporaneamente la loro posizione. Pertanto, in base ai parametri del sistema, saranno possibili molte combinazioni di energie e posizioni, ma non tutte. Per lo stesso principio nell’informatica quantistica il qubit potrà assumere contemporaneamente il valore di “0” e di “1”.

Ciò ha una ricaduta molto importante dal punto di vista del calcolo informatico (il campo del calcolo quantistico venne “inaugurato” da Yuri Manin nel 1980 e Richard Feyman nel 1982): potendo assumere contemporaneamente più valori, il qubit permette di processare una quantità maggiore di informazioni, garantendo quindi un maggior scambio informativo rispetto all’informatica classica, limitata dalla sua scala binaria.

Chris Bernhardt, autore del libro “Quantum Computing for Everyone”, scrive: «L’informatica quantistica è una splendida fusione di meccanica quantistica e informatica, che incorpora alcune delle idee più sbalorditive della fisica del ventesimo secolo in un modo completamente nuovo di pensare al calcolo».

Non si può che dargli ragione.

Uno dei principi sui quali si fonda l’informatica quantistica, è quello del no-cloning: l’informazione non può essere né copiata né letta con assoluta precisione. Può essere, però, trasferita con assoluta precisione, a patto che l’originale venga distrutto nel corso del processo (è il caso del teletrasporto quantistico, ottenuto per la prima volta da Nielsen, Klinn e LaFlamme nel 1988). Ogni misura compiuta sullo stato quantistico distrugge gran parte dell’informazione in esso contenuta, lasciandolo in uno “stato base”. La codifica dell’informazione, infine, può essere (e verrà) effettuata attraverso correlazioni “non locali” tra diverse parti del sistema fisico basate sull’entanglement quantistico.

Si potrebbe erroneamente pensare che queste caratteristiche rendono un computer inutile, ma è proprio qui che bisogna cominciare a “pensare fuori dagli schemi”.

Pur apparendo meno definita e “precisa” rispetto all’informatica che conosciamo, è dimostrabile che le Macchine di Turing quantistiche non solo possono raggiungere lo stesso grado di precisione delle Macchine classiche, ma possono compiere calcoli e operazioni impossibili per quest’ultima.

Ma cerchiamo di capire come è possibile tutto questo.

I qubit possono essere implementati misurando la proprietà di spin dei nuclei degli atomi di alcune molecole, oppure la polarizzazione dei fotoni. In realtà, pensandoci bene, ci si può accorgere che una macchina di Turing quantistica non è altro che una macchina classica il cui nastro di lettura/scrittura contiene valori casuali. Il vantaggio della casualità è nella possibilità reale di fare tentativi a caso. In questo modo si può trovare la soluzione di un problema che con un algoritmo tradizionale non è possibile affrontare.

Un buon algoritmo può, comunque, aiutare un po’ il caso.

Ovviamente per algoritmi semplici, questa idea è solo una complicazione, ma per algoritmi complessi (di conseguenza lenti da elaborare) la macchina quantistica può fornire un risultato accettabile in tempi ridotti. Potremmo fare un paragone con il metodo Monte Carlo, un metodo per ottenere un risultato approssimato sfruttando tentativi casuali. Immaginiamo di avere un’immagine dipinta su di un muro e di volerne misurare l’area. Se l’immagine è regolare, come un quadrato, un cerchio od un triangolo sarebbe sufficiente usare l’apposito algoritmo. Ma se l’immagine è un capolavoro del Da Vinci, sarebbe inverosimile costruire un algoritmo per calcolarne la superficie o, comunque, complicato ed estremamente lento. Il metodo Monte Carlo ci suggerisce di sparare a caso contro il muro.

Dopo un po’ di tempo sarà sufficiente contare il numero di proiettili che sono finiti dentro alla sagoma e moltiplicarlo per la superficie di un singolo proiettile ottenendo così una buona approssimazione della superficie della sagoma.

Un metodo simile che si usa molto nell’informatica moderna è rappresentato dagli algoritmi genetici, i quali hanno però due svantaggi:

  • deve essere possibile sviluppare una funzione di fitness, cosa non sempre possibile;
  • comunque gli algoritmi verrebbero eseguiti su una macchina che si comporta in modo classico, quindi il sistema sarebbe comunque poco efficiente.

Inoltre, è praticamente impossibile ottenere delle mutazioni davvero casuali nei codici genetici che si utilizzano per cercare una soluzione. Vale la pena ricordare, infatti, che la casualità nei computer classici non esiste, essi vengono generati da algoritmi che a loro volta non sono casuali; in informatica infatti un numero può solo essere “pseudo-randomico” (a meno di usare “Generatore hardware di numeri casuali”). I qubit risolvono questi problemi, visto che sono rappresentati da oggetti fisici naturalmente casuali.

Per concludere, uno dei settori nel quale un computer quantistico trova una naturale collocazione è la cyber-security. Infatti, è sufficiente prendere in considerazione l’algoritmo di crittografia più utilizzato e che al momento protegge qualsiasi tipo di comunicazione, ovvero l’RSA (messo a punto nel 1977 da Ron Rivest, Adli Shamir e Leonard Adlemann da cui cognomi nasce l’acronimo). Tale algoritmo è basato sul prodotto di due numeri primi di grandi dimensioni (oggi l’ordine di grandezza di assoluta sicurezza utilizzato è circa 10300). La fattorizzazione del prodotto di tali numero è praticamente impossibile per un calcolatore classico, nel senso che richiederebbe di norma tempi probabilmente superiori all’età dell’universo. Non esistono, infatti, nel mondo classico algoritmi capaci di effettuare questa operazione in maniera efficiente.

Tutt’altra storia nel mondo del calcolo quantistico dove è stato sviluppato l’algoritmo di fattorizzazione di Shor. Il suo obiettivo è proprio fattorizzare numeri interi, di grandi dimensioni, in numeri primi. Sfruttando un calcolatore quantistico le operazioni dell’algoritmo di Shor, diventano “semplici” e l’intero processo si può svolgere in un tempo (calcolabile con un polinomio) finito e, solitamente, breve. Con questo algoritmo, si potrebbero decriptare le chiavi private di cifratura di tutti i messaggi più riservati, facendo crollare l’intera sicurezza delle telecomunicazioni. Al momento con gli attuali computer quantistici, non è possibile applicare l’algoritmo di Shor in modo generale, ma ne sono già state realizzate alcuni versioni semplificate adattate per specifici casi. Se i computer quantistici diventassero più potenti ed affidabili, diventerebbe possibile sfruttare l’algoritmo su qualsiasi chiave crittografica e far crollare la sicurezza di internet.

Il mondo, per fortuna (o sfortuna), non tornerebbe comunque all’età della pietra. Infatti, usando gli stessi computer quantistici, sarebbe possibile adottare un nuovo sistema di crittografia a “blocco monouso” (ad es. Il protocollo di Ekert) con distribuzione quantistica della chiave crittografica. Tale metodo risulterebbe inviolabile poiché per forzarlo bisognerebbe dimostrare che le leggi della fisica, ed in particolare quelle della meccanica quantistica siano sbagliate e posso garantirvi che con buona probabilità non lo sono!

Ciro D’Addio