25 marzo 2015 - Home - people.unica.it · 2016. 1. 22. · Capitolo 1 Introduzione alla teoria...

Il computer quantistico

25 marzo 2015

Indice

1 Introduzione alla teoria della computabilità 51.1 Modelli di computazione . . . . . . . . . . . . . . . . . . . . . . . . 5

1.1.1 La tesi di Church–Turing . . . . . . . . . . . . . . . . . . . . 51.1.2 La macchina di Turing . . . . . . . . . . . . . . . . . . . . . 51.1.3 Modello circuitale di computazione . . . . . . . . . . . . . . 6

1.2 Complessità computazionale . . . . . . . . . . . . . . . . . . . . . . 81.2.1 Notazione asintotica . . . . . . . . . . . . . . . . . . . . . . 81.2.2 Problemi decisionali . . . . . . . . . . . . . . . . . . . . . . 91.2.3 Classi di complessità . . . . . . . . . . . . . . . . . . . . . . 91.2.4 Problemi trattabili e problemi intrattabili . . . . . . . . . . 101.2.5 L’ideazione dei computer quantistici . . . . . . . . . . . . . . 11

2 Il modello di computazione a circuito quantistico 132.1 Il bit quantistico (qubit) . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.1 Rappresentazione di un qubit nella sfera di Bloch . . . . . . 142.1.2 Informazione quantistica . . . . . . . . . . . . . . . . . . . . 152.1.3 Doppio qubit ed entanglement . . . . . . . . . . . . . . . . . 152.1.4 Qubit multipli . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2 Circuiti quantistici . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2.1 Porte logiche di singolo qubit . . . . . . . . . . . . . . . . . 172.2.2 Operatori di rotazione . . . . . . . . . . . . . . . . . . . . . 182.2.3 Interpretazione geometrica degli operatori di rotazione nella

sfera di Bloch . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2.4 Decomposizione in rotazioni delle porte logiche di singolo qubit 202.2.5 Operazioni controllate . . . . . . . . . . . . . . . . . . . . . 212.2.6 Implementazione di operazioni controllate . . . . . . . . . . 222.2.7 Misurazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.3 Un insieme di porte logiche quantistiche universali . . . . . . . . . . 272.3.1 Decomposizione in matrici unitarie a due livelli . . . . . . . 272.3.2 Applicazione di porte unitarie a due livelli qualsiasi mediate

porte di singolo qubit . . . . . . . . . . . . . . . . . . . . . . 282.3.3 Approssimazione degli operatori su singolo qubit . . . . . . . 30

3 Algoritmi quantistici 353.1 Teletrasporto quantistico . . . . . . . . . . . . . . . . . . . . . . . . 35

3.1.1 La questione della copia dei qubit . . . . . . . . . . . . . . . 35

3

Indice

3.1.2 Stati di Bell . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.1.3 Circuito per il teletrasporto quantistico . . . . . . . . . . . . 373.1.4 Trasferimento dell’informazione . . . . . . . . . . . . . . . . 38

3.2 Parallelismo quantistico . . . . . . . . . . . . . . . . . . . . . . . . 383.2.1 Algoritmo di Deutsch . . . . . . . . . . . . . . . . . . . . . . 403.2.2 Algoritmo di Deutsch–Josza . . . . . . . . . . . . . . . . . . 41

3.3 La trasformata di Fourier quantistica . . . . . . . . . . . . . . . . . 423.3.1 Stima della fase . . . . . . . . . . . . . . . . . . . . . . . . . 453.3.2 Ricerca dell’ordine moltiplicativo . . . . . . . . . . . . . . . 48

4 Dalla teoria alla pratica: realizzazione fisica dei computer quan-tistici 514.1 Decoerenza quantistica . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.1.1 Sovrapposizioni coerenti e miscele statistiche . . . . . . . . . 514.1.2 Decoerenza: definizione e tipologie . . . . . . . . . . . . . . 52

4.2 Requisiti fisici di un sistema volto alla computazione quantistica . . 54

5 Il computer quantistico basato sugli ioni intrappolati 595.1 Trappole per ioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.1.1 Il problema del confinamento . . . . . . . . . . . . . . . . . 595.1.2 Trappole a radiofrequenza . . . . . . . . . . . . . . . . . . . 605.1.3 La trappola di Paul . . . . . . . . . . . . . . . . . . . . . . . 605.1.4 Sistemi di ra↵reddamento . . . . . . . . . . . . . . . . . . . 63

5.2 Risonanze ottiche in sistemi atomici a due livelli . . . . . . . . . . . 645.2.1 Hamiltoniana di interazione dell’elettrone . . . . . . . . . . . 655.2.2 Equazioni di Bloch . . . . . . . . . . . . . . . . . . . . . . . 665.2.3 Approssimazione di onda rotante . . . . . . . . . . . . . . . 685.2.4 Soluzione nel caso di risonanza esatta . . . . . . . . . . . . . 705.2.5 Soluzione in caso di detuning . . . . . . . . . . . . . . . . . 72

5.3 Stato dell’arte dei computer quantistici a ioni intrappolati . . . . . 74

6 Conclusione 79

4

Capitolo 1

Introduzione alla teoria dellacomputabilità

1.1 Modelli di computazione

1.1.1 La tesi di Church–Turing

Sebbene le prime testimonianze storiche di algoritmi di calcolo siano molto antiche— siamo al corrente che gia i babilonesi utilizzavano algoritmi di calcolo per l’aba-co — per avere una definizione formale di algoritmo si è dovuto attendere sino aglianni ’30 nei quali, indipendentemente, Alonzo Church e Alan Turing si impegna-rono nella risoluzione di un problema posto da David Hilbert qualche anno prima:il problema si interrogava sull’esistenza di un algoritmo capace di risolvere ogniproblema della matematica. Uno scoglio per i due scienziati fu quello di formularein termini matematicamente rigorosi il concetto intuitivo di algoritmo.

Non di rado delle buone definizioni si sono dimostrate fondamentali per il pro-gresso di un campo scientifico o matematico; la nozione di macchina di Turing hasegnato la nascita dell’informatica moderna.Turing ideò una macchina — si tratta di una costruzione di pensiero, non soggettaai vincoli imposti da una realizzazione fisica pratica — che ancor oggi appare incar-nare ciò che intendiamo come “algoritmo”. La tesi di Church–Turing a↵erma chela classe di funzioni calcolabili da una macchina di Turing corrisponde esattamentealla classe di funzioni che riteniamo calcolabili da un algoritmo; sottolineiamo ilfatto che la tesi collega un concetto intuitivo ad una definizione formale.Quella di Church–Turing è una congettura in quanto non si può escludere a priorila possibilità che venga trovato prima o poi un qualche processo che definiremmoalgoritmico ma che non possa essere eseguito da una macchina di Turing. Tuttaviaad oggi non si ha alcuna evidenza contraria alla tesi.

1.1.2 La macchina di Turing

La macchina di Turing (figura 1.1) è costituita da un programma, un controllo astati finiti e un nastro sul quale la macchina abbia accesso in lettura e scritturatramite una testina.

5

Capitolo 1. Introduzione alla teoria della computabilità

Figura 1.1: Schema della macchina di Turing.

Il controllo a stati finiti è una sorta di processore che può assumere un insiemefinito di stati q1, q2, . . ., qm; il nastro è un oggetto unidimensionale che si esten-de infinitamente in una direzione: possiamo pensarlo diviso in caselle contenenticiascuna un simbolo preso da un’insieme finito � di simboli (detto alfabeto). Latestina può scorrere il nastro e agire su una casella alla volta.

La configurazione iniziale della macchina prevede che il controllo sia nello statodi partenza qs e che la testina indichi il simbolo ., posto all’origine del nastro.L’evoluzione dell’algoritmo è regolata dal programma, costituito da un elenco distringhe contenenti cinque elementi ciascuna. In primis la macchina selezionaall’interno del programma la stringa avente come primo elemento lo stato in cui sitrova il controllo e come secondo elemento il simbolo indicato dalla testina. Se ilprogramma non contiene la stringa cercata la macchina assume lo stato di arrestoqh e l’esecuzione del programma termina. In caso contrario la configurazione dellamacchina si modifica in accordo con i successivi tre elementi della stringa: il terzoelemento rappresenta lo stato che il controllo dovrà assumere; il quarto è un simbolodi � che la testina scrive sulla casella in cui punta; la quinta e ultima istruzionepermette di spostare la testina di una casella a sinistra o a destra sul nastro, o dimantenerla nella posizione corrente.Il ciclo prosegue a meno che il controllo non arrivi a trovarsi nello stato qh; quandoquesto avviene la casella su cui punta la testina contiene l’output del programma.

Abbiamo illustrato la più semplice delle molte possibili varianti della macchinadi Turing. Esse possono di↵erire ad esempio nel numero di nastri o nella lorodimensionalità. Tutte le varianti conosciute sono però tra loro equivalenti, nelsenso che ognuna è capace di simulare l’altra.

1.1.3 Modello circuitale di computazione

Un modello di calcolatore alternativo alla macchina di Turing è quello circuitale,che impiega dei circuiti composti da rami di collegamento e porte logiche permanipolare informazioni codificate in numeri binari.Nonostante all’apparenza questo modello non sembri avere molte caratteristiche

6

1.1. Modelli di computazione

in comune con la macchina di Turing, si può dimostrare che i due modelli sono difatto equivalenti.

Figura 1.2: Le più comuni porte logiche classiche.

Una porta logica è una funzione

f : {0, 1}k ! {0, 1}l (1.1)

che associa a k cifre binarie (bit) in input l cifre binarie di output — i simboliconvenzionali di alcune comuni porte logiche sono riportati in figura 1.2. Sebbenetali funzioni siano infinite, ognuna di esse si può comporre utilizzando un numerofinito di porte logiche chiamate, per questo motivo, universali (un risultato similevale nell’ambito del modello circuitale quantistico, come vedremo al §2.3).Dimostriamo rapidamente quanto a↵ermato costruendo una funzione f qualunquefacendo uso solamente delle porte logiche not, or, and e xor.Limitiamoci inizialmente a funzioni booleane f : {0, 1}k ! {0, 1} (si ottengonoponendo l = 1 nella 1.1); procediamo per induzione. Nel caso k = 1 esistonoquattro diverse possibili f : l’identità, il not e le funzioni costanti 0 e 1. Lefunzioni costanti si possono ottenere, rispettivante, facendo l’and dell’input conun ancilla bit1 posto uguale a 0 oppure facendone l’or con l’ancilla bit 1.Dimostriamo ora il passo induttivo mostrando che una funzione booleana di n+1bit può essere calcolata utilizzando funzioni di n bit. Consideriamo le due funzioni

f0(x1, x2, . . . , xn) ⌘ f(0, x1, x2, . . . , xn)

f1(x1, x2, . . . , xn) ⌘ f(1, x1, x2, . . . , xn)(1.2)

esse sono funzioni booleane ad n bit che, per l’ipotesi induttiva, possono essererealizzate con le porte scelte precedentemente.Tramite queste due funzioni è possibile calcolare f utilizzando il circuito di figura

1Gli ancilla bit, o bit di lavoro, sono dei bit che non rappresentano un informazione in sensostretto ma hanno solo un ruolo tecnico nel funzionamento del circuito.

7


Figura 1.3: Circuito per il calcolo di f(x1, x2, . . . , xn+1) che utilizza soltanto le duefunzioni di equazione 1.2 e le porte not, and e xor.

1.3.Dato che ciascuna funzione f definita dalla 1.1 può essere pensata come l

