Informatique quantique IFT6155

Algorithmes simples

1
 Calcul de fonctions
À chaque fonction f : X → Y on peut associer une opération unitaire

F |xi |yi := |xi |y ⊕ f (x)i

clairement F = F †, F F = I et

F |xi |0i := |xi |f (x)i

Si f est une fonction binaire, on peut aussi définir

F 0 |xi := (−1)f (x) |xi

encore une fois F 0 = F 0† et F 0F 0 = I.

2
 Calcul de fonctions
À partir de F , on peut construire F 0 en utilisant un qubit
supplémentaire dans l’état
1
√ (|0i − |1i)
2

1 1  E
F |xi √ (|0i − |1i) = |xi √ (|f (x)i − f (x) )

2 2
f (x) 1
= |xi (−1) √ (|0i − |1i)
2
1
= (−1)f (x) |xi √ (|0i − |1i)
2
0 1
= F |xi √ (|0i − |1i)
2

3
 Algorithme de Grover
Soit f : {0, 1}2 → {0, 1} avec la promesse qu’il existe x0 tel que
f (x0) = 1 et si x 6= x0 alors f (x) = 0.

Soit l’opération unitaire U définie par:

1
U |00i = (− |00i + |01i + |10i + |11i)
2
1
U |01i = (+ |00i − |01i + |10i + |11i)
2
1
U |10i = (+ |00i + |01i − |10i + |11i)
2
1
U |11i = (+ |00i + |01i + |10i − |11i)
2

4
 Algorithme de Grover
Algorithme de Grover(f)

• |ψi = U †F 0H ⊗2 |00i

• m = Mesure(|ψi)

• retourne m

Classique: 3 requêtes à f .
Quantique: 1 requête à f .

5
Algorithme de Grover analysé

|ψi = U †F 0H ⊗2 |00i
† 0 1
= U F (|00i + |01i + |10i + |11i)
2
1
= U † ((−1)f (00) |00i + (−1)f (01) |01i
2
+(−1)f (10) |10i + (−1)f (11) |11i )
= |x0i

6
 Algorithme de Deutsch
Problème de Deutsch (version de R. Cleve et A. Tapp): Étant donné
f : {0, 1} → {0, 1}, décider si f (0) = f (1).

Algorithme Deutsch(f)

• |ψi = HF 0H |0i

• m = Mesure(|ψi)

• si m = 0 répond CONSTANTE sinon ÉQUILIBRÉE

Classique: deux requêtes à f .

Quantique: une requête à f .
7
 Rappel

H |0i → √1 (|0i + |1i)

2
H |1i → √1 (|0i − |1i)
2

H = H†

8
 Algorithme de Deutsch
Analyse

|ψi = HF 0H |0i
0 1
= HF √ (|0i + |1i)
2
1
= H √ ((−1)f (0) |0i + (−1)f (1) |1i)
2
f (0) 1
= H(−1) √ (|0i + (−1)f (0)(−1)f (1) |1i)
2
1
= H(−1)f (0) √ (|0i + (−1)f (0)⊕f (1) |1i)
2
= (−1)f (0) |f (0) ⊕ f (1)i

On obtient donc f (0) ⊕ f (1) avec certitude. Si f (0) ⊕ f (1) = 0 alors la

fonction est constante, (f (0) = f (1)) sinon la fonction est équilibrée
(f (0) 6= f (1)).
9
 Algorithme de Deutsch-Josza
Problème de Deutsch-Josza: Étant donné f : {0, 1}n → {0, 1} décider si
f est constante (∀x, y, f (x) = f (y)) ou équilibrée (|f −1(0)| = |f −1(1)|).

Algorithme Deutsch-Josza(f)

• |ψi = H ⊗nF 0H ⊗n |0i

• m = Mesure(|ψi)

• si m = 0 répond CONSTANTE sinon ÉQUILIBRÉE

Classique: 2n−1 + 1 requêtes à f .

