Transcript
Il computer quantistico
25 marzo 2015
2
Indice 1 Introduzione alla teoria della computabilit` a 1.1 Modelli di computazione . . . . . . . . . . . . . . 1.1.1 La tesi di Church–Turing . . . . . . . . . . 1.1.2 La macchina di Turing . . . . . . . . . . . 1.1.3 Modello circuitale di computazione . . . . 1.2 Complessit`a computazionale . . . . . . . . . . . . 1.2.1 Notazione asintotica . . . . . . . . . . . . 1.2.2 Problemi decisionali . . . . . . . . . . . . 1.2.3 Classi di complessit`a . . . . . . . . . . . . 1.2.4 Problemi trattabili e problemi intrattabili 1.2.5 L’ideazione dei computer quantistici . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
2 Il modello di computazione a circuito quantistico 2.1 Il bit quantistico (qubit) . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Rappresentazione di un qubit nella sfera di Bloch . . . . . . 2.1.2 Informazione quantistica . . . . . . . . . . . . . . . . . . . . 2.1.3 Doppio qubit ed entanglement . . . . . . . . . . . . . . . . . 2.1.4 Qubit multipli . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Circuiti quantistici . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Porte logiche di singolo qubit . . . . . . . . . . . . . . . . . 2.2.2 Operatori di rotazione . . . . . . . . . . . . . . . . . . . . . 2.2.3 Interpretazione geometrica degli operatori di rotazione nella sfera di Bloch . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.4 Decomposizione in rotazioni delle porte logiche di singolo qubit 2.2.5 Operazioni controllate . . . . . . . . . . . . . . . . . . . . . 2.2.6 Implementazione di operazioni controllate . . . . . . . . . . 2.2.7 Misurazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Un insieme di porte logiche quantistiche universali . . . . . . . . . . 2.3.1 Decomposizione in matrici unitarie a due livelli . . . . . . . 2.3.2 Applicazione di porte unitarie a due livelli qualsiasi mediate porte di singolo qubit . . . . . . . . . . . . . . . . . . . . . . 2.3.3 Approssimazione degli operatori su singolo qubit . . . . . . .
5 5 5 5 6 8 8 9 9 10 11 13 13 14 15 15 16 16 17 18 19 20 21 22 24 27 27 28 30
3 Algoritmi quantistici 35 3.1 Teletrasporto quantistico . . . . . . . . . . . . . . . . . . . . . . . . 35 3.1.1 La questione della copia dei qubit . . . . . . . . . . . . . . . 35 3
Indice
3.2
3.3
3.1.2 Stati di Bell . . . . . . . . . . . . . . . 3.1.3 Circuito per il teletrasporto quantistico 3.1.4 Trasferimento dell’informazione . . . . Parallelismo quantistico . . . . . . . . . . . . 3.2.1 Algoritmo di Deutsch . . . . . . . . . . 3.2.2 Algoritmo di Deutsch–Josza . . . . . . La trasformata di Fourier quantistica . . . . . 3.3.1 Stima della fase . . . . . . . . . . . . . 3.3.2 Ricerca dell’ordine moltiplicativo . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
36 37 38 38 40 41 42 45 48
4 Dalla teoria alla pratica: realizzazione fisica dei computer quantistici 4.1 Decoerenza quantistica . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Sovrapposizioni coerenti e miscele statistiche . . . . . . . . . 4.1.2 Decoerenza: definizione e tipologie . . . . . . . . . . . . . . 4.2 Requisiti fisici di un sistema volto alla computazione quantistica . .
51 51 51 52 54
5 Il computer quantistico basato sugli ioni intrappolati 5.1 Trappole per ioni . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 Il problema del confinamento . . . . . . . . . . . . 5.1.2 Trappole a radiofrequenza . . . . . . . . . . . . . . 5.1.3 La trappola di Paul . . . . . . . . . . . . . . . . . . 5.1.4 Sistemi di ra↵reddamento . . . . . . . . . . . . . . 5.2 Risonanze ottiche in sistemi atomici a due livelli . . . . . . 5.2.1 Hamiltoniana di interazione dell’elettrone . . . . . . 5.2.2 Equazioni di Bloch . . . . . . . . . . . . . . . . . . 5.2.3 Approssimazione di onda rotante . . . . . . . . . . 5.2.4 Soluzione nel caso di risonanza esatta . . . . . . . . 5.2.5 Soluzione in caso di detuning . . . . . . . . . . . . 5.3 Stato dell’arte dei computer quantistici a ioni intrappolati
59 59 59 60 60 63 64 65 66 68 70 72 74
6 Conclusione
4
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
79
Capitolo 1 Introduzione alla teoria della computabilit` a 1.1 1.1.1
Modelli di computazione 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’abaco — per avere una definizione formale di algoritmo si `e dovuto attendere sino agli anni ’30 nei quali, indipendentemente, Alonzo Church e Alan Turing si impegnarono nella risoluzione di un problema posto da David Hilbert qualche anno prima: il problema si interrogava sull’esistenza di un algoritmo capace di risolvere ogni problema della matematica. Uno scoglio per i due scienziati fu quello di formulare in termini matematicamente rigorosi il concetto intuitivo di algoritmo. Non di rado delle buone definizioni si sono dimostrate fondamentali per il progresso di un campo scientifico o matematico; la nozione di macchina di Turing ha segnato la nascita dell’informatica moderna. Turing ide`o una macchina — si tratta di una costruzione di pensiero, non soggetta ai vincoli imposti da una realizzazione fisica pratica — che ancor oggi appare incarnare ci`o che intendiamo come “algoritmo”. La tesi di Church–Turing a↵erma che la classe di funzioni calcolabili da una macchina di Turing corrisponde esattamente alla classe di funzioni che riteniamo calcolabili da un algoritmo; sottolineiamo il fatto che la tesi collega un concetto intuitivo ad una definizione formale. Quella di Church–Turing `e una congettura in quanto non si pu`o escludere a priori la possibilit`a che venga trovato prima o poi un qualche processo che definiremmo algoritmico ma che non possa essere eseguito da una macchina di Turing. Tuttavia ad 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 a stati finiti e un nastro sul quale la macchina abbia accesso in lettura e scrittura tramite una testina. 5
Capitolo 1. Introduzione alla teoria della computabilit`a
Figura 1.1: Schema della macchina di Turing.
Il controllo a stati finiti `e una sorta di processore che pu`o assumere un insieme finito di stati q1 , q2 , . . ., qm ; il nastro `e un oggetto unidimensionale che si estende infinitamente in una direzione: possiamo pensarlo diviso in caselle contenenti ciascuna un simbolo preso da un’insieme finito di simboli (detto alfabeto). La testina pu`o scorrere il nastro e agire su una casella alla volta. La configurazione iniziale della macchina prevede che il controllo sia nello stato di 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 di stringhe contenenti cinque elementi ciascuna. In primis la macchina seleziona all’interno del programma la stringa avente come primo elemento lo stato in cui si trova il controllo e come secondo elemento il simbolo indicato dalla testina. Se il programma non contiene la stringa cercata la macchina assume lo stato di arresto qh e l’esecuzione del programma termina. In caso contrario la configurazione della macchina si modifica in accordo con i successivi tre elementi della stringa: il terzo elemento rappresenta lo stato che il controllo dovr`a assumere; il quarto `e un simbolo di che la testina scrive sulla casella in cui punta; la quinta e ultima istruzione permette di spostare la testina di una casella a sinistra o a destra sul nastro, o di mantenerla nella posizione corrente. Il ciclo prosegue a meno che il controllo non arrivi a trovarsi nello stato qh ; quando questo avviene la casella su cui punta la testina contiene l’output del programma. Abbiamo illustrato la pi` u semplice delle molte possibili varianti della macchina di Turing. Esse possono di↵erire ad esempio nel numero di nastri o nella loro dimensionalit`a. Tutte le varianti conosciute sono per`o tra loro equivalenti, nel senso 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 per manipolare 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 pu`o dimostrare che i due modelli sono di fatto equivalenti.
Figura 1.2: Le pi` u 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 simboli convenzionali di alcune comuni porte logiche sono riportati in figura 1.2. Sebbene tali funzioni siano infinite, ognuna di esse si pu`o comporre utilizzando un numero finito di porte logiche chiamate, per questo motivo, universali (un risultato simile vale nell’ambito del modello circuitale quantistico, come vedremo al §2.3). Dimostriamo rapidamente quanto a↵ermato costruendo una funzione f qualunque facendo uso solamente delle porte logiche not, or, and e xor. Limitiamoci inizialmente a funzioni booleane f : {0, 1}k ! {0, 1} (si ottengono ponendo l = 1 nella 1.1); procediamo per induzione. Nel caso k = 1 esistono quattro diverse possibili f : l’identit`a, il not e le funzioni costanti 0 e 1. Le funzioni costanti si possono ottenere, rispettivante, facendo l’and dell’input con un ancilla bit 1 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 + 1 bit pu`o 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 essere realizzate con le porte scelte precedentemente. Tramite queste due funzioni `e possibile calcolare f utilizzando il circuito di figura 1
Gli ancilla bit, o bit di lavoro, sono dei bit che non rappresentano un informazione in senso stretto ma hanno solo un ruolo tecnico nel funzionamento del circuito.
7
Capitolo 1. Introduzione alla teoria della computabilit`a
Figura 1.3: Circuito per il calcolo di f (x1 , x2 , . . . , xn+1 ) che utilizza soltanto le due funzioni di equazione 1.2 e le porte not, and e xor.
1.3. Dato che ciascuna funzione f definita dalla 1.1 pu`o essere pensata come l funzioni booleane di k bit, questo risultato si generalizza ad l qualunque. Questo completa la dimostrazione dell’universalit`a delle porte not, or, and e xor. Queste porte si possono a loro volta simulare utilizzando solamente il nand, a patto di poter disporre di ancilla bit e fanout2 .
1.2
Complessit` a computazionale
Ci siamo finora occupati solamente della possibilit`a dell’esecuzione degli algoritmi senza badare alle risorse che `e necessario investire in termini di spazio, tempo ed ` quest’ultimo l’argomento di una branca dell’informatica nota come teoenergia. E ria della complessit`a computazionale; si tratta di una materia vasta di cui daremo solo una breve panoramica.
1.2.1
Notazione asintotica
La risoluzione di un certo problema pu`o richiedere un di↵erente quantitativo di risorse a seconda del modello di computazione che si utilizza. Vi possono essere delle di↵erenze, ad esempio, tra il numero di cicli compiuti da una macchina di Turing a nastro singolo e quelli compiuti da una macchina a due nastri, nella risoluzione di un certo problema. Tuttavia il numero esatto di cicli `e di scarso interesse: 2
Con fanout si intende la possibilit` a di creare, ad un certo punto di un ramo, dei nodi attraverso i quali l’informazione del ramo originale viene trasmessa a due o pi` u rami figli.
8
1.2. Complessit`a computazionale ci `e sufficiente conoscere l’andamento funzionale del numero di cicli rispetto alla dimensione dell’input per avere un’idea dell’efficienza della computazione nei due modelli. Si fa per questa ragione largo uso, nel campo della complessit`a 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 comportamento asintotico della funzione. Analogamente si usa ⌦ per indicare un limite inferiore: 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 pu`o scrivere f (n) = ⇥(g(n)).
1.2.2
Problemi decisionali
Molti problemi computazionali sono esprimibili in maniera naturale in termini di problemi decisionali. Questi si definiscono in maniera formale facendo uso di un insieme di simboli ⌃, chiamato alfabeto; l’insieme di tutte le possibili stringhe di simboli appartenenti all’alfabeto si indica con ⌃⇤ . Si definisce linguaggio L un sottoinsieme di ⌃⇤ . Data una stringa di simboli, il problema di verificare se la stringa appartenga o meno a L `e un problema decisionale. Facciamo un esempio pratico: se utilizziamo come alfabeto le due cifre binarie 0 e 1 allora ⌃⇤ rappresenta l’insieme di tutte le stringhe binarie, il quale pu`o essere messo in corrispondenza biunivoca con N. Se definiamo L come l’insieme dei numeri binari che rappresentano dei numeri primi allora il problema di determinare se una stringa binaria appartenga a L oppure no equivale allo stabilire se il numero ad essa corrispondente `e primo o meno. Il problema della fattorizzazione `e solitamente posto nella forma seguente: un intero 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 complessit` a
I problemi decisionali si possono classificare, ad esempio, in base al tempo impiegato 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 tempo O(f (n)), dove n `e la grandezza dell’input. I problemi TIME(nk ) formano la classe P dei problemi risolubili in un tempo polinomiale. Dimostrare che un problema non appartiene a P `e spesso molto difficile. Come nel caso della fattorizzazione, accade che sebbene non si conosca ad oggi alcun algoritmo capace di risolvere il problema in un tempo polinomiale, non si dispone di 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
Capitolo 1. Introduzione alla teoria della computabilit`a intero n abbia un fattore non banale p < l pu`o essere fatto facilmente se p `e noto. p gioca il ruolo di un testimone nel dimostrare che n ha dei fattori non banali minori di l, ovvero che n appartiene al linguaggio. Appartengono a NP quei problemi decisionali che soddisfano (indichiamo con x un generico elemento di ⌃⇤ ): 1. Se x 2 L allora esiste una stringa testimone w tale che una macchina di Turing restituisca “si” in un tempo polinomiale prendendo come input x e w. 2. Se x 2 / L allora per ogni stringa w che si proponga come testimone, la stessa macchina restituisce “no” in un tempo polinomiale prendendo come input x e w. Notiamo come le propriet`a dei problemi NP siano asimmetriche in quanto non prevedano un testimone per la verifica della non appartenenza di una stringa al linguaggio. Si definisce perci`o la classe coNP che contiene i complementi dei problemi decisionali di NP: il complemento di un problema decisionale su un linguaggio L si definisce tramite un linguaggio L0 = ⌃⇤ L, complemento in ⌃⇤ di L. Le propriet`a dei problemi coNP sono dunque: 1. Se x 2 / L0 allora esiste una stringa testimone w tale che una macchina di Turing restituisca “no” in un tempo polinomiale prendendo come input x e w. 2. Se x 2 L allora per ogni stringa w che si proponga come testimone, la stessa macchina restituisce “si” in un tempo polinomiale prendendo come input x e w. I problemi della classe P sono anche in NP e coNP, in quanto per essi esiste una macchina di Turing in grado di determinare l’appartenenza di una stringa al linguaggio in un tempo polinomiale con un testimone w vuoto. Determinare se la relazione P ✓ NP valga in senso stretto, il che implicherebbe anche NP = coNP, `e uno dei problemi aperti pi` u famosi dell’informatica.
1.2.4
Problemi trattabili e problemi intrattabili
La complessit`a computazionale si occupa di stabilire dei limiti minimi sul numero di risorse richieste per risolvere un certo problema computazionale. In questo ambito viene fatta una grossa distinzione fra quei problemi che possono essere risolti in un tempo polinomiale (classe P) e quelli che richiedono invece un tempo superpolinomiale, o esponenziale3 rispetto alla grandezza dell’input. I primi sono considerati trattabili, a di↵erenza dei secondi; vi sono varie ragioni per adottare questa distinzione. Sebbene in generale non sempre un algoritmo polinomiale 3
Questa nomenclatura, sebbene di largo uso, non `e del tutto appropriata in questa esistono funzioni, come ad esempio nlog n , che crescono pi` u velocemente di qualsiasi polinomio ma anche pi` u lentamente di un esponenziale.
10
1.2. Complessit`a computazionale comporti una maggiore efficienza rispetto a un algoritmo superpolinomiale (2n/1000 non raggiunge n1000 se non per n ⇠ 108 ), storicamente gli algoritmi polinomiali si sono dimostrati preferibili. Ci`o anche dovuto verosimilmente ad un e↵etto di selezione, in quanto ideare un algoritmo di n o n2 passi `e certamente pi` u affine al 1000 ragionamento comune piuttosto che idearne uno di n . In secondo luogo, tale distinzione trova ragione nella tesi forte di Church–Turing la quale a↵erma che ogni modello di computazione pu`o essere simulato da una macchina di Turing a prezzo di un aumento nel numero di operazioni elementari richieste al pi` u polinomiale. Essa implica che se un problema pu`o essere risolto in un tempo polinomiale con un dato modello di computazione allora pu`o essere risolto in una macchina di Turing ancora in un tempo polinomiale e anche che, viceversa, se un problema non `e risolubile in un tempo polinomiale in una macchina di Turing allora non `e risolvibile a↵atto sotto tale vincolo. La teoria della complessit`a computazionale trova cos`ı una formulazione naturale se si associa alla nozione di trattabilit`a di un problema la computabilit`a 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 pi` u volte messa in discussione nel secolo scorso e tutt’oggi la sua validit`a `e tutt’altro che accertata. Subito dopo la pubblicazione della tesi debole di Turing, avvenuta nel 1936, furono assemblati i primi calcolatori elettronici. John von Neumann si occup`o di delineare le caratteristiche che un computer reale avrebbe dovuto possedere per poter essere equiparato alla macchina di Turing, ma si dovette aspettare sino al 1947, anno dell’invenzione del transistor, per avere la possibilit`a di realizzare fisicamente un simile dispositivo. Da allora la tecnologia dei calcolatori elettronici si `e evoluta molto rapidamente, tanto che Gordon Moore, nel 1965, formul`o l’omonima legge secondo la quale la potenza di calcolo dei computer sarebbe dovuta progredire raddoppiando di anno in anno. Di fatto si `e passati dall’Intel 4004 del 1971, costituito da 2250 transistor, al Pentium 4 che, nel 2000, ne conteneva 42 milioni. Tale evoluzione procede di pari passo con la miniaturizzazione dei componenti, la quale comporta da un lato una simile crescita esponenziale dei costi di produzione e dall’altro si scontra con dei limiti fisici. Se le dimensioni di un transitor raggiungeranno infatti l’ordine di grandezza della lunghezza di De Broglie dell’elettrone, gli e↵etti quantistici non sarranno pi` u trascurabili e i circuiti elettronici non potranno pi` u funzionare nel modo in cui oggi normalmente li utilizziamo. Una delle possibili strade percorribili per non incorrere nel declino della crescita esponenziale prevista da Moore `e quella di passare ad un diverso e nuovo paradigma computazionale, quale `e quello dei computer quantistici. Nel ripercorrere i passi che hanno portato a credere che la meccanica quantistica potesse essere sfruttata per risolvere dei problemi computazionali, torniamo al 1936 e alla tesi di Church–Turing. Con il successivo sviluppo dei computer a 11
Bibliografia transistor e dell’informatica si inizi`o a credere, negli anni 60’ e 70’, che non fosse possibile 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 computer analogici, che sembravano poter riuscire a risolvere efficientemente dei problemi per i quali non si conosceva invece alcun algoritmo efficiente funzionante sulla macchina di Turing. Questa scoperta si rivel`o non vera, riconsiderando la questione senza omettere il rumore a cui questi dispositivi analogici sono soggetti.4 Una seconda obiezione alla tesi di Church–Turing forte venne avanzata da Robert Solovay e Volker Strasse, i quali fabbricarono negli anni ’70 un algoritmo stocastico capace di determinare se un numero intero fosse primo oppure no con una certa probabilit`a: l’elemento casuale permetteva di risolvere, sebbene in termini probabilistici, un problema ritenuto intrattabile. Ne risult`o la seguente modifica alla tesi di Church–Turing forte: ogni modello di computazione pu`o essere simulato da una macchina di Turing probabilistica a prezzo di un aumento nel numero di operazioni elementari richieste al pi` u polinomiale. Questa modifica ad hoc della tesi port`o a pensare di a↵rontare la questione della computabilit`a in maniera diversa, senza ricorrere a congetture: nel 1985 David Deutsch propose l’idea che un modello di computazione dovesse basarsi su una teoria fisica, e cerc`o di definire un modello di computazione capace di simulare qualsiasi sistema fisico. Dato che le leggi della fisica sono, in ultima analisi, quanto–meccaniche, egli consider`o un modello di computazione basato sulle leggi della meccanica quantistica. Non era questa un’idea del tutto nuova: Richard Feynman nel 1982 ipotizz`o che un computer quantistico avrebbe potuto velocizzare considerevolmente la simulazione di sistemi quantistici. La traccia di Deutsch non pass`o inosservata: nel 1994 Peter Shor trov`o un algoritmo quantistico per fattorizzare i numeri in un tempo polinomiale; anche altri algoritmi capaci di superare in velocit`a i corrispettivi algoritmi classici vennero scoperti. Insieme essi suggeriscono che i computer quantistici possano svolgere efficientemente alcuni compiti classicamente ritenuti difficili, contrariamente a quanto a↵erma la tesi di Church–Turing forte. Tuttavia allo stato attuale della conoscenza non si pu`o escludere l’esistenza di algoritmi classici altrettanto efficienti, per cui capire l’e↵ettiva potenza computazionale dei computer quantistici `e una questione ancora aperta.
Bibliografia [Fox06]
Mark Fox. Quantum Optics. Oxford University Press, 2006.
[NC00]
Michael A. Nielsen e Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.
4`
E questa una lezione che non potremo ignorare quando ci occuperemo, nel capitolo 4, della realizzazione fisica dei computer quantistici
12
Capitolo 2 Il modello di computazione a circuito quantistico 2.1
Il bit quantistico (qubit)
Un segnale analogico `e una grandezza fisica (una tensione, ad esempio) variabile con continuit`a nel tempo, atta a convogliare un’informazione (l’ampiezza di un’onda sonora). L’informazione trasportata da un segnale pu`o essere immagazzinata in dei supporti analogici (l’onda sonora pu`o essere convertita nell’altezza del un solco di un disco), i quali hanno una risoluzione teoricamente infinita. Nella realt`a il rumore limita la fedelt`a di queste registrazioni. Per contrasto, la rappresentazione digitale dell’informazione `e basata sull’utilizzo di stati discreti di un dispositivo fisico, ed `e praticamente esente da rumore. La rappresentazione binaria utilizza due stati, ai quali ci si riferisce solitamente con 0 e 1, che costituiscono il contenuto di informazione di un bit. Un bit pu`o essere tradotto 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’informazione, tuttavia si avvale di uno dei postulati della meccanica quantistica secondo il quale un sistema fisico pu`o 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 del sistema. Ci si pu`o riferire ai numeri ↵0 e ↵1 come ampiezze di probabilit`a, in quanto misurando un’osservabile A avente |0i e |1i come autovettori, ovvero A |0i = a0 |0i
A |1i = a1 |1i
(2.2)
la probabilit`a 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 questo il nome di stati della base computazionale. Ci`o che rende la computazione quantistica un traguardo tecnologico piuttosto che una curiosit`a matematica `e il fatto che i qubit siano degli oggetti fisici. L’esempio pi` u comune di qubit `e lo stato di spin di una particella con spin 1/2: la base 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 pu`o essere riscritto, tenendo conto della condizione di normalizzazione, come ✓ ◆ ✓ ✓ i i | i=e cos |0i + e sin |1i (2.3) 2 2 In questa scrittura compaiono tre parametri indipendenti che possono variare in accordo con 0 < 2⇡ 0✓<⇡ 0 < 2⇡
La fase globale ei non ha e↵etti osservabili nella maggior parte dei casi, e pu`o pertanto essere ignorata. I parametri ✓ e possono invece venire associati biunivocamente ai punti di una sfera unitaria secondo la legge 8 > : z = cos ✓
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 un importante 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 difficile rispondere alla domanda su quale sia il contenuto e↵ettivo di informazione di un qubit. Misurando l’osservabile A di eq. 2.2 possiamo ottenere i due autovalori con probabilit`a data dal modulo quadro delle relative ampiezze complesse. In seguito alla misura lo stato | i collassa nell’autovettore corrispondente all’autovalore misurato, procurando una perdita irreversibile di informazione. Da ci`o appare chiaro che sebbene i punti sulla sfera di Bloch siano infiniti e di conseguenza sia possibile, in principio, codificare in essi una quantit`a potenzialmente illimitata di informazione, tale informazione non risulti facilmente accessibile per via della natura probabilistica della misura quantistica e del collasso della funzione d’onda. ` certamente una questione delicata quantificare il contenuto di informazione di E un 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 che lo spazio degli stati di spin del sistema sar`a costituito dal prodotto tensoriale dei corrispettivi spazi di singola particella: 1 2 Espin = Espin ⌦ Espin
Una base di questo spazio `e costituita dai vettori |"1 i ⌦ |"2 i
"i = +,
e pertanto un generico stato del sistema si pu`o 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 di stati di singola particella: in questi casi le due particelle si dicono entangled. L’entanglement ha delle implicazioni fisiche e tecnologiche assai rilevanti, che trovano ragione nel particolare comportamento degli stati entangled in seguito ad una misura eseguita su una delle due particelle. Prendiamo in considerazione dapprima uno stato non-entangled, ovvero i | i = | 1 i ⌦ | 2 i , con | i i 2 Espin
(2.5)
In seguito ad una misurazione sulla particella 1 di una grandezza A1 lo stato si modifica in P1 | i | 0i = p (2.6) h |P1 | i
dove P1 `e l’operatore di proiezione sull’autospazio dell’osservabile A1 corrispondente all’autovalore misurato. 15
Capitolo 2. Il modello di computazione a circuito quantistico Nel caso non-entangled il proiettore non agisce sullo stato della seconda particella, il quale rimane invariato: | 0 i / P1 (| 1 i ⌦ | 2 i) = (P1 | 1 i) ⌦ | 2 i) Consideriamo ora invece uno stato entangled, quale ad esempio | i=
|00i |11i p 2
Questo stato, detto di singoletto, `e autovettore dello spin totale S delle due particelle. Esso non `e esprimibile come prodotto tensoriale nella forma dell’equazione 2.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 sar`a |0i o |1i a seconda che lo spin misurato nella prima sia, rispettivamente, ~/2 o +~/2. Questo significa che e↵ettuare una misurazione sulla prima particella produce degli e↵etti sulla seconda, la quale pu`o trovarsi anche a grande distanza dal luogo della misura. Ci`o pu`o essere detto pi` u elegantemente a↵ermando che la meccanica quantistica `e una teoria fisica non–locale. Bisogna precisare che tramite questo e↵etto non `e possibile trasmettere alcuna informazione, e non si ha dunque una violazione della teoria della relativit`a speciale.
2.1.4
Qubit multipli
Se seguitiamo ad aggiungere altre particelle al nostro sistema quantistico la dimensione dello spazio degli stati cresce di un fattore 2 per ciascuna particella aggiuntiva: un insieme di N qubit raccoglie l’informazione contentuta in 2N ampiezze complesse. Per N = 500 questo numero supera il numero stimato degli atomi nell’universo! Da ci`o deduciamo che anche un sistema fisico relativamente contenuto evolve in maniera assai complessa: in esso `e racchiuso un enorme potenziale computazionale che si vorrebbe cercare di sfruttare.
2.2
Circuiti quantistici
In somiglianza con il modello circuitale classico, nell’ambito del quale si possono disegnare degli algoritmi utilizzando collegamenti e porte logiche, nel modello circuitale quantistico si utilizzano elementi analoghi per trasportare e manipolare l’informazione. ` utile a questo punto introdurre un formalismo matriciale, secondo il quale E associamo ad un qubit singolo un vettore colonna ✓ ◆ ↵0 | i = ↵0 |0i + ↵1 |1i 7! ↵1 1
Ci` o `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 logiche X, 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 | 0 i = U | i; imponendo la conservazione 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 ragionamento rimane valido anche per qubit multipli). L’unitariet`a delle porte logiche ha delle implicazioni importanti per quanto riguarda l’entropia delle computazioni quantistiche: esse sono sempre invertibili. Un’altra importante propriet`a di queste trasformazioni `e la linearit`a. All’aumentare della dimensione dello spazio computazionale la dimensione dei vettori e delle matrici aumenta di conseguenza; la base si ordina convenzionalmente secondo il sistema di numerazione binario (|0 . . . 00i, |0 . . . 01i, . . . , |1 . . . 11i). Le porte logiche quantistiche su N qubit formano il gruppo U (2N ). Dal punto di vista grafico i collegamenti che trasportano i qubit si rappresentano come delle linee orizzontali, le porte logiche come dei quadrati e i circuiti si leggono da 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 quantistici. In primo luogo nei circuiti quantistici, non `e permesso il feedback: essi si dicono aciclici. In secondo luogo nei circuiti quantistici non pu`o esistere il fanin, operazione in cui due o pi` u qubit sono uniti in uno solo mediante una qualche porta 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 quanto richiesto dalla 2.7. Per ultimo osserviamo come il fanout, tramite il quale il ramo di un circuito logico classico si dirama in due o pi` u bracci, comporti la copia dell’informazione trasportata dal ramo originale. Come vedremo al paragrafo 3.1.1, la copia dei qubit `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 porta not, nel modello quantistico esistono invece diverse operazioni di questo tipo. 17
Capitolo 2. Il modello di computazione a circuito quantistico La naturale estensione del not classico alla logica circuitale quantistica `e la porta X, che scambia i coefficienti dei vettori della base computazionale: X=
✓
0 1 1 0
◆
Il simbolo X `e scelto in riferimento alla matrice di Pauli hanno ✓ ◆ ✓ ◆ 0 i 1 0 Y = Z= i 0 0 1
x
⌘ X. Similmente si
Altre tre porte molto utilizzate sono la porta di Hadamard, la fase S, e la porta ⇡/8 (che si indica anche con T ): 1 H=p 2 T =
2.2.2
✓
✓
1 1
1 1
1 0 i⇡/4 0 e
◆
◆
=e
S=
i⇡/8
✓
e
✓
1 0 0 i
i⇡/8
◆
0 ei⇡/8
0
◆
Operatori di rotazione
Le matrici di Pauli hanno delle propriet`a notevoli: esse generano gli operatori di rotazione nello spazio degli stati dello spin. Ricordiamo che l’operatore di rotazione di un sistema quantistico `e Ruˆ (↵) = exp
✓
1 ↵J · u ˆ i~
◆
(2.8)
Esso, agendo su un ket | i, ruota il sistema di un angolo ↵ intorno all’asse diretto lungo il versore u ˆ . J `e il momento angolare totale del sistema, dato, nel caso di una singola particella dotata di spin, da J=L+S con L momento angolare orbitale della particella. Siccome si ha che [L, S] = 0 l’operatore della 2.8 si pu`o riscrivere come Ruˆ (↵) = exp
✓
◆ ✓ ◆ 1 1 ↵L · u ˆ exp ↵S · u ˆ i~ i~
il quale `e formalmente il prodotto tensoriale di due operatore agenti, rispettivamente, 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 18
x2R
(2.9)
2.2. Circuiti quantistici possiamo ottenere le rotazioni del sistema attorno agli assi cartesiani ✓ ◆ cos 2✓ i sin 2✓ i↵X/2 Rx (↵) = e = i sin 2✓ cos 2✓ ✓ ◆ cos 2✓ sin 2✓ i↵Y /2 Ry (↵) = e = sin 2✓ cos 2✓ ✓ i✓/2 ◆ e 0 i↵Z/2 Rz (↵) = e = 0 ei✓/2
(2.10)
e anche Ruˆ (↵) = exp( i↵ˆ u · /2) = cos
⇣↵⌘ 2
I
i sin
⇣↵⌘ 2
(ux X + uy Y + uz Z)
(2.11)
dove ~2 = S. Questi operatori sono unitari, e rappresentano dunque delle valide porte logiche quantistiche.
2.2.3
Interpretazione geometrica degli operatori di rotazione nella sfera di Bloch
Mostriamo ora che gli operatori dell’equazione 2.10 agiscono su un qubit 2.3 ruotando il corrispondente vettore 2.4 sulla sfera di Bloch. Richiamiamo innanzitutto la teoria delle particelle quantistiche di spin 1/2: lo stato pi` u generale di tali particelle `e esprimibile nella forma 2.3, che `e autovettore di S · u ˆ se il versore u `e dato dalla 2.4 (l’autovalore corrispondente `e +~/2). Si avr`a perci`o, indicando con |ui lo stato del sistema, (S · u ˆ ) |ui =
~ |ui 2
E↵ettuando una rotazione R sul sistema e ruotando corrispondentemente lo strumento di misura dello spin in modo che la posizione relativa non sia mutata, ci si dovr`a trovare in una configurazione fisicamente equivalente alla precedente. Dovr`a perci`o valere ~ (S · Rˆ u)R |ui = R |ui 2 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 · Rˆ u di autovalore positivo, e dunque a tale stato sar`a associato il vettore Rˆ u nella sfera di Bloch, come volevasi dimostrare. Oltre all’appena discussa interpretazione geometrica, gli operatori di rotazione 2.10 hanno un ruolo importante nella teoria delle porte logiche quantistiche: ciascun operatore unitario di dimensione 2 pu`o infatti essere scritto come U = ei↵ Ruˆ (✓) Precedentemente abbiamo trascurato la fase globale dei qubit in quanto fisicamente non rilevante. Nel caso delle porte logiche vale un discorso analogo: anche se la 19
Capitolo 2. Il modello di computazione a circuito quantistico dimensione di una porta U `e minore della della cardinalit`a della base computazionale, ovvero se essa agisce solo su un sottoinsieme dei qubit del circuito quantistico, un’eventuale fase globale di U non pu`o introdurre degli sfasamenti relativi tra le ampiezze complesse: (ei↵ |ai) ⌦ |bi = ei↵ (|ai ⌦ |bi) ! |ai ⌦ |bi
2.2.4
Decomposizione in rotazioni delle porte logiche di singolo qubit
Dimostriamo ora alcuni metodi, di cui ci avvaleremo nel seguito, che permettono di scrivere un generico U 2⇥2 in termini di operatori di rotazione. Dimostriamo dapprima il teorema di decomposizione Z-Y : dato un operatore unitario 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=
e i( ↵ 2 ei(↵+ 2
) cos 2 2 ) sin
2
2
ei(↵ 2 + 2 ) sin 2 ei(↵+ 2 + 2 ) cos 2
!
la quale `e facilmente riconducibile alla seguente parametrizzazione del gruppo U (2) ✓ i ◆ e 1 cos ✓ ei 2 sin ✓ i e 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 precedente teorema poniamo ◆ ✓ ◆ ⇣ ⌘ ⇣ ⌘ ✓ + A = Rz ( )Ry B = Ry Rz C = Rz 2 2 2 2
Tenendo conto delle propriet`a Ruˆ (✓) + Ruˆ ( ) = Ruˆ (✓ + ) e Ruˆ (0) = I si pu`o verificare la prima parte della tesi. Per la seconda si utilizza l’identit`a XY X = 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 XXRz X = Ry Rz 2 2 2 2 Quindi
AXBXC = Rz ( )Ry
⇣ ⌘
⇣ ⌘
Ry Rz 2 2 = Rz ( )Rx ( )Rz ( )
✓
+ 2
◆
Ry
✓
2
◆
come volevasi dimostrare. La 2.12 si pu`o estendere a due assi arbitrari distinti n ˆ e m: ˆ U = ei↵ Rnˆ ( )Rm ˆ ( )Rn ˆ( ) 20
(2.13)
2.2. Circuiti quantistici
Figura 2.3: Porta logica cnot.
2.2.5
Operazioni controllate
Per operazioni controllate intendiamo dei processi algoritmici nei quali una certa operazione viene eseguita condizionalmente a certi requisiti. Queste operazioni condizionali sono fondamentali sia nella logica classica che in quella quantistica. La pi` u semplice di queste porte logiche in ambito quantistico `e il cnot, la cui azione 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 detto qubit 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 0 1 1 0 0 0 B0 1 0 0 C B C @0 0 0 1 A 0 0 1 0 e il suo simbolo circuitale `e indicato in figura 2.3. Estendendo questa idea, `e possibile e↵ettuare delle operazioni U qualsiasi controllate: |ci |ti 7! |ci U c |ti che si indicano con il simbolo di figura 2.4.
Figura 2.4: Operazione U controllata.
Pi` u in generale il numero di qubit di controllo N e quello dei qubit bersaglio K pu`o essere scelto a piacere. L’operazione controllata nel suo insieme si scrive come C N (U ) |x1 x2 . . . xN i | i = |x1 x2 . . . xN i U x1 x2 ...xN | i 21
Capitolo 2. Il modello di computazione a circuito quantistico
Figura 2.5: Operazione controllata C n (U ), con n qubit di controllo e U matrice unitaria 2k ⇥ 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 sua applicazione.
Un esempio grafico di queste porte `e riportato in figura 2.5. Nel seguito assumeremo K = 1. ` utile anche definire delle porte controllate “inverse”, nelle quali l’operatore E U 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 operazione controllata C N (U ) utilizzando solamente porte logiche di singolo qubit e cnot.
Figura 2.7: Due circuiti equivalenti per l’applicazione controllata di una fase ei↵ .
22
2.2. Circuiti quantistici
Figura 2.8: Applicazione di porte controllate C 1 (U ) qualsiasi mediante cnot e porte di singolo qubit.
Figura 2.9: Applicazione di porte controllate C 2 (U ) qualsiasi mediante cnot e porte C 1 (V ). Vale la relazione V 2 = U .
Per prima cosa analizziamo il circuito a sinistra in figura 2.7: esso applica una fase globale ei↵ condizionatamente al valore del primo qubit. Dato che ei↵ |1ti = (ei↵ |1i) ⌦ |ti
questa porta pu`o essere realizzata, in un’altra maniera, utilizzando una singola operazione U 0 che agisce invece sul qubit di controllo (vedi ancora fig. 2.7 a destra). Per costruire una qualsiasi operazione C 1 (U ) ci si serve del precedente risultato unito al teorema di decomposizione 2.12, come dal circuito in figura 2.8: quando il primo qubit `e 1 allora U = ei↵ AXBXC viene applicata al secondo. In caso contrario agisce solamente ABC = 1, e non si ha alcuna modifica dei qubit. Occupiamoci ora delle porte C 2 (U ). Esse richiedono la disponibilit`a di una porta V scelta in modo che V 2 = U . Il circuito appropriato `e rappresentato in figura 2.9. Facendo uso della logica booleana possiamo calcolare lo stato finale |f i del qubit bersaglio: 8 2 V |ii se c1 = c2 = 1 > > > 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↵etto su |f i: esso ha la funzione di ripristinare c2 al suo valore iniziale (i qubit di controllo non devono venire modificati dalla porta controllata). Utilizzando l’operatore C 2 (X), detto porta di To↵oli, `e possibile sommare i qubit modulo 2, rendendo possibile la realizzazione di porte controllate qualsiasi 23
Capitolo 2. Il modello di computazione a circuito quantistico
Figura 2.10: Circuito per la realizzazione di porte controllate C N (U ). Sono necessarie ` rappresentato il caso N = 5. C 2 (X) (porta di To↵oli) e C 1 (U ). E
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 nel circuito servono a ripristinare i qubit di controllo. In questo schema, concettualmente semplice, sono necessari N 1 qubit di lavoro per memorizzare i risultati intermedi delle somme; tuttavia `e possibile disegnare dei circuiti pi` u raffinati che non fanno uso di qubit di lavoro. Siamo ora giunti al termine di una dimostrazione completa di come eseguire delle operazioni controllate C N (U ) utilizzando solamente cnot e porte logiche di singolo qubit. Analizziamo ciascun elemento del circuito 2.10: • la porta U controllata si pu`o scomporre in cnot e operatori di singolo qubit, come dal circuito 2.8. • le porte di To↵oli p si implementano mediante lo schema 2.9 ponendo U = X, dunque V = X = (1 i)(1 + iX)/2. Sono necessari il cnot ed operatori controllati di singolo qubit; per questi ultimi ci riconduciamo al caso precedente. Come a↵ermato al paragrafo 2.2.5, ci siamo limitati al caso di U agenti su singolo qubit (K = 1). Per K qualsiasi il risultato trovato continua ad essere valido; 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 collasso dello stesso in uno stato puro e una perdita di informazione. Le misurazioni sulla 24
2.2. Circuiti quantistici
Figura 2.12: Applicazione del principio della misura ritardata.
base computazionale sono utilizzate nei circuiti quantistici per convertire dei qubit in dei bit probabilistici 2 . Esse si indicano con il simbolo di figura 2.11, nel quale i rami doppi trasportano bit classici. Le misurazioni in un circuito quantistico obbediscono a due regole: Principio della misura ritardata: le misurazioni possono sempre essere spostate 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’operazione controllata classicamente pu`o essere rimpiazzata da un operazione controllata quantisticamente. La ragione fisica di questo primo principio `e da ricercarsi nell’entanglement. Il circuito di figura 2.12 pu`o essere condensato nella frase “le misurazioni commutano con i controlli”. Ammettiamo che lo stato iniziale del sistema sia dato dalla 2.1. Possiamo vedere come nel primo caso (misura ritardata, disegno a sinistra) la perdita dell’informazione associata alle ampiezze corrispondenti allo stato del primo qubit che non viene misurato sia causata a posteriori dalla proiezione del primo qubit sullo stato che viene misurato. Chiamiamo | 0 i lo stato del sistema dopo l’applicazione dell’operazione controllata: |
0 rit. i
0 0 = C(U ) | i = ↵00 |00i + ↵01 |01i + ↵10 |10i + ↵11 |11i
in quanto l’operazione agisce solo sugli stati per i quali il qubit di controllo (rappresentato dal primo delle due cifre binarie) `e 1. Se la misura finale sul primo qubit fornisce l’autovalore legato a |0i, lo stato finale del sistema sar`a |
00 rit. i
1 =p (↵00 |00i + ↵01 |01i) |↵00 |2 + |↵01 |2
(2.14)
nell’altro caso avremo invece | 2
00 rit. i
1 0 0 =p 0 (↵10 |10i + ↵11 |11i) 0 2 2 |↵10 | + |↵11 |
(2.15)
Con “misurazione sulla base computazionale” intendiamo la misura di un osservabile avente i ket |0i e |1i come autovettori.
25
Capitolo 2. Il modello di computazione a circuito quantistico Per quanto riguarda la misura non ritardata (disegno di sinistra in figura 2.12) la proiezione della funzione d’onda avviene prima, lasciando il sistema nello stato
oppure nello stato
1 | 0i = p (↵00 |00i + ↵01 |01i) 2 |↵00 | + |↵01 |2 1 | 0i = p (↵10 |10i + ↵11 |11i) |↵10 |2 + |↵11 |2
(2.16)
(2.17)
Applicando C(U ) alle 2.16 e 2.17 si ritrovano esattamente le 2.14 e 2.15, rispettivamente (teniamo presente che per l’unitariet`a di U deve valere |↵10 |2 + |↵11 |2 = 0 2 0 2 |↵10 | + |↵11 | ). Prestiamo attenzione al fatto che nel caso della misura implicita, prima della misurazione l’informazione corrispondente a entrambe le possibilit`a (collasso in |0i o in |1i del primo qubit) `e contenuta nei due qubit. Si tratta di un aspetto peculiare della meccanica quantistica che `e possibile sfruttare a fini algoritmici (vedi parallelismo quantistico, §3.2). Esso si manifesta sperimentalmente in varianti dell’interferenza da doppia fenditura quali il quantum eraser ed esperimenti ad esso affini. Principio della misura implicita: si pu`o assumere di misurare ciascun ramo non terminato (ovvero che non si conclude con una misurazione) di un circuito quantistico senza perdita di generalit`a. Illustriamo pi` u in dettaglio il senso di questo secondo principio. Supponiamo di avere un sistema di due qubit descritti da un operatore densit`a ⇢k = |
k ih 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’operatore densit`a si trasforma in Pi | k ih k | Pi ⇢0k,|ii = h k |Pi | k i se la misura ha dato risultato i. Se ignoriamo il risultato della misurazione la nostra conoscenza dello stato del sistema si pu`o racchiudere in ⇢0k = tr(⇢k P0 )⇢0k,|0i + tr(⇢k P1 )⇢0k,|1i ovvero, essendo tr(⇢k Pi ) = h
k |Pi | k i,
⇢0k = P0 | 26
k ih k | P0
+ P1 |
k ih k | P1
(2.18)
2.3. Un insieme di porte logiche quantistiche universali Nel caso generale abbiamo che ⇢ descrive una miscela statistica di stati: X ⇢= p k ⇢k k
Secondo la 2.18 avremo che l’operatore densit`a dopo la misura sar`a ora X X⇥ ⇤ ⇢0 = pk ⇢0k = pk (P0 | k ih k | P0 + P1 | k ih k | P1 ) k
(2.19)
k
= P0 ⇢P0 + P1 ⇢P1
(2.20)
Dimostriamo che la statistica delle misurazioni sul secondo qubit non `e stata modificata dalla misurazione e↵ettuata sul primo, ovvero che: tr1 ⇢ = tr1 ⇢0 Indichiamo con |ui i i vettori della base del primo qubit e con |vi i quelli del secondo. Per definizione abbiamo X (tr1 ⇢)nn0 = hup vn |⇢|up vn0 i p
Confrontiamo questo operatore con quello ottenuto da ⇢0 : X (tr1 ⇢0 )nn0 = hup vn |(P0 ⇢P0 + P1 ⇢P1 )|up vn0 i = p
= hu0 vn |⇢|u0 vn0 i + hu1 vn |⇢|u1 vn0 i =
X p
hup vn |⇢|up vn0 i (2.21)
che `e quanto volevamo dimostrare.
2.3
Un insieme di porte logiche quantistiche universali
In questo paragrafo dimostreremo che le porte logiche H, S, cnot e T formano un insieme di porte universali, ovvero che qualunque circuito quantistico pu`o essere realizzato (o, pi` u propriamente, approssimato) utilizzando gli operatori suddetti. Questo risultato `e fondamentale dal punto di vista della realizzazione sperimentale dei computer quantistici, in quanto nella realt`a si ha a disposizione un numero finito 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 U d⇥d pu`o essere scritta come prodotto di matrici unitarie a due livelli, ovvero matrici unitarie che agiscono solamente nel sottospazio generato da due vettori qualsiasi della base computazionale. Consideriamo il caso d = 3; dimostreremo che U3 U2 U1 U = 1 27
Capitolo 2. Il modello di computazione a circuito quantistico con U3 , U2 e U1 matrici unitarie a due livelli. Sia 0 a d U = @b e c f
Da ci`o segue che U = U1† U2† U3† . 1 g hA j
Applichiamo ad U una trasformazione unitaria della prima colonna (se tale termine `e gi`a nullo 0 1 ⇤ ⇤ p a2 2 p b2 2 0 0 |a| +|b| B |a| b+|b| C a d a Bp C@ @ |a|2 +|b|2 p|a|2 +|b|2 0A b e c f 0 0 1 Allo stesso modo annulliamo il terzo termine 0 1 0⇤ 0⇤ p 0a2 0 2 0 p 0c2 0 2 0 0 a |a | +|c | C B |a | +|c | B C @ 0 1 0 @ A 00 0 0 p 0 c2 0 2 0 p 0 2a 0 2 c |a | +|c |
|a | +|c |
U1 che annulli il secondo termine possiamo porre U1 = 1): 1 0 0 0 01 g a d g A @ h = 0 e0 h0 A j c0 f 0 j 0
della prima colonna: 1 0 1 d0 g 0 1 d00 g 00 e0 h0 A = @0 e00 h00 A f 0 j0 0 f 00 j 00
Al secondo membro compare un prodotto di matrici unitarie, che `e a sua volta unitario. Per questo deve essere d00 = g 00 = 0 (le colonne e le righe di una matrice unitaria hanno norma unitaria). A questo punto abbiamo ottenuto una matrice diagonale a blocchi, e possiamo ripetere il procedimento per il secondo blocco trovando infine la matrice identit`a. Il metodo si pu`o estendere a matrici di dimensione maggiore; in generale per matrici d–dimensionali sono necessarie al pi` u d(d 1)/2 matrici Ui . In termini di qubit, N essendo d = 2 , il numero massimo di trasformazioni da utilizzare `e 2N 2 (2N 1).
2.3.2
Applicazione di porte unitarie a due livelli qualsiasi mediate porte di singolo qubit
Cerchiamo ora un metodo che ci permetta di applicare ad un sistema di N qubit una trasformazione unitaria a due livelli utilizzando le porte logiche e le tecniche di cui abbiamo parlato al §2.2. Ricordiamo che una matrice unitaria a due livelli U appare come 0 1 1 0 0 0 B0 a 0 c C B C @0 0 1 0 A 0 b 0 d Possiamo sempre costruire una matrice bidimensionale U˜ estraendo la parte non banale di U : ✓ ◆ a c ˜ U= b 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
2.3. Un insieme di porte logiche quantistiche universali all’applicazione (condizionata) dell’operatore U˜ su un singolo qubit, quindi di eseguire gli scambi inversi per riavere infine l’ordine originale. Se ad esempio la matrice U agisce solamente sui vettori |00010i e |10101i della base computazionale, identificati rispettivamente dalle stringhe binarie x1 = 00010 e xm = 10101, facciamo in modo di trasferire l’ampiezza associata a |x1 i ad un vettore |xm 1 i 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 iniziale delle ampiezze. La sequenza di scambi pi` u rapida `e un codice di Gray: con questa dicitura si indica genericamente una successione di stringhe binarie nella quale due stringhe adiacenti di↵eriscono soltanto per un bit. Nel caso in questione una sequenza del genere `e ad esempio x1 x2 x3 x4 x5
= 00010 = 00011 = 00001 = 00101 = 10101
(2.22)
Ora ci troviamo di fronte al problema di come e↵etture lo scambio di ampiezze fra due vettori |xn i e |xn+1 i aventi associate le stringhe binarie xn e xn+1 che di↵eriscono solamente nell’k–esimo bit. Ci`o si pu`o eseguire applicando allo stato | i del sistema, dato da X | i= ↵xj |xj i j
(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 stringhe binarie. Illustriamo la procedura completa nel caso di un sistema di N = 3 qubit. Supponiamo di voler applicare l’operatore 0 1 a 0 0 0 0 0 0 c B0 1 0 0 0 0 0 0C B C B0 0 1 0 0 0 0 0C B C B0 0 0 1 0 0 0 0C C U =B (2.23) B0 0 0 0 1 0 0 0C B C B0 0 0 0 0 1 0 0C B C @0 0 0 0 0 0 1 0A b 0 0 0 0 0 0 d che agisce solamente sugli stati |000i e |111i. Scriviamo il codice di Gray: x1 x2 x3 x4
= = = =
A
B
C
0 0 0 1
0 0 1 1
0 1 1 1 29
Capitolo 2. Il modello di computazione a circuito quantistico
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 da A = B = 0; il secondo e ultimo scambio applica X al qubit B condizionalmente a A = 0 e C = 1. Ora procediamo applicando U˜ al qubit A condizionalmente a B = C = 1, quindi e↵ettuiamo le operazioni di scambio in ordine inverso. Il circuito adatto `e disegnato in figura 2.13. Riassumiamo quanto abbiamo ottenuto finora. Grazie ai risultati del paragrafo 2.2.6 sappiamo realizzare tutti gli elementi contenuti nel circuito 2.13 utilizzando cnot e porte logiche di singolo qubit. D’altra parte tramite questo circuito riusciamo a realizzare qualsiasi trasformazione U , scomponendola in matrici a due livelli. Pertanto riusciamo ad applicare qualsiasi matrice U ai qubit limitandoci ad 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 che ciascuna trasformazione unitaria su singolo qubit si pu`o approssimare, con un errore piccolo a piacere, tramite un’insieme finito di porte logiche su singolo qubit. Tale insieme non `e unico; nel nostro caso sar`a formato da H
S
cnot
⇡/8
Errore di approssimazione Dato che stiamo parlando di un’approssimazione, cerchiamo per prima cosa una quantit`a che ci possa dare un indicazione dell’errore intrinseco commesso. Chiamiamo U l’operatore di interesse e V la sua approssimazione. Definiamo l’errore di approssimazione come E(U, V ) = max k(U | i
V )| ik
(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, dimostriamo che, essendo PU la probabilit`a di ottenere una data grandezza misurando un osservabile A nello stato U | i e PV il corrispettivo per lo stato V | i, vale la relazione |PU PV | 2E(U, V ) (2.25) 30
2.3. Un insieme di porte logiche quantistiche universali Secondo questa definizione la somiglianza tra le due trasformazioni `e quantificata dall’affinit`a delle statistiche delle misurazioni sugli stati trasformati. Calcoliamo il primo membro della 2.25: |PU
PV | = | h | U † M i U | i
h | V † Mi V | i |
Stiamo indicando con Mi l’operatore di proiezione sull’autostato | i i corrispondente al risultato p della misura dell’osservabile A. Ponendo ora | i = (U V ) | i — si noti che h | i = E(U, V ) — possiamo scrivere |PU
PV | = | h | U † M i | i + h | M i V | i |
| h | U † Mi | i | + | h | Mi V | i |
Sfruttiamo ora la disuguaglianza di Cauchy-Schwarz |PU
PV | kMi† U | i k · k | i k + k | i k · kMi V | i k
Calcoliamo kMi† U | i k = h | U † Mi Mi† U | i = †
X j
(2.26)
h | U † Mi | j i h j | Mi† U | i
= h | U | i i h i |U | i = | h i |U | i |2 1
P dove abbiamo fatto uso della relazione di completezza dell’osservabile A, j | j ih j | = 1, dell’unitariet`a di U e della normalizzazione di | i. Allo stesso modo si trova che kMi V | 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 allora l’errore totale commesso `e limitato superiormente dalla somma degli errori degli operatori singoli: E(Um Um
1
. . . U1 , Vm Vm
1
. . . V1 )
m X
E(Uj , Vj )
j=1
Dimostriamo questa a↵ermazione per m = 2; il caso generale segue per induzione. E(U2 U1 , V2 V1 ) = k(U2 U1 V2 V1 ) | i k = k(U2 U1 V2 U1 ) | i + (V2 U1 V2 V1 ) | i k k(U2 V2 )U1 | i k + kV2 (U1 V1 ) | i k E(U2 , V2 ) + E(U1 , V1 ) Dunque nel caso volessimo approssimare un circuito contenente m porte logiche di singolo qubit mantenendo le probabilit`a corrette entro una tolleranza , dovremmo fare in modo che E(Uj , Vj ) /(2m) per ciascuna porta logica (j = 1, 2, . . . , m). 31
Capitolo 2. Il modello di computazione a circuito quantistico Metodo di approssimazione Dimostriamo che H e T possono essere usati per approssimare qualsiasi U 2⇥2 . Da quanto esposto al §2.2 possiamo vedere come T rappresenti, a meno di una fase globale, una rotazione di ⇡/4 attorno all’asse z nella sfera di Bloch. Similmente HT H `e una rotazione dello stesso angolo attorno all’asse x. Componendo queste due rotazioni se ne ottiene una terza: ⇣ ⇡ ⌘ ⇣ ⇡ ⌘ h ⇡ ⇡ ih ⇡ ⇡ i exp i Z exp i X = cos 1 i sin Z cos 1 i sin X (2.27) 8 8 8 8 8 8i h ⇡ ⇡ ⇡ ⇡ = cos2 1 i cos (X + Z) + sin Y sin (2.28) 8 8 8 8
Riferendoci alla 2.11 possiamo ricondurre l’espressione di sopra ad una rotazione attorno al versore ⇣ 1 ⇡ ⇡ ⇡⌘ n ˆ=p cos , sin , cos 8 8 8 1 + cos2 ⇡8 rotazione di un angolo ✓ che soddisfa ( cos 2✓ = cos2 ⇡8 p sin 2✓ = sin ⇡8 1 + cos2
⇡ 8
Questo sistema ha soluzione, in quanto quadrando e sommando i secondi membri delle equazioni si trova l’unit`a. Chiamiamo Rnˆ (✓) l’operatore 2.28. Secondo alcuni teoremi della teoria dei numeri si pu`o dimostrare che ✓ `e un multiplo irrazionale di 2⇡. Questo permette di approssimare, con un errore arbitrariamente piccolo, qualsiasi rotazione attorno a n ˆ tramite applicazioni ripetute dell’operatore Rnˆ (✓). Per dimostrarlo definiamo ✓k = (k✓) mod 2⇡, dove k = 1, . . . , N . Si dovr`a avere che min |✓i
✓j |
i,j
2⇡ N
i,j = 1, . . . , N
in quanto in un insieme di N punti su una circonferenza, la distanza angolare minima tra due punti consecutivi non pu`o superare 2⇡/N radianti. Se assumiamo i > 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 Pertanto `e sempre possibile trovare un intero n tale che E(Rnˆ (↵), Rnˆ (✓)n ) <
" 3
< ✓i
j
2⇡/N . (2.29)
A questo punto se riusciamo a trovare un’altra rotazione del genere attorno a un’asse m ˆ 6= n ˆ possiamo approssimare qualsiasi porta logica di singolo qubit mediante la 2.13. Ricordando la 2.8 possiamo trovare che HRnˆ (✓)H = Rm ˆ (✓) 32
2.3. Un insieme di porte logiche quantistiche universali dove
1 m ˆ =p 1 + cos2
⇡ 8
⇣
⇡ cos , 8
⇡ ⇡⌘ sin , cos 8 8
Mediante questo operatore possiamo approssimare qualunque Rm ˆ (↵) con un errore n E Rm = E HRnˆ (↵)H,(HRnˆ (✓)H)n ) ˆ (↵), Rm ˆ (✓)
= E HRnˆ (↵)H,HRnˆ (✓)n H) " = 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ˆ (✓)n1 HRnˆ (✓)n2 HRnˆ (✓)n3 ) < " Per comporre l’insieme di porte quantistiche universali aggiungiamo agli operatori H e T il cnot, necessario per le tecniche di decomposizione dei paragrafi precedenti. La fase S viene anch’essa inclusa nell’insieme in quanto permette di rendere la computazione quantistica tollerante ai guasti (fault tolerant), ovvero per acconsentire il calcolo anche in presenza di rumore. Tratteremo questo argomento al capitolo 4.2. Efficienza dell’approssimazione Discutiamo ora brevemente di quanto efficientemente lavori il metodo di approssimazione sviluppato. Se assumiamo ragionevolmente che i punti relativi agli angoli ✓k si dispongano pi` u o meno uniformemente lungo la circonferenza, allora sarebbero necessari, secondo la notazione del precedente paragrafo, ⇥(N ) applicazioni di Rnˆ (✓) per approssimare un’arbitraria rotazione a meno di un angolo < 2⇡/N . In termini della tolleranza " il numero di porte necessarie `e dunque ⇥(1/"). Se volessimo approssimare un circuito contenente m porte logiche di singolo bit e cnot tramite il nostro insieme universale entro un errore " dovremmo approssimare ciascuna delle m porte con una tolleranza "/m. Il numero di operazioni necessarie sarebbe perci`o ⇥(m2 /"): esso cresce quadraticamente con la grandezza del circuito, da cui possiamo dedurre che l’approssimazione sia fattibile in maniera efficiente. In termini pi` u rigorosi, esiste un teorema di Solovay-Kitaev che a↵erma che un operatore di singolo qubit arbitrario pu`o essere approssimato col nostro insieme 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 si approssima con O(m logc (m/")). Si tratta di un andamento polilogaritmico per cui l’approssimazione pu`o considerarsi efficiente. La situazione si prospetta meno entusiasmante se includiamo nel circuito che vorremmo costruire operatori U di dimensione arbitraria: si pu`o dimostrare che la loro realizzazione mediante i metodi descritti richiede un numero di trasformazioni che cresce esponenzialmente con il numero di qubit del sistema. 33
Bibliografia
Bibliografia [NC00]
34
Michael A. Nielsen e Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.
Capitolo 3 Algoritmi quantistici Dopo la panoramica sui circuiti quantistici, tratteremo in questo capitolo alcuni algoritmi particolarmente istruttivi per quanto riguarda la manipolazione delle informazioni praticabile per mezzo della meccanica quantistica.
3.1
Teletrasporto quantistico
Il primo argomento di questo capitolo non `e un’algoritmo nel senso stretto del termine, ma piuttosto un interessante applicazione dell’elaborazione quantistica dell’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 avente due 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 valore `e fissato indipendentemente dall’input del circuito, possiamo creare mediante tale porta logica un circuito che copia il bit in ingresso x. Ponendo y = 0 nella 3.1 otteniamo 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. Siamo per questo tentati di convertire il circuito di copia classico nel suo equivalente quantistico (figura 3.1). Tuttavia questo circuito non e↵ettua una copia vera e propria: se il qubit da copiare (primo input) dato da | i = a |0i + b |1i controlla un cnot che agisce sull’ancilla qubit (secondo input) |0i, si ottiene come output sul secondo qubit lo stato a |00i + b |11i che `e diverso in generale da | i | i = a2 |00i + ab |01i + ab |10i + b2 |11i
Come gi`a menzionato, esiste un teorema (no–cloning theorem) che impedisce la 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 circuito quantistico (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 | 1 i e | 2 i e facendo il prodotto scalare di ambo i membri delle due espressioni si trova (h 1 | ⌦ hs|)U † U (| 2 i ⌦ |si) = (h 1 | ⌦ h 1 |)(| 2 i ⌦ | 2 i) h 1 | 2 i = (h 1 | 2 i)2 che ha per soluzioni h 1 | 2 i = 0 e h 1 | 2 i = 1. Di conseguenza un ipotetico dispositivo di copia potrebbe funzionare a dovere solo per un certo insieme di stati di input tra loro ortogonali: un processo per la copia di stati arbitrari non pu`o esistere. Ci`o che `e invece possibile `e trasferire lo stato del primo sottostistema sul secondo. Se i due sottosistemi sono spazialmente distanti il trasferimento prende l’accezione di teletrasporto. Tale nomenclatura `e per certi aspetti impropria, dato che, come vedremo, `e necessario per compiere il trasferimento uno scambio aggiuntivo di informazione classica tra i due siti distanti — ribadiamo che l’entanglement non viola la relativit`a speciale; tuttavia il termine teletrasporto sottolinea il fatto che il trasferimento avvenga in assenza di un canale di comunicazione quantistico che acconsenta lo spostamento fisico (nella fattispecie lo spostamento di uno spin in uno stato 2.1 o di un fotone con il suo stato di polarizzazione) dell’informazione quantistica.
3.1.2
Stati di Bell
Prima di analizzare lo schema circuitale del teletrasporto quantistico introduciamo i cos`ıddetti stati di Bell (noti anche come stati o coppie di EPR, per via del loro utilizzo nell’omonimo paradosso): si tratta di quattro stati massimamente entangled di due qubit. | 36
00 i
=
|00i + |11i p 2
|
01 i
=
|01i + |10i p 2
3.1. Teletrasporto quantistico
Figura 3.2: Circuito per la conversione degli stati della base computazionale di due qubit in stati di Bell.
Figura 3.3: Circuito per il teletrasporto quantistico.
|
10 i
=
|00i |11i p 2
O pi` u sinteticamente |
xy i
=
|
11 i
=
|01i |10i p 2
|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 computazionale mediante 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 | 00 i, quindi si sono separati prendendo con se ciascuno un qubit del sistema fisico impiegato. Come pu`o Alice trasferire a Bob un qubit | i = ↵ |0i + |1i, avendo a disposizione un canale di comunicazione classico? La soluzione `e il circuito 3.3 che ci apprestiamo ad analizzare. Alice accoppia il suo qubit della coppia 00 al qubit | i da teletrasportare: | Applica quindi a | |
2i
0i
0i
= | i|
00 i
un cnot e una porta di Hadamard ottenendo
⇤ 1 ⇥ = H p ↵ |0i (|00i + |11i) + |1i (|10i + |01i) 2 ⇤ 1⇥ = ↵(|0i + |1i)(|00i + |11i) + (|0i |1i)(|10i + |01i) 2 37
Capitolo 3. Algoritmi quantistici Raccogliendo i ket corrispondenti ai qubit in possesso di Alice la scrittura diventa 1⇥ | 2i = |00i (↵ |0i + |1i) + |01i (↵ |1i + |0i)+ (3.4) 2 ⇤ + |10i (↵ |0i |1i) + |11i (↵ |1i |0i) (3.5)
Alice misura ora i suoi due qubit, inviando i risultati a Bob; egli pu`o cos`ı “aggiustare” lo stato del suo qubit, applicando dei gate X o Z, in modo da farlo coincidere con | i: il teletrasporto `e completato.
3.1.4
Trasferimento dell’informazione
Mostriamo ora rigorosamente che Bob, non conoscendo il risultato della misura eseguita da Alice, non pu`o ricavare alcuna informazione sullo stato | i misurando il suo qubit. Dalla 3.5 vediamo che Alice operando la misurazione pu`o far collassare i suoi due qubit con eguale probabilit`a negli stati |00i, |01i, |10i e |11i. L’operatore densit`a post–misura del sistema `e perci`o 1⇥ ⇢= |00ih00| (↵ |0i + |1i)(↵⇤ h0| + ⇤ h1|)+ 4 + |01ih01| (↵ |1i + |0i)(↵⇤ h1| + ⇤ h0|)+ ⇤ + |10ih10| (↵ |0i |1i)(↵⇤ h0| h1|)+ ⇤ ⇤ ⇤ + |11ih11| (↵ |1i |0i)(↵ h1| h0|)
Ricaviamo ora l’operatore densit`a ridotto per il qubit di Bob (utilizziamo gli indici 1 e 2 in riferimento al sottosistema di Alice e Bob, rispettivamente). Ricordiamo che l’operatore densit`a ridotto del sistema 2 `e la traccia parziale sul sistema 1 dell’operatore densit`a totale. La traccia parziale si pu`o definire come tr2 (|a1 i ha2 | ⌦ |b1 i hb2 |) = |a1 i ha2 | tr |b1 i hb2 | nella quale |a1 i e |a2 i sono vettori qualsiasi dello spazio degli stati E1 del sistema 1, e |b1 i e |b2 i vettori qualsiasi di E2 . Essendo tr |x1 x2 ihx1 x2 | = 1 per ogni x1 , x2 = 0, 1 troviamo che 1⇥ ⇢2 = tr1 ⇢ = (↵ |0i + |1i)(↵⇤ h0| + ⇤ h1|) + (↵ |1i + |0i)(↵⇤ h1| + ⇤ h0|)+ 4 ⇤ ⇤ ⇤ (↵ |0i |1i)(↵⇤ h0| h1|) + (↵ |1i |0i)(↵⇤ h1| h0|) ⇤ 1⇥ 2(|↵|2 + | |2 ) |0ih0| + 2(|↵|2 + | |2 ) |1ih1| 4 |0ih0| + |1ih1| 1 = = 2 2 ⇢2 `e completamente slegato da | i. =
3.2
Parallelismo quantistico
Intendiamo con parallelismo quantistico la capacit`a di un sistema di n qubit di memorizzare contemporanemante i valori immagine di una funzione booleana 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 che fa l’associazione |x, yi 7! |x, y ⌦ f (x)i. Si verifica che Uf
|0i + |1i |0, f (0)i + |1, f (1)i p p |0i = 2 2
Questo stato di un singolo qubit contiene informazioni su due immagini di f . Il ragionamento si pu`o estendere a funzioni booleane di n bit con n qualsiasi utilizzando un registro di n qubit per la valutazione parallela di f pi` u uno per la memorizzazione del risultato (la base computazionale di n qubit ha dimensione 2n , quali sono anche i possibili input della funzione). In questo caso l’applicazione della porta di Hadamard sul singolo qubit del caso n = 1 si generalizza all’applicazione della trasformata di Hadamard su n qubit: quest’ultima equivale all’applicazione della porta H su ciascun qubit (fig. 3.5) e si indica con H ⌦n . Possiamo vedere che ↵ 1 X H ⌦n 0| .{z . . 0} = p |xi n 2 x n cifre
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 mediante la trasformata di Hadarmard e posto l’(n + 1)–esimo nello stato |0i si esegue un operatore Uf agente su n + 1 qubit secondo Uf |x1 x2 . . . xn i |0i = |x1 x2 . . . xn i |0
f (x1 , x2 , . . . , xn )i
Lo stato finale del sistema sar`a cos`ı 1 X p |xi |f (x)i 2 x In contrasto con il parallelismo classico, dove sono necessari n circuiti per la valutazione simultanea della funzione f , nel parallelismo quantistico `e sufficiente 39
Capitolo 3. Algoritmi quantistici un circuito soltanto. Notiamo per`o che questo non fornisce un accesso diretto ai valori f (x), per quanto a↵ermato al paragrafo 2.1.2. Per ottenere un vantaggio pratico dal parallelismo quantistico sono necessari degli algoritmi capaci di sfruttarlo. Illustreremo nel seguito due di questi algoritmi: l’algoritmo di Deutsch e quello 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 una sola valutazione della funzione. Esso `e eseguito dal circuito di figura 3.6. La trasformata di Hadarmard sullo stato iniziale |01i restituisce |0i + |1i |0i |1i p p | 1i = 2 2 Notando che
|0i |1i |0i |1i p = ( 1)f (x) p 2 2 Abbiamo che lo stato conseguente all’azione di Uf `e ih i 8 h |0i |1i p p <± |0i+|1i se f (0) = f (1) 2 2 h ih i | 2i = :± |0ip |1i |0ip |1i se f (0) 6= f (1) 2 2 Uf |xi
(3.6)
che dopo l’ultima porta di Hadamard diventa h i 8 <± |0i |0ip |1i se f (0) = f (1) 2 h i | 2i = :± |1i |0ip |1i se f (0) 6= f (1) 2 |0i |1i p = ± |f (0) f (1)i 2
Misurando il primo qubit troviamo appunto f (0) f (1). La meccanica quantistica consente di calcolare una propriet`a globale di una funzione mediante una sola valutazione. 40
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 avere una funzione booleana f ad n bit e di sapere che f pu`o essere o bilanciata, ovvero f (x) = 1 per 2n 1 input (la met`a degli input) e f (x) = 0 per i rimanenti, oppure costante. Vogliamo determinare a quale delle due tipologie appartenga f valutandola 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 met`a del numero degli input pi` u uno: 2n 1 + 1. Mediante il circuito quantistico di figura 3.7 si riesce invece a determinare la natura di f mediante una sola valutazione. Come per l’algoritmo del paragrafo precedente abbiamo bisogno di un registro di n qubit a cui poter associare gli input della funzione e di un qubit aggiuntivo per memorizzare l’immagine di f . Lo stato di partenza `e | 0 i = |0i⌦n |1i La trasformazione di Hadamard muta lo stato in X |xi |0i |1i p p | 1i = n 2 2 n x2{0,1} nel quale i primi n qubit sono in una sovrapposizione uniforme di tutti i possibili stati. Valutando f sul registro si ottiene per la 3.6 X ( 1)f (x) |xi |0i |1i p p | 2i = 2n 2 x
(3.7)
stato che contiene tutte le possibili immagini di f sugli input. Adesso applichiamo nuovamente la trasformazione di Hadarmard sul registro. Per calcolare lo stato risultante scriviamo l’azione di una singola porta di Hadamard su un singolo qubit |0i o |1i come: P ( 1)xz |zi H |xi = z p x, z = 0, 1 2 41
Capitolo 3. Algoritmi quantistici tramite la quale possiamo esprimere l’azione di H ⌦n sugli stati della base computazionale degli n qubit come P x1 z1 +...+xn zn |z1 . . . zn i z1 ,...,zn ( 1) ⌦n p H |x1 , . . . , xn i = (3.8) 2 P x·z |zi z ( 1) p = (3.9) 2 dove con x · z indichiamo il prodotto bit a bit delle due stringhe binarie, modulo 2. Sostituendo la 3.9 nell’espressione di | 2 i 3.7 si ottiene P x·z+f (x) |zi |0i |1i z ( 1) p | 3i = 2n 2 Osserviamo ora come nel caso in cui f `e costante l’ampiezza del vettore |0i⌦n , pari P a 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’autovettore corrispondente a |0i⌦n ; per qualunque altro esito f dovr`a essere bilanciata. Questo algoritmo appare molto pi` u veloce dell’equivalente classico, tuttavia vi sono alcune osservazioni da fare: • Il problema di Deutsch non ha applicazioni pratiche. • I due algoritmi, classico e quantistico, non sono facilmente comparabili dato che il metodo di valutazione di f che si impiega `e assai diverso. v • Il problema pu`o essere risolto classicamente in maniera probabilistica molto pi` u efficientemente rispetto alla risoluzione esatta che richiede 2n 1 valutazioni. Supponendo f bilanciata infatti la probabilit`a di trovare m valori uguali di f (x) in m valutazioni `e Pm =
m Y1 i=1
2n 1 i 2n i
che decresce rapidamente all’aumentare di m.
3.3
La trasformata di Fourier quantistica
Uno dei mezzi ritenuti pi` u promettenti per lo sviluppo di algoritmi quantistici in grado di velocizzare la risoluzione di certi problemi di interesse `e la trasformata di Fourier 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 date da ✓ ◆ N 1 1 X 2⇡k yk = p xj exp i j (3.10) N N j=0 42
3.3. La trasformata di Fourier quantistica La trasformazione `e invertibile secondo ✓ ◆ N 1 1 X 2⇡k xj = p yk exp i j N N k=0
(3.11)
Sostituendo infatti la 3.10 nella 3.11 si trova ✓ ◆" ✓ ◆# N 1 N 1 1 X 2⇡k 2⇡k 1 X p xj = p exp i y xm exp i m N N N k=0 N m=0 ✓ ◆ N 1 N X1 1 X 2⇡j = xm exp i (m k) N m=0 N m=0 N 1 1 X = xm N N m=0
mk
= xj
Si pu`o 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 X1 j=0
xj |ji
si ottiene sostituendo ai coefficienti complessi xj la loro trasformata di Fourier discreta: " ✓ ◆# N N N X1 X1 X1 1 N X1 2⇡k F p xj |ji ! yk |ki = xj exp i j |ki N N j=0 j=0 k=0 k=0 " ✓ ◆ # N N 1 X1 1 X 2⇡k = xj p exp i j |ki N N j=0 k=0 Si pu`o dunque definire un operatore F che agisce secondo ✓ ◆ N 1 1 X 2⇡k F |ji = p exp i j |ki N N k=0
(3.12)
Per quanto rigurda l’operatore inverso F 1 abbiamo che " ✓ ◆# N N 1 N 1 N 1 X1 X X X 1 1 2⇡k F p yk |ki ! xj |ji = yk exp i j |ji N N j=0 j=0 k=0 k=0 " ✓ ◆ # N 1 N 1 X 1 X 2⇡k = yk p exp i j |ji N N j=0 k=0 Per cui F
1
✓ ◆ N 1 1 X 2⇡k |ki = p exp i j |ji N N j=0
(3.13) 43
Capitolo 3. Algoritmi quantistici
Figura 3.8: Circuito che esegue la trasformata di Fourier quantistica di n qubit.
Mostriamo un altro modo per scrivere la trasformata di Fourier quantistica che si riveler`a fondamentale nel seguito. Supponiamo di avere n qubit ai quali `e associata la base computazionale |0i, . . ., |2n 1i costituita da 2n vettori. Per identificare tali vettori facciamo uso della numerazione binaria: j = j 1 j 2 . . . jn = j 1 2 n
1
+ j2 2 n
2
+ . . . + jn 2 0
Ci serviremo anche delle frazioni binarie 1
j = 0.jl jl+1 . . . jm = jl 2
+ jl+1 2
2
+ . . . + jm 2
(m l+1)
Riprendiamo la definizione 3.12: ✓
◆ 2⇡k F |ji = n/2 exp i n j |ki 2 2 k=0 " ! # 1 1 n X X 1 X = n/2 ... exp i2⇡ kl 2 l j |k1 . . . kn i 2 k =0 k =0 l=1 n
2 1 1 X
n
1
= = = =
1 2n/2
1 X
k1 =0
... "
1 O n X
kn =0 l=1
n 1 1 O X
2n/2 1
2n/2
l
l=1 kl =0 n h O
e2⇡ijkl 2 |kl i l
|0i + e2⇡ij2 |1i
l=1 2⇡i0.jn
(|0i + e
l
e2⇡ijkl 2 |kl i #
i
|1i)(|0i + e2⇡i0.jn 1 jn |1i) . . . (|0i + e2⇡i0.j1 j2 ...jn |1i) 2n/2
(3.14)
Il circuito per l’esecuzione della trasformata di Fourier quantistica `e riportato in figura 3.8; essendo composto esclusivamente da operatori unitari prova l’unitariet`a della trasformazione F che rappresenta. Esso `e riconducibile all’espressione 3.14: occupiamoci della prima parte del circuito, dedicata alla trasformazione del primo qubit. La porta di Hadamard modifica lo stato del sistema in 1 21/2 44
|0i + e2⇡i0.j1 |1i |j2 . . . jn i
3.3. La trasformata di Fourier quantistica dato che e2⇡i0.j1 = ( 1)j1 . La rotazione controllata ✓ ◆ 1 0 Rk = k 0 e2⇡i2 con k = 2 applica all’ampiezza del vettore |1i della base computazionale del primo qubit 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 dallo schema 3.8 si ottiene infine lo stato 1 21/2
|0i + e2⇡i0.j1 j2 ...jn |1i |j2 . . . jn i
identico, per quel che concerne il primo qubit, alla 3.14. Si procede alla stessa maniera per gli altri n 1 qubit, portando a coincidere lo stato del sistema con la definizione alternativa 3.14 della trasformata. Si pu`o notare che per il qubit k–esimo sono sempre necessarie una porta di Hadamard ed n k rotazioni: in totale nel circuito si utilizzano n + (n 1) + . . . + 1 = n(n + 1)/2 = ⇥(n2 ) operazioni. L’algoritmo pu`o apparire come un grosso passo in avanti rispetto alla FFT (fast Fourier transform) classica che richiede ⇥(n2n ) operazioni, tuttavia l’algoritmo quantistico non pu`o essere facilmente utilizzato nel calcolo delle trasformate di Fourier: ci`o si deve all’impossibilit`a della misura diretta delle ampiezze trasformate e, nondimeno, alle difficolt`a nella preparazione degli stati di input. La trasformata di Fourier quantistica ha comunque delle altre importanti applicazioni tra le quali la ricerca del fattori di un numero. Arriveremo a trattare il principio che sta alla base 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 , con 0 < 1 e incognito. L’algoritmo per la stima della fase permette di ricavare con una certa approssimazione sfruttando la trasformata di Fourier quantistica. L’algoritmo non ha una sua utilit`a propria ma pu`o venir utilizzato come subroutine in altri algoritmi. Per la sua esecuzione `e necessario un registro di t qubit inizializzati a |0i, in cui si memorizzer`a la fase , e un secondo registro nello stato |ui a cui verr`a applicato U . Come vedremo la dimensione del primo registro `e il fattore che regola la precisione con cui si determiner`a 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, seguita da delle applicazioni controllate di potenze di U 2 sul secondo registro. Alla fine di questa fase lo stato del primo registro `e 1 2t/2
(|0i + e2⇡i2
t 1
|1i)(|0i + e2⇡i2
t 2
0
|1i) . . . (|0i + e2⇡i2 |1i) = t
=
2 1 1 X
2t/2
k=0
e2⇡i
k
|ki (3.15) 45
Capitolo 3. Algoritmi quantistici
Figura 3.9: Primo stadio della stima della fase.
Figura 3.10: Circuito completo per la stima della fase. Il simbolo ‘/’ denota un registro di qubit.
in quanto le fasi controllate non sono applicate ai vettori |0i delle basi computazionali dei singoli qubit. La seconda parte dell’algoritmo consiste nell’applicazione della trasformata di Fourier inversa: se pu`o essere scritto esattamente come frazione binaria in t bit come = 0. 1 . . . t allora lo stato 3.15 si pu`o riscrivere nella forma seguente: 1 2t/2
(|0i + e2⇡i0. t |1i)(|0i + e2⇡i0.
t 1 t
|1i) . . . (|0i + e2⇡i0.
1 2 ... t
|1i)
(3.16)
Confrontando la 3.16 con la 3.14 vediamo come applicando la trasformata di Fourier inversa sul primo registro allo stadio del circuito a cui siamo giunti ci ottenga lo stato | i, da cui `e misurabile direttamente l’espansione binaria di . t
2 1 1 X
2t/2
k=0
e2⇡i
k
|ki |ui
F
↵ 1 ! e |ui
(3.17)
Il motivo per cui abbiamo utilizzato e in luogo di nella 3.17 `e che in generale non `e esprimibile esattamente come frazione binaria. A↵rontiamo ora il caso generale calcolando esplicitamente la trasformata di Fourier inversa 3.13 del primo 46
3.3. La trasformata di Fourier quantistica membro della 3.17 (sul primo registro): t
F
1
2 1 1 X
2t/2
t
e2⇡i
k=0
k
2 1 1 X
|ki |ui =
2t/2
1 = t 2
e2⇡i
k
k=0
t 1 2X
j=0
" 2t 1 X
e
"
t
2 1 1 X
2t/2
2⇡i k
exp
j=0
exp
k=0
✓
i
✓
2⇡k j 2t
◆ # 2⇡k i t j |ji |ui 2 ◆# |ji |ui
(3.18)
Chiamiamo ora b l’intero compreso tra 0 e 2t 1 tale che b/2t = 0.b1 . . . bt `e la migliore approssimazione per difetto di (vale la disuguaglianza b/2t ). Per ricavare la probabilit`a di ottenere, all’atto della misura, un valore diverso dall’autovalore di |bi calcoliamo dapprima l’ampiezza ↵l dello stato |(b + l) mod 2t i, ponendo j = (b + l) mod 2t nella 3.18 e notando che ( " #)k (b + l) mod 2t (b + l) exp i2⇡k = exp i2⇡ 2t 2t Si ha
2t 1 1 X n 2⇡i[ ↵l = t e 2 k=0
(b+l)/2t ]
ok
la quale `e la somma parziale di una serie geometrica: !k t 1 1 e2⇡i[2 (b+l)] ↵l = t 2 1 e2⇡i[ (b+l)/2t ] Definiamo
=
b/2t . Allora 1 ↵l = t 2
1 1
e2⇡i(2 e2⇡i(
t
l) l/2t )
!
Vogliamo calcolare la probilit`a di misurare una grandezza m tale che |m dove e `e un intero che quantifica la tolleranza richiesta. Questa vale X X P(|m b| > e) = |↵l |2 + |↵l |2 2t
1 e,
1
(le due sommatorie insieme coinvolgono i moduli quadri delle ampiezze di tutti i vettori della base computazionale del registro, esclusi quelli che distano al pi` ue da b). Si trova che 1 P(|m b| > e) (3.19) 2(e 1) Per cui la probabilit`a di determinare con un accuratezza di 2 n , ovvero la probabilit`a che la stima di sia esatta all’n–esima cifra binaria dopo la virgola, soddisfa, secondo la 3.19, 1
P |m
b| > 2t
n
1
1
1 2(2t n
2)
(3.20) 47
Capitolo 3. Algoritmi quantistici dove la tolleranza e `e data dal numero massimo esprimibile con t n cifre binarie. Se volessimo imporre che tale probabilit`a debba valere al meno 1 " dovremmo scegliere, per la 3.20, ✓ ◆ 1 t = n + log2 2 + 2" Vediamo dunque come il numero t di qubit del primo registro sia regolato dai vincoli imposti all’errore (parametro n) e alla probabilit`a di riuscita (parametro ") dell’algoritmo.
3.3.2
Ricerca dell’ordine moltiplicativo
Figura 3.11: Schema del circuito per la ricerca dell’ordine moltiplicativo.
Dati due interi positivi x e N , con x < N , primi tra loro, si definisce ordine moltiplicativo di x modulo N il minore intero positivo r che soddisfa xr = 1 mod N . Non `e noto ad oggi alcun algoritmo classico capace di risolvere il problema della ricerca dell’ordine in un tempo polinomiale rispetto al numero L di cifre binarie di N . L’algoritmo quantistico che ora illustreremo risolve il problema con un’alta probabilit`a di successo e con un numero di operazioni O(L3 ). Esso sfrutta l’algoritmo per la stima di fase applicandolo all’operatore U definito da U |yi = |xy
mod N i
Adottiamo la convenzione secondo la quale U |yi = |yi se y N . L’operatore U conserva la norma dei vettori; notiamo che esso `e anche invertibile in quanto l’equazione xa = xb
mod N
a,b < N
implica a = b se x e N sono coprimi. L’algoritmo impiega due registri di qubit (vedi figura 3.11): il secondo registro, formato da L qubit, `e quello su cui agisce U . Consideriamo il sottoinsieme di vettori appartenenti alla base computazionale del secondo registro costituito dagli elementi ↵ ↵ ↵ x0 mod N x1 mod N . . . xr 1 mod N Applicando l’antitrasformata di Fourier ad uno di questi vettori si ottiene ✓ ◆ r 1 ↵ 1 X 2⇡s 1 s |us i = F |x mod N i = p exp i j xj mod N (3.21) r r j=0 48
3.3. La trasformata di Fourier quantistica che `e autovettore di U di autovalore e2⇡is/r : ✓ ◆ r 1 1 X 2⇡s U |us i = p exp i j xj+1 r r j=0 ✓ ◆ 2⇡s = exp i |us i r
mod N
↵
L’autovalore di U `e una fase = s/r legata all’ordine r e ad s (ricordiamo che vale 0 s < r). Stimando `e possibile risalire a r pur non conoscendo s, facendo uso dell’espansione in frazione continua. Ci limiteremo qui a trattare solamente la parte dell’algoritmo riguardante la stima della fase. Il primo registro di t qubit viene utilizzato per memorizzare . L’algoritmo incomincia applicando la trasformata di Hadamard al primo registro inizialmente nello stato |00 . . . 0i. Il sistema dopo la trasformazione sar`a perci`o descritto da t
2 1 1 X p |ji |1i 2t j=0
dato che il secondo registro `e inizializzato allo stato |1i. Si applica quindi U 2 al secondo registro secondo uno schema analogo a quello di figura 3.9: t
2 1 1 X t p |ji U jt 2 2t j=0
t
1
... U
j 1 20
2 1 1 X t |1i = p |ji U jt 2 2t j=0
1
. . . U j2 2 xj1 2
1
1
. . . xj 1 2
Se esprimiamo xj mod N abbiamo 1 p 2t
j=0
|ji xj
mod N
t
2 1 1 X t =p |ji xjt 2 2t j=0 t
t 1 2X
0
↵
2 1 1 X =p |ji xj 2t j=0
mod N
↵
0
mod N
↵
↵
come trasformata di Fourier servendoci della 3.21
# ✓ ◆ r 1 X 1 1 2⇡s mod N = p |ji p exp i j |us i t r r s=0 2 j=0 " ✓ ◆ # r 1 2t 1 1 X 1 X 2⇡s p =p exp i j |ji |us i r r s=0 2t j=0 ↵
t 1 2X
"
Facendo agire infine la trasformata di Fourier sul primo registro si arriva allo stato r 1 1 X fE p s/r |us i r s=0
da cui `e possibile ricavare s/r mediante una misura nella base computazionale del primo registro. Anche in questo caso, trattandosi pur sempre di una stima di fase, valgono, relativamente all’errore e alla probabilit`a di riuscita dell’algoritmo, considerazioni simili a quelle fatte alla fine del paragrafo 3.3.1. 49
Bibliografia Algoritmo di Shor Il problema della fattorizzazione pu`o essere ricondotto a quello della ricerca dell’ordine invocando alcuni teoremi della teoria dei numeri la cui discussione esula dai limiti della nostra trattazione — l’algoritmo quantistico per la fattorizzazione, chiamato algoritmo di Shor, restituisce un fattore di un intero N con O((log N )3 ) operazioni.
Bibliografia [NC00]
50
Michael A. Nielsen e Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.
Capitolo 4 Dalla teoria alla pratica: realizzazione fisica dei computer quantistici Esamineremo in questo capitolo le difficolt`a che si incontrano nella progettazione e nell’allestimento di un sistema fisico capace di funzionare da calcolatore quantistico. Descriveremo il problema della decoerenza quantistica, quindi elencheremo i principali requisiti che si richiedono ad un sistema fisico volto alla computazione quantistica, prestando particolare attenzione allo schema di realizzazione che impiega degli ioni intrappolati da un campo elettromagnetico come qubit; analizzeremo questo sistema di realizzazione al capitolo 5.
4.1 4.1.1
Decoerenza quantistica Sovrapposizioni coerenti e miscele statistiche
Per introdurre il concetto di decoerenza rimarchiamo la di↵erenza fra una sovrapposizione coerente di stati e una mistura statistica di stati. Sappiamo (paragrafo 2.1) che la misura nello stato | i di un osservabile A di autovettori |un i A |un i = an |un i (stiamo supponendo lo spettro discreto e non degenere) restituisce l’autovalore an con probabilit`a | hun | i |2 . Nel caso avessimo diverse particelle tutte nello stato X | i= cn |un i (4.1) n
e misurassimo la grandezza A su ciascuna di esse, allora stando ai risultati delle misurazioni potremmo (erroneamente) pensare di avere a che fare con una miscela statistica di N particelle composta da | hu1 | i |2 N = |c1 |2 N particelle nello stato |u1 i, |c2 |2 N particelle nello stato |u2 i, e via dicendo. Consideriamo ora anche un secondo osservabile B di autovalori |vm i (assumiamo 51
Capitolo 4. Dalla teoria alla pratica: realizzazione fisica dei computer quantistici ancora uno spettro discreto e non degenere) e mostriamo come l’ipotesi precedente sia discordante con i postulati della meccanica quantistica. Se adottiamo la descrizione del sistema data dalla mistura statistica avremo che la probabilit`a di misurare un autovalore bm di B `e X |cn |2 | hvm |un i |2 (4.2) n
Applicando invece la formula corretta per lo stato coerente 4.1 abbiamo X X 2 2 P(vm ) = | hvm | i |2 = cn hvm |un i = cn hvm |un i =
X i
=
X n
ci hvm |ui i
n ! 2
X j
|cn hvm |un i | +
X i>j
c⇤j hvm |uj i⇤
!n
2 Re ci c⇤j hvm |ui i hvm |uj i⇤
la quale di↵erisce dalla 4.2 per la presenza dei termini dei cos`ıddetti termini di interferenza. Analizziamo un esempio semplice, restringendo il nostro discorso ai sistemi a due livelli (ad es. una particella di spin 1/2). Lo stato di questi sistemi si pu`o sempre esprimere come da equazione 2.3, o equivalentemente tramite la seguente matrice densit`a: ✓ ◆ cos2 2✓ sin 2✓ cos 2✓ e i ⇢= sin 2✓ cos 2✓ ei sin2 2✓ Per le ragioni sopra discusse i termini non diagonali di questa matrice vengono chiamati coerenze. Essi indicano la possibilit`a di osservare dei termini di interferenza nelle espressioni delle probabilit`a. Consideriamo invece adesso una miscela statistica. Ad esempio, l’operatore densit`a per una distribuzione di spin orientati casualmente `e Z Z 2⇡ Z ⇡ 1 1 0 ⇢ = d⌦⇢(✓, ) = d sin ✓d✓⇢(✓, ) 4⇡ 4⇡ 0 0 la cui rappresentazione matriciale `e 0
⇢ =
✓
1/2 0 0 1/2
◆
Possiamo dunque a↵ermare che la miscela statistica scelta non presenta alcuna coerenza.
4.1.2
Decoerenza: definizione e tipologie
Il fenomeno della decoerenza si pu`o definire semplificatamente come il passaggio verso una miscela statistica di stati subito da un sistema quantistico che si trovi in uno stato coerente. Sebbene tale mutamento sia dovuto a fenomeni diversi a 52
4.1. Decoerenza quantistica
Figura 4.1: Rilassamento trasverso (a) e rilassamento longitudinale (b) nella sfera di Bloch.
seconda del sistema specifico che si considera, la sua causa principale `e la dinamica del sistema quantistico prodotta dal contatto con l’ambiente circostante. La decoerenza `e anche importante in quanto responsabile dell’emergere del comportamento classico. Il tempo in cui avviene il mutamento dello stato del sistema viene detto tempo di decoerenza e gioca, come vedremo, un ruolo predominante nelle questioni tecniche concernenti la realizzazione dei computer quantistici. Si annoverano principalmente due tipologie di decoerenza: Rilassamento trasverso. Il rilassamento trasverso `e causato dalla perdita di coerenza tra le fasi relative delle ampiezze di uno stato quantistico. Il tempo di decoerenza che ne risulta si indica con T20 . Se consideriamo ancora un sistema a due livelli descritto da | i = ↵ |0i + |1i e scriviamo le ampiezze come ↵ = |↵|ei
1
= | |ei
2
vediamo come una variazione casuale di = 2 1 provochi l’annullamento i( 2 1) dei termini di coerenza |↵|| |e della matrice densit`a del sistema. ` E interessante visualizzare il mutamento del vettore di Bloch del sistema nella sfera di Bloch in seguito al rilassamento trasverso. Se riscriviamo lo stato | i nella forma 2.3 abbiamo che ✓ ✓ = ei cos 2 2 nella 2.4 si ottiene 8 > : z = | |2 |↵|2 ↵ = sin
sostituendo ↵ e
53
Capitolo 4. Dalla teoria alla pratica: realizzazione fisica dei computer quantistici Vediamo dunque che l’annullamento dei termini ↵ proietta il vettore sull’asse z (vedi prima immagine della figura 4.1); notiamo che il processo non conserva il modulo del vettore di Bloch. I vettori giacenti sull’asse z della sfera di Bloch rappresentano delle misture statistiche. L’interpretazione geometrica spiega l’utilizzo del termine trasverso riferito a questo tipo di decoerenza. Rilassamento longitudinale Il rilassamento longitudinale `e dovuto al decadimento di popolazione: gli stati eccitati tendono a decadere spontaneamente allo stato fondamentale in un certo tempo tipico T1 . Esso `e rappresentato dal secondo disegno di figura 4.1: possiamo osservare che il rilassamento longitudinale implica anche il rilassamento trasverso.
4.2
Requisiti fisici di un sistema volto alla computazione quantistica
David P. DiVincenzo ha stilato nel 2000 (in [DiV00]) una lista di cinque caratteristiche che si richiedono ai sistemi che si candidano ad essere utilizzati per il calcolo quantistico. Descriveremo uno per uno i punti di tale decalogo. Cercheremo di contestualizzare tali requisiti nell’ambito dei computer quantistici a ioni intrappolati, che descriveremo al capitolo 5. 1. Un sistema fisico scalabile con dei qubit ben caratterizzati In questo primo punto si richiede che il sistema fisico sia scalabile: ci`o si traduce principalmente nella possibilit`a di far crescere il numero di qubit del sistema senza sostanziali modifiche all’apparato tecnologico che si utilizza. Si richiede inoltre che i qubit siano ben caratterizzati: `e fondamentale conoscere in dettaglio il sistema fisico per quanto riguarda: L’hamiltoniana interna dei qubit. Essa determina l’energia degli autostati che, solitamente, vengono utilizzati come vettori della base computazionale. Nel caso degli ioni intrappolati si impiegano solitamente due livelli energetici atomici stabili. Eventuali accoppiamenti tra gli stati della base computazionale del qubit e gli altri stati del sistema. Nel caso degli ioni tale conoscenza riguarda gli altri livelli energetici dell’atomo e in particolare quelli vicini ai due livelli della base computazionale: possibili transizioni indensiderate sono sorgente di rumore nel calcolo quantistico, per cui la probabilit`a che si verifichino deve essere sufficientemente ridotta. Interazioni tra qubit diversi. L’interazione tra i qubit del sistema `e fondamentale per la creazione dell’entanglement, ed `e perci`o necessario conoscerne 54
4.2. Requisiti fisici di un sistema volto alla computazione quantistica le dinamiche e poterle controllare. Nel caso degli ioni intrappolati tali interazioni sono principalmente dovute agli stati vibrazionali dei qubit nel loro insieme (fononi). ` questo in ultima analisi il mezAccoppiamento con dei campi esterni. E zo che ci permette di manipolare i qubit. Per gli ioni si sfrutta in particolare l’interazione radiazione–atomo: dei raggi laser sono utilizzati — fra le altre cose — per e↵ettuare delle pseudorotazioni del vettore di Bloch che rappresenta il qubit (paragrafi 2.1.1 e 2.2.3). 2. L’abilit` a di inizializzare lo stato dei qubit ad uno stato noto, come ad esempio |00 . . . 0i. Questo `e importante non solo per avere un input affidabile, ma anche per soddisfare le esigenze della correzione degli errori (punto successivo). Gli algoritmi di correzione degli errori richiedono un continuo apporto di qubit in stati a bassa entropia per poter funzionare; la preparazione di tali qubit, che rappresenta una mancanza di molti dei sistemi ad oggi candidatisi, non costituisce tuttavia un problema al livello attuale della tecnologia, in quanto l’utilizzo intensivo di codici per la correzione degli errori non `e ancora stato raggiunto. Una delle possibili soluzioni per il futuro `e quella di realizzare una sorta di “nastro trasportatore” tramite il quale i qubit vengono allontanati dal sistema, inizializzati e quindi reintrodotti. Vi sono due metodi principali per l’inizializzazione dei qubit. Una strada `e quella del ra↵reddamento degli stessi al fine di portarli allo stato fondamentale. Una seconda strada `e quella della misurazione: essa provoca il collasso del qubit in un autostato dell’osservabile, a cui `e possibile risalire dal risultato della misura. Una volta che lo stato del qubit `e noto `e possibile, e↵ettuando delle operazioni appropriate, modificarlo nello stato voluto. Questo secondo approccio pu`o fruttare dei tempi potenzialmente inferiori rispetto al ra↵reddamento. Nel caso degli ioni intrappolati i due sistemi di inizializzazione sono interconnessi in quanto le misurazioni, che si e↵ettuano osservando la fluorescenza che si origina dall’assorbimento stimolato di radiazione, `e anch’essa una forma di ra↵reddamento. In alcune implementazioni l’inizializzazione non viene provocata attivamente: `e possibile ad esempio fare in modo che un insieme di spin si allinei spontaneamente ad un campo magnetico applicato. Questo ha tuttavia lo svantaggio di richiedere dei tempi lunghi, dato che il tempo scala della termalizzazione non pu`o mai essere inferiore al tempo di decoerenza del sistema; in questo approccio perci`o `e indispensabile un “nastro trasportatore”. 3. Lunghi tempi di decoerenza, maggiori del tempo di operazione delle porte logiche. Gli algoritmi quantistici si basano su fenomeni di entanglement e interferenza per cui possiamo capire come la decoerenza, sopprimendo i comportamenti quanto– meccanici delle particelle, sia rovinosa per il calcolo quantistico. 55
Capitolo 4. Dalla teoria alla pratica: realizzazione fisica dei computer quantistici Cerchiamo di rispondere alla domanda su quanto debbano essere lunghi i tempi ` necessaria a questo di decoerenza per non impedire l’esecuzione degli algoritmi. E punto una precisazione: un sistema quantistico pu`o presentare diversi tempi di coerenza a seconda del grado di libert`a che si considera. I tempi di coerenza pertinenti al nostro discorso sono quelli relativi ai gradi di libert`a su cui sono basati i qubit. Se per esempio si utilizza come qubit lo spin di un elettrone, i tempi di decoerenza riguardanti il suo moto spaziale sono irrilevanti al fine del nostro discorso. Per rispondere alla domanda iniziale non si deve ignorare l’esistenza di codici di correzione degli errori quantistici, che permettono sotto certe condizioni di correggere gli errori dovuti alla decoerenza, svolgendo un ruolo simile ai corrispettivi codici classici. Il lavoro teorico svolto nel campo dell’informatica quantistica negli ultimi decenni ha permesso di dimostrare che i calcoli quantistici possono essere resi tolleranti all’errore (fault tolerant): le operazioni di correzione possono essere interposte tra le procedure dell’algoritmo, e inoltre gli errori che occorrono nella correzione degli errori stessa non sono critici per la riuscita dell’algoritmo. La condizione `e che l’insorgenza di errori non superi un certo tasso. Grazie alla correzione degli errori i tempi di decoerenza minimi richiesti passano dalla durata dell’intera computazione a circa 104 – 105 volte il tempo di clock del computer quantistico1 ; si tratta ad ogni modo di una richiesta abbastanza stringente. Allo stato attuale della tecnologia la dimostrazione del funzionamento dei codici di correzione degli errori `e ancora impossibile. Riportiamo in tabella 4.1 il tempo di decoerenza, il clock e il numero di operazioni eseguibili entro il tempo di coerenza per vari sistemi fisici utilizzabili come computer quantistici: possiamo notare che l’implementazione a ioni intrappolati `e una delle pi` u promettenti. Gli ioni intrappolati esibiscono lunghi tempi di decoerenza e consentono una veloce applicazione delle porte logiche: `e possibile applicare fino a 1014 operazioni prima che il sistema perda le sue caratteristiche quantistiche. 1
Il tempo di clock `e il tempo richiesto per l’esecuzione di una singola operazione.
sistema spin nucleare spin elettronico trappola per ioni (In+ ) elettrone (Au) elettrone (GaAs) quantum dot cavit`a ottica cavit`a a microonde
Tdec (s) 10
2
÷ 108 10 3 10 1 10 8 10 10 10 6 10 5 100
Top (s) 10
3
÷ 10 10 7 10 14 10 14 10 13 10 9 10 14 10 4
N 6
105 ÷ 1014 104 1013 106 103 103 109 104
Tabella 4.1: Stime, per vari sistemi, del tempo di decoerenza Tdec , del tempo di clock Top e del numero di operazioni eseguibili N = Tdec /Top (tempi in secondi).
56
4.2. Requisiti fisici di un sistema volto alla computazione quantistica 4. Un insieme universale di porte logiche quantistiche. Abbiamo gi`a introdotto questo argomento al §2.3. In pratica, in una data implementazione, la disponibilit`a di porte logiche `e legata alla variet`a di hamiltoniane che le possono generare. L’apparato sperimentale deve poter provvedere all’ “accensione” e allo “spegnimento” di una collezione di hamiltoniane H1 , H2 , . . . tramite le quali `e possibile applicare le diverse trasformazioni U1 = eiH1 t/~ , U2 = eiH2 t/~ , . . .; visto che il tempo `e un parametro basilare per le trasformazioni, si deve essere in grado di controllare l’hamiltoniana del sistema quasi istante per istante. Ci ritroviamo cos`ı con dei vincoli contrastanti: il sistema deve essere isolato raffinatamente per impedire la decoerenza ma allo stesso tempo dobbiamo poterlo perturbare in maniera molto precisa. Nondimeno bisogna interessarsi alle interazioni fra i qubit, necessarie per la costruzione delle porte cnot. In alcuni sistemi, come ad esempio in quelli a risonanza magnetica nucleare, l’hamiltoniana di interazione tra i qubit `e di difficile controllo, il che pu`o diventare un ostacolo fatale per la computazione. In altri, come ad esempio negli ioni intrappolati, non `e disponibile alcuna interazione diretta tra i livelli energetici di due qubit: si ha bisogno allora di un sottosistema quantistico che funzioni da bus qubit mediando l’interazione che si vuole ottenere. Nel caso degli ioni intrappolati il sottosistema non `e altro che lo stato vibrazionale della catena di ioni. Un altro aspetto da considerare `e che, come abbiamo visto al paragrafo 2.3.3, le porte logiche quantistiche non sono applicabili — utilizzando un numero finito di porte logiche — senza un certo errore sistematico, al quale si deve aggiungere anche un’ineliminabile componente casuale. Un certo margine di errore `e comunque tollerabile, a patto di far uso dei codici di correzione. Inoltre alcuni algoritmi, come ad esempio la trasformata di Fourier, non sono eccessivamente sensibili agli errori sistematici. 5. Capacit` a di misurare qubit specifici. Una misura su uno stato ⇢ = p |0ih0| + (1
p) |1ih1| + ↵ |0i h1| + ↵⇤ |1i h0|
si dice efficiente al 100% se restituisce “0” con probabilit`a p e “1” con probabilit`a 1 p proiettando lo stato del qubit nel corrispondente autostato, e lo fa indipendentemente da ↵, dallo stato dei qubit vicini o da qualunque altro parametro del sistema fisico, non influenzando in alcun modo il resto del sistema. Nella realt`a le misurazioni sono meno efficienti, fatto, questo, che non ostacola irrimediabilmente la computazione quantistica; si pu`o ad esempio incrementare il gradi di fedelt`a di una misura ripetendola pi` u volte alla fine di diverse istanze di un algoritmo. L’abilita di eseguire rapidamente le misure, in tempi dell’ordine di 10 4 volte il tempo di coerenza, `e inoltre desiderabile in quanto giova all’esecuzione dei codici di correzione degli errori.
57
Bibliografia
Bibliografia [DiV00]
David P. DiVincenzo. “The Physical Implementation of Quantum Computation”. In: Fortschr. Phys. 48 (2000), pp. 771–783.
[Fox06]
Mark Fox. Quantum Optics. Oxford University Press, 2006.
58
Capitolo 5 Il computer quantistico basato sugli ioni intrappolati Delineeremo in questo capitolo i principi fisici che stanno alla base dello schema di realizzazione del computer quantistico a ioni intrappolati, occupandoci del confinamento e ra↵reddamento degli ioni e spiegando come si possano applicare delle porte logiche per mezzo dell’interazione radiazione–atomo.
5.1 5.1.1
Trappole per ioni Il problema del confinamento
Per mantenere gli atomi che costituiscono i qubit di un computer quantistico a ioni intrappolati in una regione spaziale limitata sono necessarie opportune tecniche di confinamento. Il fatto per cui vengono utilizzati degli ioni in luogo di atomi neutri `e che la forza esercitata da un campo elettrico su uno ione `e superiore di diversi ordini di grandezza a quella che un gradiente di campo magnetico praticamente realizzabile in un laboratorio pu`o esercitare su di un atomo neutro. E↵ettuando un rapido calcolo con dei valori tipici per i campi e per il momento di dipolo magnetico degli un atomi `e possibile valutare l’ordine di grandezza delle forze subite nei due casi: se E = 105 V/m si ha Fion = eE ⇠ 10
14
N
mentre, con dB/dz = 10T/m si trova Fneutral = µB
dB ⇠ 10 dz
22
N
Ne concludiamo che la forza elettrica `e 108 volte maggiore. Un voltaggio tipico di una trappola per ioni pu`o essere 500V, il che corrisponde ad un energia di confinamento massima per un atomo ionizzato una sola volta ` questa un energia assai maggiore di 1/40eV, energia di agitazione pari a 500eV. E termica di un gas a temperatura ambiente. L’energia di legame della trappola eguaglia l’energia cinetica media associata ad una temperatura di 6 ⇥ 106 K! 59
Capitolo 5. Il computer quantistico basato sugli ioni intrappolati
Figura 5.1: Corrispettivo meccanico della trappola di Paul: la palla sopra la superficie a sella `e sottoposta ad un potenziale gravitazionale simile al potenziale elettrostatico a cui sono sottoposti gli ioni nella trappola. Ruotando la superficie ad una velocit`a opportuna la palla rimane confinata.
Il voltaggio considerato `e dunque pi` u che sufficiente per confinare gli ioni, anche se si considera il rinculo che essi subiscono all’atto della ionizzazione. Il procedimento che si usa infatti per caricare una trappola per ioni consiste nell’indirizzare verso di essa un fascio di atomi neutri, i quali vengono ionizzati da un secondo fascio di elettroni che punta nella zona di confinamento.
5.1.2
Trappole a radiofrequenza
Dall’elettrostatica sappiamo che `e impossibile creare un campo elettrico capace di dar luogo ad una zona di equilibrio stabile nello spazio. Questo risultato `e a volte chiamato teorema di Earnshaw. Esso si pu`o dimostrare a partire dall’equazione di Laplace, soddisfatta dal potenziale elettrostatico nelle regioni prive di carica: r2 = 0 Le soluzioni di questa equazione sono funzioni armoniche: esse hanno una propriet`a per la quale il valore di una tale funzione in un punto r dello spazio `e uguale ` perci`o impossibile che al medio della funzione su una sfera centrata in r stesso. E il potenziale elettrostatico presenti una posizione di minimo locale. Quello da usare per confinare gli ioni deve essere dunque un campo elettromagnetico variabile: sono utilizzati solitamente campi a radiofrequenza.
5.1.3
La trappola di Paul
Una possibile geometria di confinamento `e quella ideata da Wolfgang Paul. Per introdurla consideriamo dapprima un parallelo meccanico: una palla posta sopra una sella (figura 5.1) di equazione z= 60
k 2 (x 2
y2)
5.1. Trappole per ioni
Figura 5.2: Schema della trappola di Paul lineare. Fra le due coppie di elettrodi si genera una d.d.p. Vac variabile a radiofrequenza (disegno a sinistra). Notiamo nel disegno a destra due elettrodi aggiuntivi (contrassegnati dal segno +), carichi positivamente, che provvedono al confinamento lungo l’asse z.
` possibile provare, anche sperimentalmente, che ruotando la sella ad una velocit`a E opportuna la palla vi rimane intrappolata. Sebbene la sua posizione media rimanga costante, la palla subisce dei moti oscillatori attorno alla posizione di equilibrio. Uno ione intrappolato in un campo a radiofrequenza `e un sistema molto simile a quello appena descritto. Lo schema della trappola di Paul (in particolare stiamo trattando la trappola lineare) `e riportato in figura 5.2. Quattro elettrodi sono disposti parallelamente all’asse z del sistema di riferimento. Due di essi, distanti 2r0 tra loro, sono posizionati in corrispondenza dell’asse x; gli altri due si trovano sull’asse y, distanti sempre 2r0 tra loro. Fra le due coppie di elettrodi si mantiene una di↵erenza di potenziale variabile V = V0 cos ⌦t a radiofrequenza. Per determinare il campo elettrico nella regione compresa tra gli elettrodi possiamo limitarci a far uso dell’elettrostatica in quanto la lunghezza d’onda delle radiofrequenze `e molto maggiore della dimensione degli elettrodi: approssimiamo il sistema come soggetto, istante per istante, ad un campo elettrostatico. Trascuriamo inoltre gli e↵etti di bordo e consideriamo gli elettrodi infinitamente lunghi: non commetteremo un grande errore se la separazione tra gli elettrodi `e molto minore della loro lunghezza. Similmente possiamo consideriamo gli elettrodi filiformi se il loro raggio `e trascurabile rispetto a r0 . La simmetria del problema ci suggerisce il seguente potenziale: = a0 + a2 (x2
y2)
In esso non sono presenti termini lineari per via dell’invarianza della configurazione degli elettrodi rispetto alle riflessioni sui piani x-z e y-z; i termini in x2 e y 2 hanno segno opposto per poter soddisfare le condizioni al contorno (il potenziale ha segno opposto in corrispondenza delle due coppie di elettrodi). 61
Capitolo 5. Il computer quantistico basato sugli ioni intrappolati Imponiamo dunque le condizioni al contorno: =
0
=
0
+
V0 cos ⌦t per x = ±r0 , y = 0 2 V0 cos ⌦t per x = 0, y = ±r0 2
(5.1) (5.2)
Ne risulta
V0 cos(⌦t)(x2 y 2 ) 2r02 Per il teorema di unicit`a dell’elettrostatica questa soluzione, soddisfacente l’equazione di Laplace e le condizioni al contorno, `e la soluzione corretta. Ricaviamo ora il campo elettrico =
E=
0
+
V0 cos(⌦t)(xˆ ex r02
r =
yˆ ey )
e quindi l’equazione del moto dello ione m
d2 x = dt2
eV0 cos(⌦t)x r02
(5.3)
Ponendo ⌧ = ⌦t/2 la 5.3 diventa d2 x = d⌧ 2
4ev0 cos(2⌧ )x ⌦2 mr02
la quale `e un caso particolare dell’equazione di Mathieu d2 x = +(ax d⌧ 2
2qx cos 2⌧ )x = 0
(5.4)
per ax = 0 e
2eV0 ⌦2 mr02 Un ansatz per la risoluzione dell’equazione del moto `e il seguente: qx =
x = x0 cos A⌧ (1 + B cos 2⌧ )
(5.5)
Sostituendo la 5.5 nella 5.4 si arriva a x0 [ 4B cos A⌧ cos 2⌧ + 4AB sin A⌧ sin 2⌧ A2 cos A⌧ (1 + B cos 2⌧ )] = = 2qx x0 cos 2⌧ cos A⌧ (1 + B cos 2⌧ )] (5.6) Assumiamo A, B ⌧ 1 intepretando l’ansatz 5.5 come la composizione di un’oscillazione principale di frequenza A e un’oscillazione secondaria alla frequenza della forzante (2⌧ = ⌦t) di ampiezza ridotta. Questa seconda oscillazione, molto pi` u rapida della prima per via del fatto che A ⌧ 1, viene chiamata micromoto. Mantenendo dunque solo i termini di primo grado in A e B nella 5.6 si trova che se B ⌧ 1 allora anche qx ⌧ 1. Si arriva quindi all’uguaglianza B= 62
qx = 2
eV0 m⌦2 r02
5.1. Trappole per ioni Occupiamoci ora dell’oscillazione principale: nell’esaminare il moto per intervalli di tempo abbastanza lunghi rispetto al periodo del micromoto possiamo sostituire nella 5.6 i termini oscillanti alla frequenza 2⌧ con laploro media temporale. Si ottiene cos`ı A2 cos A⌧ = qx B cos A⌧ ovvero A = qx / 2. Giungiamo dunque alla seguente soluzione approssimata del moto dello ione nella trappola: ✓ ◆h i qx ⌧ qx p x = x0 cos + ✓0 1 + cos 2⌧ 2 2
nella quale abbiamo incluso anche una fase iniziale arbitraria ✓0 nell’oscillazione principale. Le nostre assunzioni iniziali sui coefficienti A e B si riducono a qx ⌧ 1. Di fatto la nostra soluzione `e molto fedele anche per qx 0,4. Ci siamo preoccupati finora esclusivamente del confinamento nel piano x-y; per quanto riguarda quello lungo l’asse z `e possibile aggiungere due elettrodi positivi lungo l’asse della trappola (l’asse z per l’appunto) in z = ±z0 come da figura 5.2. Se si fa in modo che il confinamento assiale sia molto pi` u debole di quello radiale allora gli ioni tendono a formare una fila; osserviamo che lungo l’asse z non si ha micromoto in quanto gli elettrodi aggiuntivi sono posti a un potenziale fisso.
5.1.4
Sistemi di ra↵reddamento
Per ridurre al minimo l’ampiezza delle oscillazioni radiali degli ioni in una trappola di Paul — condizione necessaria affinch´e il moto degli stessi sia quantizzato — `e fondamentale il ra↵reddamento delle particelle. Sperimentalmente nell’intrappolamento degli ioni un vuoto spinto `e un requisito quasi scontato, visto il grado di isolamento che si desidera ottenere. Tuttavia per e↵ettuare un ra↵reddamento preliminare degli ioni pu`o essere utile la presenza di un gas tampone costituito da elio alla pressione di circa 10 4 mbar: se gli ioni si trovano inizialmente sopra la temperatura ambiente tramite gli urti con le molecole del gas tampone essi disperdono energia cinetica raggiungendo rapidamente l’equilibrio termico. Lo stesso processo d’altra parte per sua stessa natura impedisce un ra↵reddamento rilevante degli ioni, che pu`o essere e↵ettuato solo in alto vuoto (⇠ 10 11 mbar), ad esempio con la tecnica del ra↵reddamento doppler. Il ra↵reddamento doppler si pratica mediante un laser accordato a una frequenza ⌫ = ⌫0 + dove ⌫0 `e una frequenza di risonanza per lo ione e `e un detuning ( ⌧ ⌫0 ). Il suo principio `e basato sull’e↵etto doppler relativistico: gli ioni che si muovono verso il laser percepiscono una frequenza ⌫ 0 maggiore in accordo con s 0 ⌫ 1+ = ⌫ 1 la quale si pu`o approssimare per
⌧ 1 come ⌫0 '1+ ⌫ 63
Capitolo 5. Il computer quantistico basato sugli ioni intrappolati Se lo ione si muove verso la sorgente con velocit`a =
⌫0
= v/c che soddisfa
v c
allora si ha che ⌫ 0 = ⌫0 e la frequenza percepita dall’atomo `e risonante. Solo quando questo avviene il fotone viene assorbito dall’atomo, trasferendogli un momento pari a h p= Quando l’atomo decade subisce un rinculo verso una direzione casuale dello spazio: dopo molti cicli di assorbimento ed emissione gli e↵etti dei rinculi si annullano, laddove invece il momento trasferito dai fotoni assorbiti si accumula, rallentando lo ` questa l’idea alla base del ra↵reddamento ione lungo la direzione del fascio laser. E doppler. La velocit`a con cui il ra↵reddamento pu`o venire e↵ettuato dipende essenzialmente dalla vita media degli stati eccitati utilizzati: se indichiamo con ⌧ tale tempo di vita possiamo scrivere dp p h F = = = (5.7) dt 2⌧ 2 ⌧ Il fattore 2 al denominatore deriva dal fatto che per grandi intensit`a luminose i due stati risonanti tendono a popolarsi uniformemente. Gli atomi eccitati tuttavia, se raggiunti dai fotoni provenienti dal laser, possono subire l’emissione stimolata rilasciando un fotone lungo la direzione del raggio stimolante: il rinculo che ne risulta annulla il momento trasferito allo ione dal laser all’atto dell’eccitazione, cos`ıcch´e l’e↵etto complessivo `e nullo. Per questa riduzione si ha una perdita di efficacia del ra↵reddamento. L’accelerazione corrispondente alla 5.7 sar`a a=
F = m
h 2 ⌧
Il numero di cicli necessari per fermare l’atomo si pu`o stimare come N=
mu mu = | p| h
` bene notare che l’atomo non potr`a essere portato alla quiete completa: quando E il detuning richiesto al laser diventa comparabile con la larghezza di riga ⌫ della transizione viene a mancare l’e↵etto di selezione per il processo di assorbimento, cos`ıcch´e il limite minimo di temperatura raggiungibile con il ra↵reddamento doppler `e kB Tmin ⇠ h ⌫
5.2
Risonanze ottiche in sistemi atomici a due livelli
Dopo aver a lungo parlato delle porte logiche quantistiche al capitolo 2 esaminiamo ora come queste possano essere implementate, in termini fisici, su dei qubit 64
5.2. Risonanze ottiche in sistemi atomici a due livelli costituiti da due livelli energetici atomici, utilizzando della radiazione laser. Indichiamo con E1 ed E2 , dove E1 > E2 , le energie dei due livelli del qubit. L’interazione dell’atomo con una radiazione di frequenza angolare ! = !0 +
con
⌧ !0
prossima alla frequenza di risonanza !0 =
E2
E1 ~
genera delle rotazioni del vettore di Bloch associato al sistema. Nell’approssimazione a due livelli possiamo restringere la nostra attenzione a due soli livelli dello spettro energetico dell’atomo, a patto di utilizzare una radiazione di frequenza prossima a quella di risonanza: in questa condizione la probabilit`a di transizioni in altri livelli risulta trascurabile.
5.2.1
Hamiltoniana di interazione dell’elettrone
Studiamo il fenomeno in maniera semiclassica, evitando di quantizzare i campi: `e questa una buona approssimazione per i nostri scopi, e ha il vantaggio di essere matematicamente pi` u semplice della teoria quantistica esatta. ` utile porsi in una gauge che annulli il potenziale elettrostatico e descrivere E l’onda elettromagnetica in termini del potenziale vettore A(R, t). Le ampiezze dei campi elettrico e magnetico sono allora legate all’ampiezza del potenziale vettore dalle relazioni E0 B0 i!A0 = ikA0 = 2 2 dove k `e il modulo del vettore d’onda della radiazione. L’hamiltoniana di interazione completa dell’atomo con il campo elettromagnetico classico si scrive come Hint =
q q2 S · B(R, t) + [A(R, t)]2 m 2m
q P · A(R, t) m
(5.8)
I primi due termini dipendono linearmente da A0 a di↵erenza del terzo che vi dipende quadraticamente: nelle fonti luminose ordinarie l’intensit`a `e sufficientemente bassa da permettere di poter trascurare questo ultimo termine. Valutiamo ora l’ordine di grandezza dei primi due termini: q ~kA0 m q pA0 m
=
~k p
Tramite il principio di indeterminazione di Heisenberg possiamo stimare ~/p ⇠ a0 ; essendo k = 2⇡/ abbiamo q ~kA0 m q pA0 m
=
~k a0 ⇠ ⌧1 p
dato che nel nostro caso ⇠ 103 ˚ A mentre a0 ' 0,5˚ A. Manteniamo per questo solamente il primo termine e, sempre per via del fatto che 65
Capitolo 5. Il computer quantistico basato sugli ioni intrappolati la lunghezza d’onda della radiazione `e molto maggiore delle dimensioni atomiche tipiche, facciamo la cos`ıddetta approssimazione di dipolo: sostituiamo nella 5.8 l’espressione del potenziale vettore A(r, t) = A0ˆ ez ei(ky
!t)
+ A⇤0ˆ ez e
i(ky !t)
(stiamo considerando un’onda che si muove nella direzione positiva dell’asse y) ed espandendo in serie gli esponenziali manteniamo soltanto il termine di ordine zero in quanto appunto kY ' a0 / ⌧ 1. Si ottiene l’hamiltoniana di dipolo elettrico qE0 Pz sin !t m! HDE viene detta di dipolo elettrico in quanto mediante una trasformazione di gauge assume la forma familiare HDE = D · E HDE =
con D = qR. Useremo nel seguito questa seconda forma pi` u semplice.
5.2.2
Equazioni di Bloch
L’hamiltoniana completa dell’atomo `e H = Hatom + Hint ' Hatom
D·E
Lavoriamo nella base |+i, | i degli autovettori di Hatom corrispondenti al nostro sistema atomico a due livelli. Scriviamo la rappresentazione matriciale degli operatori Hatom e D: ✓ ◆ ✓ ◆ E2 0 0 Dr + iDi Hatom = D= (5.9) 0 E1 Dr iDi 0 (abbiamo scomposto gli elementi di matrice di D in parte reale Dr e parte immaginaria Di ). Gli elementi diagonali dell’operatore momento di dipolo negli stati atomici sono nulli, in quanto D `e un operatore dispari e gli autovettori di H hanno parit`a definita. Utilizzeremo per determinare l’evoluzione del sistema la rappresentazione di Heisenberg. Scomponiamo le due matrici 5.9 mediante le matrici di Pauli, e riscriviamo H come 1 1 H = (E2 + E1 )1 + (E2 E1 ) z (Dr · E) x + (Di · E) y (5.10) 2 2 e calcoliamo l’evoluzione delle matrici nella rappresentazione di Heisenberg mediante i~ ˙ = [ , H] Si ottengono le equazioni seguenti 2 + [Di · E(t)] z (t) ~ 2 ˙ y (t) = !0 x (t) + [Dr · E(t)] z (t) ~ 2 2 ˙ z (t) = [Dr · E(t)] y (t) [Di · E(t)] x (t) ~ ~
˙ x (t) =
66
!0
y (t)
(5.11)
5.2. Risonanze ottiche in sistemi atomici a due livelli Ricordiamo che le matrici di Pauli soddisfano 2 x
=
2 y
=
2 z
=1
Questa propriet`a si conserva anche nell’evoluzione temporale in quanto si verifica dalle 5.11 che, ad esempio, d 2 (t) = 0 dt x e dunque 2 x (t)
=
2 x (0)
=1
(5.12)
Calcolando il valor medio delle 5.11 nello stato iniziale dell’atomo otteniamo un sistema di equazioni per i valori medi si (t) = h i i (t) con i = x, y, z: 2 !0 sy (t) + [Di · E(t)]sz (t) ~ 2 s˙ y (t) = !0 sx (t) + [Dr · E(t)]sz (t) ~ 2 2 s˙ z (t) = [Dr · E(t)]sy (t) [Di · E(t)]sx (t) ~ ~
s˙ x (t) =
(5.13)
I valori medi si (t) soddisfano una legge di conservazione simile alla legge di conservazione operatoriale 5.12: moltiplicando le tre equazioni del sistema 5.13 per s1 (t), s2 (t) ed s3 (t) rispettivamente, si ottiene s2x (t) + s2y (t) + s2z (t) = cost. Per mostrare che la costante `e unitaria calcoliamo sx (0) = h | x | i = a⇤ b + ab⇤ sy (0) = h | y | i = i(a⇤ b + ab⇤ ) sz (0) = h | z | i = |a|2 |b|2 da cui si verifica s2x (0) + s2y (0) + s2z (0) = |a|2 + |b|2
2
=1
per la condizione di normalizzazione. Per quanto appena dimostrato possiamo interpretare il vettore s(t) = (sx (t), sy (t), sz (t)) come un punto sulla sfera di Bloch che rappresenta lo stato del sistema a due livelli. Cerchiamo di dare un significato fisico alle si (t): dalla 5.10 possiamo vedere che 1 ~!0 sz (t) rappresenta l’energia interna dell’atomo relativa alla media 12 (E1 + E2 ), 2 mentre sx (t) e sy (t) sono legate all’energia di interazione di dipolo elettrico. 67
Capitolo 5. Il computer quantistico basato sugli ioni intrappolati Per molte applicazioni si pu`o assumere che i due stati abbiamo lo stesso numero quantico magnetico m: in questo caso si ha che Di = 0 e il sistema 5.13 si semplifica in s˙ x (t) = !0 sy (t) s˙ y (t) = +!0 sx (t) + aE(t)sz (t) s˙ z (t) = aE(t)sy (t)
(5.14)
2 2D ˆ Dr · E(t) = Dr · E(t) = aE(t) ~ ~
(5.15)
Con a dato definito da
Col passare del tempo lo pseudospin s traccia una traiettoria sulla sfera di Bloch in accordo con la 5.14 (figura 5.3).
Figura 5.3: Evoluzione temporale dello pseudospin nella sfera di Bloch.
5.2.3
Approssimazione di onda rotante
Il sistema di equazioni 5.14 pu`o essere condensato in un unica equazione vettoriale d s(t) = ⌦F (t) ⇥ s(t) dt con ⌦Fx (t) =
aE(t)
⌦Fy (t) = 0
⌦Fz (t) = !0
(5.16)
La componente z di ⌦F `e quella predominante, infatti le transizioni ottiche hanno energie caratteristiche dell’ordine dell’eV, mentre il dipolo elettrico atomico, legato ad a dalla 5.15, `e dell’ordine di ea0 : per avere ~aE ⇡ ~!0 si deve procurare un 68
5.2. Risonanze ottiche in sistemi atomici a due livelli
Figura 5.4: Precessione del vettore s attorno a un asse fisso ⌦F .
campo elettrico pari a circa 1V/a0 ovvero E ⇡ 108 V/cm. Delle intensit`a luminose simili sono ottenibili con dei laser, ma sono maggiori di parecchi ordini di grandezza a quelle che si utilizzano negli esperimenti di risonanza. In conclusione, possiamo considerare aE ⌧ !0 La precessione dello pseudospin nella sfera di Bloch si pu`o interpretare come da figura 5.4 a patto che il periodo di rotazione sia molto maggiore del tempo scala delle variazioni di ⌦F . Ma siccome in risonanza si ha ! ⇡ !0 vediamo dalla 5.16 che questa condizione non `e verificata, e dunque s non pu`o tracciare una circonferenza attorno a ⌦F prima che quest’ultimo sia variato significativamente. Per visualizzare il moto di s si utilizza l’espediente del cambiamento di coordinate, ponendosi in un sistema di riferimento rotante. Scomponiamo ⌦F in tre componenti: ⌦F = ⌦+ + ⌦ + ⌦0 con ⌦0 = (0, 0, !0 ) ⌦+ = ( aE0 cos !t, aE0 sin !t,0) ⌦ = ( aE0 cos !t, +aE0 sin !t,0) E0 `e l’ampiezza del campo elettrico: E(t) = E0 (ei!t + c.c.). Dato che s ruota principalmente attorno all’asse z — per via del fatto che aE ⌧ !0 — e che ! ⇡ !0 , nel sistema di riferimento in cui ⌦+ `e stazionario s `e pressoch´e costante. In questo sistema di riferimento ⌦ ruota con velocit`a 2!, e si suoi e↵etti sul vettore di Bloch si annullano circa 1015 ÷ 1016 volte al secondo. L’approssimazione di onda rotante consiste nel trascurare questa ultima componente del momento torcente generalizzato ⌦F limitandosi a considerare ⌦0 e ⌦+ . 69
Capitolo 5. Il computer quantistico basato sugli ioni intrappolati Sotto queste ipotesi il sistema 5.14 diventa s˙ x (t) = !0 sy (t) aE0 sz (t) sin !t s˙ y (t) = +!0 sx (t) + aE0 sz (t) cos !t s˙ z (t) = aE0 [sy (t) cos !t sx (t) sin !t]
(5.17)
E↵ettuando il cambio di coordinate 0 1 0 10 1 u cos !t sin !t 0 sx @ v A = @ sin !t cos !t 0A @sy A w 0 0 1 sz
otteniamo dalla 5.17 l’equazione che regola l’evoluzione del vettore di Bloch nel sistema rotante: u˙ = (!0 !)v v˙ = +(!0 !)u + aE0 w w˙ = aE0 v
(5.18)
equivalente all’equazione vettoriale d ⇢=⌦⇥⇢ dt
(5.19)
dove ⇢ = (u, w, z) e ⌦ = ( aE0 , 0, !0 !). Possiamo dunque dedurre dalla piccolezza delle componenti di ⌦ come in questo sistema il vettore di Bloch si muova lentamente. Notiamo che w = s3 : w `e legato al valor medio dell’energia del sistema, e viene chiamato talvolta inversione.
5.2.4
Soluzione nel caso di risonanza esatta
Discutiamo la soluzione delle equazioni di Bloch 5.18 nel caso di risonanza esatta: ! = !0 . Definiamo la quantit`a adimensionale Z t ✓(t) = aE0 (t0 )dt0 (5.20) 1
Non escludiamo la possibilit`a che l’ampiezza E0 del campo elettrico possa variare temporalmente. Le equazioni 5.18 prendono la forma u˙ = 0 ˙ v˙ = +✓w ˙ w˙ = ✓v La soluzione della prima equazione `e immediata: u(t) = u0 . Per risolvere le ultime due eliminiamo una delle due variabili. Sostituiamo la terza equazione w= 70
v˙ ✓˙
5.2. Risonanze ottiche in sistemi atomici a due livelli
Figura 5.5: In caso di risonanza esatta il vettore ⇢(t) `e ruotato in senso antiorario attorno all’asse u di un angolo ✓(t) dato dalla 5.20, rispetto allo stato iniziale (in questo caso coincidente con lo stato fondamentale w = 1).
nella derivata della seconda trovando ✓¨ v¨ v˙ + ✓˙2 v = 0 ˙✓ Cerchiamo una soluzione del tipo v(t) = C cos ✓(t); verifichiamo che essa soddisfa l’equazione. La soluzione pi` u generale risulta essere una combinazione lineare di seni e coseni — le costanti sono legate alle condizioni iniziali: u = uo v = +w0 sin ✓(t) + v0 cos ✓(t) w = v0 sin ✓(t) + w0 cos ✓(t) La quantit`a ✓(t) altro non `e che l’angolo di inclinazione di ⇢ rispetto alla direzione negativa delle w nella sfera di Bloch, come mostrato in figura 5.5. Se l’ampiezza E0 del campo elettrico non varia nell’intervallo t2 t1 nel quale `e applicato si ha che (figura 5.6) ✓ = aE0 (t2
t1 ) = ⌦(0)(t2
t1 )
⌦(0) = aE0 `e la frequenza di Rabi in risonanza; essa fornisce una misura di quanto tempo impieghi il campo elettrico utilizzato a compiere delle rotazioni dello pseudospin. Notiamo che se l’atomo si trova allo stato fondamentale (w0 = 1) e gli si applica un impulso di durata t tale che aE0 t = ⇡ esso si porter`a allo stato eccitato (w0 = +1); un tale impulso viene chiamato di frequente impulso ⇡. 71
Capitolo 5. Il computer quantistico basato sugli ioni intrappolati
Figura 5.6: Nel caso in cui E0 = cost. (soluzione di Rabi) l’angolo ✓ `e semplicemente aE0 (t2 t1 ). L’area sottesa dalla curva `e detta area di impulso.
5.2.5
Soluzione in caso di detuning
In generale le equazioni di Bloch prevedono un detuning = !0 ! della radiazione laser rispetto alla frequenza di risonanza del sistema a due livelli. Riscriviamo la 5.18 in forma matriciale: 0 1 0 10 1 u 0 0 u d @ A @ v = + 0 aE0 A @ v A (5.21) dt w 0 aE0 0 w Consideriamo ora il caso in cui E0 `e costante (soluzione di Rabi). Se e↵etuiamo una rotazione attorno all’asse y di un angolo che soddisfa tan
=
aE0
ci riconduciamo al caso precedente, ovvero ad un moto rotatorio attorno all’asse x. Per dimostrarlo consideriamo il vettore ⇢0 = (u0 , v 0 , w0 ) a cui si arriva mediante il cambio di coordinate 0 1 0 1 0 01 u cos 0 sin u @v A = @ 0 A @ 1 0 v0 A w sin 0 cos w0 Esso obbedisce all’equazione 0 01 0 u 0 d @ 0A @ v = 0 dt 0 w 0 dove
⌦( ) =
1 0 01 0 0 u 0 ⌦( )A @ v 0 A ⌦( ) 0 w0 p
2
+ (aE0 )2
(5.22)
(5.23)
`e la frequenza di Rabi, gi`a menzionata al paragrafo precedente. Notiamo come la 5.22 sia equivalente all’equazione che si ottiene dalla 5.21 ponendo = 0, che `e quanto volevamo mostrare. 72
5.2. Risonanze ottiche in sistemi atomici a due livelli Per completare la risoluzione dell’equazione operiamo una seconda rotazione che renda stazionario il vettore di Bloch 0 01 0 1 0 00 1 u 1 0 0 u @ v 0 A = @0 cos ⌦t A @ sin ⌦t v 00 A w0 0 sin ⌦t cos ⌦t w00 essa ruota il sistema intorno all’asse x in senso antioriario di un angolo Per ricavare ⇢ e↵ettuiamo le rotazioni 0 1 0 10 1 0 00 1 u cos 0 sin 1 0 0 u @v A = @ 0 1 0 A @0 cos ⌦t sin ⌦tA @ v 00 A w sin 0 cos 0 sin ⌦t cos ⌦t w00 e notando che ⇢00 (t) = ⇢00 (0) = ⇢0 (0) si ha 0 1 0 10 u cos 0 sin 1 0 @v A = @ 0 A @ 1 0 0 cos ⌦t w sin 0 cos 0 sin ⌦t
10 0 cos A @ sin ⌦t 0 cos ⌦t sin
0 1 0
⌦(t).
10 1 sin u0 A @ 0 v0 A cos w0
Nel caso non esattamente risonante le espressioni per l’evoluzione temporale del vettore di Bloch sono pi` u complicate. Il comportamento dell’inversione nel tempo al variare del detuning `e riportato in figura 5.7: all’aumentare del detuning w oscilla con frequenze crescenti (vedi 5.23), mentre l’ampiezza delle oscillazioni diminuisce. Ci si riferisce a queste oscillazioni con il nome di oscillazioni di Rabi.
Figura 5.7: Il grafico mostra l’inversione w in funzione del tempo nel caso di ampiezza stazionaria del campo elettrico (soluzione di Rabi). La curva pi` u alta corrisponde alla risonanza esatta; quella appena pi` u in basso si ottiene con un detuning = 0,2 aE0 . Similmente si trovano a scendere le oscillazioni associate a = 1,0 aE0 , = 1,2 aE0 , = 2,0 aE0 e = 2,2 aE0 .
73
Capitolo 5. Il computer quantistico basato sugli ioni intrappolati
5.3
Stato dell’arte dei computer quantistici a ioni intrappolati
Diamo ora un’esposizione di alcuni degli ultimi risultati sperimentali raggiunti nel campo degli ioni intrappolati. Per quanto riguarda la stabilit`a del confinamento, con le attuali tecniche sperimentali si riescono a mantenere gli ioni all’interno delle trappole per mesi. Questo limite `e spesso dettato dal livello di vuoto raggiungibile all’interno della camera sperimentale: gli ioni subiscono degli urti inelastici con le molecole del gas residuo che ne possono alterare la natura. Gli urti elastici invece, che alla pressione di 10 11 torr occorrono circa una volta all’ora, e non implicano necessariamente l’espulsione degli ioni dalla trappola. Facendo uso di camere criogeniche il verificarsi di questi eventi pu`o essere ulteriormente ridotto. Le specie atomiche adatte per l’utilizzo nella computazione devono presentare delle transizioni tali da poermettere il ra↵reddamento laser, l’inizializzazione dei qubit e la loro misura. Sono queste prerogative di ioni semplici esibenti un solo elettrone nella shell di valenza come i metalli alcanino–terrosi — Be+ , Mg+ , Ca+ , Sr+ e Ba+ — o di alcuni particolari metalli di transizione — Zn+ , Hg+ , Cd+ e Yb+ . + Per rappresentare i qubit si scelgono dei livelli particolarmente stabili. Nell’171 Yb
+
Figura 5.8: Diagramma ridotto dei livelli energietici dell’171 Yb . Gli stati eccitati |ei ed |e0 i sono separati dallo stato fondamentale da una transizione ottica a 369,53nm. Nel caso b `e rappresentata l’inizializzazione dello stato | i eseguita tramite un laser bicromatico accordato alle transizioni |+i ! |ei e |+i ! |e0 i: nello stato | i il sistema non interagisce con la radiazione. Nel disegno c a destra si illustra la misura del qubit nella base computazionale: se si osserva la fluorescenza allora il qubit si trova nello stato |+i.
si utilizzano due livelli iperfini, che chiamiamo |+i e | i, separati da una frequenza ⌫HF = 12,642812GHz (figura 5.8). Altri due stati eccitati |ei ed |e0 i, anch’essi separati da una transizione iperfine, acconsentono il ra↵reddamento doppler. I singoli qubit si riescono a inizializzare con una fedelt`a essenzialmente del 100%. Le misure si e↵ettuano eccitando la transizione |+i |ei: se l’atomo si trova nello 74
5.3. Stato dell’arte dei computer quantistici a ioni intrappolati
Figura 5.9: La stringa di 20 ioni risonante, esibendo la fluorescenza
171 Yb+
intrappolati `e illuminata da una radiazione
stato |+i si osserva una forte fluorescenza (figura 5.9), e anche solo pochi fotoni rilevati permettono di e↵ettuare una misura quasi perfettamente efficiente. Il moto degli ioni all’interno di una stringa `e quello di un sistema di oscillatori accoppiati: un metodo per rendere entangled gli ioni `e quello di usare il moto vibrazionale come intermediario. Supponiamo che gli ioni reagiscono ad un campo esterno mostrando una separazione dei livelli energetici del tipo ±µE, dove E `e il campo e µ `e una costante caratteristica dell’interazione (pu`o trattarsi nella fattispecie dell’e↵etto Stark o dell’e↵etto Zeeman). Se il campo applicato non `e omogeneo spazialmente, lo stato degli ioni varia con la loro posizione all’interno della stringa: Fx = ±µE 0 (x) dove con E 0 (x) indichiamo la componente del gradiente del campo lungo la direzione x. Se il campo E `e creato da una radiazione elettromagnetica di vettore d’onda k allora Fx = ±hk⌦ dove ⌦ = µE0 /h rappresenta la frequenza di Rabi relativa all’accoppiamento dei qubit con il campo: tramite la radiazione `e possibile trasporre lo stato interno dei singoli qubit in uno stato di moto collettivo di N ioni. La velocit`a caratteristica con cui si `e capaci di eseguire queste operazioni vale p Rgate = ⌦ ⌫R /⌫ (5.24) con
⌫R = hk 2 /(8⇡ 2 M )
(5.25)
frequenza caratteristica del rinculo subito dallo ione (M `e la massa complessiva della stringa di ioni) e ⌫ frequenza associata al moto vibrazionale della catena di ioni: una sovrapposizione di stati interna al qubit viene trasposta in una sovrapposizione di modi vibrazionali (fononi). Attualmente queste trasformazioni, la cui fedelt`a `e maggiore del 99%, operano con frequenze dell’ordine di Rgate ⇠ 10 ÷ 100kHz; in futuro si aspira a raggiungere il GHz utilizzando campi ottici ultraveloci. p Dalla 5.24 e dalla 5.25 vediamo che Rgate ⇠ 1/ N : la frequenza delle operazioni diminuisce al crescere di N . All’aumentare del numero di ioni inoltre la variet`a di 75
Capitolo 5. Il computer quantistico basato sugli ioni intrappolati modi vibrazionali possibili favorisce, per via di meccanismi dissipativi, la decoerenza degli stati vibrazionali. Alla decoerenza della stringa contribuiscono anche i campi oscillanti, che a lungo andare producono degli sfasamenti sui qubit. Per queste ragioni non pare possibile scalare l’architettura a singola stringa di ioni. Le moderne tecniche ottiche, applicate ad una singola stringa di N = 10 ÷ 100 ioni, acconsentirebbero ciononostante la dimostrazione di algoritmi di simulazione quantistica applicati a sistemi a molti corpi, quali ad esempio ensemble di spin. Tali sistemi sono notorialmente intrattabili dai computer classici. Per scalare un processore a ioni intrappolati oltre il limite sopra descritto si volge lo sguardo verso nuove architetture quali la QCCD (quantum charge coupled device). Essa consiste nell’accoppiare un piccolo numero di ioni in una catena singola per mezzo dei moti vibrazionali, e quindi di muovere gli ioni verso altre ` in questo modo possibile propagare zone del processore, in maniera classica. E l’entanglement. Il controllo del moto dei singoli ioni nella QCCD richiede una refrigerazione del sistema molto efficiente; si utilizzano per questo degli ioni ausiliari per il ra↵reddamento simpatetico. L’architettura QCCD ha gi`a portato alla dimostrazione di semplici algoritmi, e del teletrasporto quantistico: essa rappresenta una nuova frontiera per il calcolo quantistico. Tuttavia la complessit`a delle interconnessioni richieste e la di↵razione dei raggi laser pongono dei limiti alla sua scalabilit`a. Vi sono recenti tecnologie che prova a spingersi oltre la QCCD: lo schema che si cerca di seguire `e quello di generare dapprima l’entanglement tra due ioni appartenenti a due diversi registri, quindi di sfruttare tali ioni per applicare delle porte su due qubit fra ioni dei diversi registri. Per accoppiare tali registri, chiamati ELU (elementary logic units), si usano dei fotoni emessi dai due ioni di comunicazione i quali memorizzano lo stato dei qubit nello stato di polarizzazione. Tali connessioni fotoniche operano oggi alla frequenza di 1000Hz, e si prospettano sostanziali miglioramenti. Un problema che si incontra sperimentale `e dovuto al fatto che gli ioni di comunicazione devono essere sufficientemente isolati dal resto della catena, per evitare che la radiazione da essi di↵usa influenzi gli altri qubit: si usano per questo delle + + specie atomiche di↵erenti — ad esempio 171 Yb per i qubit di memoria e 138 Ba per i qubit di comunicazione. La scalabilit`a delle trappole si pu`o perseguire anche mediante la costruzione di chip a ioni intrappolati, costituiti da microelettrodi di precisione. Sono stati fabbricati dei chip molto complessi in grado di manipolare decine di ioni in diverse zone di confinamento. A questa scala le operazioni di entanglement sono pi` u difficoltose per via dell’elevato rumore dei dispositivi elettronici. La decoerenza che ne deriva non `e ancora stata del tutto compresa: gli e↵etti del rumore sembrano comportarsi come 1/d4 , dove d `e la distanza tipica degli ioni dagli elettrodi. Si sperimentano anche delle interfacce ottiche che possano funzionare da connessioni per diverse ELU di un possibile multicomputer quantistico per il calcolo distribuito, nel quale porte logiche agenti su qubit appartenenti a diverse ELU sono applicate per via fotonica. Sarebbe in questo modo possibile costruire un computer a ⇠ 106 qubit, nel quale ciascuna ELU potrebbe lavorare in parallelo ed 76
Bibliografia essere entangled con le altre. Sono questi dei buoni presupposti per il raggiugimento della tolleranza agli errori. Se il meccanismo delle porte fotoniche si riuscisse ad estendere a grandi distanze sarebbe possibile distribuire entanglement su distanze macroscopiche, e realizzare protocolli di comunicazione quantistici come la quantum key distribution (QKD). Tuttavia i fotoni impiegati nella realizzazione delle porte logiche fotoniche hanno lunghezze d’onda nella regione dell’ultravioletto, e sono per questo poco adatti alla trasmissione su lunghe distanze; si progettano per questo dei convertitori quantistici di frequenza. I chip a ioni intrappolati potrebbero portare alla realizzazione di sistemi quantistici estesi, cos`ıcch´e la ricerca in questo campo permettere l’investigazione del comportamento dei sistemi quantistici su scala macroscopica.
Bibliografia [AE87]
L. Allen e J. H. Eberly. Optical Resonance and Two–Level Atoms. Dover, 1987.
[Foo05]
Christopher J. Foot. Atomic Physics. Oxford University Press, 2005.
[Fox06]
Mark Fox. Quantum Optics. Oxford University Press, 2006.
[MK03]
C. Monroe e J. Kim. “Scaling the Ion Trap Quantum Processor”. In: Science 339 (2003), pp. 1164–1169.
77
Bibliografia
78
Capitolo 6 Conclusione Riassumiamo la discussione generale portata avanti in questo scritto. Siamo partiti discutendo la formalizzazione del concetto di algoritmo legata alla tesi di Church–Turing: un algoritmo si definisce essenzialmente come un processo eseguibile da una macchina di Turing. Abbiamo quindi parlato della teoria della complessit`a computazionale, che cerca di quantificare le risorse richieste per l’esecuzione di specifici algoritmi o pi` u in generale per la risoluzione di certi problemi: si ritengono intrattabili quei problemi che richiedono un tempo di calcolo che cresce esponenzialmente con la grandezza dell’input. Questa distinzione tra problemi trattabili e intrattabili trova ragion d’essere nella tesi di Church–Turing forte, la quale a↵erma che qualsiasi problema trattabile `e risolubile efficientemente dalla macchina di Turing — o meglio dalla sua variante probabilistica. Le diverse accuse mosse contro la tesi forte hanno spinto a cercare delle motivazioni fisiche per formulare dei validi criteri di computabilit`a. Con la nascita e lo sviluppo del modello di computazione quantistico la fondatezza della tesi di Church–Turing `e stata messa fortemente in discussione: l’algoritmo quantistico di Shor potrebbe rendere possibile la fattorizzazione dei numeri in un tempo polinomiale, cosa che si crede irrealizzabile, al giorno d’oggi, con i computer classici. Nel capitolo 2 abbiamo riassunto i principi del modello di computazione quantistico, dando la definizione di qubit e mettendo in evidenza le nuove possibilit`a di calcolo o↵erte dalla meccanica quantistica. Abbiamo illustrato le porte logiche principali e le tecniche per la realizzazione delle porte logiche controllate. Siamo arrivati infine a dimostrare che ogni circuito quantistico pu`o essere costruito utilizzando solamente un insieme finito di porte logiche detto universale — un ` questo un risultato di risultato simile si dimostra per i circuiti logici classici. E fondamentale importanza per la realizzazione fisica dei computer quantistici. Successivamente abbiamo applicato il modello di computazione quantistico alla risoluzione di certi problemi. Sebbene non sia possibile copiare un qubit, il teletrasporto quantistico permette di trasferirne l’informazione non–localmente, a prezzo di un supplemento di informazione classica scambiata. Abbiamo discusso poi come il principio di sovrapposizione quantistico possa essere sfruttato per risolvere alcuni problemi pi` u efficientemente di quanto non possano 79
Capitolo 6. Conclusione fare gli algoritmi classici. Per finire abbiamo dato la definizione di trasformata di Fourier quantistica e abbiamo descritto la sua utilit`a nel trattamento di problemi di grande importanza quali in particolare la fattorizzazione dei numeri. Ci siamo poi occupati, nel capitolo 4, di stabilire quali sistemi fisici possano fungere da calcolatori quantistici, sviluppando i problemi che si pongono nel costruire e controllare un sistema che esibisce dei comportamenti quantistici. Abbiamo per questo parlato della decoerenza e dei diversi meccanismi tramite i quali vengono meno le peculiari caratteristiche di un sistema quantistico in contatto con l’ambiente esterno. Nell’ultimo capitolo abbiamo infine esaminato i principi fisici che stanno alla base del funzionamento dei computer quantistici a ioni intrappolati. Abbiamo preso in considerazione un sistema di confinamento (trappola di Paul) trovando la soluzione per il moto di uno ione all’interno della trappola e abbiamo accennato ad alcuni dei sistemi di ra↵reddamento principali che solitamente si utilizzano. Nella seconda parte del capitolo abbiamo visto come sia possibile e↵ettuare delle rotazioni del vettore di Bloch che rappresenta lo stato di un atomo nell’approssimazione a due livelli mediante l’interazione con una radiazione risonante: un’onda esattamente risonante produce variazioni dell’angolo polare ✓ nella sfera di Bloch, mentre una radiazione leggermente desintonizzata provoca delle rotazioni attorno ad assi diversi. Nell’ultimo decennio si sono susseguite diverse dimostrazioni sperimentali di computer quantistici a ioni intrappolati. Sono stati prodotti stati entangled anche di 8 qubit, e sono stati eseguiti semplici algoritmi. Si `e riusciti a realizzare il cnot e porte logiche agenti su due qubit fedeli al 99% (probabilit`a di errore dell’1%); per permettere il funzionamento dei codici di correzione degli errori `e tuttavia necessaria una fedelt`a di almeno 99,99%. Si cerca per questo di ridurre ulteriormente le perturbazioni esterne a cui gli ioni sono sottoposti. Si cerca ora anche di scalare questi prototipi ancora rudimentali, incrementando il numero di qubit. Una difficolt`a da a↵rontare `e dovuta al fatto che lunghe stringhe di ioni (dell’ordine di 20 elementi) sono difficilmente controllabili per via della variet`a dei moti vibrazionali collettivi; si cerca di sviluppare un sistema di trasporto che renda possibile la separazione dei qubit da processare da quelli di memoria. Le interazioni tra i qubit nell’implementazione a ioni intrappolati sono mediate dalle vibrazioni collettive, le quali tuttavia rendono difficile scalare l’architettura del computer. Un secondo approccio `e quello di utilizzare dei fotoni per accoppiare i qubit: in questo tentativo si `e riusciti a creare uno stato entangled a partire da due ioni distanti 1m. Anche se si `e ancora lontani dalla costruzione di un computer quantistico in grado di tradurre in pratica i pi` u audaci disegni teorici, la computazione quantistica promette di riformare i nostri standard di computazione. Gli ioni intrappolati sono gli apripista pi` u accreditati di questa trasformazione per via dell’elevato isolamento raggiungibile tramite le trappole. Si tratta di un campo di ricerca fruttuoso anche in vista di altre applicazioni: alcune operazioni logiche su due qubit sono gi`a in uso in certi orologi atomici che utilizzano come campione di tempo la frequenza delle transizioni atomiche. Tecniche simili trovano utilizzo in esperimenti di spet80
troscopia. Negli anni a venire si pianifica la realizzazione di una nuova generazione di chip a ioni intrappolati (alcuni chip sono gi`a stati costruiti), che potranno forse soddisfare le pi` u ardite prospettive.
81
Capitolo 6. Conclusione
82
Bibliografia [AE87]
L. Allen e J. H. Eberly. Optical Resonance and Two–Level Atoms. Dover, 1987.
[CDL91] Claude Cohen–Tannoudji, Bernard Diu e Franck Lalo¨e. Quantum Mechanics. Wiley, 1991. [DiV00]
David P. DiVincenzo. “The Physical Implementation of Quantum Computation”. In: Fortschr. Phys. 48 (2000), pp. 771–783.
[Foo05]
Christopher J. Foot. Atomic Physics. Oxford University Press, 2005.
[Fox06]
Mark Fox. Quantum Optics. Oxford University Press, 2006.
[MK03]
C. Monroe e J. Kim. “Scaling the Ion Trap Quantum Processor”. In: Science 339 (2003), pp. 1164–1169.
[NC00]
Michael A. Nielsen e Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.
83
