INFORMAZIONE E COMPUTAZIONE QUANTISTICA: TEORIA

Informazione e computazione quantistica: teoria

Al crocevia tra scienza e tecnologia

La nuova disciplina che va sotto il nome di informazione e computazione quantistica si sviluppa al crocevia tra la tecnologia avanzata del calcolo e della telecomunicazione e alcune scienze di base, la matematica in primo luogo, la scienza dell’informazione e – naturalmente e con un ruolo portante – la fisica. Queste si fondono in una nuova scienza con un’articolazione interdisciplinare che non ha precedenti in tutta la storia del pensiero scientifico.

Miniaturizzazione, legge di Mooreed effetti quantistici

L’informazione viene immagazzinata, trasmessa e manipolata con mezzi fisici. Dunque, i concetti di informazione e di computazione – che altro non è se non una particolare forma di manipolazione dell’informazione – possono essere formulati nel contesto di una teoria fisica e lo studio dell’informazione richiede, in ultima analisi, il ricorso all’esperimento. Questo fatto, apparentemente semplice e quasi ovvio, conduce a conseguenze non banali. È ormai generalmente accettato che ogni teoria fisica supporta un modello computazionale la cui potenza è limitata soltanto dalla natura della teoria stessa. La fisica classica e la meccanica quantistica sostengono una moltitudine di implementazioni diverse del modello di computazione dato dalla macchina di Turing (v. oltre). È stato altresì proposto che teorie di campo non abeliane (le cosiddette teorie di campo quantistiche topologiche) possano mostrare le caratteristiche necessarie a supportare un modello di computazione capace di risolvere problemi di classe di complessità non-polinomiale (una classe non trattabile classicamente) in un tempo polinomiale, rendendoli così accessibili. D’altro lato, la legge empirica nota come legge di Moore – dal nome dell’ingegnere statunitense Gordon Moore che fu fra i fondatori dell’Intel – afferma che ogni 18 mesi i moderni microprocessori (MOSFET, Metal Oxide Semiconductor Field Effect Transistors) raddoppiano la densità di transistor equivalenti che essi contengono a unità di volume. La progressiva miniaturizzazione fa dunque prevedere che in tempi molto brevi i circuiti che costituiscono le porte logiche di un computer si avvicineranno al punto in cui essi debbano essere così piccoli da essere costituiti di pochi atomi. A quel punto, gli effetti quantistici diventeranno importanti, anzi dominanti. Pertanto, se si vuole che i computer diventino sempre più veloci e sempre più piccoli, una nuova tecnologia quantistica dovrà sostituire o almeno affiancare quella attuale. La fisica moderna ha mostrato come sia possibile immaginare nuovi modi di codifica e di manipolazione dell’informazione, basati sulla meccanica quantistica, che in molti casi si rivelano molto più efficienti e potenti dei corrispondenti classici.

La matematica del calcolo

Nell’agosto 1900, a Parigi, durante il Deuxième congrès international des mathématiciens, David Hilbert elencò 23 problemi che riteneva costituissero la sfida cui i matematici avrebbero dovuto far fronte nel secolo che stava per iniziare. Uno di questi, il 10° (l’entscheidungsproblem), ha segnato la nascita di un capitolo nuovo della matematica: la teoria della complessità algoritmica. Hilbert riteneva che lo speciale sistema formale assiomatico, che è la matematica, debba essere consistente, privo di contraddizioni, completo, in quanto rappresenta la verità, e decidibile, nel senso che deve esistere una procedura meccanica, un programma, per stabilire se i suoi predicati sono veri o falsi. La matematica che studia la trattabilità degli algoritmi ha reso evidente la vastità dei problemi intrinsecamente intrattabili che caratterizzano, non soltanto la teoria del calcolo e della computazione, ma la computer science e la ricerca operativa in senso lato. Di fatto, la classe dei problemi intrattabili, noti come NP (Nondeterministic Polynominal-time) completi (v. oltre Complessità algoritmica e quantistica), è così pervasiva che gran parte delle conoscenze scientifiche, che devono fare ricorso a tecniche numeriche per poter essere quantificate, debbono fare i conti con questa vera e propria ostruzione alla potenza di calcolo di cui possiamo disporre. Metodi di computazione, basati sull’implementazione degli schemi in sistemi fisici descritti dalla teoria quantistica, hanno mostrato che i limiti della non polinomialità possono essere superati e che la misura della complessità algoritmica di un dato calcolo non dipende dall’algoritmo ma dalla natura – classica o quantistica – del sistema fisico con cui esso viene eseguito.

Fin da quando Kurt Gödel (1906-1978) enunciò i suoi teoremi d’incompletezza, si sa che l’universalità costringe a pagare un prezzo molto alto. Il programma di Hilbert, di costruire la matematica basandola su principi formali assiomatici e di dimostrare che il sistema di assiomi usati è privo di contraddizioni, avrebbe dato alla matematica – se avesse avuto successo – una forma definitiva. Al contrario, la matematica, nonostante i risultati di Gödel, ha sì trovato nel 20° sec., nella formulazione della teoria assiomatica degli insiemi, una forma che si è dimostrata universale, nel senso che qualsiasi campo della matematica oggi conosciuto può – in linea di principio – essere ricondotto a una costruzione nell’ambito di tale teoria, ma ciò che i teoremi di Gödel comportano è l’esistenza di un’inesauribile molteplicità di modelli (nel senso della teoria dei modelli dei sistemi formali assiomatici) che la teoria degli insiemi assiomatica è in grado di fornire e con cui, proprio in virtù dei risultati di Gödel, nessuna teoria può venire a patti. Con inesauribile molteplicità s’intende non soltanto il semplice fatto che sono infiniti, ma che non possono essere descritti da un’unica forma chiusa. Per questo, mentre l’ipotesi di Church-Turing della teoria classica della computazione, ossia che tutti i modelli ‘naturali’ di computazione siano essenzialmente equivalenti l’uno all’altro, non è mai stata dimostrata, la sua versione quantistica, secondo la quale un computer quantistico universale può simulare il comportamento di qualsiasi sistema fisico (computer) finito, fu dimostrata rigorosamente, nel corso degli anni Ottanta del 20° sec., in un fondamentale lavoro dal fisico inglese David Deutsch, che diede vita appunto alla computazione quantistica, vale a dire all’idea di costruire un sistema di calcolo basato su principi consistenti con la fisica quantistica.