Quantique: une requête à f .
10
 Transformation de Hadamard

Lemme:
n −1
2X
1
(H = H †) H ⊗n |yi = √ n (−1)x·y |xi
2 x=0
où x · y = x1y1 ⊕ x2y2 ⊕ · · · ⊕ xnyn et en particulier
−1
2X n
1
H ⊗n |0i = √ n |xi
2 x=0

Preuve:
Exercice...

11
Algorithme de Deutsch-Josza
Analyse

|ψi = H ⊗nF 0H ⊗n |0i

−1
2X n
1
= H ⊗nF 0 √ n |ii
2 i=0
−1
2X n
1
= H ⊗n √ n (−1)f (i) |ii
2 i=0
2n −1 2n −1
 
1 X f (i) 1 X i·j |ji
= √ n (−1)  √ (−1)
2 i=0 2n j=0
2n −1 2n −1
 
X X (−1)f (i)+i·j
=   |ji
j=0 i=0 2n

12
 Algorithme de Deutsch-Josza
Analyse
La probabilité d’observer |0i est donnée par
 n 2  n 2
 −1 (−1)f (i)+i·0  −1
2X
2X (−1) f (i) 
 
  = 

 i=0 2 n 


 i=0 2 n 


Si f est constante alors

 n 2  n
2
2 −1 2X −1
 X (−1)f (i)  1
  
 = (−1)f (0)
 
  =1

 i=0 2n 


 i=0 2 n 

Si f est équilibrée alors

 n 2 2
2 −1 f (i)

n−1 n−1
(−1) 2 2
  
 X 
 = −  =0
  

 i=0 2n 
  2n 2n 

13
 Algorithme de Simon
Étant donné f : {0, 1}n → {0, 1}n−1 telle qu’il existe s non nul avec la
propriété que ∀x 6= y : f (x) = f (y) ⇔ x = y ⊕ s, trouver s.

Algorithme Simon(f)
• S = {}
• tant que |S| < n − 1
• |ψi = (H ⊗n ⊗ I2n−1 )F (H ⊗n ⊗ I2n−1 ) |0i |0i
• (m, y) = Mesure(|ψi)
• si m est indépendant de S alors S ← S ∪ {m}
• fin du tant que
• déduire s de S.

Classique: Ω(2(1/2−)n) requêtes à f même avec probabilité de succès

constante.
Quantique: Espérance de O(n) requêtes à f .
14
 Algorithme de Simon: analyse
Soit X tel que |X| = 2(n−1) et X ∪ (s ⊕ X) = {0, 1}n.
|ψi = (H ⊗n ⊗ I2n−1 )F (H ⊗n ⊗ I2n ) |0i |0i
 
⊗n
X 1
= (H ⊗ I2n−1 )F  √ n |xi |0i
x∈{0,1}n
2
 
⊗n
X 1
= (H ⊗ I2n−1 )  √ n |xi |f (x)i
x∈{0,1}n
2
 
X 1  X 1
= √ n √ n (−1)x·y |yi |f (x)i
x∈{0,1}n
2 y∈{0,1}n
2
X (−1)x·y
= n
|yi |f (x)i
2
x,y∈{0,1}
n

X (−1)x·y (−1)(x⊕s)·y
= n
|yi |f (x)i + n
|yi |f (x ⊕ s)i
2 2
x∈X,y∈{0,1} n

X (−1)x·y + (−1)(x⊕s)·y
= n
|yi |f (x)i
2
x∈X,y∈{0,1} n

15
Algorithme de Simon: analyse (suite)

X (−1)x·y + (−1)(x⊕s)·y
|ψi = n
|yi |f (x)i
x∈X,y∈{0,1}n
2

Si s · y = 0 alors
x · y = x · y + s · y = (x ⊕ s) · y
d’où l’amplitude de |yi |f (x)i = 2−n+1.

Si par contre s · y = 1 alors

