Un premier algo-
rithme quantique
Vidéo ■ partie 8. Un premier algorithme quantique
La force de l’informatique quantique est de pouvoir faire des calculs avec des 0 et des 1 en même
temps. Au lieu de deux calculs classiques sur le bit 0, puis sur le bit 1, l’ordinateur quantique effectue
un seul calcul sur un 1-qubit. Encore plus fort : avec un n-qubit, un seul calcul quantique remplace
2n calculs classiques.
La réalité est cependant plus compliquée, car tous les algorithmes de l’informatique classique ne
vont pas miraculeusement être plus rapides grâce à l’informatique quantique. Nous allons voir dans
cette partie des problèmes que l’informatique quantique résout beaucoup mieux que les algorithmes
classiques. Le but final est de comprendre l’algorithme quantique de Shor qui permet la factorisation
rapide des entiers.
Nous commençons par étudier une version simple de l’algorithme de Deutsch–Jozsa afin de nous
familiariser avec les objets, les techniques et les types d’algorithmes que nous découvrirons dans cette
seconde partie du livre.
1. Objectifs
1.1. Motivation
L’algorithme de Deutsch–Jozsa n’est pas très utile ! Il permet de décider si une fonction est constante ou
équilibrée. Cependant cet algorithme est très intéressant car il prouve que l’informatique quantique permet
de faire des calculs plus rapidement qu’avec un ordinateur classique.
L’algorithme complet (avec n variables) sera étudié plus loin dans le chapitre « Algorithme de Deutsch–
Jozsa ». Dans ce chapitre d’introduction, on se contente de présenter l’algorithme pour les fonctions les plus
simples : celles ayant une, puis deux variables.
1.2. Fonction à étudier
On commence par le cas des fonctions d’une seule variable. L’ensemble de départ et d’arrivée est {0, 1}.
Considérons une telle fonction :
f : {0, 1} −→ {0, 1}
Il y a en fait 4 fonctions possibles que l’on sépare en deux catégories :
Fonctions constantes Fonctions équilibrées
0 7→ 0 0 7→ 0
f0 f2
1 7→ 0 1 7→ 1
0 7→ 1 0 7→ 1
f1 f3
1 7→ 1 1 7→ 0
UN PREMIER ALGORITHME QUANTIQUE 2
Problème. On nous donne une fonction f : {0, 1} −→ {0, 1}, comment déterminer si elle est constante ou
équilibrée ?
1.3. Solution classique
La solution classique à ce problème est simple :
• calculer f (0) ;
• calculer f (1) ;
• conclure : si f (0) = f (1) la fonction est constante, sinon elle est équilibrée.
Cet algorithme est très simple, mais il demande deux évaluations de la fonction f (le calcul de f (0) puis
celui de f (1)) et on ne peut pas faire mieux. Si on définit la complexité de cet algorithme par le nombre
d’évaluations de f , alors sa complexité vaut 2.
Nous allons voir un algorithme quantique dont la complexité est 1. Cela ne vous paraît peut-être pas
formidablement mieux, mais dans le cas d’une fonction de n variables alors la complexité classique est
d’ordre 2n alors que l’algorithme quantique reste de complexité 1. L’amélioration est donc exponentielle !
2. Circuit quantique
2.1. Circuit
L’algorithme quantique est fourni par le circuit quantique ci-dessous qui répond au problème à l’aide d’une
seule évaluation de f .
|0〉 H H / sortie
Of
|1〉 H
Le circuit est initialisée, puis utilise des portes de Hadamard H mais aussi un sous-circuit O f , appelé « oracle »
que nous détaillerons après.
Algorithme.
• Entrée. Une fonction f : {0, 1} → {0, 1}.
• Sortie. La sortie est donnée par la mesure sur le premier qubit du circuit. Si la mesure vaut 0, la fonction
est constante ; si la mesure vaut 1, la fonction est équilibrée.
2.2. Oracles
Un oracle est un circuit quantique associé à une fonction f . Voici ce que réalise un oracle pour une fonction
f : {0, 1} → {0, 1}.
x x
/
Of
/
y y⊕ f (x)
où x et y sont des bits classiques 0 ou 1.
L’oracle nous donne l’action de la porte O f sur les qubits de base |0〉 et |1〉.
|x〉 / |x〉
Of
| y〉 / | y ⊕ f (x)〉
Détaillons ce qui se passe sur chaque ligne de l’oracle.
Première ligne. En entrée l’oracle reçoit le bit x et en sortie il renvoie cette même valeur x.
UN PREMIER ALGORITHME QUANTIQUE 3
Seconde ligne. En entrée l’oracle reçoit le bit y mais la sortie dépend des valeurs de x, y et de la fonction f .
Cette sortie est le bit 0 ou 1, donné par la formule :
y ⊕ f (x)
Addition binaire. L’addition « ⊕ » est l’addition binaire sur les bits 0 et 1. Elle est équivalente au « ou
exclusif » :
0⊕0=0 0⊕1=1 1⊕0=1 1⊕1=0
On rappelle que les valeurs x, y et f (x) valent 0 ou 1. Ainsi la sortie y ⊕ f (x) vaut aussi 0 ou 1.
Exemple.
Prenons la fonction f définie par f (0) = 1 et f (1) = 0.
• Pour x = 0, y = 0 alors f (0) = 1 donc y ⊕ f (x) = 0 ⊕ 1 = 1.
• Pour x = 0, y = 1 alors f (0) = 1 donc y ⊕ f (x) = 1 ⊕ 1 = 0.
• Pour x = 1, y = 0 alors f (1) = 0 donc y ⊕ f (x) = 0 ⊕ 0 = 0.
• Pour x = 1, y = 1 alors f (1) = 0 donc y ⊕ f (x) = 1 ⊕ 0 = 1.
x x x x x x x x
0 / 0 0 / 0 1 / 1 1 / 1
Of Of Of Of
0 / 1 1 / 0 0 / 0 1 / 1
y y⊕ f (x) y y⊕ f (x) y y⊕ f (x) y y⊕ f (x)
Fonction de deux variables.
Dans notre situation, l’oracle fournit une fonction de deux variables F : {0, 1}2 → {0, 1}2 définie par :
F (x, y) = x, y ⊕ f (x) .
Exemple.
Reprenons la fonction f définie par f (0) = 1 et f (1) = 0. Alors
F F F F
(0, 0) 7−
→ (0, 1) (0, 1) 7−
→ (0, 0) (1, 0) 7−
→ (1, 0) (1, 1) 7−
→ (1, 1)
Action sur les qubits.
L’oracle associé à f définit alors une fonction sur les 2-qubits. Notons F̃ : C4 → C4 définie sur la base
canonique (|0.0〉 , |0.1〉 , |1.0〉 , |1.1〉) par la fonction F , c’est à dire F̃ (|x. y〉) = |F (x, y)〉, puis étendue par
linéarité à C4 . Si
|ψ〉 = α |0.0〉 + β |0.1〉 + γ |1.0〉 + δ |1.1〉 .
Alors :
F̃ |ψ〉 = α F̃ (|0.0〉) + β F̃ (|0.1〉) + γ F̃ (|1.0〉) + δ F̃ (|1.1〉).
Exemple.
Toujours sur le même exemple, cela donne :
F̃ F̃ F̃ F̃
|0.0〉 7−
→ |0.1〉 |0.1〉 7−
→ |0.0〉 |1.0〉 7−
→ |1.0〉 |1.1〉 7−
→ |1.1〉
Et ainsi :
F̃ |ψ〉 = β |0.0〉 + α |0.1〉 + γ |1.0〉 + δ |1.1〉 .
UN PREMIER ALGORITHME QUANTIQUE 4
2.3. Preuve
|0〉 H H / sortie
Of
|1〉 H
|ψ0 〉 |ψ1 〉 |ψ2 〉 |ψ3 〉
Nous détaillons les calculs en suivant l’évolution des qubits au fil du circuit.
Qubit initial |ψ0 〉.
|ψ0 〉 = |0〉 ⊗ |1〉 = |0.1〉
Qubit |ψ1 〉 obtenu après transformation de Hadamard.
On applique une porte de Hadamard sur la première ligne : H |0〉 = p1 (|0〉 + |1〉), et une autre sur la seconde
2
ligne H |1〉 = p1 (|0〉 − |1〉). Ainsi :
2
1
|ψ1 〉 =
(|0〉 + |1〉)(|0〉 − |1〉)
2
1
= |0.0〉 − |0.1〉 + |1.0〉 − |1.1〉 .
2
1
Pour simplifier l’écriture des calculs dans la suite, on va « oublier » le coefficient 2 et écrire 0.0 au lieu de
|0.0〉, 0.1 au lieu de |0.1〉,. . . Ainsi on note :
|ψ1 〉 ≡ 0.0 − 0.1 + 1.0 − 1.1
Qubit |ψ2 〉 obtenu après l’oracle.
|ψ2 〉 ≡ 0.(0 ⊕ f (0)) − 0.(1 ⊕ f (0)) + 1.(0 ⊕ f (1)) − 1.(1 ⊕ f (1))
En effet, l’oracle envoie x sur x pour la première ligne et y sur y ⊕ f (x) pour la seconde. Attention « ⊕ »
est l’addition binaire et doit être effectuée en priorité. Il ne faut pas la confondre avec l’addition de qubits,
notée « + » : x.( y ⊕ f (x)) n’a rien à voir avec x.( y + f (x)).
On regroupe les termes commençant par le même qubit :
|ψ2 〉 ≡ 0.(0 ⊕ f (0)) − 0.(1 ⊕ f (0)) + 1.(0 ⊕ f (1)) − 1.(1 ⊕ f (1)) .
| {z } | {z }
A B
Calculons le terme A en fonction de f (0) :
si f (0) = 0
0.0 − 0.1
A= donc A = (−1) f (0) (0.0 − 0.1).
−(0.0 − 0.1) si f (0) = 1
On rappelle que (−1)k est juste une façon d’obtenir +1 ou −1 selon la parité de k :
+1 si k = 0 (ou si k est pair)
k
(−1) =
−1 si k = 1 (ou si k est impair)
On calcule de façon similaire B. Ainsi :
|ψ2 〉 ≡ (−1) f (0) (0.0 − 0.1) + (−1) f (1) (1.0 − 1.1).
Qubit |ψ3 〉 obtenu après une porte de Hadamard.
Après l’oracle on applique une porte de Hadamard sur la première ligne. Ainsi :
UN PREMIER ALGORITHME QUANTIQUE 5
|ψ3 〉 ≡ (−1) f (0) ((0 + 1).0 − (0 + 1).1)
+ (−1) f (1) ((0 − 1).0 − (0 − 1).1)
≡ (−1) f (0) (0.0 − 0.1 + 1.0 − 1.1)
+ (−1) f (1) (0.0 − 0.1 − 1.0 + 1.1)
≡ (−1) f (0) + (−1) f (1) 0.0
+ − (−1) f (0) − (−1) f (1) 0.1
+ (−1) f (0) − (−1) f (1) 1.0
+ − (−1) f (0) + (−1) f (1) 1.1
1
Le coefficient que l’on a omis devant tous les qubits est p
2 2
et correspond aux trois portes de Hadamard
(chacune apportant un facteur p1 ) :
2
1
|ψ3 〉 = p (−1) f (0) + (−1) f (1) |0.0〉 +
···
2 2
Discutons maintenant selon la catégorie de f .
Si f est constante. Alors f (0) = f (1), donc
+2
f (0) f (1)
(−1) + (−1) =
ou − 2
et (−1) f (0) − (−1) f (1) = 0.
Ainsi :
|ψ3 〉 = ± p12 |0.0〉 − |0.1〉
donc la mesure sur le premier qubit donne 0 dans tous les cas, car les seuls 2-qubits présents sont |0.0〉 et
|0.1〉.
Si f est équilibrée. Alors f (0) ̸= f (1), donc
(−1) f (0) + (−1) f (1) = 0 et (−1) f (0) − (−1) f (1) = ±2
alors :
|ψ3 〉 = ± p12 |1.0〉 − |1.1〉 .
La mesure sur le premier qubit donne donc 1 dans tous les cas (car les 2-qubits présents sont |1.0〉 et |1.1〉).
Conclusion. Si f est constante la mesure du premier qubit donne 0, si f est équilibrée cette mesure donne
1. Ainsi le circuit répond bien au problème posé et l’oracle associé à f n’a été appelé qu’une seule fois.
2.4. Réalisation des oracles
C’est à celui qui utilise l’algorithme de fournir l’oracle, sorte de boîte noire, utilisée par l’algorithme. Voyons
quel circuit quantique permet de réaliser l’oracle O f pour chacune des quatre possibilités de la fonction f .
Notons au préalable que x s’envoie sur x, donc pour la première ligne quantique il n’y a rien à faire.
Fonction constante égale à 0
0 7→ 0
f0
1 7→ 0
Comme y ⊕ f (x) = y ⊕ 0 = y alors l’oracle envoie y sur y. Il n’y a rien à faire comme circuit quantique.
x / x
y / y
Fonction constante égale à 1
0 →
7 1
f1
1 → 7 1
UN PREMIER ALGORITHME QUANTIQUE 6
Comme y ⊕ f (x) = y ⊕ 1 = N OT ( y) alors l’oracle envoie y sur N OT ( y), que l’on peut réaliser par une
porte X .
x / x
y X / y
Fonction équilibrée identité
0 → 7 0
f2
1 → 7 1
Alors f2 (x) = x et y ⊕ f (x) = y ⊕ x, c’est donc y si x = 0 et N OT ( y) si x = 1. C’est exactement l’action
d’une porte C N OT :
x • / x
y / y⊕x
Fonction équilibrée f3
0 →
7 1
f3
1 → 7 0
À vous de chercher en exercice un circuit qui réalise cet oracle en vous aidant des deux circuits précédents.
3. Cas de deux variables
3.1. Problème
On considère maintenant une fonction de deux variables :
f : {0, 1}2 −→ {0, 1}
(x, y) 7−→ f (x, y)
On ne s’intéresse qu’à deux catégories de fonctions.
Fonctions constantes. Il y a en a deux :
• f est constante égale à 0 : f (x, y) = 0 ∀x, y ∈ {0, 1},
• f est constante égale à 1 : f (x, y) = 1 ∀x, y ∈ {0, 1}.
Fonctions équilibrées. Pour ces fonctions, il y a autant de valeurs (x, y) avec f (x, y) = 0 que de valeurs
avec f (x, y) = 1. Il y a 6 fonctions possibles. Voici un exemple :
f f f f
(0, 0) 7−
→1 (0, 1) 7−
→0 (1, 0) 7−
→0 (1, 1) 7−
→1
Attention ! Il existe des fonctions qui ne sont ni constantes, ni équilibrées. Par exemple, la fonction qui vaut
0 partout, sauf en (1, 1) ( f (1, 1) = 1).
Problème. On nous donne une fonction f : {0, 1}2 −→ {0, 1} qui a la propriété d’être soit constante, soit
équilibrée, mais on ne nous dit pas à quelle catégorie elle appartient. Comment déterminer cette catégorie
constante ou équilibrée ?
La solution classique est de calculer plusieurs valeurs. Parfois calculer deux valeurs suffit, par exemple si
f (0, 0) ̸= f (0, 1) alors la fonction n’est pas constante, elle est donc équilibrée. Mais si f (0, 0) = f (0, 1) alors
il faut calculer une troisième valeur f (1, 0) pour pouvoir conclure. La complexité de l’algorithme classique
est de 3 évaluations (on retient toujours le pire cas).
UN PREMIER ALGORITHME QUANTIQUE 7
3.2. Circuit solution
|0〉 H H /
sortie
|0〉 H Of H /
|1〉 H
Encore une fois, le circuit fait intervenir des portes de Hadamard et un oracle O f qui dépend de la fonction
f dont le circuit quantique est fourni par celui qui pose le problème. Pour nous, c’est une boîte noire :
x x
/
y y
Of /
z z⊕ f (x, y)
/
où x, y, z sont des bits classiques 0 ou 1. La sortie de la troisième ligne est z ⊕ f (x, y).
Noter que la mesure se fait sur les deux premières lignes quantiques seulement. La réponse au problème est
donnée par cette mesure :
• si la mesure est 0.0 alors la fonction est constante,
• sinon la fonction est équilibrée.
On rappelle que la fonction f doit par hypothèse être dans l’une des deux catégories ci-dessus.
Le circuit quantique n’effectue qu’une seule évaluation de f (plus précisément qu’un seul appel au circuit
de l’oracle) et donc la solution proposée est de complexité 1. Cette évaluation correspond à
f p12 (|0〉 + |1〉), p12 (|0〉 + |1〉) ,
qui est une façon d’évaluer f sur les quatre qubits de base |0.0〉, |0.1〉, |1.0〉 et |1.1〉 simultanément.
3.3. Calcul et preuve
Les calculs et la preuve peuvent être omis lors d’une première lecture, d’une part ils sont similaires à ceux
pour une variable (mais un peu plus compliqués) et d’autre part les calculs seront faits dans le cas général
d’une fonction de n variables dans le chapitre « Algorithme de Deutsch–Jozsa ».
|0〉 H H /
|0〉 H Of H /
|1〉 H
|ψ0 〉 |ψ1 〉 |ψ2 〉 |ψ3 〉
Qubit initial |ψ0 〉.
|ψ0 〉 = |0〉 ⊗ |0〉 ⊗ |1〉 = |0.0.1〉
Qubit |ψ1 〉. Pour simplifier l’écriture des calculs on « oublie » le coefficient constant commun à tous les
UN PREMIER ALGORITHME QUANTIQUE 8
qubits.
|ψ1 〉 ≡ (|0〉 + |1〉)(|0〉 + |1〉)(|0〉 − |1〉)
≡ |0.0.0〉 − |0.0.1〉
+ |0.1.0〉 − |0.1.1〉
+ |1.0.0〉 − |1.0.1〉
+ |1.1.0〉 − |1.1.1〉
X
≡ |x. y.0〉 − |x. y.1〉
x, y∈{0,1}
Qubit |ψ2 〉. On applique l’oracle et on va remarquer que
|x. y.(0 ⊕ f (x, y))〉 − |x. y.(1 ⊕ f (x, y))〉 = (−1) f (x, y) (|x. y.0〉 − |x. y.1〉).
Ainsi
X
|ψ2 〉 ≡ |x. y.(0 ⊕ f (x, y))〉 − |x. y.(1 ⊕ f (x, y))〉
x, y∈{0,1}
X
≡ (−1) f (x, y) (|x. y.0〉 − |x. y.1〉)
x, y∈{0,1}
X
≡ (−1) f (x, y) |x. y〉 |0 − 1〉
x, y∈{0,1}
Qubit |ψ3 〉.
X
|ψ3 〉 ≡ (−1) f (x, y) |H(x).H( y)〉 |0 − 1〉
x, y∈{0,1}
≡ (−1) f (0,0) |0 + 1〉 |0 + 1〉 |0 − 1〉
+ (−1) f (0,1) |0 + 1〉 |0 − 1〉 |0 − 1〉
+ (−1) f (1,0) |0 − 1〉 |0 + 1〉 |0 − 1〉
+ (−1) f (1,1) |0 − 1〉 |0 − 1〉 |0 − 1〉
Le troisième qubit est toujours |0 − 1〉. On ne va pas expliciter tous les termes mais seulement le coefficient
devant le qubit |0.0.(0 − 1)〉. On en profite pour remettre les coefficients oubliés :
1 ¶
|ψ3 〉 = (−1) f (0,0) + (−1) f (0,1) + (−1) f (1,0) + (−1) f (1,1) |0.0〉 p12 (0 − 1)
+ ···
|4 {z }
α
Conclusion.
Si f est constante alors α = ±1 (ce qui fait qu’il n’y a pas d’autres qubits) et
¶
|ψ3 〉 = ± |0.0〉 p12 (0 − 1) .
Ainsi toute mesure sur les deux premiers qubits donne 0.0.
Si f est équilibrée alors il y a autant de valeurs en lesquelles f vaut 0 que de valeurs en lesquelles f vaut 1,
donc
1
α = (−1) f (0,0) + (−1) f (0,1) + (−1) f (1,0) + (−1) f (1,1) = 0.
4
Ainsi |ψ3 〉 n’a pas de qubits commençant par 0.0. Donc aucune mesure sur les deux premiers qubits ne peut
donner 0.0.
Nous avons donc bien résolu notre problème : si la mesure des deux premiers qubits donne 0.0 alors f est
constante, sinon f est équilibrée.