Quantum Search Algorithms

Introduzione agli algoritmi di ricerca quantistici

Perché usare questi algoritmi?

)NO( di precedente al analogo problemaun per àcomplessit

avere di permetteGrover di algoritmo o

oquantistic ricerca di algoritmoUn •

città). una di strade N traminima la (es. desiderata soluzione

la trovareha O(N) impiega classico

computerun disu ricerca di algoritmoUn •

Formalizziamo il problema

altrimenti 1

soluzione la ènon x 0x

)desiderato indirizzol' (cioè 1-Nx 1

che x taleinteroun' dominio come ha che funzione una da

atarappresent essere può problema del istanza eparticolar Una

N M1 dove soluzioni M portare potrà ricerca Questa

.2N dove bitsn su omemorizzat

essere potrà indirizzol’, 1)-N a 0 da indici(con

elementi N di spazio unoin cercare di Supponiamo

n

sef

Cos’è un Oracolo?

register indexx

xfqubit oracleq

xfqxqx O

chiamato è

no altrimenti 1 se commuta e chiamato è

2 modulo addizionel' denota

:nalicomputazio basi seguenti sulle azionedall'

definito I) O O (cioè O unitario operatoreun’ è OracoloUn †

• Negli algoritmi quantistici si usa applicare all’Oracolo l’oracle qubit nello stato:

2

10

• Se x dovesse essere la soluzione

2

10

2

01 scambiati vengono0 e 1

xx

• Di conseguenza l’Oracolo si comporterà nel seguente modo

1 fig

2

101

2

10 )(

xx xfO

• Dalla fig 1notiamo che il termine 2

10

rimane invariato perciò possiamo ometterlo per

facilitarne la spiegazione, potremo descrivere

l’Oracolo così:

xx xfO )(1

Possiamo dire che l’Oracolo marchia la soluzione con un cambiamento di fase.

Esempio di utilizzo

• Fattorizzazione di m ,dove m è un numero grande risultato del prodotto di 2 numeri primi p e q (come nell’ RSA cryptosystem).

• In un computer classico dividiamo tutti i numeri da 2 a per trovare il più piccolo dei fattori e ricaviamo il più grande da questo risultato.

m

•Un Oracolo potrebbe essere utilizzato per velocizzare questo processo

• Si inizia definendo una funzione

altrimenti 0

divide se 1)(

mxxf

• Si costruisce un circuito classico reversibile (la traduzione di un normale circuito classico

irreversibile)

q) f(x)(x,retituisce e

q)(x, ingresso prende che

• Successivamente potrà essere tradotto in uno quantistico

q f(x)xretituisce e

x ingresso prende che

q

• Il punto chiave è che dobbiamo scrivere un Oracolo che riconosca la soluzione senza conoscere a priori i fattori primi di m.

• Il vantaggio è che possiamo cercare la soluzione da 2 a con richieste all’oracolo invece che classiche iterazioni .m

4/1m2/1m

La Procedura • L’ algoritmo fa uso di un registro a n qubits

e di altri qubits aggiuntivi usati dall’Oracolo

L’algoritmo inizia nello stato n

0

La trasformata di Hadamard è utilizzata per portare

Il computer nel superposition state:

1

0

1 N

x

xN

Grover interation o Grover operator

• Consiste nella continua ripetizione

dei seguenti passi :

1. Applico l’oracolo O

2. Applico la trasformata di Hadamard

3. Applico un shift di fase condizionato :per ogni stato tranne lo si avrà lo shift di -1

4. Applico la trasformata di Hadamard nH

0

nH

Rappresentazione schematica

OI

IHIH

nn

nnnn

002G

:così scitta essere puòGrover di iterazionel' qundi

, oracolol' dopo svolta azionel' è

2002

Spiegazione Geometrica )2(G OI

soluzioni sononon che x talidegli somma la indicax

II

N

M

N

MN

xM

xMN x

I

x

II

scrivere potrà si iniziale stato lo passaggi alcunicon

1 ,

1

tinormalizza stati seguenti i definire possiamo

• Un’iterazione di Grover corrisponde a una rotazione in uno spazio bidimensionale coperto da . Per mostrarlo adotteremo la seguente convenzione:

soluzioni sono che x talidegli somma la indicax

I

Spiegazione Geometrica 1

. da coperto spazio nellok ogniper

rimarrà che di esima-k rotazione la è G

rotazione.un è iriflession due queste di prodotto Il

. vettoresul una ottiene

si 2 similmente ,

vettoresul una attraverso agisce che

di effettol' come vistoessere puòG di effettoL'

k

e

e"riflession"

I)O(

e"riflession"

O

O

2

2

O

G

GOI in su 2 da compiuta rotazione la è destra di figura La

su oracolodall' portata one trafomazila mostra sinistra di figura La

1°riflessione 2° riflessione

23

Spiegazione Geometrica 2

ricerca. di problema del soluzione

una sarà questa, di stato nello risultatoun àprobabilit altacon produrrà

nalicomputazio basi delle neosservazioun' accade questo Quando. a vicino

stato di vettoreil porta iterazione questa di eripetizion contunua Una

.)()(

stato lo portaG di neapplicazio esima-k la che dire possiamo econclusionIn

. ad rispetto seconda la e - a vettoreil porta eriflession prima la perchè

che dire possiamo e )(

ponendo

abbiamo precedenti figure nelle Come

212

212

23

2

23

23

2

22

kkk sincosG

sincosGN

MNcos

sincos

Spiegazione Geometrica 3

G di ntocomportame esattol' è che 2/3

2/3

2/

2/

:scrivendo oconcludiam

:neduplicazio di formule dalle

2/2/

2/2/

2/

2/G

:allora e basi nelle2/

2/ iniziale vettoreil dato

)/2 e 0 tracompreso realeun è dove( G

:matriciale formain anche scritta essere puòG iterazionel' che mostrare Potremmo

)sin(

)cos(

)sin(

)cos(

))sin(sin())cos(cos()cos(

))cos(sin())cos(sin()sin(

))cos(sin())sin(cos(

))sin(sin())cos(cos(

)cos()sin(

)sin()cos(

)sin(

)cos(

)sin(

)cos(

)cos()sin(

)sin()cos(

Performance

xdifettoper

arrotonda che funzione una è )( Dove. a arriviamo 42

angolocon

di rotazioni Ripetendo.in arriva si radianti

rotando perciò ininziale stato Lo

xCI

NM

arcos

CIR

N

Marcos

N

M

N

MN

Performance 1

classico.computer un di )( che invece à,probabilit

altacon soluzione una ottenereper Grover di iterazioni )(

occrrono che dire possiamo R di emaggiorant ultimoquest' a Grazie

.4R

che troviamoeq.1in osostituend e)2(2

che abbiamo , 2 che assumendo e (eq.1) 2R generaleIn

massimo. al

di àprobabilitcon 2 massimo al di angolare erroreun

abbiamo così 2, NMper .Però21 minimo al

àprobabilit lacon soluzione una produce stato dello neosservazioL'

MN

MN

MN

NMsin

NM

NMNM

NM)sin(

L’algoritmo per M=1

qubits primi i misuro .4

2

10

volte42RG applico 2

1021 2 .3

utimoall' e qubits primi ai applico 2

1021 2.

iniziale stato 00 1.

:PROCEDURE

1 àprobabilitcon operazioni 2 :RUNTIME

:OUTPUTS

0 stato nelloqubit (2)

1)(per eccetto 20 ,0)( )(O oracolo Un (1):INPUTS

0

0

12

0

12

0

0

0

nx

x

xOI

HX nHx

x

1n

xfxxfxfqxqx

n

x

nR

n

x

n

n

n

n

n

n

E per M>=N/2 ?

M. di aumentareall' noaumenteran iterazioni

di numero il e piccolopiù è che dire possiamo N a 2N da vache Mper che

capiamo questo da )(

2 ciòper e )(

2)(

che otteniamone,duplicazio di formule le attraverso e

eriflession di figure le osservando e e )(

Ponenedo 22

N

MNMarcsin

N

MNMsin

N

Msin

N

MNcos

E per M>=N/2 ? 1

(eq1.2)/2/ NM)sin(

(eq1.1) /)(2/cos NMN)(

O

2

2

(eq1.3))(

2

N

MNMarcsin

E per M>=N/2 ? 2

)(2

cioè

eq1.3l' otteniamo 1.2 eql' e 1.1 eq l' ultimaquest'in osostituend

22

quindi e 2allora 2se

22

: neduplicazio di formula prima nella osostituend

N

MNMarcsin

)x)cos(x2sin(sin(x)

xα xα

))sin(cos()sin(

E per M>=N/2 ? 2

• Se conoscessimo che M>=N/2 possiamo scegliere un indice a caso tra quelli disponibili e sottoporlo all’oracolo.

• Altrimenti possiamo duplicare il numero degli elementi aggiungendo solo elementi che non sono soluzioni. Di conseguenza meno di metà degli elementi saranno soluzioni.

Esempio dell’Algoritmo

XH

H

H

H

H H

H

H

HOracle HH XX

X X

I00002

o!ordinament eparticolarun di ausiliol' senza

4 di insiemeun in neinformazioun' cercareper iterazione

1 occorre 3 e 1R perciò qubits 2 perciò 4 N e 1 M

)a )b )d )e)c )f

