Relazioni tra codici correttori classici e codici correttori quantistici

(1)

Introduzione

Per decenni l'aumento della potenza dei computer è andata di pari passo con la miniaturizzazione dei circuiti elettronici. Tale minia-turizzazione, però, non può procedere all'innito e, in eetti, si è fermata alle soglie del mondo microscopico, governato dalle leggi della meccanica quantistica. Nascono così dei nuovi dispositivi elet-tronici, con una potenza di calcolo nettamente superiore a quella dei computer convenzionali: i computer quantistici .

La prima idea sulla possibilità di costruire dei computer utilizzando il comportamento delle particelle elementari va attribuita a Murray Gell-Mann, premio Nobel per la sica nel 1969, che nel 1982 aveva intravisto come, sfruttando quelle proprietà delle particelle elemen-tari, si sarebbe potuto disporre di un formidabile nuovo elemento base per un nuovo tipo di informatica. Da allora lo studio per lo sviluppo di tali calcolatori ha fatto passi da gigante.

Il principio di sovrapposizione della meccanica quantistica fornisce al computer quantistico un enorme vantaggio, che consiste nella possi-bilità di elaborare una quantità notevole di dati contemporaneamen-te. Esso è cioè dotato di un intrinseco parallelismo. Naturalmente questo richiede un appropriato software quantistico, vale a dire lo sviluppo di algoritmi basati sulla logica quantistica.

Un'altra risorsa fondamentale della meccanica quantistica, assente in meccanica classica, è il cosiddetto entanglement: se due diversi sistemi quantistici entrano anche solo temporaneamente in contatto tra loro, non possono più essere considerati come oggetti separati. Anche se in seguito si allontanano essi devono essere considerati come una sola entità. Queste proprietà rendono possibile, in linea di principio, una potenza di calcolo straordinaria, non confrontabile con quella dei calcolatori classici.

(4)

quelli classici, in quanto la loro particolarissima struttura li rende adatti a superare velocemente alcune speciche situazioni complesse, mentre in altri casi, come il semplice calcolo matematico, il compu-ter attuale rescompu-terà a lungo il più adatto. Detto questo, gli scenari in cui il computer quantistico può rappresentare una vera svolta sono diversi. In primo la sicurezza: un computer quantistico pienamente eciente potrebbe sbriciolare in pochi istanti i sistemi di encryption attuali (il che giustica l'interesse del governo USA a seguirne l'e-voluzione con la massima attenzione) e allo stesso tempo, potrebbe essere utilizzato per realizzati nuovi sistemi di codica praticamen-te inviolabili. Inoltre, i compupraticamen-ter quantistici potrebbero risolvere alcuni dei più famosi problemi matematici nora senza risposta e soprattutto potrebbero dare un nuovo impulso all'analisi di grandi quantità di dati.

Al posto del convenzionale bit, unità dell'informazione binaria, in un computer quantistico l'unità dell'informazione è il quantum bit, o in breve qubit.

Un qubit è rappresentato da un vettore in C2_{. Così come il bit}

classico ammette due stati, 0 e 1, altrettanto accade per i qubit, che ammette gli stati |0i e |1i.

Grazie al principio di sovrapposizione che emerge dal primo postu-lato della meccanica quantistica però, è possibile combinare linear-mente i due stati |0i e |1i ottenendo lo stato

|ψi = α |0i + β |1i , in cui α e β sono numeri complessi tali che |α|2

+ |β|2 = 1.

Detto in altri termini, lo stato di un qubit è un vettore unitario di C2, in cui gli stati speciali |0i e |1i formano una base ortonormale detta base computazionale.

Mentre il bit classico è immaginabile come una moneta che, una volta lanciata, cadrà a terra mostrando inesorabilmente una delle due facce, il qubit è immaginabile come una moneta che, una volta lanciata, cadrà a terra continuando a ruotare su sé stessa senza arrestarsi no a che qualcuno non blocchi con una mano la rotazione, e la obblighi nalmente a mostrare una delle sue facce.

(5)

dei codici.

La teoria dei codici correttori di errori nasce in risposta al problema pratico di realizzare la trasmissione di informazioni in modo che eventuali errori possano essere scoperti e corretti in fase di ricezione. Nel caso dei computer quantistici la ricezione di errori diviene ne-cessaria anche per garantire il loro funzionamento, a causa della fragilità dei qubit, il cui stato può essere corrotto anche solo da interazioni con l'ambiente circostante.

Gli argomenti trattati in questa tesi si inseriscono nell'area di ricerca del settore appena descritto.

L'obbiettivo è quello di studiare dei codici, nel nostro caso quanti-stici, che siano in grado di rilevare l'errore ed eventualmente correg-gerlo. Fortunatamente gran parte della teoria dei codici correttori classici può essere sfruttata nella costruzione dei codici corretto-ri quantistici, propcorretto-rio per questo il fulcro della tesi è lo studio delle relazioni tra i codici correttori classici e i codici correttori quantistici. L'elaborato è strutturato in cinque capitoli:

Il primo capitolo è un capitolo introduttivo, nel quale viene ana-lizzata la teoria dell'informazione quantistica, ovvero quella branca della scienza il cui scopo è quello di investigare come, ed entro qua-li qua-limiti, le leggi fondamentaqua-li della sica possano essere impiegate per migliorare la trasmissione e l'elaborazione di segnali. Verranno deniti tutti gli enti fondamentali della computazione e dell'infor-mazione quantistica: dal qubit, alle porte logiche quantistiche, dagli algoritmi ai circuiti quantistici, e si concluderà con l'esposizione dei principi della meccanica quantistica.

Nel secondo capitolo viene esposta la teoria dei codici correttori, facendo attenzione ai principali risultati della teoria classica e dando una breve introduzione dei codici correttori quantistici. Emergono, inoltre le principali dierenze e/o analogie delle tecniche di corre-zione per i due tipi di codice. Ad esempio, una delle tecniche per la correzione degli errori classici è la ridondanza, tecnica che non può essere utilizzata per la correzione degli errori quantistici, in quan-to non è possibile copiare l'informazione quantistica in seguiquan-to al

(6)

caso classico, la misura della sindrome. Attraverso la sindrome è possibile determinare se un qubit è stato danneggiato, e in caso af-fermativo quale. Inoltre il risultato di questa operazione indica non solo il qubit corrotto, ma anche in quale dei vari modi possibili è stato inuenzato.

Il terzo capitolo è incentrato sullo studio dei codici correttori quantistici. In particolare vedremo quali sono le condizioni per la correzione degli errori. La cosa interessante che emerge nel capitolo è che, anche se nel caso quantistico l'errore è arbitrario, può esse-re ricondotto a tesse-re tipi di errori, ovvero: bit ip (che scambia lo stato di un qubit) , rappresentato dalla matrice di Pauli X; phase ip (che cambia il segno alla seconda componente dello stato di un qubit), rappresentato dalla matrice di Pauli Z; bit-phase ip (dato dalla combinazione di bit ip e phase ip), rappresentato dalla ma-trice di Pauli Y = iXZ. Il capitolo si conclude con una tecnica di costruzione dei codici correttori quantistici.

Il quarto capitolo analizza un'importante classe di codici quan-tistici, noti come codici stabilizzatori. La costruzione di tali codici è analoga a quella dei codici lineari classici. Vedremo come i codici stabilizzatori possono essere costruiti e come è possibile passare da un codice lineare ad un codice quantistico stabilizzatore.

Il quinto ed ultimo capitolo espone le relazioni che intercorrono tra i codici lineari classici e i codici correttori quantistici.

Cercheremo, in particolare, di capire come, e soprattutto sotto quali ipotesi, è possibile costruire un codice quantistico a partire da un codice lineare e viceversa.

(7)

Capitolo 1

Computazione e informazione

quantistica

1.1 Introduzione

L'informazione quantistica è una branca della scienza che ab-braccia diversi campi, dalla sica alla matematica, dal calcolo all'in-gegneria. Il suo scopo è quello di investigare come ed entro quali limiti le leggi fondamentali della sica possano essere impiegate per migliorare la trasmissione e l'elaborazione di segnali.

L'informazione quantistica nasce dalla scoperta che la meccanica quantistica può essere utilizzata in modo da eseguire compiti altri-menti impossibili, quali la creazione di codici crittograci indecifra-bili, il teletrasporto di stati di raggi di luce, la soluzione di proble-mi di calcolo in maniera più rapida rispetto a qualsiasi computer classico.

Un processo di calcolo è essenzialmente un processo sico che viene eseguito su una macchina il cui funzionamento obbedisce a certe leggi siche.