Complessità algoritmica e quantistica

La radice profonda di questa caratteristica sta nel fatto che, mentre nel mondo fisico tutto è regolato, in ultima analisi, dalle leggi quantistiche, un modello computazionale della fisica – vale a dire una rappresentazione delle leggi della natura mediante una metafora computazionale (condizioni iniziali, evoluzione ed effetto della dinamica indotta dalle leggi fisiche, interpretati, rispettivamente, come input, algoritmi di manipolazione e output di una macchina di calcolo) – si scontra con l’impossibilità di un computer (sistema di calcolo), basato su di un sistema fisico classico, di simulare esattamente la dinamica di un oggetto quantistico, se non al costo di accettare un processo di durata esponenzialmente maggiore. Si è in presenza, dunque, di un problema molto più difficile da trattare quanto più grande è il sistema che si vuole simulare. Per gli scienziati della computazione un problema matematico viene detto trattabile se la durata del processo di risoluzione (misurata come funzione del numero di operazioni elementari che si devono effettuare) cresce con la lunghezza n (in bit) dell’input come un polinomio. Viene, invece, classificato come intrattabile se la soluzione richiede un tempo che cresce esponenzialmente con n. La questione di fatto è piuttosto sottile, tanto che esiste una teoria della complessità algoritmica che ne studia la struttura. In maniera molto sintetica si può dire che il modo (classico) più efficiente di eseguire una grande quantità di computazioni è quello di inserire in esse un elemento di casualità, ovvero introdurre nel processo di manipolazione dell’informazione, che costituisce l’algoritmo, la formulazione di congetture, con le quali il computer opera per verificarle oppure per migliorarle. Calcoli eseguiti in questo modo vengono detti non deterministici.

Queste considerazioni hanno portato la scienza dei computer a una classificazione complessa e sottile delle operazioni di computazione: si parla di problemi di classe P per indicare i problemi trattabili (in tempo polinomiale), di problemi di classe NP per definire quella vasta classe di problemi che sono risolubili in modo non deterministico, ma per i quali – benché si possa verificare in tempo polinomiale se una soluzione ipotizzata è corretta o no – non si conosce alcun algoritmo che ne permetta la soluzione se non in tempo esponenziale. Una delle grandi congetture aperte della matematica è quella di stabilire quale relazione esista tra i problemi delle classi P e NP, vale a dire se P=NP oppure P≠NP. Inoltre esistono la classe EXP, che include, oltre ai problemi in NP, problemi per i quali non si è in grado neppure di verificare una soluzione congetturata se non in tempo esponenziale, e la classe universale che contiene tutti i problemi. Nella computer science il calcolo quantistico ha introdotto nuove classi di complessità: per es., QP (Quasi-Polynominal-time) classifica problemi che sono di classe NP classicamente ma P quantisticamente. Un concetto che entra in gioco in questo tipo di situazione è quello di oracolo. Introdotto dall’inglese Alan M. Turing (1912-1954) nel suo tentativo di trovare una soluzione costruttiva al problema aperto da Gödel con i suoi teoremi di incompletezza individuando problemi che fossero dimostrabilmente indimostrabili, un oracolo è una specie di assistente virtuale che, rispondendo in maniera selettiva ed efficiente a una classe ben precisa di domande, non importa se con risultati ottenuti in tempo esponenziale o no, permette alla computazione principale, che l’algoritmo esegue, di diventare efficiente. Turing era interessato al problema della fermata (halting problem), vale a dire quello di predire a priori per un dato programma di calcolo, semplicemente conoscendone la struttura, se questo sia in grado di giungere alla soluzione del problema in tempo finito oppure se il programma sia destinato a funzionare indefinitamente senza poter arrivare al risultato. Egli intendeva dimostrare che un computer, che avesse a disposizione un oracolo capace di dare risposta al problema della fermata per qualsiasi programma, sarebbe stato in grado di risolvere in modo efficiente i problemi più complessi della matematica. Nel calcolo quantistico il concetto di halting fu quello che portò, con il lavoro di Deutsch, Richard Jozsa e soprattutto di Dan Simon negli anni Novanta del 20° sec., alla nascita dell’algoritmo di Shor (che tuttavia non fa uso di oracolo). Quest’ultimo dimostrò l’effettiva superiorità del calcolo quantistico, congetturata nel decennio precedente da Richard Ph. Feynman, rispetto a quello classico, almeno in termini di complessità.

Fisica, informazione e informazione quantistica

Le radici termodinamiche

