Aller au contenu principal

L'algorithme de Simon

L'algorithme de Simon est un algorithme de requête quantique qui résout un problème connu sous le nom de problème de Simon. C'est un problème avec promesse, dont la saveur est similaire aux problèmes de Deutsch-Jozsa et de Bernstein-Vazirani, mais dont les spécificités sont différentes.

L'algorithme de Simon est remarquable car il offre un avantage exponentiel du quantique sur le classique (y compris les algorithmes probabilistes), et la technique qu'il utilise a inspiré à Peter Shor la découverte d'un algorithme quantique efficace pour la factorisation des entiers.

Le problème de Simon​

La fonction d'entrée du problème de Simon prend la forme

f:Σn→Σmf:\Sigma^n \rightarrow \Sigma^m

pour des entiers positifs nn et m.m. On pourrait se restreindre au cas m=nm = n par souci de simplicité, mais cette hypothèse n'apporte pas grand-chose — l'algorithme de Simon et son analyse sont essentiellement les mêmes dans les deux cas.

Le problème de Simon

Entrée : une fonction f:Σn→Σmf:\Sigma^n \rightarrow \Sigma^m
Promesse : il existe une chaîne s∈Σns\in\Sigma^n telle que [f(x)=f(y)]⇔[(x=y)∨(x⊕s=y)][f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)] pour tout x,y∈Σnx,y\in\Sigma^n
Sortie : la chaîne ss

Nous allons décortiquer cette promesse pour mieux comprendre ce qu'elle dit dans un instant, mais précisons d'abord clairement qu'elle exige que ff possède une structure très particulière — la plupart des fonctions ne satisferont donc pas cette promesse. Il convient également de reconnaître que ce problème n'est pas censé avoir d'importance pratique. C'est plutôt un problème quelque peu artificiel, conçu sur mesure pour être facile pour les ordinateurs quantiques et difficile pour les ordinateurs classiques.

Il y a deux cas principaux : le premier est que ss est la chaîne tout-zéro 0n,0^n, et le second est que ss n'est pas la chaîne tout-zéro.

  • Cas 1 : s=0n.s=0^n. Si ss est la chaîne tout-zéro, on peut simplifier la déclaration "si et seulement si" dans la promesse pour qu'elle lise [f(x)=f(y)]⇔[x=y].[f(x) = f(y)] \Leftrightarrow [x = y]. Cela équivaut à dire que ff est une fonction injective.

  • Cas 2 : s≠0n.s\neq 0^n. Si ss n'est pas la chaîne tout-zéro, alors le fait que la promesse soit satisfaite pour cette chaîne implique que ff est deux-à-un, ce qui signifie que pour chaque chaîne de sortie possible de f,f, il existe exactement deux chaînes d'entrée qui amènent ff à produire cette sortie. De plus, ces deux chaînes d'entrée doivent prendre la forme ww et w⊕sw \oplus s pour une certaine chaîne w.w.

Il est important de reconnaître qu'il ne peut exister qu'une seule chaîne ss valide si la promesse est satisfaite, il y a donc toujours une réponse correcte unique pour les fonctions qui satisfont la promesse.

Voici un exemple de fonction de la forme f:Σ3→Σ5f:\Sigma^3 \rightarrow \Sigma^5 qui satisfait la promesse pour la chaîne s=011.s = 011.

f(000)=10011f(001)=00101f(010)=00101f(011)=10011f(100)=11010f(101)=00001f(110)=00001f(111)=11010\begin{aligned} f(000) & = 10011 \\ f(001) & = 00101 \\ f(010) & = 00101 \\ f(011) & = 10011 \\ f(100) & = 11010 \\ f(101) & = 00001 \\ f(110) & = 00001 \\ f(111) & = 11010 \end{aligned}

Il y a 88 chaînes d'entrée différentes et 44 chaînes de sortie différentes, chacune apparaissant deux fois — c'est donc bien une fonction deux-à-un. De plus, pour deux chaînes d'entrée différentes qui produisent la même chaîne de sortie, on constate que le XOR bit à bit de ces deux chaînes d'entrée est égal à 011,011, ce qui revient à dire que l'une d'elles est égale à l'autre XORée avec s.s.