La teoria classica del calcolo si basa su un modello astratto di mac-china universale (la Macmac-china di Turing Universale) che funziona se-condo un insieme di regole e di principi enunciati nel 1936 da Alan Turing ed elaborati successivamente da John von Neumann negli anni '40. Questi principi sono rimasti essenzialmente immutati da allora, nonostante gli enormi progressi tecnologici che permettono oggi di produrre dispositivi di gran lunga più potenti rispetto a quel-li che si potevano reaquel-lizzare nella prima metà del ventesimo secolo.

(8)

La tacita assunzione alla base di questi principi è che una macchi-na di Turing idealizza un dispositivo meccanico di calcolo (con umacchi-na memoria potenzialmente innita) che obbedisce alle leggi della sica classica.

La computazione quantistica nasce come un paradigma alter-nativo, basato sui principi della meccanica quantistica. Questi sono gli unici in grado di giusticare i fenomeni sici che avvengono a livello microscopico, come per esempio all'interno di un atomo. La prima idea di computer quantistico la espose R. Feynman1 _nel

1982, quando dimostrò che nessuna Macchina di Turing classica po-teva simulare certi fenomeni sici senza incorrere in un rallentamen-to esponenziale delle sue prestazioni. Al contrario, un simularallentamen-tore quantistico universale avrebbe potuto eettuare la simulazione in maniera più eciente.

Nel 1985 D. Deutsch, pubblicò un articolo, intitolato Quantum theo-ry, the Church-Turing principle and the universal quantum compu-ter, in cui formalizzò queste idee nella sua Macchina di Turing Quantistica Universale, portando alla concezione moderna di com-putazione quantistica. Basandosi sulla tesi di Church-Turing, David Deutsch si spinse inoltre ad avanzare il principio secondo cui cia-scun sistema sico nitamente realizzabile può essere perfettamen-te simulato da un modello universale di macchina computazionale operante con risorse nite.

Naturalmente gli eetti dell'introduzione del nuovo modello di calco-lo si sono fatti sentire anche nel campo della complessità di calcocalco-lo, provocando il cambiamento della nozione di trattabilità. Infatti, nel 1994 P. Shor dimostra che il problema della fattorizzazione dei numeri primi (classicamente considerato intrattabile) si può risolvere ecientemente2 _{con un algoritmo quantistico.}

Queste considerazioni unite a quelle di tipo tecnologico, hanno por-tato all'aermarsi di un campo di ricerca oggi noto come teoria dell'informazione e della computazione quantistica.

1_{sico statunitense, Premio Nobel per la sica nel 1965.} 2_{cioè in tempo polinomiale}

(9)

1.2 La potenza della computazione quantistica

La teoria della complessità computazionale si occupa della classicazione della dicoltà di vari problemi di calcolo, sia classici che quantistici, al ne di capire la potenza dei computer quantistici. L'idea di base è quella di denire una classe di complessità.

Una classe di complessità può essere pensata come un insieme di problemi computazionali che hanno alcune caratteristiche comuni sulle risorse di calcolo necessarie per risolvere tali problemi.

Una distinzione informale, ma di grande rilievo, è quella posta tra i cosiddetti problemi facili, di cui si conoscono algoritmi di risoluzione ecienti, e dicili, di cui gli unici algoritmi noti non sono ecienti. La maggior parte della crittograa moderna si fonda sull'esisten-za di problemi ritenuti dicili; ciò pone un'enorme rilevansull'esisten-za allo studio di tali problemi, poiché, qualora si dimostrasse l'esistenza di un algoritmo eciente per un problema ritenuto dicile, i sistemi crittograci basati su di esso non sarebbero più sicuri.

Le due più importanti classi di complessità sono P e NP .

P è la classe di problemi computazionali che possono essere risolti rapidamente su un computer classico, mentre NP è la classe dei pro-blemi che hanno soluzioni che possono essere vericate velocemente su un computer classico.

Per capire la dierenza tra P e NP , prendiamo in considerazione il problema della fattorizzazione in primi di un numero intero, n. Per quanto sappiamo non c'è un metodo veloce per risolvere tale problema in un computer classico. D'altra parte, se sappiamo che un certo numero primo p è un fattore di n, allora possiamo con-trollare rapidamente che ciò è vero dividendo n per p. Quindi la fattorizzazione è un problema in NP .

È chiaro che P ⊆ NP , poiché la capacità di risolvere un problema implica la capacità di vericare le possibili soluzioni. Ciò che non è così chiaro, invece, è se vale l'altro contenimento, e quindi non possiamo stabilire se queste due classi di complessità siano diverse3_.

Non possiamo neppure stabilire, purtroppo, se i computer quantisti-ci possono essere utilizzati per risolvere rapidamente tutti i problemi in NP .