funzioni booleane di k bit, questo risultato si generalizza ad l qualunque. Questocompleta la dimostrazione dell’universalità delle porte not, or, and e xor.Queste porte si possono a loro volta simulare utilizzando solamente il nand, apatto di poter disporre di ancilla bit e fanout2.

1.2 Complessità computazionale

Ci siamo finora occupati solamente della possibilità dell’esecuzione degli algoritmisenza badare alle risorse che è necessario investire in termini di spazio, tempo edenergia. È quest’ultimo l’argomento di una branca dell’informatica nota come teo-ria della complessità computazionale; si tratta di una materia vasta di cui daremosolo una breve panoramica.

1.2.1 Notazione asintotica

La risoluzione di un certo problema può richiedere un di↵erente quantitativo di ri-sorse a seconda del modello di computazione che si utilizza. Vi possono essere delledi↵erenze, ad esempio, tra il numero di cicli compiuti da una macchina di Turinga nastro singolo e quelli compiuti da una macchina a due nastri, nella risoluzio-ne di un certo problema. Tuttavia il numero esatto di cicli è di scarso interesse:

2Con fanout si intende la possibilità di creare, ad un certo punto di un ramo, dei nodiattraverso i quali l’informazione del ramo originale viene trasmessa a due o più rami figli.

8

1.2. Complessità computazionale

ci è su�ciente conoscere l’andamento funzionale del numero di cicli rispetto alladimensione dell’input per avere un’idea dell’e�cienza della computazione nei duemodelli.Si fa per questa ragione largo uso, nel campo della complessità computazionale,della notazione asintotica per le funzioni.

Una funzione f(n) è O(g(n)) se esiste una costante c tale che f(n) cg(n)definitivamente; il simbolo O si usa per indicare un limite superiore del compor-tamento asintotico della funzione. Analogamente si usa ⌦ per indicare un limiteinferiore:

f(n) = ⌦(g(n)) se 9c, n0 tali che f(n) � cg(n) 8n > n0

Se una funzione f(n) è sia O(g(n)) sia ⌦(g(n)) allora si può scrivere f(n) =⇥(g(n)).

1.2.2 Problemi decisionali

Molti problemi computazionali sono esprimibili in maniera naturale in termini diproblemi decisionali. Questi si definiscono in maniera formale facendo uso di uninsieme di simboli ⌃, chiamato alfabeto; l’insieme di tutte le possibili stringhe disimboli appartenenti all’alfabeto si indica con ⌃⇤. Si definisce linguaggio L unsottoinsieme di ⌃⇤.Data una stringa di simboli, il problema di verificare se la stringa appartenga omeno a L è un problema decisionale.Facciamo un esempio pratico: se utilizziamo come alfabeto le due cifre binarie 0 e 1allora ⌃⇤ rappresenta l’insieme di tutte le stringhe binarie, il quale può essere messoin corrispondenza biunivoca con N. Se definiamo L come l’insieme dei numeribinari che rappresentano dei numeri primi allora il problema di determinare seuna stringa binaria appartenga a L oppure no equivale allo stabilire se il numeroad essa corrispondente è primo o meno.Il problema della fattorizzazione è solitamente posto nella forma seguente: unintero m possiede dei fattori non banali minori di l, con l < m?Il problema di trovare i fattori di n si riconduce al precedente.

1.2.3 Classi di complessità

I problemi decisionali si possono classificare, ad esempio, in base al tempo im-piegato da una macchina di Turing per risolverli. Un problema decisionale èTIME(f(n)) se è possibile risolverlo con una macchina di Turing in un tempoO(f(n)), dove n è la grandezza dell’input. I problemi TIME(nk) formano la clas-se P dei problemi risolubili in un tempo polinomiale.Dimostrare che un problema non appartiene a P è spesso molto di�cile. Comenel caso della fattorizzazione, accade che sebbene non si conosca ad oggi alcunalgoritmo capace di risolvere il problema in un tempo polinomiale, non si disponedi una dimostrazione della sua inesistenza.

Per definire la classe NP ci serviamo ancora dell’esempio della fattorizzazione:sebbene risolvere il problema richieda un tempo polinomiale, verificare che un

9


intero n abbia un fattore non banale p < l può essere fatto facilmente se p è noto.p gioca il ruolo di un testimone nel dimostrare che n ha dei fattori non banaliminori di l, ovvero che n appartiene al linguaggio.Appartengono a NP quei problemi decisionali che soddisfano (indichiamo con xun generico elemento di ⌃⇤):

1. Se x 2 L allora esiste una stringa testimone w tale che una macchina diTuring restituisca “si” in un tempo polinomiale prendendo come input x ew.

2. Se x /2 L allora per ogni stringa w che si proponga come testimone, la stessamacchina restituisce “no” in un tempo polinomiale prendendo come input xe w.

Notiamo come le proprietà dei problemi NP siano asimmetriche in quanto nonprevedano un testimone per la verifica della non appartenenza di una stringa allinguaggio. Si definisce perciò la classe coNP che contiene i complementi deiproblemi decisionali di NP: il complemento di un problema decisionale su unlinguaggio L si definisce tramite un linguaggio L0 = ⌃⇤�L, complemento in ⌃⇤ diL.Le proprietà dei problemi coNP sono dunque:

1. Se x /2 L0 allora esiste una stringa testimone w tale che una macchina diTuring restituisca “no” in un tempo polinomiale prendendo come input x ew.

2. Se x 2 L allora per ogni stringa w che si proponga come testimone, la stessamacchina restituisce “si” in un tempo polinomiale prendendo come input xe w.

I problemi della classe P sono anche in NP e coNP, in quanto per essi esisteuna macchina di Turing in grado di determinare l’appartenenza di una stringa allinguaggio in un tempo polinomiale con un testimone w vuoto. Determinare se larelazione P ✓ NP valga in senso stretto, il che implicherebbe anche NP = coNP,è uno dei problemi aperti più famosi dell’informatica.

1.2.4 Problemi trattabili e problemi intrattabili

La complessità computazionale si occupa di stabilire dei limiti minimi sul numerodi risorse richieste per risolvere un certo problema computazionale. In questoambito viene fatta una grossa distinzione fra quei problemi che possono essererisolti in un tempo polinomiale (classe P) e quelli che richiedono invece un temposuperpolinomiale, o esponenziale3 rispetto alla grandezza dell’input. I primi sonoconsiderati trattabili, a di↵erenza dei secondi; vi sono varie ragioni per adottarequesta distinzione. Sebbene in generale non sempre un algoritmo polinomiale

3Questa nomenclatura, sebbene di largo uso, non è del tutto appropriata in questa esistonofunzioni, come ad esempio nlogn, che crescono più velocemente di qualsiasi polinomio ma anchepiù lentamente di un esponenziale.

10

1.2. Complessità computazionale

comporti una maggiore e�cienza rispetto a un algoritmo superpolinomiale (2n/1000

non raggiunge n1000 se non per n ⇠ 108), storicamente gli algoritmi polinomialisi sono dimostrati preferibili. Ciò anche dovuto verosimilmente ad un e↵etto diselezione, in quanto ideare un algoritmo di n o n2 passi è certamente più a�ne alragionamento comune piuttosto che idearne uno di n1000.In secondo luogo, tale distinzione trova ragione nella tesi forte di Church–Turingla quale a↵erma che ogni modello di computazione può essere simulato da unamacchina di Turing a prezzo di un aumento nel numero di operazioni elementaririchieste al più polinomiale.Essa implica che se un problema può essere risolto in un tempo polinomiale conun dato modello di computazione allora può essere risolto in una macchina diTuring ancora in un tempo polinomiale e anche che, viceversa, se un problemanon è risolubile in un tempo polinomiale in una macchina di Turing allora non èrisolvibile a↵atto sotto tale vincolo. La teoria della complessità computazionaletrova cos̀ı una formulazione naturale se si associa alla nozione di trattabilità di unproblema la computabilità in un tempo polinomiale.

1.2.5 L’ideazione dei computer quantistici

A di↵erenza della sua controparte debole, la congettura forte di Church–Turing èstata più volte messa in discussione nel secolo scorso e tutt’oggi la sua validità ètutt’altro che accertata.Subito dopo la pubblicazione della tesi debole di Turing, avvenuta nel 1936, furonoassemblati i primi calcolatori elettronici. John von Neumann si occupò di delinearele caratteristiche che un computer reale avrebbe dovuto possedere per poter essereequiparato alla macchina di Turing, ma si dovette aspettare sino al 1947, annodell’invenzione del transistor, per avere la possibilità di realizzare fisicamente unsimile dispositivo.Da allora la tecnologia dei calcolatori elettronici si è evoluta molto rapidamente,tanto che Gordon Moore, nel 1965, formulò l’omonima legge secondo la quale lapotenza di calcolo dei computer sarebbe dovuta progredire raddoppiando di annoin anno.Di fatto si è passati dall’Intel 4004 del 1971, costituito da 2250 transistor, alPentium 4 che, nel 2000, ne conteneva 42 milioni. Tale evoluzione procede di paripasso con la miniaturizzazione dei componenti, la quale comporta da un lato unasimile crescita esponenziale dei costi di produzione e dall’altro si scontra con deilimiti fisici. Se le dimensioni di un transitor raggiungeranno infatti l’ordine digrandezza della lunghezza di De Broglie dell’elettrone, gli e↵etti quantistici nonsarranno più trascurabili e i circuiti elettronici non potranno più funzionare nelmodo in cui oggi normalmente li utilizziamo.Una delle possibili strade percorribili per non incorrere nel declino della crescitaesponenziale prevista da Moore è quella di passare ad un diverso e nuovo paradigmacomputazionale, quale è quello dei computer quantistici.

Nel ripercorrere i passi che hanno portato a credere che la meccanica quanti-stica potesse essere sfruttata per risolvere dei problemi computazionali, torniamoal 1936 e alla tesi di Church–Turing. Con il successivo sviluppo dei computer a

11

Bibliografia

transistor e dell’informatica si iniziò a credere, negli anni 60’ e 70’, che non fossepossibile trovare un modello capace di sopravanzare quello di Turing, e venne cos̀ıformulata la tesi forte enunciata al paragrafo precedente.Una prima sfida che la tesi forte dovette a↵rontare venne dal campo dei computeranalogici, che sembravano poter riuscire a risolvere e�cientemente dei problemiper i quali non si conosceva invece alcun algoritmo e�ciente funzionante sullamacchina di Turing.Questa scoperta si rivelò non vera, riconsiderando la questione senza omettere ilrumore a cui questi dispositivi analogici sono soggetti.4

Una seconda obiezione alla tesi di Church–Turing forte venne avanzata da RobertSolovay e Volker Strasse, i quali fabbricarono negli anni ’70 un algoritmo stoca-stico capace di determinare se un numero intero fosse primo oppure no con unacerta probabilità: l’elemento casuale permetteva di risolvere, sebbene in terminiprobabilistici, un problema ritenuto intrattabile. Ne risultò la seguente modificaalla tesi di Church–Turing forte: ogni modello di computazione può essere simulatoda una macchina di Turing probabilistica a prezzo di un aumento nel numero dioperazioni elementari richieste al più polinomiale.Questa modifica ad hoc della tesi portò a pensare di a↵rontare la questione dellacomputabilità in maniera diversa, senza ricorrere a congetture: nel 1985 DavidDeutsch propose l’idea che un modello di computazione dovesse basarsi su unateoria fisica, e cercò di definire un modello di computazione capace di simula-re qualsiasi sistema fisico. Dato che le leggi della fisica sono, in ultima analisi,quanto–meccaniche, egli considerò un modello di computazione basato sulle leg-gi della meccanica quantistica. Non era questa un’idea del tutto nuova: RichardFeynman nel 1982 ipotizzò che un computer quantistico avrebbe potuto velocizzareconsiderevolmente la simulazione di sistemi quantistici.La traccia di Deutsch non passò inosservata: nel 1994 Peter Shor trovò un algo-ritmo quantistico per fattorizzare i numeri in un tempo polinomiale; anche altrialgoritmi capaci di superare in velocità i corrispettivi algoritmi classici venneroscoperti. Insieme essi suggeriscono che i computer quantistici possano svolge-re e�cientemente alcuni compiti classicamente ritenuti di�cili, contrariamente aquanto a↵erma la tesi di Church–Turing forte. Tuttavia allo stato attuale della co-noscenza non si può escludere l’esistenza di algoritmi classici altrettanto e�cienti,per cui capire l’e↵ettiva potenza computazionale dei computer quantistici è unaquestione ancora aperta.