Esempio dell’Algoritmo 1

)0 )1 )2 )3

: seguenti i traoracoloun' esempioper Scegliamo 1

queste. di sola unaper commuteràqubit oraclel' perciò ingressi degli

ioneconfiguraz sola unaper 1successo.con avvenuto

è controllo il se commuta che circuito ogniper bassoin più

quello è chequbit oraclel' e register,index all' noappartengo

che controllo di 2:ingresso diqubit 3 sono ci che Notiamo

f(x)

Esempio dell’Algoritmo 2

quibit 2 primi i sono soluzione la :111)

qubit primi 2 Hadamard di ta trasformala applico :2

1

2

1

2

1)

qubit 2 primi sui fase dishift lo applico :2

1

2

1

2

1)

qubit primi 2 sui Hadamard di ta trasformala applico :2

100)

oracolol' applico :2

100)

Hadamard di ta trasformala applico :12

1

2

1

: iniziale stato seguente il e 3 oracolol' Scegliendo

f

000e

000d

0c

0b

00a)

Esempio di un algoritmo 3

oracolo.all' domande 2.25 mediain compirebbe

classicocomputer un in invece, soluzione alla arrivare prima esposti

oracoli 4 dei uno di oneconsultazi singola una tramitepossibile è

oquantistic circuito questo .Usando raggiunto abbiamo 60 di