Remarque : la seule chose qui compte dans les chaînes de sortie, c'est si elles sont identiques ou différentes pour différents choix de chaînes d'entrée. Par exemple, dans l'exemple ci-dessus, quatre chaînes (10011,(10011, 00101,00101, 00001,00001, et 11010)11010) apparaissent comme sorties de f.f. On pourrait remplacer ces quatre chaînes par d'autres chaînes, du moment qu'elles sont toutes distinctes, et la solution correcte s=011s = 011 ne changerait pas.

Description de l'algorithme​

Voici un schéma de circuit quantique représentant l'algorithme de Simon.

L'algorithme de Simon

Pour être précis, il y a nn qubits en haut sur lesquels agissent les portes Hadamard et mm qubits en bas qui entrent directement dans la porte de requête. Cela ressemble beaucoup aux algorithmes déjà vus dans cette leçon, mais cette fois il n'y a pas de retour de phase (phase kickback) ; les mm qubits du bas entrent tous dans la porte de requête dans l'état ∣0⟩.\vert 0\rangle.

Pour résoudre le problème de Simon à l'aide de ce circuit, il faudra en réalité effectuer plusieurs exécutions indépendantes, suivies d'une étape de post-traitement classique, qui sera décrite plus loin après l'analyse du comportement du circuit.

Analyse​

L'analyse de l'algorithme de Simon commence de manière similaire à celle de l'algorithme de Deutsch-Jozsa. Après que la première couche de portes Hadamard est appliquée aux nn qubits du haut, l'état devient

12n∑x∈Σn∣0m⟩∣x⟩.\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.

Lorsque UfU_f est appliqué, la sortie de la fonction ff est XORée sur l'état tout-zéro des mm qubits du bas, de sorte que l'état devient

12n∑x∈Σn∣f(x)⟩∣x⟩.\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert f(x) \rangle \vert x\rangle.

Lorsque la deuxième couche de portes Hadamard est appliquée, on obtient l'état suivant en utilisant la même formule que précédemment pour l'action d'une couche de portes Hadamard.

12n∑x∈Σn∑y∈Σn(−1)x⋅y∣f(x)⟩∣y⟩\frac{1}{2^n} \sum_{x\in\Sigma^n} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \vert y\rangle

À ce stade, l'analyse diverge de celles des algorithmes précédents de cette leçon.

On s'intéresse à la probabilité que les mesures donnent chaque chaîne possible y∈Σn.y\in\Sigma^n. En appliquant les règles d'analyse des mesures décrites dans la leçon Systèmes multiples du cours Notions de base de l'information quantique, on trouve que la probabilité p(y)p(y) d'obtenir la chaîne yy est égale à

p(y)=∥12n∑x∈Σn(−1)x⋅y∣f(x)⟩∥2.p(y) = \left\|\frac{1}{2^n} \sum_{x\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \right\|^2.

Pour mieux appréhender ces probabilités, nous allons avoir besoin d'un peu plus de notation et de terminologie. Tout d'abord, l'image de la fonction ff est l'ensemble contenant toutes ses chaînes de sortie.

range⁡(f)={f(x):x∈Σn}\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}

Ensuite, pour chaque chaîne z∈range⁡(f),z\in\operatorname{range}(f), on peut exprimer l'ensemble de toutes les chaînes d'entrée qui amènent la fonction à s'évaluer à cette chaîne de sortie zz sous la forme f−1({z}).f^{-1}(\{z\}).

f−1({z})={x∈Σn:f(x)=z}f^{-1}(\{z\}) = \{ x\in\Sigma^n : f(x) = z \}