Bibliografia

[Fox06] Mark Fox. Quantum Optics. Oxford University Press, 2006.

[NC00] Michael A. Nielsen e Isaac L. Chuang. Quantum Computation andQuantum Information. Cambridge University Press, 2000.

4È questa una lezione che non potremo ignorare quando ci occuperemo, nel capitolo 4, dellarealizzazione fisica dei computer quantistici

12

Capitolo 2

Il modello di computazione acircuito quantistico

2.1 Il bit quantistico (qubit)

Un segnale analogico è una grandezza fisica (una tensione, ad esempio) variabilecon continuità nel tempo, atta a convogliare un’informazione (l’ampiezza di un’on-da sonora). L’informazione trasportata da un segnale può essere immagazzinatain dei supporti analogici (l’onda sonora può essere convertita nell’altezza del unsolco di un disco), i quali hanno una risoluzione teoricamente infinita. Nella realtàil rumore limita la fedeltà di queste registrazioni.Per contrasto, la rappresentazione digitale dell’informazione è basata sull’utilizzodi stati discreti di un dispositivo fisico, ed è praticamente esente da rumore.

La rappresentazione binaria utilizza due stati, ai quali ci si riferisce solitamentecon 0 e 1, che costituiscono il contenuto di informazione di un bit. Un bit può esseretradotto fisicamente come, ad esempio, una tensione in un circuito elettronico(bassa 7! 0, alta 7! 1).

L’informatica quantistica non abbandona la rappresentazione digitale dell’in-formazione, tuttavia si avvale di uno dei postulati della meccanica quantisticasecondo il quale un sistema fisico può trovarsi in una sovrapposizione di stati

| i = ↵0 |0i+ ↵1 |1i con |↵0|2 + |↵1|

2 = 1 (2.1)

dove | i è lo stato del sistema, ↵0 e ↵1 sono generici numeri complessi e |0i e|1i sono due vettori (ket) ortonormali appartenenti allo spazio degli stati E delsistema.Ci si può riferire ai numeri ↵0 e ↵1 come ampiezze di probabilità, in quantomisurando un’osservabile A avente |0i e |1i come autovettori, ovvero

A |0i = a0 |0i A |1i = a1 |1i (2.2)

la probabilità di ottenere l’autovalore ai è

| hi| i |2 = |↵i|2 i = 0, 1

L’informazione immagazzinata nello stato quantistico | i viene chiamata qubit(abbreviazione di quantum bit). I due vettori |0i e |1i generano il sottospazio di E

13

Capitolo 2. Il modello di computazione a circuito quantistico

all’interno del quale si svolge la computazione quantistica, e prendono per questoil nome di stati della base computazionale.

Ciò che rende la computazione quantistica un traguardo tecnologico piuttostoche una curiosità matematica è il fatto che i qubit siano degli oggetti fisici.L’esempio più comune di qubit è lo stato di spin di una particella con spin 1/2: labase computazionale è assimilabile in tal caso ai due autovettori di Sz: |+i e |�i.

2.1.1 Rappresentazione di un qubit nella sfera di Bloch

Lo stato | i dato dall’equazione 2.1 può essere riscritto, tenendo conto dellacondizione di normalizzazione, come

| i = ei�✓cos

✓

2|0i+ ei� sin

✓

2|1i

◆(2.3)

In questa scrittura compaiono tre parametri indipendenti che possono variare inaccordo con

0 � < 2⇡ 0 ✓ < ⇡ 0 � < 2⇡

La fase globale ei� non ha e↵etti osservabili nella maggior parte dei casi, e puòpertanto essere ignorata. I parametri ✓ e � possono invece venire associati biuni-vocamente ai punti di una sfera unitaria secondo la legge8>:

x = sin ✓ cos�

y = sin ✓ sin�

z = cos ✓

(2.4)

Figura 2.1: Rappresentazione di un qubit nella sfera di Bloch.

Questa rappresentazione prende il nome di sfera di Bloch (figura 2.1), ed è unimportante ausilio intuitivo per la comprensione della computazione quantistica.

14

2.1. Il bit quantistico (qubit)

2.1.2 Informazione quantistica

La natura intrinsecamente probabilistica della meccanica quantistica rende di�cilerispondere alla domanda su quale sia il contenuto e↵ettivo di informazione di unqubit.

Misurando l’osservabile A di eq. 2.2 possiamo ottenere i due autovalori conprobabilità data dal modulo quadro delle relative ampiezze complesse.In seguito alla misura lo stato | i collassa nell’autovettore corrispondente all’au-tovalore misurato, procurando una perdita irreversibile di informazione.

Da ciò appare chiaro che sebbene i punti sulla sfera di Bloch siano infinitie di conseguenza sia possibile, in principio, codificare in essi una quantità po-tenzialmente illimitata di informazione, tale informazione non risulti facilmenteaccessibile per via della natura probabilistica della misura quantistica e del collas-so della funzione d’onda.È certamente una questione delicata quantificare il contenuto di informazione diun oggetto di cui non è possibile determinare lo stato se non con metodi statistici.

2.1.3 Doppio qubit ed entanglement

Se consideriamo un sistema costituito da due particelle di spin 1/2 avremo chelo spazio degli stati di spin del sistema sarà costituito dal prodotto tensoriale deicorrispettivi spazi di singola particella:

Espin = E1spin ⌦ E

2spin

Una base di questo spazio è costituita dai vettori

|"1i ⌦ |"2i "i = +,�

e pertanto un generico stato del sistema si può scrivere (facciamo la corrispondenza|0i 7! |�i e |1i 7! |+i) come

| i = ↵00 |00i+ ↵01 |01i+ ↵10 |10i+ ↵11 |11i

In generale uno stato di questo tipo non è esprimibile come prodotto tensoriale distati di singola particella: in questi casi le due particelle si dicono entangled.

L’entanglement ha delle implicazioni fisiche e tecnologiche assai rilevanti, chetrovano ragione nel particolare comportamento degli stati entangled in seguito aduna misura eseguita su una delle due particelle.Prendiamo in considerazione dapprima uno stato non-entangled, ovvero

|�i = |�1i ⌦ |�2i , con |�ii 2 Eispin (2.5)

In seguito ad una misurazione sulla particella 1 di una grandezza A1 lo stato simodifica in

|�0i =P1 |�iph�|P1|�i

(2.6)

dove P1 è l’operatore di proiezione sull’autospazio dell’osservabile A1 corrispon-dente all’autovalore misurato.

15


Nel caso non-entangled il proiettore non agisce sullo stato della seconda particella,il quale rimane invariato:

|�0i / P1(|�1i ⌦ |�2i) = (P1 |�1i)⌦ |�2i)

Consideriamo ora invece uno stato entangled, quale ad esempio

| i =|00i � |11ip

2

Questo stato, detto di singoletto, è autovettore dello spin totale S delle due parti-celle. Esso non è esprimibile come prodotto tensoriale nella forma dell’equazione2.5.Supponiamo di misurare la proiezione sull’asse z dello spin della prima particella1.In accordo con la 2.6 lo stato della seconda particella dopo la misura sarà |0i o |1ia seconda che lo spin misurato nella prima sia, rispettivamente, �~/2 o +~/2.

Questo significa che e↵ettuare una misurazione sulla prima particella producedegli e↵etti sulla seconda, la quale può trovarsi anche a grande distanza dal luogodella misura. Ciò può essere detto più elegantemente a↵ermando che la meccanicaquantistica è una teoria fisica non–locale.Bisogna precisare che tramite questo e↵etto non è possibile trasmettere alcu-na informazione, e non si ha dunque una violazione della teoria della relativitàspeciale.

2.1.4 Qubit multipli

Se seguitiamo ad aggiungere altre particelle al nostro sistema quantistico la di-mensione dello spazio degli stati cresce di un fattore 2 per ciascuna particellaaggiuntiva: un insieme di N qubit raccoglie l’informazione contentuta in 2N am-piezze complesse. Per N = 500 questo numero supera il numero stimato degliatomi nell’universo!Da ciò deduciamo che anche un sistema fisico relativamente contenuto evolve inmaniera assai complessa: in esso è racchiuso un enorme potenziale computazionaleche si vorrebbe cercare di sfruttare.

2.2 Circuiti quantistici

In somiglianza con il modello circuitale classico, nell’ambito del quale si posso-no disegnare degli algoritmi utilizzando collegamenti e porte logiche, nel modellocircuitale quantistico si utilizzano elementi analoghi per trasportare e manipolarel’informazione.È utile a questo punto introdurre un formalismo matriciale, secondo il qualeassociamo ad un qubit singolo un vettore colonna

| i = ↵0 |0i+ ↵1 |1i 7!

✓↵0↵1

◆1Ciò è possibile solamente se le due particelle sono distinguibili. Nelle applicazioni questa

condizione è soddisfatta per via della adeguata separazione spaziale delle particelle.

16

2.2. Circuiti quantistici

Figura 2.2: Tre esempi di circuiti quantistici, che illustrano l’azione delle porte logicheX, Z e H (vedi par. 2.2.1).

mentre rappresentiamo le porte agenti su un singolo qubit come matrici 2⇥ 2.Le porte logiche agiscono sui qubit secondo | 0i = U | i; imponendo la conserva-zione della norma dello stato si trova che le porte U accettabili sono unitarie:

h 0| 0i =⌦ ��U †U �� ↵ = h | i = 1 8 | i =) U †U = I (2.7)

Questa è l’unica condizione che si richiede a una porta logica quantistica (il ragio-namento rimane valido anche per qubit multipli).L’unitarietà delle porte logiche ha delle implicazioni importanti per quanto riguar-da l’entropia delle computazioni quantistiche: esse sono sempre invertibili.Un’altra importante proprietà di queste trasformazioni è la linearità.

All’aumentare della dimensione dello spazio computazionale la dimensione deivettori e delle matrici aumenta di conseguenza; la base si ordina convenzionalmentesecondo il sistema di numerazione binario (|0 . . . 00i, |0 . . . 01i, . . . , |1 . . . 11i). Leporte logiche quantistiche su N qubit formano il gruppo U(2N).Dal punto di vista grafico i collegamenti che trasportano i qubit si rappresentanocome delle linee orizzontali, le porte logiche come dei quadrati e i circuiti si leggonoda sinistra a destra. In figura 2.2 riportiamo alcuni prototipi di circuiti quantistici.