Quando, nella seconda metà del 19° sec., James Clerk Maxwell, con l’idea di verificare la validità del secondo principio della termodinamica e stabilire il fondamento probabilistico e il ruolo delle fluttuazioni in quella teoria, ideò l’esperimento mentale oggi noto come il diavoletto di Maxwell – dove una creatura immaginaria, aprendo e chiudendo un divisorio fra due recipienti pieni di gas, riesce a far accumulare da una parte tutte le molecole del gas che si muovono con velocità più alta, facendo così evolvere il sistema da una configurazione di entropia più alta a una di entropia più bassa (o, equivalentemente, portando calore dal sottoinsieme a temperatura più bassa a quello a temperatura più alta), in contraddizione con i principi fondamentali della termodinamica – certo non immaginava che il tentativo di risolvere il paradosso sollevato dal suo modello-giocattolo sarebbe diventato la metafora paradigmatica di base per una serie di discussioni tanto minuziose quanto complesse, che avrebbero trovato la loro soluzione soltanto con il calcolo quantistico. Passando attraverso l’identificazione fra l’entropia termodinamica di Ludwig E. Boltzmann e quella di Claude E. Shannon, fondamento della teoria dell’informazione, e la riformulazione semplificata dell’esperimento mentale di Maxwell da parte di Leo Szilard, la metafora del diavoletto portò a una domanda tanto semplice quanto profonda, che fu John von Neumann a formulare nella maniera seguente: quale energia è associata a un atto elementare di informazione, vale a dire a una decisione rispetto a un’alternativa binaria e alla corrispondente trasmissione di un’unità di informazione? La risposta di von Neumann (derivata dal ragionamento di Szilard) fu che tale energia minima è la stessa richiesta per effettuarne la misura corrispondente: k_BTln2, dove k_B è la costante di Boltzmann e T la temperatura assoluta. Léon N. Brillouin estese successivamente la questione al caso quantistico, di cui fu Charles H. Bennett a dare la soluzione definitiva, ispirata a una profonda intuizione di Rolf W. Landauer del 1961, che introdusse nel dibattito l’identificazione di Feynman fra processo naturale e computazione e l’arricchì con il concetto di irreversibilità logica, estendendo al processo di calcolo il tipo di misura che Brillouin aveva immaginato per il processo fisico. Un concetto fondamentale della prospettiva di Landauer era quello di cancellazione, in base al quale egli correttamente concludeva che un computer avrebbe dovuto spendere energia ogni qualvolta la sua memoria venisse azzerata e che anche un computer reversibile avrebbe sofferto di un problema derivante dalla necessità di cancellare l’informazione che si deve eliminare. Ciò che soltanto l’ingegnosità di Bennett portò a comprendere, era come fosse possibile superare il problema dell’informazione eliminata.

Secondo Bennett, la reversibilità che caratterizza la fisica microscopica (in contrasto con l’irreversibilità dei sistemi macroscopici) permette di realizzare uno schema concettuale relativo proprio a oggetti fisici quantistici e ai corrispondenti programmi di calcolo. L’idea è che una computazione deve consistere di due parti, delle quali la seconda sostanzialmente disfaccia (cioè svolga al contrario) quanto fatto nella prima. La prima parte produrrebbe dunque la risposta desiderata (corretta) al problema, eventualmente corredata di altre informazioni; la seconda, eliminerebbe l’informazione estranea, invertendo il processo che l’aveva generata, ma preservando la risposta e l’informazione utile. Bennett provò che qualsiasi processo di computazione può essere ricondotto a questa forma reversibile semplicemente accumulando la storia di tutta l’informazione che sarebbe normalmente eliminata e poi gettando via questa storia e invertendo il processo che l’aveva generata.

Fisica dei quanti e codifica dell’informazione

La computazione quantistica si colloca, dunque, al confine fra due discipline ben stabilite, aprendo un campo nuovo d’indagine e di sviluppo. Da un lato, la scienza dell’informazione, con tutte le sue problematiche tradizionali, a partire dal diavoletto di Maxwell che la connette alla meccanica statistica, e proseguendo con il teorema di Shannon, la macchina di Turing (il computer), la crittografia, la complessità e i problemi operativi quali i codici di correzione d’errore; dall’altro, la meccanica quantistica con i suoi paradigmi: lo spazio di Hilbert degli stati, le rappresentazioni di Schrödinger e di Heisenberg, le correlazioni di Bell, Einstein, Podolski e Rosen, l’interferenza a molti corpi, la decoerenza e i problemi connessi con la misura quantistica. Fra le due, la sfida del computer quantistico, con gli algoritmi, la correzione degli errori, la compressione dei dati, la crittografia con la sue nuove possibilità di distribuzione delle chiavi.

Fra i concetti fondamentali della fisica quantistica, due, in particolare, stanno alla base dell’informazione quantistica, cioè della capacità della materia di codificare informazione nei suoi stati microscopici e di elaborarla e decodificarla mediante un’evoluzione dinamica controllata: la sovrapponibilità degli stati quantistici – e, in particolare, l’esistenza fra gli stati sovrapposti di stati inseparabili (entangled) – che non ha controparte classica, e l’indistinguibilità delle particelle la cui dinamica è regolata dalla meccanica quantistica. Invece di definire la sovrapposizione in maniera astratta, verrà esaminato qui l’esperimento che ne è la quintessenza, che ha in sé il cuore della meccanica quantistica, come affermato da Feynman. Gli ingredienti essenziali di questo esperimento sono una sorgente di particelle (per es., fotoni, o elettroni, o addirittura molecole), uno schermo con due fenditure posto di fronte alla sorgente e uno schermo di osservazione, parallelo a quello con le fenditure e dal lato opposto rispetto alla sorgente. L’essenza dell’esperimento è che sul secondo schermo si osservano frange di interferenza, se entrambe le fenditure sono aperte, e un singolo picco d’intensità, se una sola delle fenditure è aperta. Le frange sono immediatamente interpretabili mediante l’ipotesi ondulatoria, vale a dire l’idea che alle particelle emesse dalla sorgente si possa attribuire anche natura di onde. Nel linguaggio della meccanica quantistica, indicando con ∣Ψ⟩ il vettore nello spazio di Hilbert che descrive lo stato del sistema osservato sullo schermo,