L'ensemble f−1({z})f^{-1}(\{z\}) est connu sous le nom d'image réciproque de {z}\{z\} par f.f. On peut définir l'image réciproque par ff de n'importe quel ensemble à la place de {z}\{z\} de manière analogue — c'est l'ensemble de tous les éléments que ff envoie sur cet ensemble. (Cette notation ne doit pas être confondue avec l'inverse de la fonction f,f, qui peut ne pas exister. Le fait que l'argument du membre gauche soit l'ensemble {z}\{z\} plutôt que l'élément zz est l'indice qui permet d'éviter cette confusion.)

En utilisant cette notation, on peut décomposer la somme dans notre expression des probabilités ci-dessus pour obtenir

p(y)=∥12n∑z∈range⁡(f)(∑x∈f−1({z})(−1)x⋅y)∣z⟩∥2.p(y) = \left\| \frac{1}{2^n} \sum_{z\in\operatorname{range}(f)} \Biggl(\sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y}\Biggr) \vert z \rangle \right\|^2.

Chaque chaîne x∈Σnx\in\Sigma^n est représentée exactement une fois par les deux sommations — on répartit essentiellement ces chaînes dans des groupes séparés selon la chaîne de sortie z=f(x)z = f(x) qu'elles produisent lorsqu'on évalue la fonction f,f, puis on somme séparément sur tous les groupes.

On peut maintenant calculer le carré de la norme euclidienne pour obtenir

p(y)=122n∑z∈range⁡(f)∣∑x∈f−1({z})(−1)x⋅y∣2.p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2.

Pour simplifier davantage ces probabilités, examinons la valeur

∣∑x∈f−1({z})(−1)x⋅y∣2(1)\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}

pour un choix arbitraire de z∈range⁡(f).z\in\operatorname{range}(f).

S'il s'avère que s=0n,s = 0^n, alors ff est une fonction injective et il y a toujours un seul élément x∈f−1({z}),x\in f^{-1}(\{z\}), pour tout z∈range⁡(f).z\in\operatorname{range}(f). La valeur de l'expression (1)(1) est 11 dans ce cas.

Si, en revanche, s≠0n,s\neq 0^n, alors il y a exactement deux chaînes dans l'ensemble f−1({z}).f^{-1}(\{z\}). Pour être précis, si on choisit w∈f−1({z})w\in f^{-1}(\{z\}) comme étant l'une quelconque de ces deux chaînes, alors l'autre chaîne doit être w⊕sw \oplus s d'après la promesse du problème de Simon. En utilisant cette observation, on peut simplifier (1)(1) comme suit.

∣∑x∈f−1({z})(−1)x⋅y∣2=∣(−1)w⋅y+(−1)(w⊕s)⋅y∣2=∣(−1)w⋅y(1+(−1)s⋅y)∣2=∣1+(−1)y⋅s∣2={4y⋅s=00y⋅s=1\begin{aligned} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 & = \Bigl\vert (-1)^{w\cdot y} + (-1)^{(w\oplus s)\cdot y} \Bigr\vert^2 \\ & = \Bigl\vert (-1)^{w\cdot y} \Bigl(1 + (-1)^{s\cdot y}\Bigr) \Bigr\vert^2 \\ & = \Bigl\vert 1 + (-1)^{y\cdot s} \Bigr\vert^2 \\ & = \begin{cases} 4 & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases} \end{aligned}

Ainsi, il s'avère que la valeur (1)(1) est indépendante du choix particulier de z∈range⁡(f)z\in\operatorname{range}(f) dans les deux cas.