Vi sono delle di↵erenze fondamentali tra i circuiti logici classici e quelli quan-tistici. In primo luogo nei circuiti quantistici, non è permesso il feedback: essi sidicono aciclici. In secondo luogo nei circuiti quantistici non può esistere il fanin,operazione in cui due o più qubit sono uniti in uno solo mediante una qualche por-ta logica: operazioni come l’and o l’or classici, che mappano quattro stati (00,01, 10, 11) su due (0, 1) non possono essere invertite, contrariamente a quantorichiesto dalla 2.7.Per ultimo osserviamo come il fanout, tramite il quale il ramo di un circuitologico classico si dirama in due o più bracci, comporti la copia dell’informazionetrasportata dal ramo originale. Come vedremo al paragrafo 3.1.1, la copia deiqubit è fisicamente impossibile, risultato noto come no–cloning theorem.

2.2.1 Porte logiche di singolo qubit

Se nel modello classico l’unica porta logica non banale di singolo bit è la portanot, nel modello quantistico esistono invece diverse operazioni di questo tipo.

17


La naturale estensione del not classico alla logica circuitale quantistica è la portaX, che scambia i coe�cienti dei vettori della base computazionale:

X =

✓0 11 0

◆Il simbolo X è scelto in riferimento alla matrice di Pauli �x ⌘ X. Similmente sihanno

Y =

✓0 �ii 0

◆Z =

✓1 00 �1

◆Altre tre porte molto utilizzate sono la porta di Hadamard, la fase S, e la porta⇡/8 (che si indica anche con T ):

H =1p

2

✓1 11 �1

◆S =

✓1 00 i

◆

T =

✓1 00 ei⇡/4

◆= ei⇡/8

✓e�i⇡/8 00 ei⇡/8

◆

2.2.2 Operatori di rotazione

Le matrici di Pauli hanno delle proprietà notevoli: esse generano gli operatori dirotazione nello spazio degli stati dello spin.Ricordiamo che l’operatore di rotazione di un sistema quantistico è

Rû(↵) = exp

✓1

i~↵J · û◆

(2.8)

Esso, agendo su un ket | i, ruota il sistema di un angolo ↵ intorno all’asse direttolungo il versore û. J è il momento angolare totale del sistema, dato, nel caso diuna singola particella dotata di spin, da

J = L+ S

con L momento angolare orbitale della particella. Siccome si ha che [L,S] = 0l’operatore della 2.8 si può riscrivere come

Rû(↵) = exp

✓1

i~↵L · û◆exp

✓1

i~↵S · û◆

il quale è formalmente il prodotto tensoriale di due operatore agenti, rispettiva-mente, nello spazio degli stati orbitale e in quello dello spin.Calcoliamo questi operatori limitandoci a considerare la parte relativa allo spin.Sfruttando l’uguaglianza

exp(iAx) = cos(x)I + i sin(x)A x 2 R (2.9)

18


possiamo ottenere le rotazioni del sistema attorno agli assi cartesiani

Rx(↵) = e�i↵X/2 =

✓cos ✓2 �i sin

✓2

�i sin ✓2 cos✓2

◆Ry(↵) = e

�i↵Y/2 =

✓cos ✓2 � sin

✓2

sin ✓2 cos✓2

◆Rz(↵) = e

�i↵Z/2 =

✓e�i✓/2 00 ei✓/2

◆ (2.10)

e anche

Rû(↵) = exp(�i↵û · �/2) = cos⇣↵2

⌘I � i sin

⇣↵2

⌘(uxX + uyY + uzZ) (2.11)

dove ~2� = S. Questi operatori sono unitari, e rappresentano dunque delle valideporte logiche quantistiche.

2.2.3 Interpretazione geometrica degli operatori di rota-zione nella sfera di Bloch

Mostriamo ora che gli operatori dell’equazione 2.10 agiscono su un qubit 2.3 ruo-tando il corrispondente vettore 2.4 sulla sfera di Bloch.Richiamiamo innanzitutto la teoria delle particelle quantistiche di spin 1/2: lostato più generale di tali particelle è esprimibile nella forma 2.3, che è autovettoredi S · û se il versore u è dato dalla 2.4 (l’autovalore corrispondente è +~/2). Siavrà perciò, indicando con |ui lo stato del sistema,

(S · û) |ui =~2|ui

E↵ettuando una rotazione R sul sistema e ruotando corrispondentemente lo stru-mento di misura dello spin in modo che la posizione relativa non sia mutata, ci sidovrà trovare in una configurazione fisicamente equivalente alla precedente. Dovràperciò valere

(S · Rû)R |ui =~2R |ui

nella quale R è la matrice di rotazione classica corrispondente all’operatore R.Vediamo cos̀ı che lo stato R | i deve essere autovettore di S · Rû di autovalorepositivo, e dunque a tale stato sarà associato il vettore Rû nella sfera di Bloch,come volevasi dimostrare.

Oltre all’appena discussa interpretazione geometrica, gli operatori di rotazio-ne 2.10 hanno un ruolo importante nella teoria delle porte logiche quantistiche:ciascun operatore unitario di dimensione 2 può infatti essere scritto come

U = ei↵Rû(✓)

Precedentemente abbiamo trascurato la fase globale dei qubit in quanto fisicamen-te non rilevante. Nel caso delle porte logiche vale un discorso analogo: anche se la

19


dimensione di una porta U è minore della della cardinalità della base computazio-nale, ovvero se essa agisce solo su un sottoinsieme dei qubit del circuito quantistico,un’eventuale fase globale di U non può introdurre degli sfasamenti relativi tra leampiezze complesse:

(ei↵ |ai)⌦ |bi = ei↵(|ai ⌦ |bi)! |ai ⌦ |bi

2.2.4 Decomposizione in rotazioni delle porte logiche disingolo qubit

Dimostriamo ora alcuni metodi, di cui ci avvaleremo nel seguito, che permettonodi scrivere un generico U2⇥2 in termini di operatori di rotazione.

Dimostriamo dapprima il teorema di decomposizione Z-Y : dato un operatoreunitario U esistono sempre quattro numeri reali ↵, �, � e � tali che

U = ei↵Rz(�)Ry(�)Rz(�) (2.12)

Eseguendo la moltiplicazione al secondo membro si trova

U =

ei(↵�

�2�

�2) cos �2 �e

i(↵��2+�2) sin �2

ei(↵+�2�

�2) sin �2 e

i(↵+�2+�2) cos �2

!la quale è facilmente riconducibile alla seguente parametrizzazione del gruppo U(2)

ei�✓

ei�1 cos ✓ ei�2 sin ✓�e�i�2 sin ✓ e�i�1 cos ✓

◆Il teorema ha il seguente corollario: per ciascun operatore su singolo qubit U

esistono tre matrici A, B e C tali che ABC = I e U = ei↵AXBXC.La dimostrazione procede per costruzione: utilizzando la notazione del precedenteteorema poniamo

A = Rz(�)Ry⇣�2

⌘B = Ry

⇣�

�

2

⌘Rz

✓�

� + �

2

◆C = Rz

✓� � �

2

◆Tenendo conto delle proprietà Rû(✓) + Rû(�) = Rû(✓ + ) e Rû(0) = I si puòverificare la prima parte della tesi.Per la seconda si utilizza l’identità XYX = �Y che implica XRy(✓)X = Ry(�✓);quest’ultima si verifica per sostituzione sfruttando la 2.9.Sostituendo le matrici A, B e C nell’espressione di U si ottiene

XBX = XRy⇣�

�

2

⌘XXRz

✓�

� + �

2

◆X = Ry

⇣�

�

2

⌘Rz

✓� + �

2

◆Quindi

AXBXC = Rz(�)Ry⇣�2

⌘Ry⇣�2

⌘Rz

✓� + �

2

◆Ry

✓� � �

2

◆= Rz(�)Rx(�)Rz(�)

come volevasi dimostrare.La 2.12 si può estendere a due assi arbitrari distinti n̂ e m̂:

U = ei↵Rn̂(�)Rm̂(�)Rn̂(�) (2.13)

20


Figura 2.3: Porta logica cnot.

2.2.5 Operazioni controllate

Per operazioni controllate intendiamo dei processi algoritmici nei quali una certaoperazione viene eseguita condizionalmente a certi requisiti. Queste operazionicondizionali sono fondamentali sia nella logica classica che in quella quantistica.La più semplice di queste porte logiche in ambito quantistico è il cnot, la cuiazione sulla base computazionale è data da

|ci |ti 7! |ci |t� ci t,c = 0,1

dove indichiamo con il simbolo � la somma modulo 2. Il primo qubit viene dettoqubit di controllo in quanto la porta di singolo qubit X viene applicata al qubit|ti (target qubit) solo quanto c = 1.La rappresentazione matriciale del cnot è0BB@

1 0 0 00 1 0 00 0 0 10 0 1 0

1CCAe il suo simbolo circuitale è indicato in figura 2.3.

Estendendo questa idea, è possibile e↵ettuare delle operazioni U qualsiasicontrollate:

|ci |ti 7! |ciU c |ti

che si indicano con il simbolo di figura 2.4.

Figura 2.4: Operazione U controllata.

Più in generale il numero di qubit di controllo N e quello dei qubit bersaglioK può essere scelto a piacere.L’operazione controllata nel suo insieme si scrive come

CN(U) |x1x2 . . . xNi | i = |x1x2 . . . xNiUx1x2...xN

| i

21


Figura 2.5: Operazione controllata Cn(U), con n qubit di controllo e U matrice unitaria2k ⇥ 2k.

Figura 2.6: Questa porta logica inverte il qubit inferiore quando quello superiore è|0i. Si ricava dal tradizionale cnot, invertendo il qubit di controllo prima e dopo la suaapplicazione.

Un esempio grafico di queste porte è riportato in figura 2.5.Nel seguito assumeremo K = 1.

È utile anche definire delle porte controllate “inverse”, nelle quali l’operatoreU viene applicato ai qubit bersaglio solo se il qubit di controllo è 1 (fig. 2.6).

2.2.6 Implementazione di operazioni controllate

Mostriamo in questo paragrafo come sia possibile realizzare una generica opera-zione controllata CN(U) utilizzando solamente porte logiche di singolo qubit ecnot.

Figura 2.7: Due circuiti equivalenti per l’applicazione controllata di una fase ei↵.

22


Figura 2.8: Applicazione di porte controllate C1(U) qualsiasi mediante cnot e portedi singolo qubit.

Figura 2.9: Applicazione di porte controllate C2(U) qualsiasi mediante cnot e porteC1(V ). Vale la relazione V 2 = U .

Per prima cosa analizziamo il circuito a sinistra in figura 2.7: esso applica unafase globale ei↵ condizionatamente al valore del primo qubit.Dato che

ei↵ |1ti = (ei↵ |1i)⌦ |ti

questa porta può essere realizzata, in un’altra maniera, utilizzando una singolaoperazione U 0 che agisce invece sul qubit di controllo (vedi ancora fig. 2.7 a destra).

Per costruire una qualsiasi operazione C1(U) ci si serve del precedente risultatounito al teorema di decomposizione 2.12, come dal circuito in figura 2.8: quandoil primo qubit è 1 allora U = ei↵AXBXC viene applicata al secondo. In casocontrario agisce solamente ABC = 1, e non si ha alcuna modifica dei qubit.

Occupiamoci ora delle porte C2(U). Esse richiedono la disponibilità di unaporta V scelta in modo che V 2 = U . Il circuito appropriato è rappresentato infigura 2.9. Facendo uso della logica booleana possiamo calcolare lo stato finale |fidel qubit bersaglio:

|fi = V c2�V †�c1�c2 V c1 |ii =

8>>>>>:V 2 |ii se c1 = c2 = 1

V †V |ii se c1 = 1, c2 = 0

V V † |ii se c1 = 0, c2 = 1

|ii se c1 = c2 = 0

