-
IQ 2006 - Ph. Jorrand - Grover 1
Algorithme quantique de GroverAccleration quadratique de la
recherche
dans une base de donnes
Philippe Jorrand
CNRS
Laboratoire Leibniz, Grenoble, France
[email protected]
IQ 2006 - Ph. Jorrand - Grover 2
Inverser les amplitudes des a tels que f(a) = 1
Uf|1 H
Vf
f(a) {0,1}a [0,2n-1]
|00..0 HN
Vf
1/!N .. .. 1/!N
- 1/!N
.. .. .. ..
IQ 2006 - Ph. Jorrand - Grover 3
x {0,1}n
(-1)f(x) |x1/!N
1/!2 (|0-|1)
Implmentation de linversion des amplitudes
f : {0,1}n ! {0,1}
Uf
|0 HN
1/!2 (|0-|1)
(N = 2n)
x X0
|x( | 0 " 0 - | 1 " 0) + 1/!N 1/!2( x X1
|x( | 0 " 1 - | 1 " 1) )
x X0
|x( | 0 - | 1) -= 1/!N 1/!2( x X1
|x( | 0 - | 1) )
x {0,1}n
(-1)f(x) |x ( | 0 - | 1) = 1/!N 1/!2 x {0,1}n
(-1)f(x) |x= 1/!N 1/!2(|0-|1)!
IQ 2006 - Ph. Jorrand - Grover 4
Symtrie par rapport la moyenne
SN1/!N
-1/!N
.. .. .. ..
-
IQ 2006 - Ph. Jorrand - Grover 5
Dfinition de la symtrie / la moyenne
......
-1/!N
1/!N
-1/!N
1/!N
......
x =0
(2A-ax) |xN-1
SNx =0
ax |xN-1
A = 1/N axx =0
N-1
x =0
ax |xN-1
|y = ax A - (ax - A)
IQ 2006 - Ph. Jorrand - Grover 6
Implmenter la symtrie / la moyenne
HN = H!n
H =1/!2 1 11 -1JN,1 =
1 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1
SN= HN . JN,1 . HN =
2/N - 1 2/N 2/N 2/N 2/N - 1 2/N 2/N 2/N - 1 2/N 2/N 2/N 2/N -
1
x =0
(2A-ax) |xN-1
x =0
ax |xN-1 SN
HN HNJN,1
IQ 2006 - Ph. Jorrand - Grover 7
Recherche dans un annuaire tlphonique quantique
1,000,000 de noms lists dans un annuaire, en ordre alphabtique :
NOM nnn nn nn
Etant donn un numro xxx xx xx, trouver le NOM unique tel que
:nnn nn nn = xxx xx xx
Informatique classique (c..d. physique classique) :jusqu
1,000,000 dappels !nnn nn nn = xxx xx xx ?!
Informatique quantique (c..d. physique quantique) :seulement
1,000 appels !nnn nn nn = xxx xx xx ?!
IQ 2006 - Ph. Jorrand - Grover 8
Trouver llment qui, parmi N=2 n, satisfait f
f(a) {0,1}a [0,2n-1]
f(a)=1 pour un et un seul a0 [0,2n-1]
Aucune autre information disponible sur f
Problme : trouver ce a0
Calcul classique : au pire, N appels f en moyenne, N/2 appels
f
Calcul quantique : exactement !N appels f, hors daccs du calcul
classique
-
IQ 2006 - Ph. Jorrand - Grover 9
Amplification de lamplitude de |a0
GN=
SNVf
1/!N .. .. .. ..
|a0
f(a) {0,1}a [0,2n-1]
f(a)=1 pour un seul a=a0 [0,2n-1]
|a0
IQ 2006 - Ph. Jorrand - Grover 10
Recherche de a0 : algorithme de Grover
GN GN
Mesurer
GN GN 1-$
.. ..
|a0
1/!N .. ..
|a0
IQ 2006 - Ph. Jorrand - Grover 11
Stop !N fois GN ! Preuve gomtrique
1/!N
|a0
But : arriver aussi prs quepossible de |a0. Pour cela, ilfaut
rpter k fois GN, o :
p/2 q b q + k 2q b p/2 + q
N est grand, donc q est petit :
q # sin q = 1/!N
Donc : k # p/4 !N
Acclration quadratique
q 2q