∣Ψ⟩=-12 (∣Ψ1⟩+∣Ψ2⟩)

è la sovrapposizione coerente dei due stati quantistici ∣Ψ1⟩ e ∣Ψ2⟩ che descrivono lo stato corrispondente, rispettivamente, a una sola fenditura, 1 o 2, aperta. Una delle proprietà più interessanti dell’esperimento di Young (così come viene indicato) è che esso si riesce a realizzare con intensità così bassa da avere la certezza che la funzione d’onda ∣Ψ⟩ di una sola particella interferisca con sé stessa. Ciò porta a una domanda la cui risposta fissa il paradigma fondamentale della meccanica quantistica: attraverso quale delle due fenditure passa realmente la particella? Non è possibile dare una risposta deterministica a questa domanda, senza stabilire un appropriato schema interpretativo. Infatti, per fare un qualsiasi esperimento che permettesse di decidere attraverso quale delle due fenditure la particella passa, si dovrebbe in qualche modo interagire con la particella, il che produrrebbe decoerenza, vale a dire perdita dell’interferenza, perché è soltanto quando non c’è alcun modo di conoscere, neppure in linea di principio, quale sia la fenditura attraversata dalla particella che di fatto osserviamo l’interferenza. Alcuni filosofi della scienza hanno avanzato l’ipotesi che si possa affermare che la particella passa attraverso entrambe le fenditure simultaneamente, ma questo non è corretto ed è contraddittorio perché, da un lato una particella è un’entità localizzata, dall’altro, non esiste alcuna procedura operativa per dimostrare sperimentalmente una tale affermazione.

Il concetto fondamentale della scienza dell’informazione, d’altra parte, è il bit, un sistema sostenuto da un appropriato supporto fisico che può assumere due soli valori, 0 e 1 (o vero e falso). In una realizzazione classica il supporto potrebbe, per es., essere un interruttore, nel quale ci sia una barriera di energia fra i due stati fisici che esso determina e distingue (interruttore aperto e chiuso), tale da non permettere transizioni spontanee – vale a dire non determinate dall’azionamento dell’interruttore stesso – fra di essi. Nella teoria quantistica dell’informazione si definisce l’analogo del bit, il qubit, che è anch’esso un sistema fisico capace di esistere in due stati distinti, convenzionalmente indicati come ∣0⟩ e ∣1⟩. Una particella di spin 1/2 è un buon esempio di qubit, perché essa può esistere in due soli stati misurabili ∣↑⟩ (spin-up) e ∣↓⟩ (spin-down) associabili a ∣0⟩ e ∣1⟩. La proprietà che in maniera netta distingue il qubit dal bit è proprio la possibilità di sovrapposizione coerente che permette di realizzarne lo stato generico ∣Q⟩=α∣0⟩+β∣1⟩, con ∣α∣2+∣β∣2=1. Questo non significa che il valore del qubit sia compreso fra 0 e 1, ma – ed è questo lo schema interpretativo proprio della meccanica quantistica – che, se si effettua una misurazione sul sistema fisico che lo supporta, si troverà con probabilità ∣α∣2 il valore 0 e con probabilità ∣β∣2 il valore 1. Un punto essenziale qui è che una qualsiasi trasformazione su un qubit, tra quelle che sono necessarie per manipolare l’informazione che esso codifica, deve conservare la normalizzazione dello stato, vale a dire la proprietà che la somma dei moduli quadrati dei coefficienti complessi della sovrapposizione che lo realizza valga 1. Questo per non violare l’interpretazione di tali numeri, per es. ∣α∣2, come probabilità che lo stato puro che ha α come coefficiente venga ottenuto come risultato di una misura. Le operazioni che soddisfano questa proprietà vengono dette unitarie (e unitari gli operatori che le realizzano). Inoltre, per una qualsiasi sovrapposizione coerente degli stati ∣0⟩ e ∣1⟩ si può sempre immaginare di effettuare un cambiamento (unitario) di base per cui il valore del qubit è ben definito, e vale 0 o 1, mentre una mescolanza incoerente dei due stati darà sempre un valore del qubit intermedio, compreso fra 0 e 1, privo di significato, comunque lo misuriamo.

Si consideri ora un sistema costituito di due qubit, per es. una coppia di particelle, entrambe di spin 1/2, emesse da una stessa sorgente, e si immagini di fare riferimento a coordinate ancorate alla sorgente, in maniera tale che questa abbia quantità di moto e momento angolare nulli. Le due particelle, in quel sistema di riferimento, avranno quantità di moto e momenti angolari opposti, cioè trasportano valori di qubit differenti. Lo stato di un tale sistema (scrivendo solo i numeri quantici di qubit delle particelle e non della sorgente, che non gioca alcun ruolo) è dato da

∣Φ⟩=-1√−2 (∣0⟩1∣1⟩2+∣1⟩1∣2⟩2)