Notiamo che il secondo cnot che agisce sui qubit di controllo non ha alcun e↵ettosu |fi: esso ha la funzione di ripristinare c2 al suo valore iniziale (i qubit di controllonon devono venire modificati dalla porta controllata).

Utilizzando l’operatore C2(X), detto porta di To↵oli, è possibile sommare iqubit modulo 2, rendendo possibile la realizzazione di porte controllate qualsiasi

23


Figura 2.10: Circuito per la realizzazione di porte controllate CN (U). Sono necessarieC2(X) (porta di To↵oli) e C1(U). È rappresentato il caso N = 5.

Figura 2.11: Simbolo circuitale della misura su un qubit.

come da figura 2.10. Ancora una volta, le porte che si trovano a destra di U nelcircuito servono a ripristinare i qubit di controllo.In questo schema, concettualmente semplice, sono necessari N � 1 qubit di lavoroper memorizzare i risultati intermedi delle somme; tuttavia è possibile disegnaredei circuiti più ra�nati che non fanno uso di qubit di lavoro.

Siamo ora giunti al termine di una dimostrazione completa di come eseguiredelle operazioni controllate CN(U) utilizzando solamente cnot e porte logiche disingolo qubit. Analizziamo ciascun elemento del circuito 2.10:

• la porta U controllata si può scomporre in cnot e operatori di singolo qubit,come dal circuito 2.8.

• le porte di To↵oli si implementano mediante lo schema 2.9 ponendo U =X, dunque V =

p

X = (1 � i)(1 + iX)/2. Sono necessari il cnot edoperatori controllati di singolo qubit; per questi ultimi ci riconduciamo alcaso precedente.

Come a↵ermato al paragrafo 2.2.5, ci siamo limitati al caso di U agenti susingolo qubit (K = 1). Per K qualsiasi il risultato trovato continua ad esserevalido; i metodi da utilizzare sono simili a quelli appena spiegati.

2.2.7 Misurazioni

Come detto nei paragrafi 2.1 e 2.1.3, la misura di un qubit comporta il collassodello stesso in uno stato puro e una perdita di informazione. Le misurazioni sulla

24


Figura 2.12: Applicazione del principio della misura ritardata.

base computazionale sono utilizzate nei circuiti quantistici per convertire dei qubitin dei bit probabilistici 2 .Esse si indicano con il simbolo di figura 2.11, nel quale i rami doppi trasportanobit classici.

Le misurazioni in un circuito quantistico obbediscono a due regole:

Principio della misura ritardata: le misurazioni possono sempre essere spo-state da uno stadio intermedio di un circuito quantistico alla fine dello stesso;se il risultato della misura viene utilizzato all’interno del circuito, allora l’o-perazione controllata classicamente può essere rimpiazzata da un operazionecontrollata quantisticamente.

La ragione fisica di questo primo principio è da ricercarsi nell’entanglement.Il circuito di figura 2.12 può essere condensato nella frase “le misurazioni commu-tano con i controlli”.Ammettiamo che lo stato iniziale del sistema sia dato dalla 2.1. Possiamo vederecome nel primo caso (misura ritardata, disegno a sinistra) la perdita dell’infor-mazione associata alle ampiezze corrispondenti allo stato del primo qubit che nonviene misurato sia causata a posteriori dalla proiezione del primo qubit sullo sta-to che viene misurato. Chiamiamo | 0i lo stato del sistema dopo l’applicazionedell’operazione controllata:

| 0rit.i = C(U) | i = ↵00 |00i+ ↵01 |01i+ ↵010 |10i+ ↵

011 |11i

in quanto l’operazione agisce solo sugli stati per i quali il qubit di controllo (rap-presentato dal primo delle due cifre binarie) è 1. Se la misura finale sul primoqubit fornisce l’autovalore legato a |0i, lo stato finale del sistema sarà

| 00rit.i =1p

|↵00|2 + |↵01|2(↵00 |00i+ ↵01 |01i) (2.14)

nell’altro caso avremo invece

| 00rit.i =1p

|↵010|2 + |↵011|

2(↵010 |10i+ ↵

011 |11i) (2.15)

2Con “misurazione sulla base computazionale” intendiamo la misura di un osservabile aventei ket |0i e |1i come autovettori.

25


Per quanto riguarda la misura non ritardata (disegno di sinistra in figura 2.12) laproiezione della funzione d’onda avviene prima, lasciando il sistema nello stato

| 0i =1p

|↵00|2 + |↵01|2(↵00 |00i+ ↵01 |01i) (2.16)

oppure nello stato

| 0i =1p

|↵10|2 + |↵11|2(↵10 |10i+ ↵11 |11i) (2.17)

Applicando C(U) alle 2.16 e 2.17 si ritrovano esattamente le 2.14 e 2.15, rispetti-vamente (teniamo presente che per l’unitarietà di U deve valere |↵10|2 + |↵11|2 =|↵010|

2 + |↵011|2).

Prestiamo attenzione al fatto che nel caso della misura implicita, prima dellamisurazione l’informazione corrispondente a entrambe le possibilità (collasso in |0io in |1i del primo qubit) è contenuta nei due qubit.Si tratta di un aspetto peculiare della meccanica quantistica che è possibile sfrut-tare a fini algoritmici (vedi parallelismo quantistico, §3.2). Esso si manifesta spe-rimentalmente in varianti dell’interferenza da doppia fenditura quali il quantumeraser ed esperimenti ad esso a�ni.

Principio della misura implicita: si può assumere di misurare ciascun ramonon terminato (ovvero che non si conclude con una misurazione) di uncircuito quantistico senza perdita di generalità.

Illustriamo più in dettaglio il senso di questo secondo principio. Supponiamo diavere un sistema di due qubit descritti da un operatore densità

⇢k = | kih k|

il quale descrive uno stato puro.Chiamiamo Pi l’operatore di proiezione sullo stato |ii del primo qubit:

Pi = |iihi|⌦ 1

E↵ettuando una misura sulla base computazionale del primo qubit l’operatoredensità si trasforma in

⇢0k,|ii =Pi | kih k|Pih k|Pi| ki

se la misura ha dato risultato i.Se ignoriamo il risultato della misurazione la nostra conoscenza dello stato delsistema si può racchiudere in

⇢0k = tr(⇢kP0)⇢0k,|0i + tr(⇢kP1)⇢

0k,|1i

ovvero, essendo tr(⇢kPi) = h k|Pi| ki,

⇢0k = P0 | kih k|P0 + P1 | kih k|P1 (2.18)

26

2.3. Un insieme di porte logiche quantistiche universali

Nel caso generale abbiamo che ⇢ descrive una miscela statistica di stati:

⇢ =Xk

pk⇢k

Secondo la 2.18 avremo che l’operatore densità dopo la misura sarà ora

⇢0 =Xk

pk⇢0k =

Xk

⇥pk(P0 | kih k|P0 + P1 | kih k|P1)

⇤(2.19)

= P0⇢P0 + P1⇢P1 (2.20)

Dimostriamo che la statistica delle misurazioni sul secondo qubit non è statamodificata dalla misurazione e↵ettuata sul primo, ovvero che:

tr1 ⇢ = tr1 ⇢0

Indichiamo con |uii i vettori della base del primo qubit e con |vii quelli del secondo.Per definizione abbiamo

(tr1 ⇢)nn0 =Xp

hupvn|⇢|upvn0i

Confrontiamo questo operatore con quello ottenuto da ⇢0:

(tr1 ⇢0)nn0 =

Xp

hupvn|(P0⇢P0 + P1⇢P1)|upvn0i =

= hu0vn|⇢|u0vn0i+ hu1vn|⇢|u1vn0i =Xp

hupvn|⇢|upvn0i (2.21)

che è quanto volevamo dimostrare.

2.3 Un insieme di porte logiche quantistiche uni-versali

In questo paragrafo dimostreremo che le porte logiche H, S, cnot e T formano uninsieme di porte universali, ovvero che qualunque circuito quantistico può essererealizzato (o, più propriamente, approssimato) utilizzando gli operatori suddetti.Questo risultato è fondamentale dal punto di vista della realizzazione sperimentaledei computer quantistici, in quanto nella realtà si ha a disposizione un numerofinito di operazioni e↵ettuabili sul sistema fisico.

2.3.1 Decomposizione in matrici unitarie a due livelli

Per prima cosa dimostriamo che qualunque matrice unitaria Ud⇥d può essere scrittacome prodotto di matrici unitarie a due livelli, ovvero matrici unitarie che agisconosolamente nel sottospazio generato da due vettori qualsiasi della base computazio-nale.Consideriamo il caso d = 3; dimostreremo che

U3U2U1U = 1

27


con U3, U2 e U1 matrici unitarie a due livelli. Da ciò segue che U = U†1U

†2U

†3 .

Sia

U =

0@a d gb e hc f j

1AApplichiamo ad U una trasformazione unitaria U1 che annulli il secondo terminedella prima colonna (se tale termine è già nullo possiamo porre U1 = 1):0BB@

a⇤p

|a|2+|b|2b⇤

p

|a|2+|b|20

�bp

|a|2+|b|2a

p

|a|2+|b|20

0 0 1

1CCA0@a d gb e hc f j

1A =0@a0 d0 g00 e0 h0c0 f 0 j0

1AAllo stesso modo annulliamo il terzo termine della prima colonna:0BB@

a0⇤p

|a0|2+|c0|20 c

0⇤p

|a0|2+|c0|2

0 1 0c0

p

|a0|2+|c0|20 �a

0p

|a0|2+|c0|2

1CCA0@a0 d0 g00 e0 h0c0 f 0 j0

1A =0@1 d00 g000 e00 h000 f 00 j00

1AAl secondo membro compare un prodotto di matrici unitarie, che è a sua voltaunitario. Per questo deve essere d00 = g00 = 0 (le colonne e le righe di una matriceunitaria hanno norma unitaria).

A questo punto abbiamo ottenuto una matrice diagonale a blocchi, e possiamoripetere il procedimento per il secondo blocco trovando infine la matrice identità.Il metodo si può estendere a matrici di dimensione maggiore; in generale per matricid–dimensionali sono necessarie al più d(d � 1)/2 matrici Ui. In termini di qubit,essendo d = 2N , il numero massimo di trasformazioni da utilizzare è 2N�2(2N �1).

2.3.2 Applicazione di porte unitarie a due livelli qualsiasimediate porte di singolo qubit

Cerchiamo ora un metodo che ci permetta di applicare ad un sistema di N qubituna trasformazione unitaria a due livelli utilizzando le porte logiche e le tecnichedi cui abbiamo parlato al §2.2.Ricordiamo che una matrice unitaria a due livelli U appare come0BB@

1 0 0 00 a 0 c0 0 1 00 b 0 d

1CCAPossiamo sempre costruire una matrice bidimensionale Ũ estraendo la parte nonbanale di U :

Ũ =

✓a cb d

◆L’idea della procedura che utilizzeremo è quella di e↵ettuare degli scambi di

ampiezze dei vettori della base computazionale in modo da ridurre il problema

28


all’applicazione (condizionata) dell’operatore Ũ su un singolo qubit, quindi di ese-guire gli scambi inversi per riavere infine l’ordine originale.Se ad esempio la matrice U agisce solamente sui vettori |00010i e |10101i dellabase computazionale, identificati rispettivamente dalle stringhe binarie x1 = 00010e xm = 10101, facciamo in modo di trasferire l’ampiezza associata a |x1i ad unvettore |xm�1i tale che xm�1 e xm di↵eriscono soltanto per l’i–esima cifra.Possiamo quindi applicare Ũ all’i–esimo qubit e ripristinare infine l’ordine inizialedelle ampiezze.

