Definizione e differenza tra computazione classica e quantistica

La computazione classica e la macchina di Turing

La macchina di Turing è una macchina ideale che manipola i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite. Ad ogni istante la macchina si trova in uno stato appartenente ad un insieme finito e legge un carattere sul nastro. La funzione di transizione, in modo deterministico, specifica tre cose: il simbolo da scrivere sul nastro, la direzione in cui la testina deve muoversi, e il successivo stato della macchina.

Nella macchina di Turing deterministica (TM) l’insieme di regole prevede al massimo un’azione da eseguire per ogni situazione. Al contrario, nella macchina di Turing non deterministica (NTM) l’insieme di regole possono prevedere più azioni da eseguire per ogni situazione.

Una computazione eseguita da una macchina non deterministica può essere rappresentata con un albero di computazioni deterministiche.

La computazione classica si basa sul modello della macchina di Turing, che risulta essere un modello astratto di macchina universale.

La macchina di Turing funziona seguendo un insieme di regole e di principi enunciati da Alan Turing nel 1936 e successivamente elaborati da John von Neumann negli anni ’40. Alla base di questi principi vi è l’assunzione che la macchina di Turing idealizza un dispositivo che obbedisce alle regole della fisica classica.

La computazione quantistica

La computazione quantistica, a differenza della computazione classica, nasce come paradigma alternativo. Si basa sui principi della Meccanica quantistica, che sono gli unici in grado di giustificare i fenomeni fisici a livello microscopico, come ad esempio all’interno di un atomo.

Quindi la Meccanica quantistica spiega i fenomeni che avvengono a livello atomico per i quali la Meccanica classica (o newtoniana) è del tutto inadeguata.

La caratteristica fondamentale della Meccanica quantistica è che descrive la materia e la radiazione sia come entità particellare che come fenomeno ondulatorio. Al contrario la Meccanica classica non gode del dualismo onda-particella, infatti la luce è descritta come onda e l’elettrone come una particella.

Con la computazione quantistica viene introdotta la teoria della quantizzazione. A livello microscopico, le quantità fisiche come per ad esempio l’energia non sono scambiabili in modo “continuo”, ma attraverso “pacchetti” detti quanti. In base a questa proprietà, la luce è costituita da corpuscoli di energia chiamati “fotoni”.

Le prime applicazioni di questo metodo di calcolo non convenzionale si ebbero agli inizi degli anni Ottanta. In quegli anni, infatti, cominciò ad affacciarsi l’idea di realizzare un modello di computazione come un sistema quantistico allor quando il fisico statunitense P.Benioff pubblicò una descrizione completa del modello meccanico quantistico della Macchina di Turing. Il modello computazionale era basato su considerazioni precedentemente elaborate da C.Bennet che definiscono la Macchina di Turing reversibile.

Una computazione è reversibile quando il processo di calcolo è invertibile. Di conseguenza, si ritorna allo stato inziale ripercorrendo all’indietro i vari passi eseguiti. Benioff è stato il primo a dimostrare che il calcolo quantistico reversibile è teoricamente possibile. La sua ricerca aprì la strada a numerosi altri scienziati che approfondirono il campo dell’informatica quantistica.

Feynman, successivamente, dimostrò che nessuna Macchina di Turing classica riusciva a simulare alcuni fenomeni fisici senza subire un rallentamento esponenziale delle prestazioni. Un “simulatore quantistico universale”, al contrario, avrebbe potuto effettuare la simulazione in maniera molto più efficiente.

Nel 1985 fu fondamentale il contributo del fisico britannico D. Deutsch. Egli formalizzò le idee fino ad allora formulate nella sua Macchina di Turing Quantistica Universale, che ha portato alla concezione moderna di computazione quantistica. Basandosi sulla tesi di Church-Turing, David Deutsch si spinse inoltre ad avanzare il principio secondo cui “ciascun sistema fisico realizzabile può essere perfettamente simulato da un modello universale di macchina computazionale operante con risorse finite”. Secondo Deutsch, questo principio implica che un computer quantistico è in grado di simulare qualsiasi esperimento fisico.