On peut maintenant terminer l'analyse en examinant séparément les deux mêmes cas qu'auparavant.

  • Cas 1 : s=0n.s = 0^n. Dans ce cas, la fonction ff est injective, il y a donc 2n2^n chaînes z∈range⁡(f),z\in\operatorname{range}(f), et on obtient

    p(y)=122n⋅2n=12n.p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.

    En d'autres termes, les mesures donnent une chaîne y∈Σny\in\Sigma^n choisie uniformément au hasard.

  • Cas 2 : s≠0n.s \neq 0^n. Dans ce cas, ff est deux-à-un, il y a donc 2n−12^{n-1} éléments dans range⁡(f).\operatorname{range}(f). En utilisant la formule ci-dessus, on conclut que la probabilité de mesurer chaque y∈Σny\in\Sigma^n est

    p(y)=122n∑z∈range⁡(f)∣∑x∈f−1({z})(−1)x⋅y∣2={12n−1y⋅s=00y⋅s=1p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \Biggl\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \Biggr\vert^2 = \begin{cases} \frac{1}{2^{n-1}} & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases}

    En d'autres termes, on obtient une chaîne choisie uniformément au hasard dans l'ensemble {y∈Σn:y⋅s=0},\{y\in\Sigma^n : y \cdot s = 0\}, qui contient 2n−12^{n-1} chaînes. (Comme s≠0n,s\neq 0^n, exactement la moitié des chaînes binaires de longueur nn ont un produit scalaire binaire de 11 avec ss et l'autre moitié a un produit scalaire binaire de 00 avec s,s, comme on l'a déjà observé dans l'analyse de l'algorithme de Deutsch-Jozsa pour le problème de Bernstein-Vazirani.)

Post-traitement classique​

On sait maintenant quelles sont les probabilités des résultats de mesure possibles lorsqu'on exécute le circuit quantique de l'algorithme de Simon. Est-ce suffisant pour déterminer ss ?

La réponse est oui, à condition d'être prêt à répéter le processus plusieurs fois et d'accepter qu'il puisse échouer avec une certaine probabilité, que l'on peut rendre très faible en exécutant le circuit suffisamment de fois. L'idée essentielle est que chaque exécution du circuit nous fournit une preuve statistique concernant s,s, et on peut utiliser cette preuve pour trouver ss avec une très haute probabilité si on exécute le circuit suffisamment de fois.

Supposons que l'on exécute le circuit indépendamment kk fois, avec k=n+10.k = n + 10. Ce nombre d'itérations n'a rien de particulier — on pourrait choisir kk plus grand (ou plus petit) selon la probabilité d'échec qu'on est prêt à tolérer, comme on va le voir. Choisir k=n+10k = n + 10 garantit qu'on aura plus de 99,999{,}9% de chances de retrouver s.s.

En exécutant le circuit kk fois, on obtient des chaînes y1,...,yk∈Σn.y^1,...,y^{k} \in \Sigma^n. Pour être clair, les exposants ici font partie du nom de ces chaînes et ne sont pas des puissances ou des indices sur leurs bits, donc on a

y1=yn−11⋯y01y2=yn−12⋯y02    ⋮yk=yn−1k⋯y0k\begin{aligned} y^1 & = y^1_{n-1} \cdots y^1_{0}\\[1mm] y^2 & = y^2_{n-1} \cdots y^2_{0}\\[1mm] & \;\; \vdots\\[1mm] y^{k} & = y^{k}_{n-1} \cdots y^{k}_{0} \end{aligned}

On forme maintenant une matrice MM ayant kk lignes et nn colonnes en prenant les bits de ces chaînes comme entrées binaires.

M=(yn−11⋯y01yn−12⋯y02⋮⋱⋮yn−1k⋯y0k)M = \begin{pmatrix} y^1_{n-1} & \cdots & y^1_{0}\\[1mm] y^2_{n-1} & \cdots & y^2_{0}\\[1mm] \vdots & \ddots & \vdots \\[1mm] y^{k}_{n-1} & \cdots & y^{k}_{0} \end{pmatrix}

À ce stade, on ne connaît pas ss — notre objectif est de trouver cette chaîne. Mais imaginons un instant que l'on connaisse la chaîne s,s, et qu'on forme un vecteur colonne vv à partir des bits de la chaîne s=sn−1⋯s0s = s_{n-1} \cdots s_0 comme suit.

v=(sn−1⋮s0)v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}

Si on effectue le produit matrice-vecteur MvM v modulo 22 — c'est-à-dire qu'on effectue la multiplication normalement puis qu'on prend le reste des entrées du résultat après division par 22 — on obtient le vecteur tout-zéro.