La sequenza di scambi più rapida è un codice di Gray: con questa dicitura siindica genericamente una successione di stringhe binarie nella quale due stringheadiacenti di↵eriscono soltanto per un bit. Nel caso in questione una sequenza delgenere è ad esempio

x1 = 00010

x2 = 00011

x3 = 00001

x4 = 00101

x5 = 10101

(2.22)

Ora ci troviamo di fronte al problema di come e↵etture lo scambio di ampiezzefra due vettori |xni e |xn+1i aventi associate le stringhe binarie xn e xn+1 chedi↵eriscono solamente nell’k–esimo bit. Ciò si può eseguire applicando allo stato| i del sistema, dato da

| i =Xj

↵xj |xji

(la somma è estesa a tutte le stringhe binarie xj possibili) l’operatore X sull’k–esimo qubit, condizionalmente al valore delle cifre identiche delle due stringhebinarie.

Illustriamo la procedura completa nel caso di un sistema di N = 3 qubit.Supponiamo di voler applicare l’operatore

U =

0BBBBBBBBBB@

a 0 0 0 0 0 0 c0 1 0 0 0 0 0 00 0 1 0 0 0 0 00 0 0 1 0 0 0 00 0 0 0 1 0 0 00 0 0 0 0 1 0 00 0 0 0 0 0 1 0b 0 0 0 0 0 0 d

1CCCCCCCCCCA(2.23)

che agisce solamente sugli stati |000i e |111i. Scriviamo il codice di Gray:

A B C

x1 = 0 0 0x2 = 0 0 1x3 = 0 1 1x4 = 1 1 1

29


Figura 2.13: Circuito che applica la trasformazione U data dalla 2.23.

Il primo scambio si e↵ettua mediante un operatore X sul qubit C condizionato daA = B = 0; il secondo e ultimo scambio applica X al qubit B condizionalmente aA = 0 e C = 1.Ora procediamo applicando Ũ al qubit A condizionalmente a B = C = 1, quindie↵ettuiamo le operazioni di scambio in ordine inverso. Il circuito adatto è disegnatoin figura 2.13.

Riassumiamo quanto abbiamo ottenuto finora. Grazie ai risultati del paragrafo2.2.6 sappiamo realizzare tutti gli elementi contenuti nel circuito 2.13 utilizzandocnot e porte logiche di singolo qubit. D’altra parte tramite questo circuito riu-sciamo a realizzare qualsiasi trasformazione U , scomponendola in matrici a duelivelli. Pertanto riusciamo ad applicare qualsiasi matrice U ai qubit limitandociad usare cnot e porte logiche singole.

2.3.3 Approssimazione degli operatori su singolo qubit

Per arrivare al traguardo enunciato all’inizio dell’§2.3 ci resta da dimostrare checiascuna trasformazione unitaria su singolo qubit si può approssimare, con unerrore piccolo a piacere, tramite un’insieme finito di porte logiche su singolo qubit.Tale insieme non è unico; nel nostro caso sarà formato da

H S cnot ⇡/8

Errore di approssimazione

Dato che stiamo parlando di un’approssimazione, cerchiamo per prima cosa unaquantità che ci possa dare un indicazione dell’errore intrinseco commesso. Chia-miamo U l’operatore di interesse e V la sua approssimazione. Definiamo l’erroredi approssimazione come

E(U, V ) = max| ik(U � V ) | i k (2.24)

dove il massimo coinvolge tutti i possibili stati | i della base computazionale.Per convincerci che la 2.24 rappresenta una buona stima dell’errore, dimostria-mo che, essendo PU la probabilità di ottenere una data grandezza misurando unosservabile A nello stato U | i e PV il corrispettivo per lo stato V | i, vale larelazione

|PU � PV | 2E(U, V ) (2.25)

30


Secondo questa definizione la somiglianza tra le due trasformazioni è quantificatadall’a�nità delle statistiche delle misurazioni sugli stati trasformati.Calcoliamo il primo membro della 2.25:

|PU � PV | = | h |U†MiU | i � h |V

†MiV | i |

Stiamo indicando con Mi l’operatore di proiezione sull’autostato |�ii corrispon-dente al risultato della misura dell’osservabile A. Ponendo ora |�i = (U � V ) | i— si noti che

ph�|�i = E(U, V ) — possiamo scrivere

|PU � PV | = | h |U†Mi |�i+ h�|MiV | i |

| h |U †Mi |�i |+ | h�|MiV | i |

Sfruttiamo ora la disuguaglianza di Cauchy-Schwarz

|PU � PV | kM†i U | i k · k |�i k+ k |�i k · kMiV | i k (2.26)

Calcoliamo

kM †i U | i k = h |U†MiM

†i U | i =

Xj

h |U †Mi |�ji h�j|M†i U |�i

= h |U † |�ii h�i|U | i = | h�i|U | i |2 1

dove abbiamo fatto uso della relazione di completezza dell’osservabileA,P

j |�jih�j| =1, dell’unitarietà di U e della normalizzazione di | i. Allo stesso modo si trovache kMiV | i k 1.Tornando ora alla 2.26 abbiamo

|PU � PV | k |�i k+ k |�i k

= 2E(U, V )

che è la tesi 2.25.Nel caso volessimo approssimare, piuttosto che una porta logica singola, una

successione di operatori U1, U2, . . ., Um mediante la sequenza V1, V2, . . ., Vm alloral’errore totale commesso è limitato superiormente dalla somma degli errori deglioperatori singoli:

E(UmUm�1 . . . U1, VmVm�1 . . . V1) mXj=1

E(Uj, Vj)

Dimostriamo questa a↵ermazione per m = 2; il caso generale segue per induzione.

E(U2U1, V2V1) = k(U2U1 � V2V1) | i k

= k(U2U1 � V2U1) | i+ (V2U1 � V2V1) | i k

k(U2 � V2)U1 | i k+ kV2(U1V1) | i k

E(U2, V2) + E(U1, V1)

Dunque nel caso volessimo approssimare un circuito contenente m porte lo-giche di singolo qubit mantenendo le probabilità corrette entro una tolleranza�, dovremmo fare in modo che E(Uj, Vj) �/(2m) per ciascuna porta logica(j = 1, 2, . . . ,m).

31


Metodo di approssimazione

Dimostriamo che H e T possono essere usati per approssimare qualsiasi U2⇥2.Da quanto esposto al §2.2 possiamo vedere come T rappresenti, a meno di una faseglobale, una rotazione di ⇡/4 attorno all’asse z nella sfera di Bloch. SimilmenteHTH è una rotazione dello stesso angolo attorno all’asse x. Componendo questedue rotazioni se ne ottiene una terza:

exp⇣�i⇡

8Z⌘exp

⇣�i⇡

8X⌘=hcos

⇡

81� i sin

⇡

8Zi h

cos⇡

81� i sin

⇡

8Xi

(2.27)

= cos2⇡

81� i

hcos

⇡

8(X + Z) + sin

⇡

8Yisin

⇡

8(2.28)

Riferendoci alla 2.11 possiamo ricondurre l’espressione di sopra ad una rotazioneattorno al versore

n̂ =1p

1 + cos2 ⇡8

⇣cos

⇡

8, sin

⇡

8, cos

⇡

8

⌘rotazione di un angolo ✓ che soddisfa(

cos ✓2 = cos2 ⇡

8

sin ✓2 = sin⇡8

p1 + cos2 ⇡8

Questo sistema ha soluzione, in quanto quadrando e sommando i secondi membridelle equazioni si trova l’unità. Chiamiamo Rn̂(✓) l’operatore 2.28.Secondo alcuni teoremi della teoria dei numeri si può dimostrare che ✓ è un multiploirrazionale di 2⇡. Questo permette di approssimare, con un errore � arbitraria-mente piccolo, qualsiasi rotazione attorno a n̂ tramite applicazioni ripetute dell’o-peratore Rn̂(✓). Per dimostrarlo definiamo ✓k = (k✓) mod 2⇡, dove k = 1, . . . , N .Si dovrà avere che

mini,j

|✓i � ✓j| 2⇡

Ni,j = 1, . . . , N

in quanto in un insieme di N punti su una circonferenza, la distanza angolareminima tra due punti consecutivi non può superare 2⇡/N radianti. Se assumiamoi > j allora ✓i�j 2⇡/N , pertanto, fissato i� j, l’insieme di angoli

{✓l(i�j) : l soddisfa ✓l(i�j) < 2⇡}

permette di approssimare qualunque rotazione con un errore � < ✓i�j 2⇡/N .Pertanto è sempre possibile trovare un intero n tale che

E(Rn̂(↵), Rn̂(✓)n) <

"

3(2.29)

A questo punto se riusciamo a trovare un’altra rotazione del genere attornoa un’asse m̂ 6= n̂ possiamo approssimare qualsiasi porta logica di singolo qubitmediante la 2.13. Ricordando la 2.8 possiamo trovare che

HRn̂(✓)H = Rm̂(✓)

32


dove

m̂ =1p

1 + cos2 ⇡8

⇣cos

⇡

8,� sin

⇡

8, cos

⇡

8

⌘Mediante questo operatore possiamo approssimare qualunque Rm̂(↵) con un errore

E�Rm̂(↵), Rm̂(✓)

n�= E

�HRn̂(↵)H,(HRn̂(✓)H)

n)�

= E�HRn̂(↵)H,HRn̂(✓)

nH)�

= E�Rn̂(↵), Rn̂(✓)

n)�<"

3

dato che H = H† = H�1 e per via della 2.29.In conclusione data una certa tolleranza ", possiamo contare sull’esitenza di

tre numeri interi n1, n2 e n3 per i quali

E(U,Rn̂(✓)n1HRn̂(✓)

n2HRn̂(✓)n3) < "

Per comporre l’insieme di porte quantistiche universali aggiungiamo agli ope-ratori H e T il cnot, necessario per le tecniche di decomposizione dei paragrafiprecedenti. La fase S viene anch’essa inclusa nell’insieme in quanto permette direndere la computazione quantistica tollerante ai guasti (fault tolerant), ovvero peracconsentire il calcolo anche in presenza di rumore. Tratteremo questo argomentoal capitolo 4.2.

E�cienza dell’approssimazione