dove il pedice, 1 o 2, indica la particella cui lo stato si riferisce. Qui emerge una nuova proprietà: in questo stato nessuno dei due qubit ha un valore definito, ma – secondo quanto stabilisce la teoria della misura quantistica – quando si effettua una misurazione su uno dei due qubit (cioè su una delle due particelle) si vedrà immediatamente che l’altro si trova nello stato con valore opposto, qualunque sia la distanza fra i due al momento della misura. È questo, nella sua formulazione più semplice, il cosiddetto problema della non località della meccanica quantistica. La dimostrazione rigorosa di quanto avviene in una situazione come quella descritta sta nel fatto che le correlazioni che si originano nel sistema violano le cosiddette diseguaglianze di Bell, cioè non possono essere spiegate sulla base delle sole proprietà locali dei singoli qubit. Per meglio comprendere la natura degli stati come ∣Φ⟩, che sono la sovrapposizione di stati-prodotto di più particelle e del ruolo che essi giocano nell’informazione quantistica, si può osservare che – esattamente come nell’esperimento delle due fenditure – anche qui la sovrapposizione implica che non si può dire quale dei due diversi modi possibili di formare la sovrapposizione sia quello reale. Quando questo avviene si dice che c’è inseparabilità (entanglement, aggrovigliamento), perché non c’è modo di scrivere ∣Φ⟩ come il prodotto (separato) di uno stato della particella 1 per uno della particella 2, ossia ∣Φ⟩≠∣Φ⟩1∣Φ⟩2. Nello stato non c’è modo di stabilire se il qubit 1 ha valore 0 o 1 né, analogamente, se il qubit 2 ha valore 1 o 0. Però se uno dei qubit viene misurato, l’altro immediatamente assume uno stato quantistico ben definito, di valore complementare rispetto a quello del primo. Stati inseparabili possono essere realizzati sperimentalmente, per es. con coppie di particelle di spin 1/2, oppure osservando gli stati di polarizzazione di due fotoni.

Storicamente, già immediatamente dopo la scoperta della meccanica quantistica, gli scienziati si accorsero che essa contiene numerose proprietà che sono contrarie alla normale intuizione, e alcuni (fra cui Albert Einstein, in un famoso dialogo con Niels Bohr) tentarono di dedurre da questo che la teoria fosse inconsistente e incompleta. La descrizione sopra riportata altro non è che una riscrittura in linguaggio moderno di quanto contenuto in un seminale lavoro di Einstein con Boris Podolski e Nathan Rosen (per questo gli stati entangled sono spesso indicati come stati EPR, dalle iniziali di questi tre autori) e nell’altrettanto importante replica a tale lavoro di Bohr. Successivamente, la discussione passò dal livello quasi filosofico che i due grandissimi fisici le avevano impresso a uno più fenomenologico grazie a David Bohm che, di fatto, descrisse per primo un sistema di due spin entangled, e da John Bell che, proprio studiando le correlazioni in un sistema come quello proposto da Bohm, dimostrò come queste diano risultati diversi da quanto ci si potrebbe aspettare nella fisica classica, in quanto le proprietà misurate sono presenti nel sistema indipendentemente dall’operazione di osservazione.

La macchina di Turing classica

Nel tentare di dare una risposta alla sfida di Hilbert di trovare un algoritmo capace di risolvere tutti i problemi, Turing provò a dare una definizione rigorosa di quanto intendiamo con algoritmo. Egli, nel suo sforzo di razionalizzazione, definì la macchina virtuale che oggi porta il suo nome e che è il più importante modello di computazione. Una macchina di Turing consiste di quattro elementi fondamentali: un nastro, cioè una memoria discreta, suddivisa in caselle che possono contenere gli elementi di cui la computazione si serve (per es., tipicamente, 0 e 1, gli elementi binari che stanno alla base dell’algebra booleana usata nei computer classici, ed eventualmente nulla); una testa, capace di leggere, scrivere e cancellare il contenuto delle caselle del nastro, che funge anche da puntatore per indicare su quale casella tale operazione venga correntemente eseguita; un sistema di controllo a numero di stati finito, che è una sorta di processore che contiene l’informazione relativa allo stato interno della testa (che cosa essa ha letto o quali operazioni abbia compiuto in precedenza) e del nastro e, sulla base di questa, coordina le operazioni che la testa deve compiere; un programma, cioè una sequenza di passi operativi che la testa deve compiere per passare dall’input, che contiene i dati di ingresso dell’algoritmo, all’output, che ne contiene il risultato. Questi passi sono esprimibili con un numero limitato di istruzioni elementari. È tale la potenza di questo schema concettuale che oggi si considerano computabili con un algoritmo tutte le funzioni nella classe di quelle computabili con una macchina di Turing. Esiste altresì una macchina di Turing universale, capace di realizzare il funzionamento di qualsiasi macchina di Turing specificata.

La macchina di Turing quantistica

Fu Deutsch a comprendere per primo che lo schema concettuale della macchina di Turing poteva essere realizzato in modo molto simile in una macchina consistente con i principi della fisica quantistica anziché di quella classica (Deutsch stesso dimostrò che la macchina di Turing consueta utilizza la fisica classica). La differenza sostanziale fra le due è che laddove la prima fa riferimento ai bit, la seconda si serve di qubit. Inoltre, nel caso quantistico, le operazioni che il programma implementa devono essere realizzate da operatori unitari quando la macchina esegue un algoritmo, mentre, nelle fasi di lettura, si identificano con il processo – tipicamente quantistico – del collasso della funzione d’onda, diventando dunque irreversibili. Ciò che caratterizza, in maniera assolutamente innovativa, una macchina di Turing quantistica (computer quantistico) rispetto a una classica è che, in virtù del principio di sovrapposizione degli stati, essa ha l’intrinseca capacità di un parallelismo massiccio, mentre, nel caso classico, le operazioni sono di tipo seriale e diventano parallele soltanto a costo d’introdurre una forte ridondanza negli elementi costitutivi e una complicazione non indifferente nelle tecniche di programmazione.