rotazione singola unacon perciò , vettoredal30 a trovasi

211011000 iniziale stato lo o,Concludend

Uno sguardo al futuro

• Nonostante l'algoritmo di Grover sia uno strumento estremamente versatile e potente, in pratica la ricerca in un database fisico sarà difficilmente una delle sue applicazioni fondamentali, almeno fino a quando la memoria classica resterà molto più economica di quella quantistica. Per queste ragioni, il campo in cui questo algoritmo da' il meglio di sé è sicuramente quello della ricerca algoritmica, nella quale i dati non sono conservati in memoria, ma sono generati al volo da un programma: pensiamo ad esempio ad un calcolatore quantistico programmato per giocare a scacchi, che utilizzi l'algoritmo di Grover per investigare tutte le possibili mosse a partire da una determinata configurazione della scacchiera.

Uno sguardo al futuro 1

• Gilles Brassard dell'Universita' di Montreal ha recentemente fatto notare, inoltre, un'altra importantissima applicazione dell'algoritmo di Grover e' nel campo della crittanalisi, per attaccare schemi crittografici classici come il Data Encryption Standard (DES) con un approccio a forza bruta. Crackare il DES fondamentalmente richiede una ricerca tra tutte le 2^56 = 7 x 10^16 possibili chiavi. Un computer classico, potendo esaminarne ad esempio 1 milione al secondo, impiegherebbe migliaia di anni a scoprire quella corretta; un computer quantistico che utilizzi l'algoritmo di Grover, invece, ci metterebbe meno di 4 minuti.