Mv=(y1⋅sy2⋅s⋮yk⋅s)=(00⋮0)M v = \begin{pmatrix} y^1 \cdot s\\ y^2 \cdot s\\ \vdots\\[1mm] y^{k} \cdot s \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ \vdots\\[1mm] 0 \end{pmatrix}

Autrement dit, traité comme un vecteur colonne vv tel que décrit ci-dessus, la chaîne ss sera toujours un élément du noyau de la matrice M,M, à condition de faire l'arithmétique modulo 2.2. Cela est vrai dans le cas s=0ns = 0^n comme dans le cas s≠0n.s\neq 0^n. Pour être plus précis, le vecteur tout-zéro est toujours dans le noyau de M,M, et il est accompagné du vecteur dont les entrées sont les bits de ss dans le cas où s≠0n.s\neq 0^n.

La question qui reste est de savoir s'il y aura d'autres vecteurs dans le noyau de MM en dehors de ceux correspondant à 0n0^n et s.s. La réponse est que cela devient de moins en moins probable à mesure que kk augmente — et si on choisit k=n+10,k = n + 10, le noyau de MM ne contiendra aucun autre vecteur en plus de ceux correspondant à 0n0^n et ss avec une probabilité supérieure à 99,999{,}9%. Plus généralement, si on remplace k=n+10k = n + 10 par k=n+rk = n + r pour un choix arbitraire d'entier positif r,r, la probabilité que les vecteurs correspondant à 0n0^n et ss soient seuls dans le noyau de MM est au moins 1−2−r.1 - 2^{-r}.

En utilisant l'algèbre linéaire, il est possible de calculer efficacement une description du noyau de MM modulo 2.2. Plus précisément, cela peut être fait en utilisant l'élimination de Gauss, qui fonctionne de la même manière lorsque l'arithmétique est faite modulo 22 qu'avec des nombres réels ou complexes. Tant que les vecteurs correspondant à 0n0^n et ss sont seuls dans le noyau de M,M, ce qui se produit avec une haute probabilité, on peut déduire ss des résultats de ce calcul.

Difficulté classique​

Combien de requêtes un algorithme de requête classique doit-il effectuer pour résoudre le problème de Simon ? La réponse est : beaucoup, en général.

On peut formuler différentes déclarations précises sur la difficulté classique de ce problème, et en voici une. Si on dispose d'un algorithme de requête probabiliste qui effectue moins de 2n/2−1−12^{n/2 - 1} - 1 requêtes — un nombre de requêtes exponentiel en nn — alors cet algorithme échouera à résoudre le problème de Simon avec une probabilité d'au moins 1/2.1/2.

Parfois, prouver des résultats d'impossibilité comme celui-ci peut être très difficile, mais celui-ci n'est pas trop difficile à prouver par une analyse probabiliste élémentaire. Ici, cependant, on se contentera d'examiner brièvement l'intuition de base qui le sous-tend.

On cherche à trouver la chaîne cachée s,s, mais tant qu'on n'interroge pas la fonction sur deux chaînes ayant la même valeur de sortie, on obtiendra très peu d'informations sur s.s. Intuitivement parlant, tout ce qu'on apprendra est que la chaîne cachée ss n'est pas le XOR exclusif de deux chaînes distinctes qu'on a interrogées. Et si on interroge moins de 2n/2−1−12^{n/2 - 1} - 1 chaînes, il restera encore de nombreuses possibilités pour ss qu'on n'aura pas éliminées, car il n'y a pas suffisamment de paires de chaînes pour le faire. Ce n'est pas une preuve formelle, c'est juste l'idée de base.

Ainsi, en résumé, l'algorithme de Simon nous offre un avantage frappant du quantique sur le classique dans le modèle de requête. En particulier, l'algorithme de Simon résout le problème de Simon avec un nombre de requêtes linéaire en le nombre de bits d'entrée nn de notre fonction, tandis que tout algorithme classique, même probabiliste, doit effectuer un nombre de requêtes exponentiel en nn pour résoudre le problème de Simon avec une probabilité de succès raisonnable.