Discutiamo ora brevemente di quanto e�cientemente lavori il metodo di approssi-mazione sviluppato.Se assumiamo ragionevolmente che i punti relativi agli angoli ✓k si dispongano piùo meno uniformemente lungo la circonferenza, allora sarebbero necessari, secondola notazione del precedente paragrafo, ⇥(N) applicazioni di Rn̂(✓) per approssi-mare un’arbitraria rotazione a meno di un angolo � < 2⇡/N . In termini dellatolleranza " il numero di porte necessarie è dunque ⇥(1/").Se volessimo approssimare un circuito contenente m porte logiche di singolo bite cnot tramite il nostro insieme universale entro un errore " dovremmo appros-simare ciascuna delle m porte con una tolleranza "/m. Il numero di operazioninecessarie sarebbe perciò ⇥(m2/"): esso cresce quadraticamente con la grandezzadel circuito, da cui possiamo dedurre che l’approssimazione sia fattibile in manierae�ciente.

In termini più rigorosi, esiste un teorema di Solovay-Kitaev che a↵erma cheun operatore di singolo qubit arbitrario può essere approssimato col nostro insie-me con un numero di operazioni O(logc(1/")), dove c è una costante vicina a 2.Segue che un circuito contenente soltanto cnot e operatori di singolo qubit siapprossima con O(m logc(m/")). Si tratta di un andamento polilogaritmico percui l’approssimazione può considerarsi e�ciente.

La situazione si prospetta meno entusiasmante se includiamo nel circuito chevorremmo costruire operatori U di dimensione arbitraria: si può dimostrare che laloro realizzazione mediante i metodi descritti richiede un numero di trasformazioniche cresce esponenzialmente con il numero di qubit del sistema.

33

Bibliografia

Bibliografia

[NC00] Michael A. Nielsen e Isaac L. Chuang. Quantum Computation andQuantum Information. Cambridge University Press, 2000.

34

Capitolo 3

Algoritmi quantistici

Dopo la panoramica sui circuiti quantistici, tratteremo in questo capitolo alcunialgoritmi particolarmente istruttivi per quanto riguarda la manipolazione delleinformazioni praticabile per mezzo della meccanica quantistica.

3.1 Teletrasporto quantistico

Il primo argomento di questo capitolo non è un’algoritmo nel senso stretto deltermine, ma piuttosto un interessante applicazione dell’elaborazione quantisticadell’informazione e in particolare dell’entanglement.

3.1.1 La questione della copia dei qubit

Approfondiamo il problema della copia dei qubit citato alla fine del paragrafo 2.2.Nel caso della logica classica è senza dubbio possibile creare una porta logica aventedue bit, x e y, come entrate e altrettante uscite che esegua

x 7! x y 7! x� y (3.1)

Trattando l’entrata y come un ancilla qubit, ovvero come un qubit il cui valoreè fissato indipendentemente dall’input del circuito, possiamo creare mediante taleporta logica un circuito che copia il bit in ingresso x. Ponendo y = 0 nella 3.1otteniamo infatti

x 7! x 0 7! x� 0 = x (3.2)

L’operazione 3.1 ricorda il cnot quantistico, che esegue |xi |yi 7! |xi |x� yi. Sia-mo per questo tentati di convertire il circuito di copia classico nel suo equivalentequantistico (figura 3.1).Tuttavia questo circuito non e↵ettua una copia vera e propria: se il qubit dacopiare (primo input) dato da | i = a |0i + b |1i controlla un cnot che agiscesull’ancilla qubit (secondo input) |0i, si ottiene come output sul secondo qubit lostato a |00i+ b |11i che è diverso in generale da

| i | i = a2 |00i+ ab |01i+ ab |10i+ b2 |11i

Come già menzionato, esiste un teorema (no–cloning theorem) che impediscela copia di un generico stato quantistico. Per dimostrarlo consideriamo un sistema

35

Capitolo 3. Algoritmi quantistici

Figura 3.1: Circuito classico per la copia di un bit (a sinistra) convertito in circuitoquantistico (a destra).

quantistico composto da due sottosistemi identici ma separati, descritti dagli stati| i e |si. Il primo di questi rappresenta, nel caso particolare della copia dei qubit,il qubit da copiare; il secondo è lo stato bersaglio sul quale vorremmo copiare | i.Supponiamo che esista una trasformazione unitaria U tale che

U | i ⌦ |si = | i ⌦ | i (3.3)

Sostituendo nella 3.3 a | i due stati arbitrari |�1i e |�2i e facendo il prodottoscalare di ambo i membri delle due espressioni si trova

(h�1|⌦ hs|)U†U(|�2i ⌦ |si) = (h�1|⌦ h�1|)(|�2i ⌦ |�2i)

h�1|�2i = (h�1|�2i)2

che ha per soluzioni h�1|�2i = 0 e h�1|�2i = 1. Di conseguenza un ipoteticodispositivo di copia potrebbe funzionare a dovere solo per un certo insieme di statidi input tra loro ortogonali: un processo per la copia di stati arbitrari non puòesistere.Ciò che è invece possibile è trasferire lo stato del primo sottostistema sul secondo.Se i due sottosistemi sono spazialmente distanti il trasferimento prende l’accezionedi teletrasporto. Tale nomenclatura è per certi aspetti impropria, dato che, comevedremo, è necessario per compiere il trasferimento uno scambio aggiuntivo diinformazione classica tra i due siti distanti — ribadiamo che l’entanglement nonviola la relatività speciale; tuttavia il termine teletrasporto sottolinea il fatto cheil trasferimento avvenga in assenza di un canale di comunicazione quantistico cheacconsenta lo spostamento fisico (nella fattispecie lo spostamento di uno spin inuno stato 2.1 o di un fotone con il suo stato di polarizzazione) dell’informazionequantistica.

3.1.2 Stati di Bell

Prima di analizzare lo schema circuitale del teletrasporto quantistico introduciamoi cos̀ıddetti stati di Bell (noti anche come stati o coppie di EPR, per via delloro utilizzo nell’omonimo paradosso): si tratta di quattro stati massimamenteentangled di due qubit.

|�00i =|00i+ |11ip

2|�01i =

|01i+ |10ip

2

36

3.1. Teletrasporto quantistico

Figura 3.2: Circuito per la conversione degli stati della base computazionale di duequbit in stati di Bell.

Figura 3.3: Circuito per il teletrasporto quantistico.

|�10i =|00i � |11ip

2|�11i =

|01i � |10ip

2

O più sinteticamente

|�xyi =|0, yi+ (�1)x |1, ȳi

p

2

dove ȳ è la negazione di y.Gli stati di Bell si possono ottenere a partire dagli stati della base computazionalemediante il circuito di figura 3.2.

3.1.3 Circuito per il teletrasporto quantistico

A↵rontiamo il seguente problema: Alice e Bob hanno generato, tempo addietro,una coppia |�00i, quindi si sono separati prendendo con se ciascuno un qubit delsistema fisico impiegato. Come può Alice trasferire a Bob un qubit | i = ↵ |0i +� |1i, avendo a disposizione un canale di comunicazione classico? La soluzione è ilcircuito 3.3 che ci apprestiamo ad analizzare.

Alice accoppia il suo qubit della coppia �00 al qubit | i da teletrasportare:

| 0i = | i |�00i

Applica quindi a | 0i un cnot e una porta di Hadamard ottenendo

| 2i = H1p

2

⇥↵ |0i (|00i+ |11i) + � |1i (|10i+ |01i)

⇤=

1

2

⇥↵(|0i+ |1i)(|00i+ |11i) + �(|0i � |1i)(|10i+ |01i)

⇤37


Raccogliendo i ket corrispondenti ai qubit in possesso di Alice la scrittura diventa

| 2i =1

2

⇥|00i (↵ |0i+ � |1i) + |01i (↵ |1i+ � |0i)+ (3.4)

+ |10i (↵ |0i � � |1i) + |11i (↵ |1i � � |0i)⇤

(3.5)

Alice misura ora i suoi due qubit, inviando i risultati a Bob; egli può cos̀ı “ag-giustare” lo stato del suo qubit, applicando dei gate X o Z, in modo da farlocoincidere con | i: il teletrasporto è completato.

3.1.4 Trasferimento dell’informazione

Mostriamo ora rigorosamente che Bob, non conoscendo il risultato della misuraeseguita da Alice, non può ricavare alcuna informazione sullo stato | i misurandoil suo qubit. Dalla 3.5 vediamo che Alice operando la misurazione può far collassarei suoi due qubit con eguale probabilità negli stati |00i, |01i, |10i e |11i. L’operatoredensità post–misura del sistema è perciò

⇢ =1

4

⇥|00ih00| (↵ |0i+ � |1i)(↵⇤ h0|+ �⇤ h1|)+

+ |01ih01| (↵ |1i+ � |0i)(↵⇤ h1|+ �⇤ h0|)+

+ |10ih10| (↵ |0i � � |1i)(↵⇤ h0|� �⇤ h1|)+

+ |11ih11| (↵ |1i � � |0i)(↵⇤ h1|� �⇤ h0|)⇤

Ricaviamo ora l’operatore densità ridotto per il qubit di Bob (utilizziamo gli indici1 e 2 in riferimento al sottosistema di Alice e Bob, rispettivamente). Ricordiamoche l’operatore densità ridotto del sistema 2 è la traccia parziale sul sistema 1dell’operatore densità totale. La traccia parziale si può definire come

tr2(|a1i ha2|⌦ |b1i hb2|) = |a1i ha2| tr |b1i hb2|

nella quale |a1i e |a2i sono vettori qualsiasi dello spazio degli stati E1 del sistema 1,e |b1i e |b2i vettori qualsiasi di E2. Essendo tr |x1x2ihx1x2| = 1 per ogni x1, x2 = 0, 1troviamo che

⇢2 = tr1 ⇢ =1

4

⇥(↵ |0i+ � |1i)(↵⇤ h0|+ �⇤ h1|) + (↵ |1i+ � |0i)(↵⇤ h1|+ �⇤ h0|)+

(↵ |0i � � |1i)(↵⇤ h0|� �⇤ h1|) + (↵ |1i � � |0i)(↵⇤ h1|� �⇤ h0|)⇤

=1

4

⇥2(|↵|2 + |�|2) |0ih0|+ 2(|↵|2 + |�|2) |1ih1|

⇤=

|0ih0|+ |1ih1|

2=

12

⇢2 è completamente slegato da | i.

3.2 Parallelismo quantistico

Intendiamo con parallelismo quantistico la capacità di un sistema di n qubitdi memorizzare contemporanemante i valori immagine di una funzione boolea-na f(x) : {0, 1}⇥n ! {0, 1}.

38

3.2. Parallelismo quantistico

Figura 3.4: Circuito quantistico per la valutazione simultanea di f(0) e f(1).

Figura 3.5: Trasformazione di Hadamard di due qubit.

Consideriamo per esempio n = 1 (fig. 3.4). Chiamiamo Uf l’operatore unitario chefa l’associazione |x, yi 7! |x, y ⌦ f(x)i. Si verifica che

Uf|0i+ |1ip

2|0i =

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

2

Questo stato di un singolo qubit contiene informazioni su due immagini di f .Il ragionamento si può estendere a funzioni booleane di n bit con n qualsiasiutilizzando un registro di n qubit per la valutazione parallela di f più uno per lamemorizzazione del risultato (la base computazionale di n qubit ha dimensione 2n,quali sono anche i possibili input della funzione). In questo caso l’applicazione dellaporta di Hadamard sul singolo qubit del caso n = 1 si generalizza all’applicazionedella trasformata di Hadamard su n qubit: quest’ultima equivale all’applicazionedella porta H su ciascun qubit (fig. 3.5) e si indica con H⌦n. Possiamo vedere che

H⌦n�� 0 . . . 0| {z }

n cifre

↵=

1p

2n

Xx

|xi

dove la somma è estesa a tutte le possibili stringhe binarie x di n cifre.L’idea del procedimento è la medesima: dopo aver preparato gli n qubit mediantela trasformata di Hadarmard e posto l’(n + 1)–esimo nello stato |0i si esegue unoperatore Uf agente su n+ 1 qubit secondo

Uf |x1x2 . . . xni |0i = |x1x2 . . . xni |0� f(x1, x2, . . . , xn)i

Lo stato finale del sistema sarà cos̀ı

1p

2

Xx

|xi |f(x)i

In contrasto con il parallelismo classico, dove sono necessari n circuiti per lavalutazione simultanea della funzione f , nel parallelismo quantistico è su�ciente

39


un circuito soltanto. Notiamo però che questo non fornisce un accesso diretto aivalori f(x), per quanto a↵ermato al paragrafo 2.1.2. Per ottenere un vantaggiopratico dal parallelismo quantistico sono necessari degli algoritmi capaci di sfrut-tarlo. Illustreremo nel seguito due di questi algoritmi: l’algoritmo di Deutsch equello di Deutsch-Josza.

3.2.1 Algoritmo di Deutsch

Figura 3.6: Circuito che esegue l’algoritmo di Deutsch.

L’algoritmo di Deutsch permette di calcolare la somma f(0)�f(1) tramite unasola valutazione della funzione. Esso è eseguito dal circuito di figura 3.6.La trasformata di Hadarmard sullo stato iniziale |01i restituisce

| 1i =

|0i+ |1ip

2

� |0i � |1ip

2

�Notando che

Uf |xi|0i � |1ip

2= (�1)f(x)

|0i � |1ip

2(3.6)

Abbiamo che lo stato conseguente all’azione di Uf è

| 2i =

8

3.2. Parallelismo quantistico

Figura 3.7: Circuito per l’algoritmo di Deutsch-Josza

3.2.2 Algoritmo di Deutsch–Josza

Questo algoritmo risolve il cos̀ıddetto problema di Deutsch: supponiamo di avereuna funzione booleana f ad n bit e di sapere che f può essere o bilanciata, ovverof(x) = 1 per 2n�1 input (la metà degli input) e f(x) = 0 per i rimanenti, oppurecostante. Vogliamo determinare a quale delle due tipologie appartenga f valutan-dola il numero minimo di volte possibile. Osserviamo che il precedente algoritmo(di Deutsch) risolve il problema nel caso n = 1.Classicamente il numero minimo di valutazioni è uguale alla metà del numero de-gli input più uno: 2n�1 + 1. Mediante il circuito quantistico di figura 3.7 si riesceinvece a determinare la natura di f mediante una sola valutazione. Come per l’al-goritmo del paragrafo precedente abbiamo bisogno di un registro di n qubit a cuipoter associare gli input della funzione e di un qubit aggiuntivo per memorizzarel’immagine di f .Lo stato di partenza è

| 0i = |0i⌦n

|1i

La trasformazione di Hadamard muta lo stato in

| 1i =X

x2{0,1}n

|xip

2n

|0i � |1ip

2

�

nel quale i primi n qubit sono in una sovrapposizione uniforme di tutti i possibilistati. Valutando f sul registro si ottiene per la 3.6

| 2i =Xx

(�1)f(x) |xip

2n

|0i � |1ip

2

�(3.7)

stato che contiene tutte le possibili immagini di f sugli input.Adesso applichiamo nuovamente la trasformazione di Hadarmard sul registro. Percalcolare lo stato risultante scriviamo l’azione di una singola porta di Hadamardsu un singolo qubit |0i o |1i come:

H |xi =

Pz(�1)

xz|zi

p

2x, z = 0, 1

41


tramite la quale possiamo esprimere l’azione di H⌦n sugli stati della base compu-tazionale degli n qubit come

H⌦n |x1, . . . , xni =

Pz1,...,zn

(�1)x1z1+...+xnzn |z1 . . . znip

2(3.8)

=

Pz(�1)

x·z|zi

p

2(3.9)

dove con x · z indichiamo il prodotto bit a bit delle due stringhe binarie, modulo2. Sostituendo la 3.9 nell’espressione di | 2i 3.7 si ottiene

| 3i =

Pz(�1)

x·z+f(x)|zi

2n

|0i � |1ip

2

�Osserviamo ora come nel caso in cui f è costante l’ampiezza del vettore |0i⌦n, pariaP

x(�1)f(x)/2n, è uguale a 1; diversamente essa è nulla. Misurando gli n qubit del

registro sappiamo dunque con certezza che f è costante se otteniamo l’autovettorecorrispondente a |0i⌦n; per qualunque altro esito f dovrà essere bilanciata.

Questo algoritmo appare molto più veloce dell’equivalente classico, tuttavia visono alcune osservazioni da fare:

• Il problema di Deutsch non ha applicazioni pratiche.

• I due algoritmi, classico e quantistico, non sono facilmente comparabili datoche il metodo di valutazione di f che si impiega è assai diverso. v

• Il problema può essere risolto classicamente in maniera probabilistica moltopiù e�cientemente rispetto alla risoluzione esatta che richiede 2n � 1 valu-tazioni. Supponendo f bilanciata infatti la probabilità di trovare m valoriuguali di f(x) in m valutazioni è

Pm =m�1Yi=1

2n�1 � i

2n � i

che decresce rapidamente all’aumentare di m.

3.3 La trasformata di Fourier quantistica

Uno dei mezzi ritenuti più promettenti per lo sviluppo di algoritmi quantistici ingrado di velocizzare la risoluzione di certi problemi di interesse è la trasformata diFourier quantistica.Introduciamo innanzitutto il concetto di trasformata di Fourier discreta: essa èun mezzo matematico che trasforma un vettore di N numeri complessi x0, x1, . . .,xn in un secondo vettore della stessa dimensione le cui componenti yk sono dateda

yk =1p

N

N�1Xj=0

xj exp

✓i2⇡k

Nj

◆(3.10)

42

3.3. La trasformata di Fourier quantistica

La trasformazione è invertibile secondo

xj =1p

N

N�1Xk=0

yk exp

✓�i

2⇡k

Nj

◆(3.11)

Sostituendo infatti la 3.10 nella 3.11 si trova

xj =1p

N

N�1Xk=0

exp

✓�i

2⇡k

Ny

◆"1p

N

N�1Xm=0

xm exp

✓i2⇡k

Nm

◆#

=1

N

N�1Xm=0

xm

N�1Xm=0

exp

✓i2⇡j

N(m� k)

◆

=1

N

N�1Xm=0

xmN�mk = xj

Si può vedere che la somma in m alla seconda riga è nulla se m 6= k.La trasformata di Fourier quantistica su un vettore di E dato da

N�1Xj=0

xj |ji

si ottiene sostituendo ai coe�cienti complessi xj la loro trasformata di Fourierdiscreta:

N�1Xj=0

xj |jiF�!

N�1Xk=0

yk |ki =N�1Xk=0

"1p

N

N�1Xj=0

xj exp

✓i2⇡k

Nj

◆#|ki

=N�1Xj=0

xj

"1p

N

N�1Xk=0

exp

✓i2⇡k

Nj

◆|ki

#

Si può dunque definire un operatore F che agisce secondo

F |ji =1p

N

N�1Xk=0

exp

✓i2⇡k

Nj

◆|ki (3.12)

Per quanto rigurda l’operatore inverso F�1 abbiamo che

N�1Xk=0

yk |kiF�1��!

N�1Xj=0

xj |ji =N�1Xj=0

"1p

N

N�1Xk=0

yk exp

✓�i

2⇡k

Nj

◆#|ji

=N�1Xk=0

yk

"1p

N

N�1Xj=0

exp

✓�i

2⇡k

Nj

◆|ji

#

Per cui

F�1 |ki =1p

N

N�1Xj=0

exp

✓�i

2⇡k

Nj

◆|ji (3.13)

43


Figura 3.8: Circuito che esegue la trasformata di Fourier quantistica di n qubit.

Mostriamo un altro modo per scrivere la trasformata di Fourier quantisticache si rivelerà fondamentale nel seguito. Supponiamo di avere n qubit ai quali èassociata la base computazionale |0i, . . ., |2n � 1i costituita da 2n vettori. Peridentificare tali vettori facciamo uso della numerazione binaria:

j = j1j2 . . . jn = j12n�1 + j22

n�2 + . . .+ jn20

Ci serviremo anche delle frazioni binarie

j = 0.jljl+1 . . . jm = jl2�1 + jl+12

�2 + . . .+ jm2�(m�l+1)

Riprendiamo la definizione 3.12:

F |ji =1

2n/2

2n�1Xk=0

exp

✓i2⇡k

2nj

◆|ki

=1

2n/2

1Xk1=0

. . .1X

kn=0

exp

"i2⇡

nX

l=1

kl2�l

!j

#|k1 . . . kni

=1

2n/2

1Xk1=0

. . .1X

kn=0

nOl=1

e2⇡ijkl2�l|kli

=1

2n/2

nOl=1

"1X

kl=0

e2⇡ijkl2�l|kli

#

=1

2n/2

nOl=1

h|0i+ e2⇡ij2

�l|1ii

=(|0i+ e2⇡i0.jn |1i)(|0i+ e2⇡i0.jn�1jn |1i) . . . (|0i+ e2⇡i0.j1j2...jn |1i)

2n/2(3.14)

Il circuito per l’esecuzione della trasformata di Fourier quantistica è riportato infigura 3.8; essendo composto esclusivamente da operatori unitari prova l’unitarietàdella trasformazione F che rappresenta. Esso è riconducibile all’espressione 3.14:occupiamoci della prima parte del circuito, dedicata alla trasformazione del primoqubit. La porta di Hadamard modifica lo stato del sistema in

1

21/2�|0i+ e2⇡i0.j1 |1i

�|j2 . . . jni

44

3.3. La trasformata di Fourier quantistica

dato che e2⇡i0.j1 = (�1)j1 . La rotazione controllata

Rk =

✓1 00 e2⇡i2

�k

◆con k = 2 applica all’ampiezza del vettore |1i della base computazionale del primoqubit la fase e2⇡i0.0j2 (se j2 = 0 la porta logica controllata non ha alcun e↵etto).Seguitando ad applicare gli operatori controllati Rk sul primo qubit come dalloschema 3.8 si ottiene infine lo stato

1

21/2�|0i+ e2⇡i0.j1j2...jn |1i

�|j2 . . . jni

identico, per quel che concerne il primo qubit, alla 3.14. Si procede alla stessamaniera per gli altri n� 1 qubit, portando a coincidere lo stato del sistema con ladefinizione alternativa 3.14 della trasformata.Si può notare che per il qubit k–esimo sono sempre necessarie una porta di Hada-mard ed n� k rotazioni: in totale nel circuito si utilizzano n+ (n� 1) + . . .+1 =n(n+ 1)/2 = ⇥(n2) operazioni.L’algoritmo può apparire come un grosso passo in avanti rispetto alla FFT (fa-st Fourier transform) classica che richiede ⇥(n2n) operazioni, tuttavia l’algoritmoquantistico non può essere facilmente utilizzato nel calcolo delle trasformate di Fou-rier: ciò si deve all’impossibilità della misura diretta delle ampiezze trasformate e,nondimeno, alle di�coltà nella preparazione degli stati di input. La trasformatadi Fourier quantistica ha comunque delle altre importanti applicazioni tra le qualila ricerca del fattori di un numero. Arriveremo a trattare il principio che sta allabase dell’algoritmo di fattorizzazione al paragrafo 3.3.2.

3.3.1 Stima della fase

Sia U un operatore unitario avente un autovettore |ui di autovalore e2⇡i�, con0 � < 1 e incognito. L’algoritmo per la stima della fase permette di ricavarecon una certa approssimazione � sfruttando la trasformata di Fourier quantistica.L’algoritmo non ha una sua utilità propria ma può venir utilizzato come subroutinein altri algoritmi.

Per la sua esecuzione è necessario un registro di t qubit inizializzati a |0i,in cui si memorizzerà la fase �, e un secondo registro nello stato |ui a cui verràapplicato U . Come vedremo la dimensione del primo registro è il fattore che regolala precisione con cui si determinerà la fase. Il circuito è illustrato nelle figure 3.9(prima parte) e 3.10 (schema completo).L’algoritmo comincia con la trasformata di Hadamard del primo registro, seguitada delle applicazioni controllate di potenze di U2 sul secondo registro. Alla fine diquesta fase lo stato del primo registro e

25 marzo 2015 - Home - people.unica.it · 2016. 1. 22. · Capitolo 1 Introduzione alla teoria...

Documents

Transcript of 25 marzo 2015 - Home - people.unica.it · 2016. 1. 22. · Capitolo 1 Introduzione alla teoria...