Porte e circuiti

L’esigenza di avere, nel caso quantistico, computer capaci di eseguire tutte le operazioni di una macchina di Turing classica, ha portato a introdurre, anche nella computazione quantistica, il concetto di circuito e di porte elementari. Mentre queste ultime, che altro non sono a livello classico che gli strumenti per riformulare gli algoritmi nel linguaggio proprio della logica booleana, si ritrovano essenzialmente identiche nel caso quantistico, la realizzazione quantistica del modello a circuito apre prospettive, ma anche problematiche, diverse. Fra queste, occorre ricordare che c’è un’operazione addizionale, che non esiste classicamente, che corrisponde a variare la fase relativa fra le componenti dello stato di input (questo è dovuto al fatto che la funzione d’onda che descrive uno stato quantistico è un numero complesso, caratterizzato da un modulo e da una fase). A tale operazione corrisponde una porta logica che non ha analogo classico. Inoltre, mentre per un circuito classico le connessioni che portano l’output di una generica porta logica all’input di un’altra si possono correttamente pensare come realizzate da un semplice filo (conduttore), nel caso quantistico tale filo dev’essere rimpiazzato da un complesso dispositivo che realizzi il teletrasporto dello stato.

L’automa quantistico

La teoria degli automi e dei linguaggi formali si occupa della descrizione delle proprietà di sequenze di simboli. Attivare un processo in un dato linguaggio equivale ad azionare una macchina da calcolo. Mentre, come si è già visto, il modello universale per un computer è la macchina di Turing, che è in grado di accettare tutti i linguaggi numerabili in forma ricorrente, per una teoria formale della computazione quantistica, benché le sue strutture siano uguali a quelle classiche, è spesso conveniente fare ricorso al concetto – equivalente – di automa quantistico a numero di stati finito. Da un punto di vista generale, quest’ultimo è ottenuto a partire dalla sua controparte classica probabilistica cambiando la nozione di probabilità di transizione con quella di ampiezza quantistica di transizione e sviluppando tutti i passi del processo mediante operatori rappresentati nello spazio di Hilbert degli stati da matrici unitarie. Gli automi quantistici hanno un insieme finito di stati, un alfabeto di input finito e una funzione di transizione che specifica le modalità con cui lo stato dell’automa evolve a ogni passo in cui la sua configurazione viene aggiornata. Per determinare lo stato dell’automa a un certo istante, occorre effettuare misurazioni che, tuttavia, proiettano in maniera irreversibile l’automa su uno dei possibili stati dell’insieme che lo caratterizza. La configurazione di un automa quantistico è, in generale, la sovrapposizione quantistica di stati nello spazio di Hilbert in cui esso vive, mentre la funzione di transizione è rappresentata da un’assegnata matrice unitaria in corrispondenza di ogni simbolo che l’automa può leggere.

Algoritmi quantistici

Lo studio di algoritmi quantistici, sino a oggi, è stato sostanzialmente improntato alla ricerca di metodi di calcolo capaci di risolvere, in tempo polinomiale, problemi che non hanno soluzione polinomiale nel contesto classico. Questo perché la struttura della meccanica quantistica, come si è visto e discusso, mette naturalmente a disposizione di chi costruisce l’algoritmo due ingredienti che non hanno una controparte classica, dai quali può venire un’accelerazione esponenziale della velocità del calcolo, rispetto appunto al caso classico. Il primo è il principio di sovrapposizione che consente a una macchina quantistica di esplorare, in una singola istanza, l’intero spazio delle possibili soluzioni e la dota così di un intrinseco parallelismo, di grandissima efficienza. Il secondo è la non separabilità di certi stati con più particelle, che permette al computer quantistico azioni a distanza che anch’esse non hanno analogo classico e a loro volta contribuiscono ad accelerare il processo di calcolo mettendo in relazione gradi di libertà computazionali altrimenti (classicamente) non correlati. Di seguito verranno concisamente presi in considerazione alcuni fra gli algoritmi quantistici proposti dalla nascita della teoria dell’informazione e computazione quantistiche; quelli che hanno avuto più successo e hanno contribuito a convincere gli scienziati dell’importanza – che va ben al di là del mero interesse concettuale, pur grandissimo – di questa nuova disciplina.

