Quantum Search Algorithms
Introduzione agli algoritmi di
ricerca quantistici
Perché usare questi algoritmi?
• Un algoritmo di ricerca su di un computer
classico impiega O(N) ha trovare la
soluzione desiderata (es. la minima tra N strade di una città).
• Un algoritmo di ricerca quantistic o
o algoritmo di Grover permette di avere
complessit à per un problema analogo al precedente di O( N )
Formalizziamo il problema
Supponiamo di cercare in uno spazio di N elementi
(con indici da 0 a N - 1) , l’ indirizzo potrà essere
memorizzat o su n bits dove N  2 n.
Questa ricerca potrà portare M soluzioni dove 1  M  N
Una particolar e istanza del problema può essere rappresent ata
da una funzione che ha come dominio un' intero x tale che
1  x  N - 1 (cioè l' indirizzo desiderato )
0 se x non è la soluzione
f x   
1 altrimenti
Cos’è un Oracolo?
Un Oracolo è un’ operatore unitario O (cioè O O†  I) definito
dall' azione sulle seguenti basi computazio nali :
O
x q 

x q  f x 
 denota l' addizione modulo 2
q è chiamato oracle qubit e commuta se f x   1 altrimenti no
x è chiamato index register
• Negli algoritmi quantistici si usa applicare
all’Oracolo l’oracle qubit nello stato:  0  1 
2
• Se x dovesse essere la soluzione
1 e 0 vengono scambiati x
1
 0
2
 x 0
1
2
• Di conseguenza l’Oracolo si comporterà nel
seguente modo
x
0
1
2
  1
O
f ( x)
x
0
1
2

fig 1

• Dalla fig 1notiamo che il termine  0  1 
2
rimane invariato perciò possiamo ometterlo per
facilitarne la spiegazione, potremo descrivere
l’Oracolo così:
x 
 1
O
f ( x)
x
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 m per trovare il più piccolo dei fattori e
ricaviamo il più grande da questo risultato.
•Un Oracolo potrebbe essere utilizzato
per velocizzare questo processo
• Si inizia definendo una funzione
1 se x divide m
f ( x)  
0 altrimenti
• Si costruisce un circuito classico reversibile (la
traduzione di un normale circuito classico
irreversibile) che prende ingresso (x, q)
e retituisce (x, f(x)  q)
• Successivamente potrà essere tradotto in uno
quantistico che prende ingresso x q
e retituisce x f(x)  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
1/ 2
1/ 4
m
m
soluzione da 2 a
con
richieste
all’oracolo invece che m classiche iterazioni .
La Procedura
• L’ algoritmo fa uso di un registro a n qubits
e di altri qubits aggiuntivi usati dall’Oracolo
n
0
L’algoritmo inizia nello stato
La trasformata di Hadamard è utilizzata per portare
Il computer nel superposition state:
1
 
N
N 1

x 0
x
Grover interation o Grover operator
•
1.
2.
3.
4.
Consiste nella continua ripetizione
dei seguenti passi :
Applico l’oracolo O
n
Applico la trasformata di Hadamard H
Applico un shift di fase condizionato :per
ogni stato tranne lo 0 si avrà lo shift di -1
Applico la trasformata di Hadamard H  n
Rappresentazione schematica
H
n
2 0
n
0
n
 I H
n
 2   I
è l' azione svolta dopo l' oracolo ,
qundi l' iterazione di Grover può essere scitta così :

G 2 0
n
0
n
 I O
Spiegazione Geometrica
•
Un’iterazione di Grover (G  2    I O) corrisponde
a una rotazione in uno spazio bidimensionale
coperto da  . Per mostrarlo adotteremo la
seguente convenzione:

I
indica la somma degli x tali che sono soluzioni
x

II
indica la somma degli x tali che non sono soluzioni
x
possiamo definire i seguenti stati normalizza ti
1
1
II
I
 
x
,


x


N M x
M x
con alcuni passaggi lo stato iniziale si potrà scrivere
 
N M
M
 

N
N
Spiegazione Geometrica 1
L' effetto di G può essere visto come l' effetto di O
che agisce attraverso una " riflession e" sul vettore 
O(    )     , similmente 2    I si
ottiene una " riflession e" sul vettore  .
Il prodotto di queste due riflession i è un rotazione.
G k  è la rotazione k - esima di  che rimarrà
per ogni k nello spazio coperto da  e  .

1°riflessione

2° riflessione
G


3
2


2


2
O


O
La figura di sinistra mostra la trafomazi one portata dall' oracolo su 
La figura di destra è la rotazione compiuta da 2    I su O  in G 
Spiegazione Geometrica 2
Come nelle figure precedenti abbiamo   cos 2   sin 2 
(N  M )
e possiamo dire che G   cos 32   sin 32 
N
perchè la prima riflession e porta il vettore a - 2 e la seconda 32 rispetto ad  .
ponendo cos 2 
In conclusion e possiamo dire che la k - esima applicazio ne di G porta lo stato
G k   (cos 2 k21  )   ( sin 2 k21  )  .
Una contunua ripetizion e di questa iterazione porta il vettore di stato
vicino a  .Quando questo accade un' osservazio ne delle basi computazio nali
produrrà con alta probabilit à un risultato nello stato di  , questa sarà una
soluzione del problema di ricerca.
Spiegazione Geometrica 3
Potremmo mostrare che l' iterazione G può essere scritta anche in forma matriciale :
cos(  )  sin(  )
G
(dove  è un reale compreso tra 0 e /2 )

 sin(  ) cos(  ) 
cos(  / 2 )
dato il vettore iniziale   
 nelle basi  e  allora :
sin(

/
2
)


cos(  / 2 ) cos(  )  sin(  ) cos(  / 2 )cos(  )  sin(  / 2 )sin(  )
 G
  sin(  ) cos(  )   cos(  / 2 )sin(  )  sin(  / 2 )cos(  )
sin(

/
2
)


 

dalle formule di duplicazio ne :
sin(    )  sin(  )cos(  )  sin(  )cos(  )
cos(    )  cos(  )cos(  )  sin(  )sin(  )
concludiam o scrivendo :
cos(  / 2   ) cos( 3 / 2 )
 sin(  / 2   )    sin( 3 / 2 )  che è l' esatto comportame nto di G

 

Performance
Lo stato ininziale  
 M 
N M
M

 
 perciò rotando arcos 

N
N
N





 arcos  M  
 N 


 rotazioni di 
radianti si arriva in  .Ripetendo R  CI 








con angolo

2
per difetto x


4
arriviamo a  .Dove CI ( x) è una funzione che arrotonda
Performance 1
L' osservazio ne dello stato produce una soluzione con la probabilit à
al minimo 1 2 .Però per M  N ,   sin(  )  2 M N così abbiamo
un errore angolare di al massimo  2  M N con probabilit à di M N
al massimo.
In generale R   2  (eq.1) e assumendo che M  N 2 , abbiamo che
 2  sin ( 2)  M N e sostituend o in eq.1 troviamo che
R


N M 4.
Grazie a quest' ultimo maggiorant e di R possiamo dire che occrrono
( N M ) iterazioni di Grover per ottenere una soluzione con alta
probabilit à, invece che ( N M ) di un computer classico.
L’algoritmo per M=1
INPUTS : (1) Un oracolo O x q  x q  f ( x) f ( x)  0,  0  x  2 n eccetto per f ( x0 )  1
(2) n  1 qubit nello stato 0
OUTPUTS : x0
 
RUNTIME :  2 n operazioni con probabilit à 1
PROCEDURE :
1. 0
n
0
stato iniziale
2 n 1
2. 1
2
n

x 0
0 1
x

2


3. 2    I O  1
R
applico H n ai primi n qubits e HX all' utimo
2 n 1
2n

x 0
0 1
 x0 

2


4.  x0
0 1
n
x
 applico G R   2 4 volte
2 



misuro i primi n qubits
E per M>=N/2 ?
(N  M )
M

Ponenedo cos 
e sin 2 
e osservando le figure di riflession e
N
N
e attraverso le formule di duplicazio ne, otteniamo che

2
 M (N  M ) 
M (N  M )
 da questo capiamo
sin ( )  2
e per ciò   arcsin  2


N
N


che per M che va da N 2 a N possiamo dire che  è più piccolo e il numero di
iterazioni aumenteran no all' aumentare di M.

E per M>=N/2 ? 1


M (N  M ) 

(eq1.3)
  arcsin  2

N



sin(  / 2 )  M / N (eq1.2)

2

2
O
cos(  / 2 )  ( N  M ) / N (eq1.1)
E per M>=N/2 ? 2
sostituend o nella prima formula di duplicazio ne    :
sin( 2 )  2cos(  )sin(  )
se 2α  x allora α  x 2 e quindi
sin(x)  2sin( x 2 )cos( x 2 )
sostituend o in quest' ultima l' eq 1.1 e l' eq 1.2 otteniamo l' eq1.3
cioè
 M (N  M ) 

  arcsin  2

N


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
X
H
H
X
H
X
H
X
H
H
Oracle
H
X
H
H
H
a)
H
b)
c)
d)
2 00 00  I
e)
M  1 e N  4 perciò 2 qubits perciò R  1 e    3 occorre 1
iterazione per cercare un' informazio ne in un insieme di 4
senza l' ausilio di un particolar e ordinament o!
f)
Esempio dell’Algoritmo 1
1 Scegliamo per esempio un' oracolo tra i seguenti :
0)
1)
2)
3)
Notiamo che ci sono 3 qubit di ingresso : 2 di controllo che
appartengo no all' index register, e l' oracle qubit che è quello
più in basso per ogni circuito che commuta se il controllo è
avvenuto con successo. f(x)  1 per una sola configuraz ione
degli ingressi perciò l' oracle qubit commuterà per una sola di queste.
Esempio dell’Algoritmo 2
Scegliendo l' oracolo 3 e il seguente stato iniziale :
 0  1  0
a)

2 

0 1
b) 0 0 
2

0 1
c) 0 0 
2

 0  1  0
d )

2


1
1 :
2 

:


:

 1  0  1

2 
2
applico la trasforma ta di Hadamard
applico l' oracolo
applico la trasforma ta di Hadamard sui 2 primi qubit

:

 0  1  0  1  0  1 
e) 


:
2 
2 
2 

f )1 1 1 :
applico lo shift di fase sui primi 2 qubit
applico la trasforma ta di Hadamard 2 primi qubit
la soluzione sono i primi 2 quibit
Esempio di un algoritmo 3
Concludend o, lo stato iniziale   00  10  01  11 2
si trova a 30dal vettore  , perciò con una singola rotazione
di 60 abbiamo raggiunto  .Usando questo circuito quantistic o
è possibile tramite una singola consultazi one di uno dei 4 oracoli
esposti prima arrivare alla soluzione , invece in un computer classico
compirebbe in media 2.25 domande all' oracolo.
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.