Un Sistema a pi` u Qubit - L'Algoritmo di Deutsch-Jozsa in QScript

3.5 Un Sistema a pi`u Qubit

Si consideri ora un registro composto da n bit. Ogni stato del registro cos`ı formato sar`a rappresentabile dal vettore di qubit |xi = |x1i |x2i · · · |xni

che per brevit`a verr`a spesso scritto come |x1x2· · · xni. Dal momento che

ogni |xii pu`o assumere i valori o |0i o |1i, in totale, lo spazio degli stati del

registro `_{e composto da D}2,n= 2n stati e viene indicato come:

B_c(n)=                     

|0i |0i · · · |0i |0i |0i · · · |1i · ··

|1i |1i · · · |0i |1i |1i · · · |1i

                     = n |xi = |x1x2· · · xni : |xii ∈ {0, 1} o 5_{. Cos`ı come B}

q si sviluppa sopra la base computazionale {|0i , |1i} = Bc,

cos`ı allo stesso modo `e possibile generalizzare un sistema quantistico sopra B(n)c : B(n) q = n X x∈{0,1}nax|xi : ax ∈ C ∧ X x∈{0,1}n|ax| 2 = 1o

il cui spazio degli stati `e composto da tutti i possibili vettori complessi di dimensione 2n _{che hanno norma 1. Un sistema a n qubit pu`}_{o trovarsi in una}

sovrapposizine di 2n _{valori differenti, per esempio, il seguente stato}

|ψi =       00 1₂ 01 1₂ 10 1 2 11 1₂       = 1 2|00i + 1 2|01i + 1 2|10i + 1 2|11i

appartiene a Bq(2). I numeri a fianco nella rappresentazione matriciale

indicano la componente della base {|00i , |01i , |10i , |11i} a cui `e associato il coefficiente complesso, si noti che |ψi `e uno stato di perfetta sovrapposizione.

5_{Nello specifico B}(n)

c `e data dal prodotto tensoriale Bc ⊗ Bc ⊗ · · · ⊗ Bc di n basi

3.5. UN SISTEMA A PI `U QUBIT 34

Il sistema è composto da n osservabili, uno per ogni qubit, le proiezio- ni P₀(i), P₁(i) sono formate da tutte le componenti dello stato nelle quali, rispettivamente, l’i-esimo qubit è |0i e l’i-esimo qubit è |1i; la probabilità che l’i-esimo qubit venga misurato con valore |xi è calcolata di conseguen- za: prob[|Ψi → |x1x2· ·x · ·xni] = P (i) x 2

, dove |Ψi è uno stato generico. Il vettore risultante da una misurazione di un qubit è poi normalizzato analo- gamente a quanto già esposto per gli altri sistemi. Supponiamo ad esempio che venga misurato il secondo qubit di |ψi (per convenzione rispetto alla rappresentazione di Dirac numeriamo i qubits da sinistra a destra) e che il valore osservato sia |1i, allora:

P₁(2)(|ψi) = 1

2|01i + 1 2|11i e lo stato |ψ1i risultante dalla misurazione:

|ψ1i = P₁(2)(|ψi) P (2) 1 (|ψi) = 1 2|01i + 1 2|11i q (1₂)2_{+ (}1 2) 2 = 1 2|01i + 1 2|11i q 1 2 = √1 2|01i + 1 √ 2|11i `

e lo stato in cui il secondo qubit ha valore |1i con certezza mentre il primo si trova in perfetta sovrapposizione, con il 50% di probailit`a di misurare o |0i o |1i, in accordo con la definizione di |ψi. In generale, prob[|Ψi → |xi] = |ax|2.

Trasformazioni

Le trasformazioni che descrivono la dinamica di questo registro sono le unitarie U ∈ M2n×2n. In realt`a, una qualsiasi trasformazione unitaria che agisca su di un singolo qubit del sistema risulta essere valida in quanto altera lo stato nel suo complesso, per convincersi di ci`o, si supponga di applicare N OT sul primo qubit di Bc(2):

3.5. UN SISTEMA A PI `U QUBIT 35

N OT1|00i → |10i

N OT1|01i → |11i

N OT1|10i → |00i

N OT1|11i → |01i

dove il pedice 1 è stato aggiunto per meglio esplicitare la semantica dell’operazione, come si può notare, questa trasformazione altro non fa che permutare gli elementi e, dal momento che Bc(2)è la base su cui è costruito Bq(2), l’azione

di N OT1 su di un generico stato: N OT1|Ψi = N OT1( X x∈{0,1}2ax|xi) = X x∈{0,1}2axN OT1|xi

ne preserverà la norma. Più in generale, è possibile estendere una trasformazione T : Bq → Bq che agisce su di un singolo qubit in una trasformazione

T(n)_{: B}

q(n)→ Bq(n) che agisce su un intero registro quantistico.

Le trasformazioni su singoli qubits non sono le uniche trasformazioni am- missibili in un registro ma `e possibile effettuare trasformazioni unitarie anche agendo su pi`u qubits contemporaneamente, ad esempio, la porta6 _C

iN OTj

(”controlled-NOT”) `e la trasformazione che effettua un NOT su l’j-esimo qubit se e solo se l’i-esimo qubit `e |1i altrimenti lo lascia inalterato. Applichiamo C1N OT2 su Bc(2):

C1N OT2|00i → |00i

C1N OT2|01i → |01i

C1N OT2|10i → |11i

C1N OT2|11i → |10i

ancora, CiN OTj `e unitaria su Bq(n) perch`e effettua una permutazione degli

elementi di base. Tale trasformazione verr`a ripresa per l’implementazione dell’algoritmo di Deutsch-Jozsa nell’ultimo capitolo.

6_{cominciamo a chiamare le trasformazioni con il nome ”porta” in riferimento alla}

3.6. ENTANGLEMENT 36

3.6 Entanglement

Utilizzando le trasformazioni a più qubits come CNOT è possibile rendere il sistema entangled, è cioè possibile giungere in uno stato che non sia più esprimibile come composizione dei suoi sottosistemi. In questa situazione, le componenti sono intrinsecamente connesse e non possono essere descritte indipendentemente.

Si consideri l’evoluzione di un registro a due qubits partendo dallo stato iniziale: |ψ1i = |00i applicando H1 si ottiene: |ψ2i = H1|ψ1i = |00i + |10i √ 2 applicando ora C1N OT2 passiamo allo stato

|ψ3i = C1N OT2|ψ2i =

|00i + |11i √

che è entangled. Infatti, se misuriamo il primo qubit ottenendo |0i, allora sia avrà che |ψ3i collasserà nello stato:

|ψ4i = P₀(1)(|ψ3i) P (1) 0 (|ψ3i) = 1 √ 2|00i + 0 |01i q 1 2

= 1 |00i + 0 |01i = |00i

quindi, la misura del secondo qubit porter`a a rilevare il valore |0i con certezza. Inversamente, se la misura avesse riportato |1i come valore del primo qubit, avremmo trovato |1i anche nel secondo sempre con certezza.

Da un punto di vista formale, un sistema si dice entangled se non pu`o essere espresso come prodotto tensoriale delle sue componenti di base, nel caso di un sistema a due qubit, una generica composizione ha la forma:

(c0|0i+c1|1i)⊗(c00|0i+c 0

3.7. SFRUTTARE IL PARALLELISMO 37

Il problema, sostituendo per |ψ3i, consiste nel risolvere il seguente sistema di

equazioni:                c0c00 = 1 √ 2 c0c01 = 0 c1c00 = 0 c1c01 = √1₂

che, chiaramente, non ha soluzioni. Lo stato |ψ3i non pu`o essere riscritto

come prodotto tensoriale degli stati base che sono quindi ora inseparabili. Ritornando al significato fisico: in un certo senso, è come se nel preci- so istante in cui viene compiuta un’osservazione, il valore calcolato venisse trasmesso istantaneamente al secondo qubit entangled il quale si comporta coerentemente con il valore trasmesso/osservato. Questa relazione tuttavia non contempla nè mezzi di trasmissione di questa ipotetica informazione, nè distanze tra i due sistemi. Sarebbe quindi possibile, almeno in linea di principio, utilizzare l’entanglement per comunicare subitaneamente anche a distanze superiori all’anno luce e ciò, come già anticipato, è in contraddizio- ne con le leggi della relatività generale e con il principio di località su cui è fondata praticamente tutta la fisica non quantistica [9]. La correttezza delle previsioni teoriche è stata dimostrata ripetutamente in laboratorio grazie ad una serie di esperimenti [10] e sono state inoltre proposte, già a partire dal secolo scorso, numerose interpretazioni della meccanica quantistica che giustificherebbero il perchè dell’entanglement [11].

3.7 Sfruttare il Parallelismo

Il parallelismo, nel calcolo quantistico, emerge con la sovrapposizione. Come gi`a visto nella sezione sui sistemi a pi`u qubits, sia T una qualsiasi trasformazione unitaria che agisce sulla base Bc(n) allora, l’applicazione di T

3.7. SFRUTTARE IL PARALLELISMO 38

T |Ψi = T (X

x∈{0,1}nax|xi) =

x∈{0,1}naxT |xi

T agisce quindi contemporaneamente su tutti i 2n _{stati |xi ∈ B} q(n).

Sappiamo per`o che una misura dell’intero sistema comporta il collasso inevitabile del registro in una specifica configurazione con probabilit`a |ax|2;

a primo impatto sembrerebbe dunque che il parallelismo sia solo una prero- gativa di quel noumeno imponderabile che è la sovrapposizione, della quale non si può avere un quadro deterministico rendendo quindi apparentemente impossibile ricavarne vantaggi computazionali. Scopo di questa sezione, e in particolare della tesi in generale da questo punto in poi, è mostrare che non `

e cos`ı. L’utilizzo di particolari stati di partenza uniti a cambi di base appro- priati permettono infatti la progettazione di algoritmi quantistici in grado di risolvere svariate tipologie di problemi con efficienza maggiore rispetto agli equivalenti algoritmi classici.

Viene qui di seguito proposta una procedura che, per una generica funzione Booleana f : {0, 1} → {0, 1}, permette di calcolare f (0) e f (1) contemporaneamente applicando f una volta sola.

Per quanto dimostrato da Deutsch [12], il potere espressivo del calcolo quantistico `e almeno equivalente a quello di un qualsiasi formalismo classico, `

e quindi possibile affermare che, per ogni funzione g calcolabile esiste una corrispettiva procedura Ug che la calcola. Ug avr`a la forma:

Ug|x, yi = |x, y ⊕ g(x)i

dove |yi `e un qubit ausiliario che permette di rispettare il vincolo di reversi- bilt`a: Ug|x, y ⊕ g(x)i = |x, (y ⊕ g(x)) ⊕ g(x)i = |x, yi .

Per motivi di chiarezza espositiva e per rimanere fedeli all’approccio di- dattico utilizzato in letteratura per l’esposizione di questi argomenti affian- chiamo al modello di calcolo fino a qui utilizzato il modello a circuiti. Il modello a circuiti `e un’astrazione grafica di una procedura di calcolo che uti- lizza la metafora di un circuito elettronico, ogni trasformazione `e raffigurata da una porta (detta logica nel caso classico e quantistica altrimenti) e l’evolu-

3.7. SFRUTTARE IL PARALLELISMO 39

zione `e da leggersi da sinistra verso destra. Come primi esempi consideriamo il circuito formato dalla porta NOT:

|xi

|1 − xi

o il circuito che implementa Ug:

|xi

|yi |g(x) ⊕ yi

La semantica di questi diagrammi coincide con la semantica delle relative trasformazioni. In questo caso Ug viene anche detto ”oracolo” ad indicare

una porta di cui non si conosce la struttura interna ma solo il mapping input e output.

Si ritorni allora al problema inizialmente sollevato riscrivendolo usando la terminologia introdotta: vogliamo calcolare di una funzione f : B → B se f (0) = f (1) valutando Uf una sola volta. `E evidente che per risolvere

classicamente il problema `e necessario calcolare f due volte, una per entrambi gli input.

Per sfruttare il parallelismo, il sistema deve essere posto in uno stato di sovrapposizione. Quale sia per`o la successione di trasformazioni che permetta di risolvere il problema `e il vero ostacolo che si incontra nella progettazione di qualsivoglia algoritmo quantistico. Procediamo allora per tentativi al fine di indirizzarci verso la soluzione corretta. Dal momento che Uf(|x, yi) =

|x, f (x) ⊕ yi calcola f sul primo qubit, la scelta pi`u intuitiva `e quella di porlo in sovrapposizione.

Sia |ψ1i = |00i lo stato iniziale scelto arbitrariamente e

|0i H

|xi

3.7. SFRUTTARE IL PARALLELISMO 40

il circuito relativo. Per verificare se questo algoritmo (un circuito individua un algoritmo) sia sufficiente a risolvere il problema, monitoriamo l’evoluzione della computazione tramite |ψii che descrive lo stato in cui si trova il registro

dopo l’i-esima operazione. Cominciamo con l’applicare H1, si avr`a:

|ψ2i = H1|ψ1i =

h|0i + |1i √

2 i

|0i = h|00i + |10i√ 2 i e, dopo l’applicazione di Uf |ψ3i = Uf |ψ2i = h|0, f (0) ⊕ 0i + |1, f (1) ⊕ 0i √ 2 i =h|0, f (0)i + |1, f (1)i√ 2 i

che calcola effettivamente f (0) e f (1)! Solo che lo fa mantenendosi in sovrapposizione, un oggetto macroscopico come uno scienziato che non sperimenta gli effetti della meccanica quantistica può ugualmente ricavare f (0) e f (1) da questo circuito? La risposta è no, infatti, misurare uno qualsiasi dei 2 qubits permette soltanto d’ottenere informazioni su di un unico valore: o f (0) con il 50% di probabilità o f (1) con la stessa probabilità. È dunque necessario cambiare qualcosa, invece di porre il primo qubit in uno stato di sovrapposizione, si provi con il secondo settandolo inizialmente a |1i. Per aumentare in generalità il primo qubit è lasciato in un generico |xi. Ne risulta il seguente circuito:

|xi

|1i H |f (x) ⊕ yi

3.7. SFRUTTARE IL PARALLELISMO 41 |ψ2i = H2|ψ1i = |xi h|0i − |1i √ 2 i =h|x, 0i − |x, 1i√ 2 i

di cui si noti il cambio di fase rispetto alla sovrapposizione nel tentativo precedente. Applicando poi Uf

|ψ3i = Uf|ψ2i =

h|x, f (x) ⊕ 0i − |x, f (x) ⊕ 1i √

= |xih|f (x)i − |f (x)i√ 2 i ⇒ |ψ3i =    |xi [|1i−|0i√ 2 ] f (x) = 1 |xi [|0i−|1i√ 2 ] f (x) = 0

= (−1)f (x)|xi [|0i − |1i√ 2 ] Nota: a(b − c) = −a(c − b)

ancora, misurare i 2 qubits non ci fornisce informazioni sulla struttura interna della funzione in quanto questa viene valutata solo sull’input |xi che non è mai posto in sovrapposizione. Tuttavia, questo tentativo non è stato vano, ci ha infatti permesso di esplicitare f (x) come parametro per il primo stato, suggerendo cos`ı di mettere in sovrapposizione l’intero registro, questo passo permette di giungere alla soluzione cercata. Lasciamo inalterato il valore iniziale a |1i del secondo qubit e esplicitiamo |xi = |0i (arbitrario, andrebbe bene anche |1i), l’evoluzione sarà:

|ψ2i = H1|ψ1i = h|0, 1i + |1, 1i √ 2 i , |ψ3i = H2|ψ2i = h|0i + |1i √ 2 ih|0i − |1i √ 2 i

=h|00i − |01i + |10i − |11i 2

= 1

3.7. SFRUTTARE IL PARALLELISMO 42

. Una volta raggiunto uno stato di completa sovrapposizione degli osservabili e tenendo in mente il risultato del tentativo precedente, l’applicazione di Uf

porter`a a:

|ψ4i = Uf |ψ3i =

1 2[(−1)

f (0)_{|0i (|0i − |1i) + (−1)}f (1)_{|1i (|0i − |1i)]}

il secondo qubit resta invariato, si pu`o quindi semplificare |ψ4i =

1 2[[(−1)

f (0)_{|0i + (−1)}f (1)_{|1i][(|0i − |1i)]}

a questo punto `e possibile dimenticarsi del secondo qubit non dipendendo da f e normalizzare lo stato. Andando poi a semplificare ulteriormente

|ψ4i₁ = 1 √ 2[(−1) f (0) (|0i + (−1)f (1)⊕f (0)|1i)]

finalmente f (1) e f (0) sono in relazione diretta. In particolare, si noti che: f (1) ⊕ f (0) = 0 se e solo se f costante, possiamo quindi riscrivere

|ψ4i1 =    ±[|0i+|1i√ 2 ] f costante ±[|0i−|1i√ 2 ] altrimenti

. Si noti come in realtà i segni ± individuano ogni possibile funzione f : B → B e non solo la proprietà di essere costante7. Questi valori non dovrebbero poi essere nuovi, difatti il primo qubit non è altro che H1|0i se f costante e

H1|0i altrimenti, inoltre, poich`e H `e la trasformazione inversa di se stessa,

baster`a riapplicarla per giungere finalmente a

|ψ5i = H1|ψ4i =    ± |0i [|0i+|1i√ 2 ] f costante ± |1i [|0i−|1i√ 2 ] altrimenti

. Per quanto l’informazione salvata nei segni andr`a persa, non ci resta che misurare l’osservabile del primo qubit per risolvere il nostro problema: se risulta nello stato |0i allora f (0) = f (1), mentre se risulta nello stato |1i allora f (0) 6= f (1).

7_{Come visto nel primo capitolo sono 2}(21₎

= 4 funzioni di cui 2 costanti e 2 no Ad esempio la f0 costante a 0 `e rappresentata da |ψ₄0i₁= +|0i+|1i√

2 essendo (−1)

3.7. SFRUTTARE IL PARALLELISMO 43

Il procedimento appena seguito pu`o essere riassunto dal circuito:

|0i H1

H1 |ψ5i_n

|1i H2 |ψ5i₂

ed `e lo stesso algoritmo che David Deutsch propose nel 1985 [12] dimostrando per la prima volta che l’Informazione quantistica poteva esserre impiegata per eseguire calcoli guadagnando in efficienza rispetto alla computazione classica.

E da sottolineare però che, nonostante la procedura esposta permetta di risolvere il problema in un’unica esecuzione invece che in due, il vantaggio ricavatone è solo costante e perciò non rilevante a livello asintotico. In termini di complessità, in realtà, è la formulazione di per sè a non essere interessante in quanto l’input di f non è variabile ma fisso (0,1). Il problema quindi, non sembrerebbe essere il candidato ideale per scommettere sulla computazione quantistica, tuttavia, la soluzione di Deutsch fu (ulteriormente) importante poichè portò allo sviluppo del primo algoritmo in grado di sfruttare le vere potenzialità di questa disciplina.

Capitolo 4

L’Algoritmo di Deutsch-Jozsa

Il problema originale di Deutsch fu successivamente generalizzato da Deu- tsch stesso e Richard Jozsa nell’articolo ”Rapid solution of problems by quantum computation” [15] nel 1992, il risultato che proposero fu poi ri- visitato e completato da Richard Cleve, Artur Ekert, Chiara Macchiavello e Michele Mosca nel 1998 [16]. Questo lavoro `e conosciuto in letteratura come l’algoritmo di Deutsch-Jozsa.

Se il primo algoritmo di Deutsch fu pi`u un risultato simbolico, l’algoritmo di Deutsch-Jozsa fu invece il vero passo in avanti che mise in luce come, utilizzando il paradigma quantistico, si poteva ottenere un aumento esponenziale in velocit`a per la risoluzione di un determinato problema.

Nello specifico il problema diventa: sia data una funzione f : Bn _{→ B}

di cui non si conosce la definizione, determinare se tale funzione è costante oppure bilanciata*, sapendo per certo che f sarà o costante o bilanciata. D’ora in poi si farà riferimento a questo problema chiamandolo D.J.

Si noti come questa formulazione altro non sia che un’estensione della formulazione originaria, infatti, se nel caso particolare di n = 1 f non `e costante, allora sar`a per forza bilanciata, e viceversa. Deutsch e Jozsa riu- scirono a dimostrare che il problema poteva essere risolto per qualunque n valutando f una volta sola.

Viene di seguito mostrata la soluzione al problema mediante il sistema

classico e il sistema quantistico al fine di mostrare come quest’ultimo risulti vincente per complessit`a e correttezza.

Teorema 4.1. Classicamente, il problema di D.J. appartiene a Ω(2(n−1)), cio`e non esiste algoritmo che lo risolva con complessit`a o(2(n−1)).

Dimostrazione. Sia f : Bn _{→ B espressa in un registro a n bit attraverso la}

trasformazione Uf : B (n)

c → B(n)c tale che Uf|xi = Uf|00 · · · f (x)i sappiamo

che f è sicuramente o costante o bilanciata. Si noti che in questo sistema non è necessario imporre la reversibilità.

Una qualsiasi procedura che risolve il problema non pu`o fare altro che cominciare a valutare Uf su ogni possibile stato |xi ∈ B

(n)

c e fermarsi se:

• Sono stati trovati due stati |xi₁, |xi₂tali che Uf(|xi₁) 6= Uf(|xi₂) poich`e

in questo caso f sar`a bilanciata non essendo costante;

• Sono stati già valutati 2(n−1)+ 1 stati e tutti hanno effettuato lo stesso cambio di stato, poichè in questo caso f sarà costante non essendo bilanciata.

Il caso pessimo coincide con quello costante e quindi ogni algoritmo che risolve D.J. nel caso classico avr`a complessit`a Ω(2(n−1)_).

Teorema 4.2. Un qualsiasi algoritmo probabilistico che compia k < 2n−1_{+ 1}

valutazioni di f (x) di valori x ∈ Bn _{scelti indipendentemente e uniforme-}

mente, avr`a almeno una probabilit`a di errore ≥ ₂12k [17].

Questo risultato `e ovviamente valido anche per un sistema a n bit tradu- cendo f in Uf come fatto per il teorema precedente. Utilizzando l’algoritmo

probabilistico ottimale saranno comunque necessarie 2n−1 _{+ 1 valutazioni}

per rispondere con certezza e, una singola valutazione di f (k=1) porter`a a sbagliare mediamente 1 volta ogni 4.

L’algoritmo di Deutsch–Jozsa segue lo stesso schema dell’algoritmo di Deutsch solo generalizzandolo per un sistema a n + 1 qubit. Il circuito che ne risulta `e il seguente:

|0i H⊗n

H⊗n

|1i H

indica dove viene effettuata la misurazione finale.

Per mettere n qubits in sovrapposizione è necessario applicare Hadamard ad ogni qubit, ciò è esprimibile sinteticamente attraverso il prodotto tensoriale H⊗n _{di n Hadamard. Si ricordi infatti che la composizione di pi`}_{u sistemi}

quantistici `e data dal prodotto tensoriale degli stessi, lo stesso principio si applica alla composizione di trasformazioni. Per capire come costruire H⊗n

cominciamo ricavando H⊗2 _{e cerchiamo di dedurne una struttura generale.}

Possiamo esplicitare H come:

H = √1 2 " 0 1 0 1 1 1 1 −1 # = √1 2 " 0 1 0 (−1)0∧0 (−1)0∧1 1 (−1)1∧0 (−1)1∧1 #

dove H[i, j] indica l’azione di H sullo stato |ii dato lo stato |ji come input. Possiamo quindi calcolare semplicemente la composizione di 2 Hadamard:

47 H⊗2 ₌ _√1 2 " 0 1 0 (−1)0∧0 (−1)0∧1 1 (−1)1∧0 (−1)1∧1 # ⊗ √1 2 " 0 1 0 (−1)0∧0 (−1)0∧1 1 (−1)1∧0 (−1)1∧1 # = = 1 2       00 01 10 11 00 (−1)0∧0∗ (−1)0∧0 (−1)0∧0∗ (−1)0∧1 (−1)0∧1∗ (−1)0∧0 (−1)0∧1∗ (−1)0∧1 01 (−1)0∧0∗ (−1)1∧0 (−1)0∧0∗ (−1)1∧1 (−1)0∧1∗ (−1)1∧0 (−1)0∧1∗ (−1)1∧1 10 (−1)1∧0∗ (−1)0∧0 (−1)1∧0∗ (−1)0∧1 (−1)1∧1∗ (−1)0∧0 (−1)1∧1∗ (−1)0∧1 11 (−1)1∧0∗ (−1)1∧0 (−1)1∧0∗ (−1)1∧1 (−1)1∧1∗ (−1)1∧0 (−1)1∧1∗ (−1)1∧1      

Nota: (−1)x∗ (−1)y = (−1)x+y = (−1)x⊕y

viene utile allora definire la funzione < , > : {0, 1}n× {0, 1}n _{→ {0, 1}}

< x, y > = < x0x1· · · xn−1, y0y1· · · yn−1 >

= (x0∧ y0) ⊕ (x1∧ y1) ⊕ · · · ⊕ (xn−1∧ yn−1)

che ci permette di scrivere sinteticamente H⊗n

H⊗n_{[i, j] =} _√1

2n(−1) <i,j>

. Proviamo a capire il comportamento della matrice ricavata: sia |yi ∈ B(n)c

uno stato certo, riscritto vettorialmente

|yi =             00···0 0 00···1 0 ··· · · · y 1 ··· · · · 11···1 0             y ∈ {0, 1}n avremo

48 H⊗n_{|yi = H}⊗n_{[−, y] =} _√1 2n X x∈{0,1}n(−1) <x,y>_|xi =             00···0 (−1)<00···0,y>√1 2n 00···1 (−1)<00···1,y>√1 2n ··· · · · y (−1)<y,y>√1 2n ··· · · · 11···1 (−1)<11···1,y>√1 2n            

che `e uno stato di perfetta sovrapposizione sopra la base computazionale, come ci aspettavamo.

Acquisiti gli strumenti necessari `e possibile ora procedere alla formulazione e dimostrazione del seguente teorema.

Teorema 4.3. L’algoritmo di Deutsch–Jozsa `e un algoritmo deterministico che risolve il problema D.J. con un’unica valutazione di Uf.

Dimostrazione. La correttezza dell’algoritmo `e deducibile per costruzione svolgendo l’algoritmo stesso.

Sia |ψii lo stato del sistema dopo l’i-esima operazione. Monitoriamo quin-

di l’evoluzione del sistema operazione per operazione. Lo stato iniziale |ψ1i

` e:

|ψ1i = |0i |1i = |01i |02i · · · |0ni |1i

dopo l’applicazione di H⊗n _{su |0i il sistema si trover`}_{a nello stato:}

|ψ2i = h 1 √ 2n X x∈{0,1}n(−1) <x,0>_|xii_|1i =h√1 2n X x∈{0,1}n|xi i |1i Nota: < x, 0 >= 0

49 dopo Hn+1: |ψ3i = h 1 √ 2n X x∈{0,1}n|xi ih|0i − |1i √ 2 i

come per l’algoritmo di Deutsch, aver posto in sovrapposizione il qubit ausiliario ci permette di esplicitare f sui primi n stati dopo l’applicazione di Uf: |ψ4i = h 1 √ 2n X x∈{0,1}n(−1)

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

2 i

a questo punto possiamo dimenticarci dell’ultimo qubit concentrandoci su quello che accade dopo la riapplicazione di H⊗n _{: otteniamo una sovrappo-}

sizione degli stati gi`a in sovrapposizione!

|ψ5in= 1 2n X z∈{0,1}n X x∈{0,1}n(−1) f (x)₍₋₁₎<x,z>_|zi = 1 2n X z∈{0,1}n X x∈{0,1}n(−1) f (x)⊕<x,z>_|zi

ora |ψ5i_nviene misurato. Invece di controllare subito il risultato chiediamoci

prima quale sia la probabilit`a di osservare lo stato |0i, cio`e:

prob[|ψ5in → |0i] = kP0(|ψ5in)k 2 = 1 2n X x∈{0,1}n(−1) f (x)_|0i 2

quindi, la probabilit`a di collassare a |0i `e totalmente dipendente da f (x), in particolare: se f costante: P0(|ψ5i_n) = ₂1n P x∈{0,1}n(−1)f (x)|0i = ±2 n 2n|0i = ±1 |0i ⇒ prob[|ψ5i_n → |0i] = 1 se f bilanciata: P0(|ψ5in) = 1 2n P x∈{0,1}n(−1)f (x)|0i = 2 n−1 2n |0i− 2n−1 2n |0i = 0 |0i ⇒ prob[|ψ5in → |0i] = 0

.Verrà quindi misurato |0i se e solo se la funzione f è costante, altrimenti, verrà misurato un qualsiasi altro |xi se e solo se la funzione è bilanciata.

In conclusione, l’algoritmo di Deutsch–Jozsa risolve il controverso problema con una sola esecuzione in contrasto alle 2n−1_{+ 1 necessarie per avere}

certezza nella computazione classica, risultando quindi esponenzialmente pi`u veloce di ogni altra procedura conosciuta.

Capitolo 5

Implementazione di

Deutsch-Jozsa tramite QScript

Come ultimo argomento, questa tesi si propone di presentare un esempio concreto di quanto esposto fino ad ora. Viene di seguito implementato ed eseguito su pi`u istanze l’algoritmo di Deutsch-Jozsa. Per sviluppare il lavoro `

e stata scelta la piattaforma web QuantumPlayground [18]: un esperimento di Chrome che simula il comportamento di un registro quantistico fino a 22 qubit programmabile attraverso il linguaggio di scripting ad hoc chiamato QScript. A supporto della programmazione QuantumPlayground fornisce un sistema di debugging e un motore grafico che permette di visualizzare l’evoluzione dello stato del sistema durante l’esecuzione.

L’obiettivo `e quello di tradurre il circuito per D.J.

|0i _H⊗n

H⊗n

|1i H

in un programma che ne simuli il comportamento. Per farlo, `e necessario una funzione f su cui valutare l’algoritmo, a tal proposito, sono state scelte due funzioni bilanciate e una costante. Di ogni funzione viene mostrato il procedimento seguito per la costruzione dell’oracolo, il codice relativo e uno snapshot del risultato finale.

Si cominci con il caso più elementare e cioè il caso in cui f è costante. È stata scelta consapevolmente la f costante a 0, il motivo di questa preferenza risiede nella definizione dell’oracolo, infatti, Uf per f (x) = 0 è semplicemente

Uf(|x, yi) = |x, y ⊕ f (x)i = |x, yi ovvero la trasformazione identit`a.

Passiamo ad esporre e commentare lo script che implementa l’algoritmo per l’oracolo I, il primo passo `e inizializzare il sistema:

//inizialization

VectorSize 8 SetViewMode 2

il primo comando crea un sistema di 8 qubits tutti inizializzati a |0i. La scelta della dimensione è coerente con i successivi esempi ma fondamental- mente arbitraria per questo esempio. SetViewMode è una costante che setta la modalità di visualizzazione grafica, 2 indica la modalità 3D. Per allinearsi con lo sato iniziale dell’algoritmo è necessario invertire l’ultimo qubit:

//swap the last qubit’s value using X Pauli gate.

SigmaX 7

QScript ha come primitive le pi`u comuni operazioni quantistiche tra cui, appunto, la porta X di Pauli ossia l’equivalente quantistica della trasformazione NOT. Come gi`a esposto nel capitolo precedente, all’algoritmo sono necessarie due applicazioni di H⊗n_{, delle quali la prima in concomitanza con}

H su |1i; `e utile allora definire una procedura che ponga in sovrapposizione un numero variabile di qubit:

//hadamard gate on j qubits, note: j=n on first call, j=n-1 on

Nel documento L'Algoritmo di Deutsch-Jozsa in QScript (pagine 35-72)