x · y = x · y + s · y + 1 = (x ⊕ s) · y + 1
d’où l’amplitude de |yi |f (x)i est 0.

16
Algorithme de Simon: analyse (suite)

En observant le premier registre, on obtient y uniformément distribué

et tel que y · s = 0.

Posons s = snsn−1 · · · s1. Une fois que |S| = n − 1 nous avons obtenu
n − 1 équations linéaires avec comme variables les si. Le système
d’équations possède deux solutions, dont l’une est la solution triviale
s = 0. Nous avons donc déterminé s.

17
Algorithme de Simon: analyse (suite)
Analysons maintenant le nombre d’essais nécessaires pour obtenir
n − 1 équations linéairement indépendantes.

À chaque itération, tous les vecteurs x tels que x · s = 0 sont

équiprobables. Il en existe exactement 2n−1.

Si |S| = k alors il existe 2k vecteurs linéairement dépendants de S et

donc 2n−1 − 2k vecteurs linéairement indépendants.

Le cas critique (probabilité la plus faible) advient quand |S| = n − 1,

auquel cas exactement la moitié des vecteurs sont acceptables.

À chaque itération, la probabilité de succès est donc au moins 1/2, ce

qui nous donne un nombre d’itérations espéré dans O(n).

18
Mesure partielle

Pour tout état |ψi ∈ HABC on peut mesurer le sous-espace B.

Pour un sous-espace B de dimension d et un état
Pd−1
|ψi = i=0 αi |aii |ii |cii on obtient le résultat classique i avec
probabilité |αi|2 et l’état devient |aii |ii |cii.

19
Exemple 1:
Si on mesure tout un registre dans l’état |ψi = i αi |ii on obtiendra
P

comme résultat |ii avec probabilité |αi|2.

Exemple 2:
Soit l’état |ψi = √1 (|000i + |110i + |111i).
3 √
On a que |ψi = √ |0i |00i + √2 |1i ( √1 (|10i + |11i)).
1
3 3 2
Si on mesure le premier qubit on obtiendra |0i avec probabilité
 1 2
 
 √  = 1 et l’état devient |000i. On obtient |1i avec probabilité
 3 3
 √ 2
 2
 √  = 2 pour se retrouver dans l’état |1i ( √1 (|10i + |11i)).
 3 3 2

Exemple 3:
De façon générale, si on mesure le sous-espace HB d’un registre
|ψi = ijk αijk |ii |ji |ki ∈ HABC on obtiendra |ji avec probabilité
P

2
ik |αijk | .
P

20
Algorithme de Simon: analyse V2
 
⊗n ⊗n ⊗n
X 1
|ψi = (H ⊗ I2n−1 )F (H ⊗ I2n ) |0i |0i = (H ⊗ I2n−1 )F  √ n |xi |0i
x∈{0,1}n
2
 
⊗n
X 1
= (H ⊗ I2n−1 ) √ n |xi |f (x)i
x∈{0,1}n
2
!
X (|xi + |x ⊕ si)
1
= (H ⊗n ⊗ I2n−1 ) √ √ |f (x)i
2 n−1 2
 x∈X 
|xi + |x ⊕ si
= (H ⊗n ⊗ I2n−1 ) √ |f (x)i M ESU RE
2
P (−1)x·y P (−1)(x⊕s)·y
√ n |yi + √ n |yi
y 2 y 2
= √
2
X (−1)x·y + (−1)(x⊕s)·y X (−1)x·y + (−1)(x·y)⊕(s·y)
= √ n |yi = √ n |yi
y
2 + 1 y
2 + 1

21
 Algorithme de Simon: analyse V2
X (−1)x·y + (−1)(x·y)⊕(s·y) X (−1)x·y (1 + (−1)s·y )
√ n |yi = √ n |yi
y 2 +1 y 2 +1

p
Si s · y = 0 alors l’amplitude de |yi est 2−n+1.

Si par contre si s · y = 1 alors l’amplitude de |yi est 0.

22