3_{questo è uno dei grandi problemi ancora aperti nell'informatica teorica, tanto da meritarsi}

(10)

P e NP sono solo due di una moltitudine di classi di complessità che possono essere denite.

Un'altra importante classe di complessità è P SP ACE.

La classe P SP ACE include quei problemi che possono essere risolti da un algoritmo che utilizzi uno spazio di memoria la cui dimensione sia al più funzione polinomiale della dimensione dell'input (quindi basso spazio in memoria, ma non necessariamente in tempo). La classe P SP ACE è ritenuta strettamente maggiore sia della classe P che della classe NP , anche se non è mai stato dimostrato.

Inne, abbiamo la classe di complessità BP P .

BP P è una classe di complessità a cui appartengono quei problemi decisionali che richiedono un tempo polinomiale per avere una solu-zione probabilistica corretta. Più precisamente, essi sono risolvibili in tempo polinomiale da una macchina di Turing probabilistica, con una probabilità di errore al massimo di 1

3 per tutte le istanze.

BP P è una delle più grandi classi "pratiche" di problemi, vale a dire che la maggior parte dei problemi di interesse in BP P hanno algoritmi probabilistici ecienti che possono essere eseguiti su mac-chine moderne reali. Per questa ragione è di grande interesse pratico stabilire quali problemi e quali classi di problemi stanno all'interno di BP P .

Sappiamo con sicurezza che BP P contiene anche P , (classe dei pro-blemi risolvibili in tempo polinomiale con una macchina determi-nistica) dal momento che una macchina deterministica è un caso speciale di una macchina probabilistica.

Nella denizione della classe BP P , se sostituiamo la macchina di Turing comune con un computer quantistico, otteniamo la classe BQP. Quest'ultima è la classe di complessità a cui appartengono quei problemi che richiedono un tempo polinomiale da parte di un computer quantistico per avere una soluzione corretta con probabi-lità maggiore o uguale a 2

3 e quindi, corrispondentemente, con una

probabilità di errore minore o uguale a 1 3.

Quello che si sa è che i computer quantistici possono risolvere non solo tutti i problemi in P ecientemente, ma anche problemi esterni, contenuti nella classe P SP ACE. Pertanto, BQP si colloca tra P e P SP ACE, come illustrato in gura

(11)

Figura 1.1: Rapporto tra le varie classi di compessità.

1.3 Quantum Bit

Nella computazione classica l'unità di base dell'informazione è il bit, che può assumere ad ogni istante i soli valori 0 o 1.

L'analogo del bit nella computazione quantistica è il quantum bit, o in breve qubit.

Esempi sono lo spin dell'elettrone, lo stato di polarizzazione di un fotone, oppure lo stato base ed eccitato di un atomo.

Ogni qubit è rappresentato da un vettore di uno spazio di Hil-bert H, 2-dimensionale isomorfo a C2_. _{I vettori |0i e |1i formano}

una base ortonormale per questo spazio vettoriale, nota come base computazionale standard.

Usando la notazione classica dell'algebra lineare, possiamo scrivere |0i = 1 0 e |1i = 0 1 .

Gli stati |0i e |1i di un qubit si possono vedere come i corrispondenti degli stati 0 e 1 di un bit classico.

La dierenza tra bit e qubit sta nel fatto che un qubit si può trovare anche in altri stati diversi da |0i e |1i.

Infatti, un possibile stato di un qubit, viene rappresentato da un combinazione lineare

(12)

|ψi = α |0i + β |1i , (1.1) dove α e β sono numeri complessi tali che |α|2

+ |β|2 = 1. In notazione algebrica, il vettore |ψi corrisponde a

|ψi = α 1 0 + β 0 1 = α β .

Tali stati sono spesso chiamati sovrapposizioni.

Un sistema composto da n-qubit è rappresentato da un vettore dello spazio di Hilbert

H ⊗ · · · ⊗ H = H⊗n= h{|in . . . i1i : ij ∈ [0, 1] ∀j = 1, . . . , n}i .

Ogni elemento di questo spazio può essere identicato con un numero intero tra 0 e 2n_{− 1,}_{e può essere scritto come}

2n₋₁

X

k=0

ck|ki

con la condizione che Pn k=0|ck|

2

= 1.

Un qubit si può trovare in un numero di stati che è innitamente maggiore di quello dei possibili stati di un bit classico.

Infatti, a dierenza di quanto accade per un bit classico, che può assumere solo ed esclusivamente gli stati 0 e 1, per un qubit non possiamo determinare con precisione il suo stato quantistico, cioè i valori di α e β.

La meccanica quantistica ci dice che quando misuriamo un qubit possiamo solo ottenere lo stato |0i con una probabilità |α|2 _{o lo}

stato |1i con una probabilità |β|2_.

Per questo motivo i valori α e β sono chiamati ampiezze di pro-babilità e la somma |α|2

(13)

Esempio:

Un qubit si può trovare nello stato |ψi = √1

2|0i + 1 √

2|1i , no al momento in cui viene osservato.

Nel momento in cui lo misuriamo il risultato sarà 0 con probabilità

1

2 o 1 con probabilità 1 2.

@

Un qubit può essere espresso anche in una base diversa dalla base computazionale standard, in quanto una qualsiasi base di C2 _può

essere vista come una base computazionale.

Ad esempio possiamo considerare la base formata da |+i = √1

2(|0i + |1i) e |−i =

1 √

2(|0i − |1i) .

Un qubit arbitrario |ψi = α |0i + β |1i, può essere espresso nella nuova base come

|ψi = α |0i + β |1i = √α

2(|+i + |−i) + β √ 2(|+i − |−i) = = α + β√ 2 |+i + α − β √ 2 |−i .

Sistemi classici di n-bit e quantistici di n-qubit dieriscono per il numero di elementi di base necessari a rappresentarli.

Mentre per il sistema classico la dimensione dello spazio, prodotto cartesiano degli spazi bidimensionali che rappresentano ogni bit, è n su Z_/_2Z, il sistema quantistico ha dimensione 2n, ed è datò dal

prodotto tensore degli spazi bidimensionali che rappresentano ogni qubit.

(14)

La crescita esponenziale del caso quantistico paragonata a quella li-neare del caso classico ci fa comprendere come la simulazione di siste-mi quantistici complessi non possa essere eettuata ecientemente con gli attuali calcolatori.

La crescita esponenziale degli elementi di base con il numero di qubit è uno dei due punti di forza della computazione quantistica, mentre l'altro risiede nel parallelismo quantistico.

Un sistema composto da N qubit può essere preparato in una so-vrapposizione di stati; se consideriamo una soso-vrapposizione di tutti i 2N elementi di base, un operatore lineare che agisce su tale stato per-mette di eseguire in un solo passaggio l'operazione di elaborazione su tutti i possibili valori rappresentabili con n-bit.

Sperimentalmente il parallelismo quantistico introduce due dicoltà legate alla misura del sistema:

la lettura di un sistema quantistico in sovrapposizione di stati

fa collassare lo stato al valore misurato. Si aggira il problema preparando lo stato iniziale del sistema e lasciandolo evolvere liberamente sotto gli opportuni operatori computazionali, senza mai misurarlo dall'esterno;

una volta conclusa il calcolo il sistema deve essere letto per

estrarre l'informazione necessaria. Il risultato restituito dalla lettura è di tipo probabilistico, quindi la misura deve essere ripetuta molte volte per ottenere un valore corretto. Questo problema può annullare i potenziali vantaggi della computa-zione quantistica, rendendo il tempo di lettura del risultato maggiore del guadagno dovuto al minor tempo computaziona-le. Il problema viene risolto attraverso gli algoritmi quantistici di elaborazione che cercano di far si che il risultato voluto abbia un'alta probabilità di essere misurato una volta conclusa la calcolo.

(15)

1.3.1 Interpretazione geometrica di un qubit

Un modo utile per visualizzare un qubit è mediante un'interpre-tazione geometrica che associa gli stati di un qubit ai punti sulla supercie di una sfera di raggio unitario.

Abbiamo visto che nella sua forma più generale un qubit viene scritto |ψi = α |0i + β |1i ,

con α e β numeri complessi tali che |α|2

+ |β|2 = 1.

Poichè ogni numero complesso può essere scritto in modo esponen-ziale attraverso la formula di Eulero, poniamo

(

α = ραeiφα

β = ρβeiφβ

dove ρα (risp. ρβ) è la norma di α (risp. β), e φα (risp. φβ) è

l'angolo formato nel piano complesso tra l'asse dei reali ed ρα (risp.

ρβ), come in gura

(16)

Figura 1.3: denizione dell'angolo γ

Quindi

|ψi = ραeiφα|0i + ρβeiφβ|1i ,

dove continua a valere che

ρ2_α+ ρ2_β = 1,

quest'ultima è l'equazione che descrive un cerchio unitario in R2_,

quindi le componenti ρα e ρβ possono essere scritte in termini di un

angolo γ (Figura 1.3) come (

ρα= cos γ

ρβ = sin γ

,

con γ ∈ [0,π_/₂_], poichè ρ

α e ρβ possono essere solo positivi. Ponendo

ϑ = 2γ l'equazione generale per il qubit diventa

|ψi = cosϑ 2e

iφα_{|0i + sin}ϑ

2e

(17)

= eiφα cosϑ 2|0i + sin ϑ 2e iϕ_|1i ,

dove è stato denito l'angolo ϕ = φβ− φα.

Il fattore eiφα può essere ignorato in quanto introduce sul qubit una

fase non osservabile, e quindi |ψi = cosϑ 2|0i + sin ϑ 2e iϕ_{|1i ,} con ϑ ∈ [0, π] e ϕ ∈ [0, 2π).

Questa equazione identica sulla sfera unitaria R3 un punto di

coor-dinate sferiche ϑ e ϕ. Questo tipo di rappresentazione del qubit è nota come rappresentazione sulla sfera di Bloch.

(18)

1.3.2 Interpretazione sica di un qubit

Un qualsiasi sistema sico, con almeno due livelli di energia di-screti e sucientemente separati è un candidato appropriato per rappresentare un qubit.

Per realizzare sicamente un qubit i tre approcci più comuni sono quelli basati su:

le due diverse polarizzazione di un fotone;

l'allineamento di uno spin nucleare in un campo magnetico uniforme;

due livelli di energia4 _{di un elettrone che orbita in un singolo}

atomo.

Ad esempio, possiamo considerare il sistema costituito dall'atomo di idrogeno H.

In questo sistema, lo stato |0i del qubit può essere rappresentato dal primo livello di energia (n = 0), corrispondente allo stato base dell'elettrone, e lo stato |1i dal secondo livello di energia (n = 1) corrispondente allo stato eccitato dell'elettrone, come in gura

Figura 1.5: Qubit rappresentato da un elettrone in un atomo di idrogeno

Il passaggio dell'elettrone da uno stato all'altro può essere realiz-zato sottoponendo l'elettrone ad un impulso laser di appropriata intensità, durata e lunghezza d'onda.

4_{In un atomo i livelli di energia dei vari elettroni sono discreti. Due di essi possono essere}

selezionati per rappresentare i valori logici 0 e 1. Questi livelli corrispondono a specici stati di eccitazione degli elettroni nell'atomo.

(19)

Riducendo opportunamente la durata, si può realizzare il passaggio di un elettrone inizialmente nello stato |0i ad uno stato che si trova a metà tra |0i e |1i, corrispondente allo stato

|ψi = √1 2|0i +

1 √

2|1i .

Come abbiamo già visto, quando osserviamo un qubit, il risultato può solo essere 0 oppure 1. Inoltre, la misurazione che abbiamo fatto cambia lo stato del qubit facendolo collassare dalla sua sovrapposi-zione di |0i e |1i allo stato specico consistente con il risultato della misurazione.

Queste proprietà si spiegano mediante i principi della meccanica quantistica.

1.4 Qubit multipli

Con due bit classici possiamo formare quattro possibili stati: 00, 01, 10, 11. In generale, con n bit è possibile costruire 2n stati distinti.

Quanti stati si possono ottenere con n qubit?

Lo spazio degli stati generato da un sistema di n qubit ha dimensione 2n su C. Questa crescita esponenziale nel numero dei qubit delle dimensioni dello spazio degli stati suggerisce la potenziale capacità di un computer quantistico di elaborare informazioni ad una velocità esponenzialmente superiore a quella di un computer classico. Formalmente un registro quantistico di n qubit è un elemento dello spazio di Hilbert 2n-dimensionale, C2n

, con base computazionale formata da

|i1i ⊗ · · · ⊗ |ini ,

con ij ∈ {0, 1} , 1 ≤ j ≤ n.

Per convenienza, questo vettore della base si scrive |i1i |i2i · · · |ini

oppure semplicemente |i1i2· · · ini .

Consideriamo il caso di due qubit. In analogia con il singolo qubit, possiamo costruire la base computazionale dello spazio degli stati come formata dai vettori |00i , |01i , |10i , |11i .

(20)

In notazione algebrica questi vettori corrispondono quindi a     1 0 0 0     ,     0 1 0 0     ,     0 0 1 0     ,     0 0 0 1     .

Una coppia di qubit può anche essere una sovrapposizioni di questi quattro stati. Il vettore di stato che descrive i due qubit, in questo caso, è

|ψi = α00|00i + α01|01i + α10|10i + α11|11i ,

con la condizione di normalizzazione X

k∈{0,1}2

|αk| 2

= 1.

Analogamente al caso di un singolo qubit, il risultato di una misu-razione sarà uno degli stati k ∈ {0, 1}2 _{con probabilità |α}

k|2.

In un sistema di n qubit possiamo anche misurare solo un suo sottoinsieme.

Per esempio, nel caso di due qubit possiamo misurare il primo qubit ottenendo come risultato 0 con probabilità |α00|

2

+ |α01| 2_.

Dopo aver eettuato la misurazione lo stato collasserà a α00|00i + α01|01i

q

|α00|2+ |α01|2

.

Ogni vettore normalizzato in questo spazio rappresenta un possibile stato computazionale, che chiameremo registro quantistico a n qubit.

(21)

1.4.1 Stati entangled

Una proprietà importante dei registri quantistici a n qubit è che non è sempre possibile decomporli.

Gli stati di questo tipo sono detti entangled e godono di proprietà che non si possono ritrovare in nessun oggetto della sica classica. Gli elementi di una collezione entangled non hanno un proprio sta-to individuale, solo l'intero insieme corrisponde a uno stasta-to ben denito.

Gli stati entangled si comportano come se fossero strettamente con-nessi l'uno all'altro indipendentemente dalla distanza che li separa. Ad esempio, una misurazione di uno dei due stati di una coppia entangled fornisce simultaneamente informazioni riguardo all'altro. Questa proprietà è alla base di soluzioni di problemi in information-processing che non possono essere riprodotte classicamente.

Un esempio a riguardo è la realizzazione di circuiti quantistici per il teletrasporto di uno stato quantistico da una locazione all'altra. Esempio:

Vediamo un esempio di entangled.

Lo stato |00i + |11i non può essere fattorizzato nel prodotto tensore di due qubit indipendenti, cioè non esistono α1, α2, β1, β2 tali che

|00i + |11i = (α1|0i + β1|1i) ⊗ (α2|0i + β2|1i) .

(22)

1.5 Matrici di Pauli

In meccanica quantistica, le matrici di Pauli sono un insieme di matrici quadrate 2 × 2 complesse hermitiane5 _{unitarie, usualmente}

indicate dalla lettera greca σ. Devono il loro nome al sico Wolfgang Ernst Pauli6 _.

Le matrici di Pauli sono denite come: σ1 ≡ σx ≡ X ≡ 0 1 1 0 σ2 ≡ σy ≡ Y ≡ 0 −i i 0 σ3 ≡ σz ≡ Z ≡ 1 0 0 −1 .

A queste tre matrici viene aggiunta la matrice identità I. 1.5.1 Proprietà algebriche

Indicata con I la matrice identità 2 × 2, possiamo aermare che le matrici di Pauli soddisfano le seguenti proprietà algebriche.

Innanzitutto

σ₁2 = σ2₂ = σ₃2 = I,

e inoltre soddisfano la seguente relazione: σiσj = iεijkσk+ δijI,

5_{una matrice hermitiana o matrice autoaggiunta è una matrice a valori complessi che}

coincide con la propria trasposta coniugata (o matrice aggiunta). Una matrice hermitiana con elementi nel campo dei numeri reali è dunque una matrice simmetrica.

6_{Fu fra i padri fondatori della meccanica quantistica. Vinse il Premio Nobel nel 1945 per il}

suo è il principio di esclusione, secondo il quale due elettroni in un atomo non possono avere tutti i numeri quantici uguali.

(23)

dove εijk è il tensore di Levi-Civita, mentre δij è la delta di

Kronec-ker.

Il determinante e la traccia, inne sono date da det (σi) = −1

tr (σi) = 0.

Dalle relazioni precedenti si ricava semplicemente che gli autovalori delle tre matrici di Pauli sono ±1.

Le tre matrici, così denite, con l'aggiunta dell'identità, formano un insieme completo di matrici, ovvero una base dello spazio delle matrici 2Ö2 hermitiane su R:

A = α0I + α1X + α2Y + α3Z.

1.6 Porte logiche quantistiche

Analogamente ai computer classici, un computer quantistico è for-mato da circuiti quantistici costituiti da porte logiche quantistiche elementari.

Nel caso classico esiste un'unica porta logica (non banale) a un bit, la porta NOT, che implementa l'operazione logica di negazione denita mediante una tabella di verità in cui

1 −→ 0 e 0 −→ 1.

Per denire un'operazione analoga su un qubit, non possiamo li-mitarci a stabilire la sua azione sugli stati di base, ma dobbiamo specicare anche come deve essere trasformato un qubit che si trova in una sovrapposizione degli stati |0i e |1i.

Le porte logiche quantistiche implementano degli operatori uni-tari agenti sugli stati di un certo numero di qubit. Se il numero di qubit su cui agisce un operatore è, ad esempio, n, la porta logica viene rappresentata con una matrice appartenente al gruppo U (2n₎_.

(24)

Dalla denizione di porta logica quantistica segue che ogni operazio-ne eseguita su un qualunque insieme di qubit è reversibile, ovvero che dal risultato nale si può risalire ai valori iniziali semplicemen-te inversemplicemen-tendo l'algoritmo di elaborazione. Quindi la computazione quantistica, a dierenza di quella classica, è sempre reversibile. Descriviamo, ora, alcune porte logiche che per la loro semplicità po-tremmo denire elementari. Queste porte possono implementare, sotto opportune condizioni, qualunque tipo di calcolo computazio-nale quantistico per complesso che sia.

1.6.1 Porte logiche ad un qubit

Si tratta del caso più semplice perchè lavorano su un solo qubit in ingresso, trasformandolo in un qubit in uscita. Contrariamente al caso classico, in cui possiamo denire una sola operazione non banale su un singolo bit, nel caso quantistico esistono molte operazioni non banali su un singolo qubit.

Il primo operatore che si incontra è la porta NOT , rappresentato con la matrice unitaria

X = 0 1

1 0

.

L'applicazione di X a un qubit |ψi = α |0i + β |1i, scritto in nota-zione vettoriale, è: X |ψi = X α β = β α .

La condizione di normalizzazione deve valere anche per lo stato che si ottiene dopo aver eettuato l'operazione. La proprietà delle matrici che garantisce la trasformazione di un vettore unitario in un vettore che è ancora unitario è l'unitarietà.

(25)

Teorema 1.1

Una funzione lineare preserva vettori normalizzati, cioè trasforma un qubit in un qubit, se e solo se è unitaria.

In generale un'operazione su un singolo qubit può essere specicata da una matrice 2Ö2. Tuttavia non tutte le matrici 2Ö2 deniscono operazioni lecite su qubit.

Oltre al NOT due operazioni importanti che useremo in seguito sono la porta Z :

Z = 1 0

0 −1

che agisce solo sulla componente |1i scambiandone il segno, e la porta di Hadamard: H = √1 2 1 1 1 −1 .

Quest'ultima operazione è una delle più utili e viene usata molto spesso nella denizione di circuiti quantistici.

Il suo eetto è quello di trasformare uno stato base in una sovrappo-sizione che risulta, dopo una misurazione nella base computazionale, essere 0 oppure 1 con uguale probabilità.

Esempio:

Applicando H a |0i si ottiene:

H 1 0 = √1 2 1 1 1 −1 1 0 = √1 2 1 1 = |0i + |1i√ 2 .

L'eetto di H si può quindi vedere come un NOT eseguito a me-tà in modo che lo stato risultante non è nè 0 nè 1, bensì una sovrapposizione coerente dei due stati di base.

(26)

Per questo motivo H viene spesso chiamata la radice quadrata di NOT7_.

@

Nella sfera di Bloch l'operazione H corrisponde ad una rotazione di 90° della sfera intorno all'asse y seguita da una riessione attraverso il piano (x, y).

Illustriamo l'eetto dell'applicazione di H al qubit |0i. Si può provare a visualizzare l'eetto di H sul qubit |0i+|1i

√ 2 .

Per eetto della rotazione e della successiva riessione attraverso il piano x, y si otterrà nuovamente |0i.

Figura 1.6: Visualizzazione della porta di Hadamard applicata all'input |0i. L'output è |ψi = |0i+|1i

√ 2

Le porte logiche a un qubit X, Z e H sono rappresentate gracamente come

Figura 1.7: Porte X, Z e H

7_{Nota che questa espressione ha un signicato solo sico! Da un punto di vista algebrico,}

H2_{non è la matrice X. Con un semplice calcolo si può infatti vericare che H}2_{è l'identità e}

(27)

1.6.2 Porte logiche a due qubit

Le operazioni su registri quantistici di due (o più) qubit sono neces-sarie per descrivere le trasformazioni di stati composti e in partico-lare dei cosiddetti stati entangled.

Abbiamo visto che non sempre un registro di due qubit può essere decomposto nel prodotto tensore dei singoli qubit componenti; di conseguenza non possiamo in questi casi simulare un'operazione sui due qubit mediante operazioni su ciascun qubit che lo compone. Anche le operazioni su registri di qubit corrispondono a operazioni unitarie come nel caso di un singolo qubit.

Le più importanti porte logiche che implementano operazioni su due bit classici sono le porte AND, OR, XOR, NAND e NOR.

Le porte NOT e AND formano un insieme universale, cioè qualsiasi funzione booleana può essere realizzata mediante una combinazione di queste due operazioni.

Per lo stesso motivo, il NAND costituisce un insieme universale. La porta XOR da sola o anche insieme con la porta NOT non è universale.

L'analogo quantistico di XOR è la porta CNOT (controlled-NOT ) che opera su due qubit: il primo è chiamato qubit di controllo e il secondo è il qubit target. Se il controllo è 0 allora il target è lasciato inalterato; se il controllo è 1, allora il target viene negato, cioè:

|00i −→ |00i |01i −→ |01i |10i −→ |11i |11i −→ |10i .

Equivalentemente, CNOT si può vedere come la trasformazione |A, Bi 7→ |A, B ⊕ Ai ,

dove A è il qubit di controllo, B è il target e ⊕ è la somma modulo 2, cioè l'operazione classica XOR.

(28)

Gracamente la porta CNOT è rappresentata come

Figura 1.8: Porta CNOT

La rappresentazione come matrice unitaria è:

UCN OT =     1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0     ,

dove la prima colonna descrive la trasformazione del vettore della base computazionale |00i, la seconda quella del vettore |01i, la terza di |10i e la quarta di |11i.

Osservazione:

Il CNOT, come tutte le trasformazioni unitarie, è invertibile: dal-l'output si può sempre ottenere l'input.

Questo non è vero per le porte logiche XOR e NAND: in generale le operazioni classiche sono irreversibili.

Altre porte logiche a due qubit sono la SWAP e CPHASE, che gracamente vengono rappresentate come:

(29)

Figura 1.10: Porta CPHASE

La prima scambia lo stato dei due qubit in ingresso e la sua rappre-sentazione matriciale è: USW AP =     1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1     ,

mentre la seconda ha come rappresentazione matriciale

UCP HASE =     1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 eiφ     .

L'operatore CPHASE aggiunge una fase eiφ _{al secondo qubit}

sola-mente se entrambi i qubit in ingresso sono nello stato |1i. 1.6.3 Porte logiche a tre qubit

Un esempio di porta logica a tre qubit è la porta CCNOT. Essa è una estensione immediata della porta logica CNOT ad un sistema con tre qubit. La porta CCNOT (Controlled-Controlled-Not), indicata anche con C2_{NOT, è conosciuta come porta di Tooli (T). La sua}

(30)

Figura 1.11: Porta CCNOT

mentre la sua rappresentazione matriciale è

UC2_{N OT} = U_T =            1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0            .

Questa porta logica lascia inalterati i primi due qubit, mentre viene eseguita l'operazione NOT sul terzo qubit solamente se i primi due si trovano nello stato |1i.

In altre parole l'operatore CCNOT si comporta come un CNOT dove il qubit di controllo è l'AND logico dei primi due qubit e il qubit target è rappresentato dal terzo qubit in ingresso all'operatore.

(31)

(32)

1.7 Circuiti logici quantistici

Le porte logiche elementari si possono assemblare per eseguire ope-razioni quantistiche più complicate di quanto permesso dalle porte di partenza. Un semplice esempio di circuito quantistico è dato da

Figura 1.13: Circuito che scambia due qubit ed equivalente simbolo schematico

Il circuito realizza lo scambio degli stati di due qubit.

Dato in input il registro di due qubit |a, bi, viene eettuato un CNOT con qubit di controllo a. Come risultato b viene rimpiazzato da a ⊕ b. Quest'ultimo viene preso come controllo di un secondo CNOT con target a. L'eetto è che a viene sostituito da

a ⊕ (a ⊕ b) = b.

Un ultimo CNOT con controllo b e target a ⊕ b realizza inne lo scambio rimpiazzando a ⊕ b con a.

Data una qualsiasi operazione unitaria U su n qubit, si può denire il circuito controlled − U come la naturale estensione della porta CNOT

(33)

Figura 1.14: Porta controlled-U

La linea con il pallino nero indica il qubit di controllo, mentre i qubit target sono gli n inputs di U.

Secondo questa convenzione il controlled − NOT non è altro che un controlled-U con U = X.

Un'altra operazione importante consiste nella misurazione di un qubit |ψi = α |0i + β |1i.

Come sappiamo il risultato è un bit classico M (indicato con una doppia linea) che sarà 0 oppure 1 con probabilità rispettivamente |α|2 e |β|2.

Tale operazione viene rappresentata gracamente come

Figura 1.15: Simbolo del circuito per la misurazione

1.7.1 No-cloning

La domanda che sorge spontanea a questo punto è: è possibile costruire un circuito che fa la copia di un qubit?

(34)

Figura 1.16: Circuito quantistico per copiare un qubit

Si potrebbe pensare di utilizzare un CNOT con qubit di controllo contenente il qubit |ai da copiare e il target posto inizialmente a |0i. Il risultato sarebbe la copiatura di a nel target.

In realtà questo è vero per bit classici ma non per un generico qubit |ψi = α |0i + β |1i.

Infatti, consideriamo il circuito

Tale circuito è costituito da un CNOT che ha come input i qubit |ψi (controllo) e |0i (target), cioè il registro |ψi |0i.

Il nostro obiettivo, però, è ottenere il risultato |ψi |ψi. Osserviamo che

|ψi |ψi = α2_{|00i + αβ |01i + αβ |10i + β}2_{|11i .}

Questo stato è in generale diverso dal risultato del nostro circuito, a meno che αβ = 0. Quindi questo circuito non eettua la copia di un qubit.

In generale, l'impossibilità di copiare un qubit è un'importantissi-ma proprietà dei sistemi quantistici nota come teoreun'importantissi-ma del no-cloning:

Teorema 1.2 (Teorema del no-cloning) Non esiste una trasformazione unitaria A tale che

A |ψi |0i = |ψi |ψi , per ogni stato |ψi .

(35)

Dim.

Supponiamo che esista A tale che

A |ψi |0i = |ψi |ψi

per ogni qubit |ψi . Allora possiamo scegliere due qubit |ψi e |ϕi tali che 0 < hψ| ϕi < 1. Ad esempio si può prendere

|ψi = |0i e |ϕi = |0i + |1i√

2 .

Allora otteniamo che

A |ψi |0i = |ψi |ψi e A |ϕi |0i = |ϕi |ϕi .

Facciamo ora il prodotto scalare membro a membro delle due equa-zioni. Siccome A è unitaria, quindi preserva i prodotti scalari, e per la proprietà distributiva del prodotto tensore rispetto al prodotto scalare otteniamo che

hψ| ϕi hψ| ϕi = hψ| ϕi h0| 0i = hψ| ϕi , contraddicendo l'ipotesi 0 < hψ| ϕi < 1.

Quindi A non può esistere.

@

Abbiamo appena visto che il teorema no-cloning nega l'esistenza di un operatore unitario che permetta di ottenere copie perfette di uno stato quantistico generico. L'impossibilità imposta dal teorema è un'impossibilità intrinseca, dovuta esclusivamente alla struttura della meccanica quantistica.

Tuttavia è possibile rilassare una delle ipotesi del teorema, in modo da analizzare più a fondo le potenzialità della clonazione: infatti il teorema no-cloning non impedisce esplicitamente il procedimento

(36)

di copia imperfetta di uno stato generico; questo può essere fatto a patto di introdurre un errore la cui grandezza dipenderà dal tipo di trasformazione che si decide di applicare al sistema; l'ecienza della trasformazione può essere poi valutata tramite la fedeltà.

1.7.2 Esempi di circuiti quantistici

Descriviamo due circuiti quantistici molto signicativi: il primo per-mette di trasformare i quattro stati computazionali di due qubit in altrettanti stati che sono detti stati di Bell o coppie EPR; il secondo usa questi stati per realizzare il teletrasporto di un qubit. Questi due esempi mostrano come costruire stati computazionali (che abbiamo chiamato entangled) che non hanno alcuna contropar-te classica e usarli per dar luogo a fenomeni paradossali secondo le leggi della sica classica.

Stati di Bell

Abbiamo visto che la porta CNOT può essere usata per creare stati che sono entangled.

Il circuito,

Figura 1.17: Circuito quantistico per la creazione di stati Bell

dove con H viene indicata la porta di Hadamard, genera per ogni stato della base computazionale

|00i , |01i , |10i , |11i

un particolare stato entangled. Questi stati, che indichiamo con β00, β01, β10, β11, sono chiamati stati di Bell.

Il circuito trasforma il primo qubit in una sovrapposizione che viene poi usata come input di controllo per CNOT. Il target viene quindi

(37)

invertito solo quando il controllo è 1. Pertanto i vettori in input vengono trasformati come segue:

|00i 7→ |β00i ≡ |00i + |11i √ 2 |01i 7→ |β01i ≡ |01i + |10i √ 2 |10i 7→ |β10i ≡ |00i − |11i √ 2 |11i 7→ |β11i ≡ |01i − |10i √ 2 . Teletrasporto quantistico

Il teletrasporto quantistico è una tecnica utilizzata per traspor-tare stati quantistici da un posto ad un altro sfruttando solo la trasmissione di bit classici.

Questa tecnica è stata scoperta nel 1993 e la sua validità è stata poi confermata da vari risultati sperimentali.

Uno dei primi esperimenti, che segnarono un enorme progresso nello studio di questa tecnica, venne eettuato all'Università di Ginevra e realizzava il teletrasporto di un qubit tra due laboratori posti a 55 metri di distanza e sfruttando un canale standard di telecomunica-zione di 2 Km. Da allora si sono fatti enormi progressi. La rivista Nature ha recentemente pubblicato (cf. N. 489 del 13 Settembre 2012) un articolo di Anton Zeilinger e il suo team dell'Institute for Quantum Optics and Quantum Information di Vienna in cui viene riportato come un esperimento ha permesso al team di teletraspor-tare fotoni ad una distanza di circa 143 Km tra le due isole delle Canarie La Palma e Tenerife.

Per capire il tipo di problemi che il teletrasporto permette di risolve-re, immaginiamo una situazione in cui una persona che chiamiamo Alice deve far conoscere lo stato di un qubit ad un'altra persona che chiameremo Bob. Alice non conosce lo stato del qubit e per il teorema del no-cloning sappiamo che non le è possibile farne una copia. Inoltre Alice può solo mandare a Bob informazione classica.

(38)

In questa situazione sembrerebbe impossibile trasmettere il qubit a Bob. Vediamo come ciò è possibile grazie alle proprietà degli stati entangled.

L'ipotesi fondamentale è che Bob e Alice possiedono ciascuno un qubit di una coppia EPR generata precedentemente. Sia Alice che Bob possono operare sul loro qubit. Il circuito

Figura 1.18: Circuito quantistico per la trasmissione di un qubit.

illustra come avviene la trasmissione di un qubit |ψi = α |0i + β |1i

di cui si ignorano le ampiezze α e β, da parte di Alice a Bob. Lo stato di input del circuito è |ψ0i = |ψi |β00i.

Alice combina |ψi con la sua metà della coppia EPR e misura i suoi due qubit dopo aver applicato le porte CNOT e Hadamard. I due bit che ottiene dopo la misurazione vengono mandati attraverso un canale di comunicazione classico a Bob, il quale sarà in grado di ricostruire lo stato |ψi sfruttando l'informazione classica ricevuta da Alice e la sua metà della coppia EPR.

Nel circuito in gura 1.18, le prime due linee corrispondono ai qubit usati da Alice, mentre l'ultima linea corrisponde al qubit posseduto da Bob.

L'input è

|ψ0i = |ψi |β00i =

[α |0i (|00i + |11i) + β |1i (|00i + |11i)] √

(39)

Come risultato di CNOT applicato ai suoi due qubit, Alice ottiene |ψ1i =

[α |0i (|00i + |11i) + β |1i (|01i + |10i)] √

2 .

Viene quindi applicato Hadamard al primo qubit, |ψi, ottenendo |ψ2i =

[α (|0i + |1i) (|00i + |11i) + β (|0i − |1i) (|10i + |01i)]

2 .

A questo punto Alice misura i suoi due qubit ottenendo una delle quattro coppie di bit: 00, 01, 10, 11. Per eetto della misurazione anche il qubit di Bob collasserà nello stato corrispondente al risultato della misurazione, cioè:

|00i 7→ α |0i + β |1i |01i 7→ α |1i + β |0i |10i 7→ α |0i − β |1i |11i 7→ α |1i − β |0i . Nella gura 1.18 questo stato è indicato con |ψ3i.

Alice comunica i due bit mn ottenuti a Bob mediante un canale classico.

Bob è ora in grado di ottenere il qubit |ψiapplicando al suo qubit il circuito Xn_Zm_.

(40)

1.8 Algoritmi quantistici

La realizzazione pratica dei qubit, delle porte logiche e dei circui-ti logici è suciente a realizzare la computazione quancircui-tiscircui-tica, ma non se ne possono trarre i vantaggi, che ad essa sono legati, se ad un Hardware robusto non si associa un Software altrettanto robu-sto. Il software viene inteso come algoritmo computazionale che, data la natura quantistica del sistema, prende il nome di algoritmo quantistico. Gli algoritmi quantistici sono importanti perchè dopo avere processato l'informazione la preparano in uno stato di facile lettura.

Sappiamo che la lettura di un sistema quantistico è probabilistica, quindi per determinare lo stato nale del calcolo possiamo percorrere due strade diverse:

preparare il sistema nello stato iniziale, farlo evolvere e suc-cessivamente leggerne lo stato nale. Il processo deve essere ripetuto molte volte no ad ottenere tutti i possibili risultati con le relative probabilità, intese come numero di esiti positivi su un numero di misure totali.

Dopo avere concluso l'elaborazione dello stato iniziale,

pro-cessare ulteriormente l'informazione per far si che il risulta-to aspettarisulta-to abbia una grande probabilità di essere misu-rato. Questo metodo permette di ridurre il numero di cicli preparazione-evoluzione-misura che devono essere compiuti per ottenere il risultato nale ed è quindi preferibile rispetto il primo.

Compito degli algoritmi è elaborare l'informazione e, successivamen-te, prepararla in uno stato altamente leggibile.

1.8.1 Computazioni classiche e probabilistiche su circuiti quantistici

Una dierenza fondamentale tra i circuiti classici e quelli quantistici è che le porte logiche classiche potrebbero essere irreversibili (ad esempio AND, XOR, NAND), mentre le porte logiche quantistiche sono sempre unitarie e quindi reversibili. D'altra parte, sarebbe auspicabile che un modello di calcolo alternativo fosse in grado di esprimere almeno tutte le computazioni esprimibili con il modello classico.

(41)

Il nostro primo obiettivo è quindi quello di rappresentare le compu-tazioni classiche come trasformazioni unitarie, cioè come computa-zioni quantistiche. Poichè le trasformacomputa-zioni unitarie sono invertibili (cioè reversibili), il primo passo da fare è quello di trasformare ogni computazione classica irreversibile in una reversibile.

Una computazione classica reversibile corrisponde ad una permuta-zione sulle sequenze dei bit in input. Questo garantisce la possibilità di costruire una matrice unitaria complessa che la rappresenta. In particolare la porta di Tooli può essere implementata come circuito quantistico.

La porta di Tooli è un'operazione classica reversibile, rappresen-tata dal seguente circuito

Figura 1.19: Rappresentazione della porta di Tooli

che opera su tre bit in input: due sono bit di controllo e il terzo è il bit target che viene scambiato se i bit di controllo sono entrambi 1. Nel caso in cui la porta di Tooli viene implementata come cir-cuito quantistico l'input è dato da tre qubit e la trasformazione, analogamente al caso classico, consiste nello scambio del terzo qubit se i primi due sono 1. Ad esempio la porta di Tooli quantistica applicata allo stato |110i produce lo stato |111i.

La porta di Tooli quantistica si può quindi usare per simulare su un computer quantistico tutte le computazioni classiche.

Oltre ai circuiti classici anche gli algoritmi probabilistici possono essere simulati ecientemente mediante circuiti quantistici. Infatti, per simulare un bit random è suciente preparare un qubit nello stato |0i e applicare poi la porta di Hadamard.

(42)

Si otterrà così lo stato

|ψi = (|0i + |1i)√ 2 che misurato darà 0 o 1 con probabilità 1

2.

Bisogna osservare inoltre che in questo modo si ottiene un numero realmente random, cosa che un computer classico non può fare. 1.8.2 Parallelismo quantistico

Tra i numerosi vantaggi che si hanno nell'utilizzare un computer quantistico c'è il fatto che si può valutare una funzione f (x) su valori dierenti di x contemporaneamente.

Questo è noto come parallelismo quantistico e rappresenta una caratteristica fondamentale dei circuiti quantistici.

Consideriamo una funzione booleana della forma f : {0, 1} −→ {0, 1} .

Per calcolare f(x) mediante una computazione quantistica si deve denire la trasformazione f(x) come una trasformazione unitaria Uf

. Questo si può fare applicando sullo stato di input |x, yi, un'appro-priata sequenza di porte logiche quantistiche che trasformano |x, yi nello stato |x, y ⊕ f (x)i.

|x, yiviene detto registro dei dati, mentre |x, y ⊕ f (x)i viene detto registro target. Se y = 0 allora lo stato nale del secondo qubit conterrà esattamente il valore di f(x).

(43)

Figura 1.20: Esempio di circuito quantistico che valuta f(0) e f(1) simultaneamente

che ha come input

|0i + |1i √

2 ⊗ |0i . Applicando Uf a questo registro si ottiene

|0, f (0)i + |1, f (1)i √

2 .

Questo stato contiene informazioni sia sul valore di f(0) che sul valore di f(1). Abbiamo, dunque, valutato simultaneamente f su x = 0 e x = 1.

Questo tipo di parallelismo è diverso da quello classico dove più circuiti vengono eseguiti contemporaneamente.

Si può generalizzare questa procedura per calcolare funzioni su un numero arbitrario di bit usando una generalizzazione della porta di Hadamard nota come la trasformata di Walsh-Hadamard.

Questa operazione consiste in n porte di Hadamard che agiscono in parallelo su n qubit.

(44)

La valutazione parallela di una funzione, f(x) con input x di n bit e 1 bit come output, può quindi essere eseguita da un circuito simile a quello illustrato in Figura 1.20, con n + 1 qubit in input preparati nello stato |0i⊗n_{. Si applica quindi Hadamard ai primi n qubit e}

successivamente il circuito Uf . Il risultato sarà

1 √ 2n X x |xi |f (x)i .

Con il parallelismo quantistico non è possibile ottenere tutti i va-lori calcolati con una sola misurazione: la misurazione dello stato

1 √

2n

P

x|xi |f (x)i darà il valore di f(x) per un singolo valore di x.

Per sfruttare l'informazione nascosta in questo parallelismo dob-biamo in qualche modo sfruttare meglio l'informazione contenuta nella sovrapposizione _√1

2n

P

x|xi |f (x)i, ad esempio utilizzando in

maniera opportuna l'interferenza tra gli stati nella sovrapposizione. Combinando il parallelismo quantistico con questa proprietà che vie-ne dalla meccanica quantistica si possono ottevie-nere risultati come quello esemplicato dall'algoritmo di Deutsch.

1.8.3 Algoritmo di Deutsch

L'algoritmo di Deutsch mostra come attraverso la valutazione parallela di una funzione su tutti i suoi inputs si possano determinare proprietà globali della funzione come, per esempio, quella di essere una funzione costante o bilanciata.

L'input del circuito che calcola la funzione f è quindi |ψ1i = |0i + |1i √ 2 ⊗ |0i − |1i √ 2 .

Applicando Uf, matrice unitaria, allo stato

|xi (|0i − |1i) √

2 si ottiene

(45)

(−1)f (x)|xi (|0i − |1i) √

2 .

Infatti, poichè Uf non è |xi , se f (x) = 0 allora il risultato è |xi(|0i−|1i)_√

2 , mentre f (x) = 1 il risultato è

|xi(|1i−|0i)_√

2 . Quindi,

ap-plicando Uf a |ψ1i otteniamo un risultato, che indichiamo con |ψ2i ,

che dipende da due possibilità:

se f (0) = f (1) otteniamo ±h|0i+|1i√ 2 ⊗ |0i−|1i_√ 2 i; se f (0) 6= f (1) otteniamo ±h|0i−|1i√ 2 ⊗ |0i−|1i √ 2 i.

Nota che nella seconda alternativa, si ha che (−1)f (1)= − (−1)f (0), e che |ψ1i = 1 √ 2

|0i|0i − |1i√

2 + |1i |0i − |1i √ 2 .

Pertanto Uf applicato a |ψ1i si può scrivere come

1 √ 2

(−1)f (0)|0i|0i − |1i√

2 + (−1)

f (1)

|1i|0i − |1i√ 2 , o, equivalentemente 1 √ 2

(−1)f (0)|0i|0i − |1i√

2 − (−1)

f (1)_|1i|0i − |1i_√

2 , cioè ±√1 2

|0i|0i − |1i√

2 − |1i |0i − |1i √ 2 ,

(46)

ovvero ± |0i − |1i√ 2 ⊗ |0i − |1i √ 2 .

Applichiamo ora Hadamard al primo qubit e otteniamo |ψ3i che

risulta

± |0i |0i − |1i√ 2

se f (0) = f (1) ± |1i |0i − |1i√

2

se f (0) 6= f (1) .

A questo punto possiamo osservare che f (0) ⊕ f (1) = 0 se f (0) = f (1) ,altrimenti f (0) ⊕ f (1) = 1. Possiamo quindi scrivere il risul-tato in maniera più compatta come

|ψ3i = ± |f (0) ⊕ f (1)i |0i − |1i √ 2 .

Attraverso una misurazione del primo qubit possiamo dunque deter-minare con certezza il valore di f (0)⊕f (1) e quindi se la funzione f è costante oppure bilanciata. Per far questo abbiamo dovuto valutare f una volta sola.

1.8.4 Algoritmo di Deutsch-Jozsa

L'algoritmo precedente si può estendere a funzioni booleane su n bit.

Supponiamo di sapere che f può essere o costante oppure bilan-ciata8_{. Usando un algoritmo classico, nel caso peggiore abbiamo}

bisogno di valutare la funzione su almeno 2n−1_{+ 1}_{valori per poter}

essere in grado di stabilire con certezza se f è costante o bilanciata. L'algoritmo quantistico di Deutsch-Jozsa ci permette di sta-bilirlo in un solo passo. A dierenza dell'algoritmo di Deutsch, nel-l'algoritmo di Deutsch-Jozsa l'input x della funzione è dato da n

(47)

qubit preparati nello stato |0i, che chiameremo il registro dei dati. Il qubit target, destinato a contenere il risultato di f(x), è invece preparato nello stato |1i. Il registro iniziale è quindi

|ψ0i = |0i ⊗n

|1i ,

dove |0i⊗n _{indica il prodotto tensore di n qubit |0i .}

Al registro dei dati |0i⊗n

viene applicata la trasformazione di Walsh-Hadamard, H⊗n_{, per produrre una sovrapposizione equiprobabile di}

tutti i 2n _{stati della base computazionale.}

Indicando con x, y ∈ {0, 1}n _{sequenze di bit di lunghezza n, si}

dimostra che H⊗n|xi = √1 2n X y∈{0,1}n (−1)x·y|yi , dove x · y = Pn

k=1xkyk (mod 2) . In particolare risulta che

H⊗n|0i⊗n= √1 2n

X

x∈{0,1}n

|xi .

Gli stati dell'algoritmo risultano quindi: |ψ1i = 1 √ 2n X x∈{0,1}n

|xi |0i − |1i√ 2 , |ψ2i = 1 √ 2n X x∈{0,1}n

(−1)f (x)|xi |0i − |1i√ 2 , |ψ3i = X y∈{0,1}n X x∈{0,1}n (−1)x·y+f (x)|xi 2n |0i − |1i √ 2 .

L'ampiezza di |ψi = |0i⊗n _{in |ψ}

3iè Px

(−1)f (x) 2n .

(48)

Consideriamo i due casi:

Se f è costante, tale valore risulta 1 o =1. Questo signica che le ampiezze associate a tutti gli altri stati sono 0. Una misurazione del registro dei dati produce lo stato |0i⊗n _con

probabilità 1.

Se invece f è bilanciata, l'ampiezza di |yi = |0i⊗nrisulta 0. Ciò

signica che il risultato di una misurazione deve essere diverso da zero su almeno un qubit del registro dei dati.

Dopo la misurazione siamo quindi in grado di stabilire con certezza se la funzione è costante o bilanciata. Abbiamo ottenuto quindi una riduzione esponenziale della complessità rispetto ad un qualsiasi algoritmo classico.

1.8.5 Algoritmo di Shor

L'algoritmo di Shor è un algoritmo per la fattorizzazione dei numeri interi. E' particolarmente importante per la teoria dell'informazione perchè svolge il suo compito in tempi estremamente brevi se parago-nati a quelli dei migliori algoritmi classici. La sua importanza risiede anche nel fatto che gli algoritmi di crittograa più robusti, attual-mente utilizzati e conosciuti, si basano sulla dicoltà di fattorizzare grandi numeri.

La realizzazione di un computer quantistico che implementa l'algo-ritmo di Shor renderebbe immediatamente insicuro qualsiasi sistema crittograco attualmente utilizzato. Ironicamente la computazione quantistica permetterebbe, allo stesso tempo, di realizzare nuovi sistemi crittograci matematicamente inviolabili (per una trattazio-ne dettagliata sui sistemi crittograci, anche se a livello puramente divulgativo, si veda [2]).

Il migliore algoritmo classico conosciuto svolge il compito di fattoriz-zazione in un tempo che è esponenziale nelle dimensioni del numero in ingresso, l'algoritmo di Shor, invece, svolge lo stesso compito in un tempo che è polinomiale.

L'algoritmo permette, quindi, di trattare problemi che sono pesanti per la computazione classica in modo eciente.

(49)

Per comprendere appieno l'algoritmo di Shor è necessario conoscere nel dettaglio i seguenti punti:

trasformata di Fourier quantistica;

problema della stima della fase (Phase estimation); problema della ricerca dell'ordine (Order-nding);

integrazione dei tre punti precedenti in un unico algoritmo per

la fattorizzazione.

Per ulteriori approfondimenti sull'algoritmo di Shor si può consul-tare [3].

1.9 I postulati della meccanica quantistica

Un modello matematico che ci permette di denire in maniera for-male tutto quello di cui abbiamo parlato no ad ora (sistemi quanti-stici, stati quantiquanti-stici, evoluzione e misurazione di stati quantiquanti-stici, ecc..) è la teoria quantistica.

La meccanica quantistica fornisce la descrizione più accurata e com-pleta delle leggi che governano il mondo sico. Il formalismo ma-tematico su cui si basa e la realtà sica che descrive sono messi in relazione mediante alcuni postulati fondamentali.

Postulato 1: Ogni sistema sico isolato ha associato uno spazio di Hilbert complesso, detto spazio degli stati del sistema. Il sistema è completamente descritto dal suo vettore di stato, che è un vettore unitario nello spazio degli stati.

Il sistema sico isolato più semplice è il qubit. Lo spazio di Hilbert associato è C2_.

La base computazionale formata da |0i e |1i è una base ortonormale. La condizione che ogni vettore

|ψi = α |0i + β |1i , _{con α, β ∈ C} sia un vettore unitario è espressa equivalentemente da |α|2

+|β|2 = 1. Osserviamo inoltre che uno stato di un sistema quantistico è in realtà

(50)

una classe di equivalenza di vettori che dieriscono per moltiplica-zione di uno scalare complesso non nullo; il vettore unitario è il rappresentante di questa classe.

Quindi lo stato eiϑ_|ψiè equivalente a |ψi, dove |ψi è uno stato e ϑ è

un numero reale. Il fattore eiϑè detto fattore di fase globale. Questa

identicazione degli stati con fasi globali diverse è giusticata dal fatto che le statistiche di misurazione di questi stati sono le stesse. Un altro tipo di fattore, detto fase relativa, è invece sicamente signicativo e due stati che dieriscono per un fattore di fase relativa non possono essere identicati. Ad esempio, identichiamo α |ϕi + β |ψicon eiϑ(α |ϕi + β |ψi) ma non con α |ϕi + eiϑβ |ψi.

Postulato 2: L'evoluzione di un sistema quantistico chiuso è descritto da una trasformazione unitaria: lo stato |ψi del sistema al tempo t1 è in relazione con lo stato |ψ0i del sistema al tempo t2

mediante un operatore unitario U che dipende solo da t1 e t2,

|ψ0i = U |ψi .

Per il semplice sistema quantistico rappresentato da un qubit ab-biamo visto vari esempi di operatori unitari: le matrici di Pauli e la porta di Hadamard.

Una versione più ranata di questo postulato descrive l'evoluzione di un sistema quantistico chiuso in tempo continuo.

Postulato 2bis: L'evoluzione nel tempo dello stato di un siste-ma quantistico chiuso è descritta dall'equazione di Schrödinger

ièd |ψi

dt = H |ψi ,

dove è una costante sica, nota come la costante di Planck, il cui valore deve essere determinato sperimentalmente. H è un operatore Hermitiano ssato, noto come l'Hamiltoniano del sistema chiuso. In generale, trovare l'Hamiltoniano di un sistema è un problema molto dicile che richiede un numero sostanziale di esperimenti per poter essere risolto. Per i nostri scopi ci basterà comunque sapere

(51)

che ogni operatore unitario U può essere realizzato come una solu-zione dell'equasolu-zione di Shröndinger e che esiste una corrispondenza biunivoca tra la descrizione della dinamica di un sistema a tempo di-screto mediante operatori unitari e la descrizione a tempo continuo mediante gli Hamiltoniani.

Postulato 3: Ogni osservabile M (cioè ogni proprietà di un si-stema sico che può essere misurata) è rappresentato da un operato-re Hermitiano sullo spazio degli stati del sistema che viene osservato e viceversa. M ha la forma

M =X

m

mPm,

dove Pm è la proiezione sul sottospazio degli autovettori di M

cor-rispondenti all'autovalore m. I possibili risultati di una misura del-l'osservabile M corrispondono agli autovalori m di M.

Dopo una misura di M nello stato ψ, la probabilità di ottenere il risultato m è

p (m) = hψ| Pm|ψi = kPm|ψik 2

.

Lo stato del sistema immediatamente dopo una misura con risultato m è

Pm|ψi

pp (m).

Gli operatori Pm soddisfano l'equazione di completezza

X

m

Pm = I.

L'equazione di completezza esprime il fatto che la somma delle probabilità dei risultati di una misura deve essere 1. Infatti:

(52)

1 =X

m

p (m) = X

m

hψ| Pm|ψi = hψ |ψi .

Questo tipo di misurazione viene spesso chiamata misurazione pro-iettiva completa o misurazione di von Neumann perchè l'osservabile M è determinato da un qualsiasi insieme di operatori di proiezione ortogonali Pm che soddisfano la relazione di completezza e tali che

PmPm0 = δ_mm0P_m.

Misurare nella base {|mi}, dove {|mi} è una base ortonormale, signi-ca eseguire una misurazione proiettiva con operatori di proiezione |mi hm|.

Postulato 4: Lo spazio degli stati di un sistema sico composto è il prodotto tensore degli spazi degli stati dei sistemi sici componenti. Se il sistema è composto da n sottosistemi e il componente i-esimo si trova nello stato |ψii, allora lo stato del sistema totale è

|ψ1i ⊗ |ψ2i ⊗ · · · ⊗ |ψni .

Questo postulato descrive come costruire lo spazio degli stati di un sistema quantistico composto da due o più sistemi sici distinti a partire dagli spazi degli stati dei sistemi componenti.

Il Postulato 4 permette di denire la nozione di entanglement che, insieme al problema della misurazione, rappresenta una delle pro-prietà più discusse dei sistemi quantistici. Uno stato di un sistema composto si dice entangled se non può essere scritto come pro-dotto dei suoi sistemi componenti. Come già visto nell'esempio del teletrasporto, gli stati entangled possono essere utilizzati per otte-nere dei risultati sorprendenti (come la trasmissione dello stato di un qubit attraverso due soli bit di informazione classica).

1.9.1 Il problema della misurazione quantistica

Il problema della misurazione quantistica diede luogo ad accesi di-battiti sin dalla nascita della teoria quantistica nel 1920. John von Neumann introdusse il primo trattamento assiomatico rigoroso del-la meccanica quantistica nel 1955, intervenendo in maniera decisi-va anche sul problema della misurazione e fornendo una