L’algoritmo di Deutsch. L’algoritmo di Deutsch è importante non soltanto in sé, ma perché esso è stato il primo esempio esplicito di un compito computazionale che poteva essere portato a termine in tempi esponenzialmente più brevi usando mezzi di calcolo quantistici che non i corrispondenti classici. Esso, nella formulazione più semplice, limitata a un singolo qubit (B) di input, consiste in quanto segue. Si consideri una funzione f: B→B; essa può dare luogo a quattro diversi risultati: f(0)=0 e f(1)=0; f(0)=1 e f(1)=1; f(0)=0 e f(1)=1; f(0)=1 e f(1)=0. Nei primi due casi, si dice che la funzione è costante, nei rimanenti due che è bilanciata. Si supponga anche di avere a disposizione un oracolo che computa uno di questi risultati. Il problema è di determinare se la funzione calcolata dall’oracolo è costante o bilanciata. Classicamente, si deve interrogare l’oracolo due volte per dare risposta a questa domanda, perché con un solo valore della funzione non siamo in grado di decidere come essa sia. Quantisticamente, preparato il sistema fisico all’ingresso nello stato ∣0⟩∣0⟩ e ponendo l’output – prima della misura – nello stato 2⁻1^/2(∣0⟩−∣1⟩), il computer quantistico opera applicando un algoritmo che consiste dell’operazione NOT seguita dall’operazione unitaria detta trasformata di Hadamard, ossia una trasformata di Fourier nello spazio di Hilbert di dimensione 2 del singolo qubit, che trasforma lo stato 2⁻1^/2(∣0⟩−∣1⟩) in ∣1⟩ e lo stato, ortogonale a quest’ultimo, 2⁻1^/2(∣0⟩+∣1⟩) in ∣0⟩. Si può vedere che una singola misura dello stato in cui si dispone l’output fornisce la risposta con un solo passo dell’oracolo. Il guadagno esponenziale si ha, naturalmente, quando si generalizza al caso f: Bⁿ→B, in cui la funzione f dà risultato 0 o 1 con un input costituito da una stringa di n bit. Classicamente, si deve interrogare l’oracolo 2ⁿ−1+1 volte; quantisticamente, si devono effettuare n operazioni interrogando l’oracolo una volta sola.

L’algoritmo di Shor. Il problema è scomporre un numero intero N nei suoi fattori primi. Scegliamo un numero q∈N, 1<q<N, coprimo con N: è un risultato classico della teoria dei numeri che se r è il periodo della funzione f:x↦q^x(modN) e soddisfa alle condizioni di essere pari e che q⁽1^/2^)r ≢ ± 1(modN), allora ciascuno dei due numeri q⁽1^/2^)r ± 1 ha almeno un divisore primo in comune con N.

N richiede n=log2N bit di memoria binaria per essere dato come input a un computer: considerando q come un parametro random, poiché la probabilità di trovare una coppia q e r con le proprietà richieste è ≥1−2^−p+1, essendo p il numero di fattori primi di N, si avrà un q ‘buono’ con probabilità arbitrariamente prossima a 1 con un numero di tentativi che per p=2 è 2(n). Poiché, inoltre, trovare il massimo comune divisore fra due numeri (per es., con l’algoritmo di Euclide) non richiede che risorse di tempo polinomiali, si individueranno i fattori primi di N in modo efficiente se si riuscirà a determinare r in tempo polinomiale. A tutt’oggi, non è stato individuato alcun algoritmo di fattorizzazione classico di un numero intero N la cui complessità sia migliore di exp[n1^/3(log2n)2^/3] con n=log2N, vale a dire che non appartenga essenzialmente alla classe di complessità NP. Per questa ragione, il sistema crittografico a chiave pubblica RSA (dalle iniziali di Ronald Rivest, Adi Shamir e Leonard Adleman, che per primi la descrissero), il più diffuso fra i sistemi di codifica e decodifica crittografica, ritenuto praticamente inviolabile, si basa sulla fattorizzazione di un numero intero molto grande, prodotto di due numeri primi a loro volta molto grandi.

Nel 1994, il matematico statunitense Peter Shor ha costruito un algoritmo quantistico per il problema della fattorizzazione la cui complessità è n1^/4, cioè appartiene alla classe di complessità QP. Per l’algoritmo occorre un registro di memoria la cui dimensione M (in bit m, M=2^m) sia dell’ordine del doppio di quella di N, ossia N2<M<2N2. La costruzione dell’algoritmo richiede uno spazio degli stati con la struttura di prodotto (tensore) di due spazi fattore, ciascuno dei quali in grado di contenere stati-registro ∣x⟩, 0≤x≤M−1. Il primo dei due registri sarà quello di lavoro, l’altro servirà per operazioni transitorie e il suo contenuto verrà via via reversibilmente cancellato ogni qualvolta esso sarà stato utilizzato. Ciò premesso, lo schema di Shor di calcolo quantistico di r consiste nel ripetere – se necessario più volte – una sequenza di operazioni costituite di quattro passi strettamente quantistici, seguiti da due passi classici.

Partendo dallo stato iniziale ∣0⟩∣0⟩, si costruisce innanzi tutto lo stato ∣Ψ1⟩ che, nel primo registro, contiene la sovrapposizione uniforme degli M stati numero ∣x⟩, 0≤x≤M−1 e lascia il secondo registro nello stato ∣0⟩. È interessante osservare che lo spazio degli stati del primo registro si può altresì pensare esso stesso come uno spazio prodotto di m spazi di Hilbert uguali, ognuno di dimensione 2, ciascuno capace di ospitare un qubit, cosicché, facendo ricorso all’espressione di x in base 2, vale a dire x=Ʃ^m−1_k=0a_k2^k, con a_k∈{0,1}, si può scrivere ∣x⟩=∣a_m−1⟩...∣a0⟩, dove ∣a_k⟩ rappresenta un qubit (cioè uno stato ∣0⟩o∣1⟩). Si effettua poi il calcolo di f(x)=qx (modN) sulle x etichette del primo registro e si usa il risultato come etichette del secondo registro, dando luogo a uno stato ∣Ψ2⟩ (nello spazio completo degli stati) che è la sovrapposizione uniforme di stati della forma ∣x⟩∣f(x)⟩. Il calcolo di una qualsiasi funzione ricorsiva booleana che, come f(x), si possa ricondurre a una permutazione, è sempre equivalente a una sequenza (la cui lunghezza ne misura la complessità) di un numero finito di operazioni elementari. Dunque, grazie all’intrinseco parallelismo quantistico, per ottenere ∣Ψ2⟩ basta un’unica operazione dell’operatore unitario U_f tale che U_f∣x⟩∣0⟩=∣x⟩∣f(x)⟩. U_f sarà espresso come prodotto di operatori semplici. Pur essendo la computabilità di una generica permutazione tipicamente esponenziale, in questo caso la lunghezza, cioè il numero di operazioni unitarie elementari di cui U_f è il prodotto, è polinomiale (quadratico) in m.