L’introduzione del nuovo modello di calcolo ha influenzato significativamente il campo della complessità computazionale, provocando il cambiamento della nozione di “trattabilità”. Infatti, nel 1994 P. Shor dimostra che il problema della fattorizzazione dei numeri primi, che fino ad allora era stato considerato intrattabile, si può risolvere efficientemente, in tempo polinomiale, con un algoritmo quantistico. Queste considerazioni, unite a quelle di tipo tecnologico, hanno portato all’affermarsi di un campo di ricerca del tutto nuovo e allo sviluppo di computer in grado di risolvere problemi complessi e lunghi in tempi brevissimi. In particolare nei prossimi capitoli si affronteranno tre fenomeni fondamentali della teoria quantistica su cui la computazione quantistica si basa in maniera essenziale, e che determinano la sua enorme potenzialità di calcolo: il principio di sovrapposizione degli stati, il principio di misurazione e il fenomeno dell’entanglement.

Computer classico e quantistico

La programmazione di un computer quantistico, al giorno d’oggi, può svolgersi anche tra le mura domestiche.

Che cos’è, dunque, un programma quantistico? E come funziona nel dettaglio un computer quantistico?

E’ possibile rispondere a queste domande facendo confronti con computer digitali standard. I computer classici funzionano a bit. I bit hanno solo due valori, 0 e 1, con i quali si può rappresentare qualsiasi informazione. Un numero è rappresentato da dieci cifre 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9, ognuna delle quali, in base alla posizione che occupa, assume un valore diverso.

I computer quantistici invece sono macchine che utilizzano le proprietà della fisica quantistica per memorizzare dati ed eseguire calcoli. Questo può essere estremamente vantaggioso per svolgere alcuni compiti in cui le prestazioni potrebbero ampiamente superare quelle dei migliori super-computer presenti attualmente.

In altre parole, i computer attuali manipolano singoli bit, che memorizzano le informazioni come stati binari, 0 e 1. I computer quantistici, invece, si basano su bit quantici o qubit.

I Qubit sono realizzati usando sistemi fisici, come lo spin di un elettrone o l’orientamento di un fotone. Questi sistemi possono trovarsi contemporaneamente in stati diversi, grazie a una proprietà nota come sovrapposizione quantistica.

I Qubit, inoltre, possono essere indissolubilmente legati tra loro, tale fenomeno è chiamato entanglement quantistico. Il risultato è che una serie di qubit può rappresentare simultaneamente tanti stati diversi.

Ad esempio, otto bit sono sufficienti per un computer classico per rappresentare qualsiasi numero compreso tra 0 e 255. Otto qubit sono sufficienti per un computer quantistico per rappresentare otto numeri compresi tra 0 e 255 contemporaneamente. Poche centinaia di qubit intrecciati sarebbero sufficienti per rappresentare più numeri di quanti sono gli atomi nell’universo.

Sfruttando la capacità unica delle particelle subatomiche che consente loro di esistere in più di uno stato, cioè 1 e 0 contemporaneamente, la sovrapposizione e l’entanglement sono due caratteristiche della fisica quantistica su cui si basano i computer quantistici. Ciò consente di gestire le operazioni a velocità esponenzialmente superiori rispetto ai computer convenzionali e con un consumo di energia molto inferiore.

In situazioni in cui esiste un gran numero di possibili combinazioni, i computer quantistici possono considerarle tutte contemporaneamente. Tuttavia, ci possono essere anche molte situazioni in cui i computer classici risultano migliori rispetto a quelli quantistici, di conseguenza i computer del futuro potrebbero essere pensati come una combinazione tra computer classico e computer quantistico.

Attualmente i computer quantistici sono estremamente sensibili: il calore, i campi elettromagnetici e le collisioni con molecole d’aria possono far perdere le proprietà quantiche a un qubit. Questo processo, noto come decoerenza quantistica, è tanto più rapido quante più particelle sono coinvolte e provoca il crash del sistema.

Inoltre, i computer quantistici devono garantire che i qubits siano isolandoti fisicamente dalle interferenze esterne, mantenendoli a temperature molto basse o sottoponendoli a impulsi di energia attentamente controllati. Ecco perché l’interno del computer quantistico di D-Wave Systems ci sono -460 gradi Fahrenheit. Infine, sono necessari qubit aggiuntivi per correggere errori che si insinuano nel sistema, di conseguenza la realizzazione di un computer quantistico ha molte complicazioni.