Si effettua la trasformata di Fourier (quantistica) sul primo registro. Si genera dunque lo stato entangled ∣Ψ3⟩, sovrapposizione di stati ∣y⟩∣q^x (modN)⟩ pesati con le fasi di Fourier exp(i2πxy/M).

L’ultimo passo quantistico consiste nella ‘misura’ del sistema nello stato ∣Ψ3⟩, cioè della sua osservazione rispetto alla base naturale. Questo dà come risultato uno stato ∣y⟩∣q^l (modN)⟩, con una densità di probabilità P_l(y)≐Pr(∣y⟩∣q^l (modN)⟩), che – come funzione di y – grazie alla periodicità della funzione f, è uno ‘spettro’ che consiste di una sequenza di righe distanziate di r′, sottomultiplo intero di r.

I due passi successivi di una singola ‘passata’ della sequenza possono essere eseguiti con un computer classico. Dapprima occorre trovare la migliore approssimazione di y/M, la quale denomina r′, r'<N<√−−M, che fornisca un y ‘buono’, tale cioè da poter valutare r da r′. Ovviamente interesserebbe r′=r (y ‘molto buono’). Stimando la somma degli esponenziali in P_l (y) si vede che la probabilità di trovare un y buono è ≥1/(3r2) ma che ci sono molti stati ∣y⟩∣q^l (modN)⟩ con y molto buono: il loro numero si può calcolare e risulta esprimibile in termini della funzione ϕ di Eulero. Di quest’ultima sappiamo che per argomento grande ha un andamento della forma ϕ(ν)≳ν/lnν, ν≫1, e ne segue che con probabilità O(r2lnr), cioè facendo un numero al più polinomiale di tentativi, si può individuare un r′ coincidente con r.

Si prova infine r′ nel suo ruolo, vale a dire: se r′ è pari, si calcola il massimo comune denominatore fra q⁽1^/2^)r'±1 e N. Se invece r′ è dispari, oppure r′ è pari ma non si è trovato un divisore proprio di N, si ripete la procedura con lo stesso valore di q, un numero di volte che al massimo è O(lnlnN). In caso di mancata soluzione, si cambia q e si inizia una nuova passata.

L’algoritmo di Grover. Qui lo scenario di riferimento è una base di dati non strutturati e non organizzati, disposti in una lista di N ingressi, uno solo dei quali soddisfa una proprietà specificata. Si vuole trovare l’elemento della lista che ha quella proprietà. Qualsiasi metodo classico in grado di risolvere questo problema con una data probabilità (indipendente da N) richiede un numero di passi dell’ordine O(N). Infatti, la teoria elementare delle probabilità afferma che, se si prendono in considerazione k elementi della lista, si ha probabilità k/N di trovare quello speciale che si cerca. Questa tende a zero per N crescente e molto grande, a meno che k non sia esso stesso dell’ordine di N. L’algoritmo quantistico, proposto nel 1996 da Lov K. Grover, richiede invece un numero di passi dell’ordine O(√−−N). Questo aumento quadratico della velocità – minore di quello esponenziale degli algoritmi di Deutsch e Shor, ma pur sempre molto interessante – si basa ancora una volta sul principio di sovrapposizione, cioè sulla capacità di un sistema quantistico di esaminare molti elementi in parallelo, che genera un’amplificazione dell’ampiezza di probabilità. Recentemente, sono state sviluppate anche tecniche che combinano il metodo di Grover con la traduzione quantistica del processo noto come cammino aleatorio (random walk), sostituendo alle probabilità classiche le ampiezze di probabilità proprie della meccanica quantistica per risolvere problemi affini, ma di portata più ampia, quale quello di decidere se due elementi in una base di dati sono distinti o no. È stato altresì provato rigorosamente che nessun processo quantistico può migliorare la velocità di un processo di ricerca in un insieme non strutturato oltre l’accelerazione quadratica dell’algoritmo di Grover.

Il ricorso a metodi topologici e, in particolare, alla teoria topologica quantistica dei campi, anziché alla ordinaria meccanica quantistica, recentemente, ha aperto la strada a nuove forme di algoritmi quantistici, che fanno sperare di poter affrontare in modo efficiente (in tempo polinomiale) problemi ardui.

Bibliografia

J.S. Bell, Speakable and unspeakable in quantum mechanics, Cambridge-New York 1987 (trad. it. Milano 2010).

A. Peres, Quantum theory. Concepts and methods, Dordrecht-London 1993.

D. Deutsch, The fabric of reality, London-New York 1997 (trad. it. La trama della realtà, Torino 1997).

J. Gruska, Quantum computing, London 1999.

N.D. Mermin, Quantum computer science. An introduction, Cambridge-New York 2007.