L'algorithme de Grover

Pour ce module Qiskit en classe, les étudiants doivent disposer d'un environnement Python fonctionnel avec les packages suivants installés :

• qiskit v2.1.0 ou plus récent
• qiskit-ibm-runtime v0.40.1 ou plus récent
• qiskit-aer v0.17.0 ou plus récent
• qiskit.visualization
• numpy
• pylatexenc

Pour configurer et installer les packages ci-dessus, consulte le guide Installer Qiskit. Pour exécuter des tâches sur de vrais ordinateurs quantiques, les étudiants devront créer un compte IBM Quantum® en suivant les étapes du guide Configurer ton compte IBM Cloud.

Ce module a été testé et a utilisé 12 secondes de temps QPU. Il s'agit d'une estimation de bonne foi ; ton utilisation réelle peut varier.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Introduction

L'algorithme de Grover est un algorithme quantique fondamental qui aborde le problème de recherche non structurée : étant donné un ensemble de $N$ éléments et un moyen de vérifier si un élément donné est celui qu'on cherche, à quelle vitesse peut-on trouver l'élément désiré ? En informatique classique, si les données ne sont pas triées et qu'il n'y a aucune structure à exploiter, la meilleure approche consiste à vérifier chaque élément un par un, ce qui conduit à une complexité de requêtes en $O(N)$ — en moyenne, tu devras vérifier environ la moitié des éléments avant de trouver la cible.

L'algorithme de Grover, introduit par Lov Grover en 1996, démontre comment un ordinateur quantique peut résoudre ce problème de manière bien plus efficace, en ne nécessitant que $O(\sqrt{N})$ étapes pour trouver l'élément marqué avec une haute probabilité. Cela représente une accélération quadratique par rapport aux méthodes classiques, ce qui est significatif pour les grands ensembles de données.

L'algorithme opère dans le contexte suivant :

• Configuration du problème : Tu disposes d'une fonction $f(x)$ qui renvoie 1 si $x$ est l'élément recherché, et 0 sinon. Cette fonction est souvent appelée un oracle ou une boîte noire, car tu ne peux apprendre des données qu'en interrogeant $f(x)$.
• Utilité du quantique : Alors que les algorithmes classiques pour ce problème nécessitent en moyenne $N/2$ requêtes, l'algorithme de Grover peut trouver la solution en environ $\pi\sqrt{N}/4$ requêtes, ce qui est beaucoup plus rapide pour les grands $N$.
• Comment ça fonctionne (à haut niveau) :
  • L'ordinateur quantique crée d'abord une superposition de tous les états possibles, représentant simultanément tous les éléments possibles.
  • Il applique ensuite de manière répétée une séquence d'opérations quantiques (l'itération de Grover) qui amplifie la probabilité de la bonne réponse et diminue les autres.
  • Après suffisamment d'itérations, la mesure de l'état quantique donne la bonne réponse avec une haute probabilité.

Voici un diagramme très basique de l'algorithme de Grover qui passe sous silence de nombreuses nuances. Pour un diagramme plus détaillé, consulte cet article.

Quelques points à noter sur l'algorithme de Grover :

• Il est optimal pour la recherche non structurée : aucun algorithme quantique ne peut résoudre le problème avec moins de $O(\sqrt{N})$ requêtes.
• Il ne fournit qu'une accélération quadratique, et non exponentielle — contrairement à certains autres algorithmes quantiques (par exemple, l'algorithme de Shor pour la factorisation).
• Il a des implications pratiques, comme l'accélération potentielle des attaques par force brute sur les systèmes cryptographiques, bien que l'accélération ne soit pas suffisante pour briser la plupart des chiffrements modernes à elle seule.

Pour les étudiants de licence familiarisés avec les concepts informatiques de base et les modèles de requêtes, l'algorithme de Grover offre une illustration claire de la façon dont l'informatique quantique peut surpasser les approches classiques pour certains problèmes, même quand l'amélioration n'est « que » quadratique. Il sert également de point d'entrée pour comprendre des algorithmes quantiques plus avancés et le potentiel plus large de l'informatique quantique.

L'amplification d'amplitude est un algorithme quantique généraliste, ou sous-routine, qui peut être utilisé pour obtenir une accélération quadratique sur une poignée d'algorithmes classiques. L'algorithme de Grover a été le premier à démontrer cette accélération sur les problèmes de recherche non structurée. La formulation d'un problème de recherche de Grover nécessite une fonction oracle qui marque un ou plusieurs états de la base computationnelle comme les états que l'on cherche à trouver, et un circuit d'amplification qui augmente l'amplitude des états marqués, supprimant ainsi les états restants.

Ici, nous montrons comment construire des oracles de Grover et utiliser le GroverOperator de la bibliothèque de circuits Qiskit pour configurer facilement une instance de recherche de Grover. La primitive Sampler de runtime permet une exécution transparente des circuits de Grover.

Théorie

Supposons qu'il existe une fonction $f$ qui mappe des chaînes binaires vers une seule variable binaire, ce qui signifie

$$f: \Sigma^n \rightarrow \Sigma$$

Un exemple défini sur $\Sigma^6$ est

$$f(x)= \begin{cases} 1 \qquad \text{si }x=\{010101\}\\ 0 \qquad \text{sinon } \end{cases}$$

Un autre exemple défini sur $\Sigma^{2n}$ est

$$f(x)= \begin{cases} 1 \qquad \text{si nombre égal de 1 et de 0 dans la chaîne}\\ 0 \qquad \text{sinon } \end{cases}$$

Tu as pour tâche de trouver les états quantiques correspondant aux arguments $x$ de $f(x)$ qui sont mappés à 1. En d'autres termes, trouve tous les $\{x_1\}\in \Sigma^n$ tels que $f(x_1)=1$ (ou s'il n'y a pas de solution, indique-le). Nous désignerions les non-solutions comme $x_0$. Bien sûr, nous allons faire cela sur un ordinateur quantique, en utilisant des états quantiques, il est donc utile d'exprimer ces chaînes binaires comme des états :

$$\{|x_1\rangle\} \in |\Sigma^n\rangle$$

En utilisant la notation des états quantiques (notation de Dirac), nous cherchons un ou plusieurs états spéciaux $\{|x_1\rangle\}$ dans un ensemble de $N=2^n$ états possibles, où $n$ est le nombre de qubits, et avec les non-solutions notées $\{|x_0\rangle\}.$

On peut penser à la fonction $f$ comme étant fournie par un oracle : une boîte noire que l'on peut interroger pour déterminer son effet sur un état $|x\rangle.$ En pratique, on connaît souvent la fonction, mais elle peut être très complexe à implémenter, ce qui signifie que réduire le nombre de requêtes ou d'applications de $f$ pourrait être important. Alternativement, on peut imaginer un paradigme dans lequel une personne interroge un oracle contrôlé par une autre personne, de sorte qu'on ne connaît pas la fonction oracle, on ne connaît que son action sur des états particuliers suite à des requêtes.

Il s'agit d'un problème de « recherche non structurée », en ce sens qu'il n'y a rien de particulier dans $f$ qui nous aide dans notre recherche. Les sorties ne sont pas triées et les solutions ne sont pas connues pour se regrouper, etc. Considère les anciens annuaires téléphoniques en papier comme analogie. Cette recherche non structurée ressemblerait à parcourir l'annuaire à la recherche d'un certain numéro, et non à parcourir une liste alphabétique de noms.

Dans le cas où une seule solution est recherchée, classiquement, cela nécessite un nombre de requêtes linéaire en $N$. Tu pourrais clairement trouver une solution dès le premier essai, ou tu pourrais ne trouver aucune solution dans les $N-1$ premiers essais, de sorte que tu doives interroger la $N^{ième}$ entrée pour voir s'il y a une solution. Puisque les fonctions n'ont aucune structure exploitable, tu auras besoin de $N/2$ essais en moyenne. L'algorithme de Grover nécessite un nombre de requêtes ou de calculs de $f$ qui évolue comme $\sqrt{N}.$

Esquisse des circuits dans l'algorithme de Grover

Un traitement mathématique complet de l'algorithme de Grover se trouve, par exemple, dans Fondamentaux des algorithmes quantiques, un cours de John Watrous sur IBM Quantum Learning. Un traitement condensé est fourni dans une annexe à la fin de ce module. Mais pour l'instant, nous ne passerons en revue que la structure globale du circuit quantique qui implémente l'algorithme de Grover.

L'algorithme de Grover peut être décomposé en les étapes suivantes :

• Préparation d'une superposition initiale (application de portes Hadamard à tous les qubits)
• « Marquage » des états cibles avec un retournement de phase
• Une étape de « diffusion » dans laquelle des portes Hadamard et un retournement de phase sont appliqués à tous les qubits.
• Des répétitions possibles des étapes de marquage et de diffusion pour maximiser la probabilité de mesurer l'état cible
• Mesure

Souvent, la porte de marquage $Z_f$ et les couches de diffusion composées de $H,$ $Z_{\text{OR}},$ et $H$ sont collectivement appelées l'« opérateur de Grover ». Dans ce diagramme, une seule répétition de l'opérateur de Grover est affichée.

Les portes Hadamard $H$ sont bien connues et largement utilisées dans l'informatique quantique. La porte Hadamard crée des états de superposition. Plus précisément, elle est définie par

$$H|0\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)\\ H|1\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)$$

Son opération sur tout autre état est définie par linéarité. En particulier, une couche de portes Hadamard nous permet de passer de l'état initial avec tous les qubits en $|0\rangle$ (noté $|0\rangle^{\otimes n}$) à un état où chaque qubit a une certaine probabilité d'être mesuré en $|0\rangle$ ou $|1\rangle$ ; cela nous permet d'explorer l'espace de tous les états possibles différemment de l'informatique classique.

Une propriété corollaire importante de la porte Hadamard est qu'une seconde application peut défaire de tels états de superposition :

$$H\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)=|0\rangle\\ H\frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)=|1\rangle$$

Cela sera important dans un instant.

Vérifie ta compréhension

Lis la question ci-dessous, réfléchis à ta réponse, puis clique sur le triangle pour révéler la solution.

En partant de la définition de la porte Hadamard, démontre qu'une deuxième application de la porte Hadamard défait de tels états de superposition comme affirmé ci-dessus.

Réponse :

Quand on applique X à l'état $|+\rangle$, on obtient la valeur +1 et à l'état $|-\rangle$ on obtient -1, donc si on avait une distribution 50-50, on obtiendrait une valeur d'espérance de 0.

La porte $Z_\text{OR}$ est moins courante, et est définie selon

$$\text{Z}_\text{OR}|x\rangle = \begin{cases} |x\rangle & \text{si } x = 0^n \\ -|x\rangle & \text{si } x \neq 0^n \end{cases} \qquad \forall x \in \Sigma^n$$

Enfin, la porte $Z_f$ est définie par

$$Z_f:|x\rangle \rightarrow (-1)^{f(x)}|x\rangle \qquad \forall x \in \Sigma^n$$

Note que l'effet est que $Z_f$ retourne le signe sur un état cible pour lequel $f(x) = 1$ et laisse les autres états non affectés.

À un niveau très élevé et abstrait, tu peux penser aux étapes du circuit de la façon suivante :

• Première couche Hadamard : met les qubits dans une superposition de tous les états possibles.
• $Z_f$ : marque les états cibles en ajoutant un signe « - » devant. Cela ne change pas immédiatement les probabilités de mesure, mais cela change la façon dont l'état cible se comportera dans les étapes suivantes.
• Une autre couche Hadamard : le signe « - » introduit à l'étape précédente va changer le signe relatif entre certains termes. Puisque les portes Hadamard transforment un mélange d'états computationnels $(|0\rangle+|1\rangle)/\sqrt{2}$ en un état computationnel, $|0\rangle,$ et transforment $(|0\rangle-|1\rangle)/\sqrt{2}$ en $|1\rangle$, cette différence de signe relatif peut maintenant commencer à jouer un rôle dans les états mesurés.
• Une dernière couche de portes Hadamard est appliquée, puis des mesures sont effectuées. Nous verrons plus en détail comment cela fonctionne dans la section suivante.

Exemple

Pour mieux comprendre comment fonctionne l'algorithme de Grover, travaillons à travers un petit exemple à deux qubits. Cela peut être considéré comme facultatif pour ceux qui ne se concentrent pas sur la mécanique quantique et la notation de Dirac. Mais pour ceux qui espèrent travailler substantiellement avec des ordinateurs quantiques, cela est fortement recommandé.

Voici le diagramme du circuit avec les états quantiques étiquetés à divers endroits tout au long. Note qu'avec seulement deux qubits, il n'y a que quatre états possibles qui pourraient être mesurés dans tous les cas : $|00\rangle$, $|01\rangle$, $|10\rangle$, et $|11\rangle$.

Supposons que l'oracle ($Z_f$, inconnu pour nous) marque l'état $|01\rangle$. Nous allons travailler à travers les actions de chaque ensemble de portes quantiques, y compris l'oracle, et voir quelle distribution des états possibles sort au moment de la mesure. Au tout début, nous avons

$$|\psi_0\rangle = |00\rangle$$

En utilisant la définition des portes Hadamard, nous avons

$$|\psi_1\rangle = \frac{1}{2}\left(|0\rangle+|1\rangle\right)\left(|0\rangle+|1\rangle\right)=\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)$$

Maintenant, l'oracle marque l'état cible :

$$|\psi_2\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle+|11\rangle\right)$$

Note que dans cet état, les quatre résultats possibles ont la même probabilité d'être mesurés. Ils ont tous un poids de magnitude $1/2,$ ce qui signifie qu'ils ont chacun une chance $|1/2|^2=1/4$ d'être mesurés. Ainsi, bien que l'état $|01\rangle$ soit marqué par la phase « - », cela n'a pas encore entraîné une probabilité accrue de mesurer cet état. Nous continuons en appliquant la couche suivante de portes Hadamard.

$$\begin{aligned} |\psi_3\rangle = &\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

En combinant les termes semblables, nous trouvons

$$|\psi_3\rangle = \frac{1}{2}\left(|00\rangle+|01\rangle-|10\rangle+|11\rangle\right)$$

Maintenant $Z_{\text{OR}}$ retourne le signe sur tous les états sauf $|00\rangle$ :

$$|\psi_4\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)$$

Et enfin, nous appliquons la dernière couche de portes Hadamard :

$$\begin{aligned} |\psi_5\rangle =&\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Cela vaut la peine de travailler à travers la combinaison de ces termes pour te convaincre que le résultat est bien :

$$|\psi_5\rangle =|01\rangle$$

C'est-à-dire que la probabilité de mesurer $|01\rangle$ est de 100 % (en l'absence de bruit et d'erreurs) et la probabilité de mesurer tout autre état est nulle.

Cet exemple à deux qubits était un cas particulièrement simple ; l'algorithme de Grover ne donnera pas toujours une chance de 100 % de mesurer l'état cible. Il amplifiera plutôt la probabilité de mesurer l'état cible. De plus, l'opérateur de Grover peut devoir être répété plus d'une fois.

Dans la section suivante, nous allons mettre cet algorithme en pratique en utilisant de vrais ordinateurs quantiques IBM®.

La représentation géométrique

L'exemple à deux qubits ci-dessus a montré comment l'algèbre fonctionne pour un petit cas, mais il existe une manière bien plus intuitive de comprendre l'algorithme de Grover : comme une suite de réflexions géométriques dans un plan à deux dimensions. Nous décrivons cette image ci-dessous. Tu peux également consulter le cours de John Watrous Fondamentaux des algorithmes quantiques pour plus de détails.

Mise en place du plan. Nous pouvons décomposer l'état de superposition initiale $|\psi\rangle$ en deux composantes. L'état correct — celui que nous cherchons — nous l'appelons $|A_1\rangle$. Chaque autre état, regroupé ensemble, nous l'appelons $|A_0\rangle$. Par définition, $|A_1\rangle$ et $|A_0\rangle$ sont orthogonaux l'un à l'autre, donc nous pouvons les représenter comme des axes perpendiculaires dans un espace abstrait à deux dimensions. Puisque $|\psi\rangle$ est une combinaison linéaire de ces deux composantes, il se trouve à un petit angle $\theta$ par rapport à l'axe $|A_0\rangle$ — proche de $|A_0\rangle$, car au départ, seule une infime fraction de l'état est dans la composante correcte $|A_1\rangle$.

Réflexions. Le fait mathématique clé dont nous avons besoin est qu'un opérateur de la forme

$$2|v\rangle\langle v| - I$$

reflète tout état par rapport à l'axe défini par $|v\rangle.$ Pour comprendre pourquoi, considère deux cas : un état le long de $|v\rangle$ reste inchangé, et un état perpendiculaire à $|v\rangle$ voit son signe inversé. Tout autre état peut être décomposé en ces deux composantes, et l'opérateur agit sur chacune en conséquence — ce qui est exactement une réflexion par rapport à $|v\rangle$.

Il s'avère que l'oracle et l'étape de diffusion dans l'algorithme de Grover peuvent tous deux être exprimés comme des réflexions dans cette représentation géométrique.

L'oracle comme réflexion. L'oracle inverse le signe de l'état $|A_1\rangle$ et laisse tout le reste intact. C'est la même chose qu'une réflexion par rapport à l'axe $|A_0\rangle$.

La diffusion comme réflexion. Il est un peu plus difficile de voir comment l'opérateur de diffusion est également une réflexion. L'opérateur de diffusion est

$$H^{\otimes n}\, Z_{\text{OR}}\, H^{\otimes n}$$

$Z_{\text{OR}}$ seul est une réflexion par rapport à l'état tout-zéro, car il inverse le signe de chaque état qui n'est pas $|0\rangle^{\otimes n}$. Cela peut s'écrire $2|0\rangle\langle 0| - I$. Les couches Hadamard environnantes effectuent effectivement un changement de base, transformant l'axe de réflexion. Rappelle-toi que $H^{\otimes n}$ mappe $|0\rangle^{\otimes n}$ vers la superposition uniforme $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$. Puisque la porte Hadamard est sa propre inverse, l'expression complète devient

$$H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n} = 2|u\rangle\langle u| - I$$

ce qui est une réflexion par rapport à $|u\rangle$. Puisque $|u\rangle$ est très proche de $|\psi\rangle$ (tous deux sont presque le long de $|A_0\rangle$), cette deuxième réflexion envoie l'état à un angle $2\theta$ de son point de départ.

Rotation de $2\theta$. L'effet combiné de ces deux réflexions est une rotation de $2\theta$ vers $|A_1\rangle$. Chaque itération successive de l'opérateur de Grover fait pivoter l'état d'un autre $2\theta.$

Nombre optimal d'itérations. Notre objectif est de faire pivoter l'état aussi près que possible de $|A_1\rangle$, ce qui signifie faire pivoter d'environ $\pi/2$ radians au total (un quart de tour). Si chaque itération contribue $2\theta$, le nombre optimal d'itérations $t$ satisfait

$$(2t + 1)\theta \approx \frac{\pi}{2}$$

Pour une seule solution parmi $N$ états, l'angle initial est $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (pour $N$ grand). En substituant,

$$t \approx \frac{\pi}{4}\sqrt{N} - \frac{1}{2}$$

C'est de là que vient la célèbre accélération en $\sqrt{N}$ : nous n'avons besoin que de $O(\sqrt{N})$ itérations pour atteindre la cible, plutôt que les $O(N)$ vérifications qu'une recherche classique nécessiterait.

Plus généralement, s'il y a $|A_1|$ états solutions parmi $N$ états au total, le nombre optimal d'itérations est

$$t \approx \frac{\pi}{4}\sqrt{\frac{N}{|A_1|}} - \frac{1}{2}$$

Note que si tu appliques trop d'itérations, tu dépasses $|A_1\rangle$ et la probabilité de trouver ton état cible recommencera à diminuer. Trouver le bon nombre d'itérations est important, bien que sur du matériel quantique bruité le nombre optimal expérimentalement puisse différer de cette formule idéale.

Pourquoi l'algorithme de Grover est-il utile ?

À ce stade, tu te demandes peut-être : nous venons de construire un oracle qui marque un état cible — mais pour le construire, nous devions connaître l'état cible. Que cherchons-nous donc vraiment ?

C'est une question légitime, et il y a plusieurs bonnes réponses.

• Le modèle de requête est un outil théorique. Le modèle de requête de calcul n'a jamais été conçu pour être directement pratique. Son but est de nous donner un moyen propre d'analyser la complexité algorithmique en séparant un problème en deux parties : l'oracle, et tout le reste. Quelle est la difficulté de la recherche, sachant que la vérification est gratuite ? Comment le nombre de requêtes évolue-t-il avec la taille de l'entrée ? Ce sont des questions utiles même si aucun système réel ne fonctionne exactement de cette façon.

• Tu peux aussi y voir une activité à deux parties : une personne connaît l'état cible et construit l'oracle ; le rôle de l'autre personne est de trouver la réponse en utilisant l'oracle comme une boîte noire, sans regarder à l'intérieur. Dans l'Activité 2 ci-dessous, tu feras exactement cela avec un partenaire.

• L'amplification d'amplitude est une sous-routine largement utile. Même si cette première démonstration semble circulaire, le mécanisme sous-jacent — appelé amplification d'amplitude — réapparaît encore et encore en informatique quantique. Ce que nous construisons vraiment ici, c'est une intuition pour un outil qui apparaît comme sous-routine dans de nombreux algorithmes quantiques plus complexes.

• Il existe des problèmes pour lesquels tu peux construire un oracle sans connaître la réponse. L'idée clé est qu'il existe toute une classe de problèmes pour lesquels il est très difficile de trouver une solution, mais très facile de vérifier qu'une solution donnée est correcte. La factorisation en est un exemple : étant donné un produit de deux grands nombres premiers, il est extrêmement difficile de déterminer quels sont ces nombres premiers, mais une fois que tu les as, tu peux facilement les multiplier pour vérifier. (Nous avons un meilleur algorithme que celui de Grover pour la factorisation spécifiquement — voir l'algorithme de Shor — mais ce n'est loin d'être le seul problème avec cette caractéristique.) Le Sudoku, la satisfaction de contraintes, et même le jeu classique du Démineur sont tous des problèmes difficiles à résoudre mais faciles à vérifier.

Pourquoi est-ce pertinent ? Cela signifie que nous pouvons connaître toutes les conditions et exigences qu'une solution doit satisfaire, et nous pouvons encoder ces exigences dans un circuit quantique qui sert d'oracle — même si nous ne connaissons pas la solution elle-même. L'algorithme de Grover la trouvera pour nous.

Avec ces idées à l'esprit, travaillons à travers plusieurs exemples. Nous commencerons par un exemple dans lequel l'état solution est clairement spécifié afin de pouvoir suivre la logique de l'algorithme. Nous passerons ensuite à une activité à deux parties, et enfin à un exemple dans lequel l'oracle est construit à partir des contraintes du problème plutôt que de la connaissance de la réponse.

Imports généraux et approche

Nous commençons par importer plusieurs packages nécessaires.

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

Tout au long de ce tutoriel et d'autres, nous utiliserons un cadre pour l'informatique quantique connu sous le nom de « Qiskit patterns », qui décompose les flux de travail en les étapes suivantes :

• Étape 1 : Mapper les entrées classiques vers un problème quantique
• Étape 2 : Optimiser le problème pour l'exécution quantique
• Étape 3 : Exécuter en utilisant les primitives Qiskit Runtime
• Étape 4 : Post-traitement et analyse classique

Nous suivrons généralement ces étapes, bien que nous ne les étiquetions pas toujours explicitement.

Activité 1 : Trouver un seul état cible donné

Étape 1 : Mapper les entrées classiques vers un problème quantique

Nous avons besoin de la porte de requête de phase pour mettre une phase globale (-1) sur les états solutions, et laisser les états non-solutions non affectés. Autrement dit, l'algorithme de Grover nécessite un oracle qui spécifie un ou plusieurs états de la base computationnelle marqués, où « marqué » signifie un état avec une phase de -1. Cela se fait à l'aide d'une porte Z contrôlée, ou de sa généralisation multi-contrôlée sur $N$ qubits. Pour voir comment cela fonctionne, considère un exemple spécifique d'une chaîne de bits {110}. Nous voudrions un circuit qui agit sur un état $|\psi\rangle = |q_2,q_1,q_0\rangle$ et applique une phase si $|\psi\rangle = |011\rangle$ (où nous avons inversé l'ordre de la chaîne binaire, en raison de la notation dans Qiskit, qui place le qubit le moins significatif (souvent 0) à droite).

Ainsi, nous voulons un circuit $Z_f$ qui accomplit

$$Z_f|\psi\rangle = \begin{cases} -|\psi\rangle \qquad \text{si} \qquad |\psi\rangle = |011\rangle \\ |\psi\rangle \qquad \text{si} \qquad |\psi\rangle \neq |011\rangle\end{cases}$$

Nous pouvons utiliser la porte multi-contrôle multi-cible (MCMTGate) pour appliquer une porte Z contrôlée par tous les qubits (retourner la phase si tous les qubits sont dans l'état $|1\rangle$). Bien sûr, certains des qubits dans notre état désiré peuvent être $|0\rangle$. Par conséquent, pour ces qubits, nous devons d'abord appliquer une porte X, puis faire la porte Z multi-contrôlée, puis appliquer une autre porte X pour annuler notre changement. La MCMTGate ressemble à ceci :

mcmt_ex = QuantumCircuit(3)
mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)
mcmt_ex.draw(output="mpl", style="iqp")

Note que beaucoup de qubits peuvent être impliqués dans le processus de contrôle (ici trois qubits le sont), mais aucun qubit seul n'est désigné comme cible. C'est parce que l'état entier reçoit un signe global « - » (retournement de phase) ; la porte affecte tous les qubits de manière équivalente. Cela diffère de nombreuses autres portes multi-qubits, comme la porte CX, qui a un seul qubit de contrôle et un seul qubit cible.

Dans le code suivant, nous définissons une porte de requête de phase (ou oracle) qui fait ce que nous venons de décrire ci-dessus : marque un ou plusieurs états de la base d'entrée définis par leur représentation en chaîne de bits. La porte MCMT est utilisée pour implémenter la porte Z multi-contrôlée.

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bitstring to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bitstring
        zero_inds = [
            ind for ind in range(num_qubits) if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bitstring has a '0' entry
        qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        qc.x(zero_inds)
    return qc

Maintenant nous choisissons un état « marqué » spécifique comme cible, et appliquons la fonction que nous venons de définir. Voyons quel type de circuit elle a créé.

marked_states = ["1110"]
oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Si les qubits 1-3 sont dans l'état $|1\rangle$, et que le qubit 0 est initialement dans l'état $|0\rangle$, la première porte X va retourner le qubit 0 vers $|1\rangle$ et tous les qubits seront dans $|1\rangle.$ Cela signifie que la porte MCMT appliquera un changement de signe global ou un retournement de phase, comme désiré. Pour tout autre cas, soit les qubits 1-3 sont dans l'état $|0\rangle$, soit le qubit 0 est retourné vers l'état $|0\rangle$, et le retournement de phase ne sera pas appliqué. On voit que ce circuit marque bien notre état désiré $|0111\rangle,$ ou la chaîne de bits {1110}.

L'opérateur de Grover complet se compose de la porte de requête de phase (oracle), des couches Hadamard, et de l'opérateur $Z_\text{OR}$. On peut utiliser le grover_operator intégré pour construire cela à partir de l'oracle que nous avons défini ci-dessus.

grover_op = grover_operator(oracle)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

Comme nous l'avons expliqué dans la représentation géométrique ci-dessus, nous pourrions avoir besoin d'appliquer l'opérateur de Grover plusieurs fois. Le nombre optimal d'itérations $t$ pour maximiser l'amplitude de l'état cible en l'absence de bruit est

$$t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

où $|A_1|$ est le nombre d'états solutions et $N=2^n$ est le nombre total d'états. Sur les ordinateurs quantiques bruités modernes, le nombre optimal d'itérations expérimentalement pourrait être différent — mais ici nous calculons et utilisons ce nombre théorique optimal en utilisant $|A_1|=1$.

optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)
print(optimal_num_iterations)

3

Construisons maintenant un circuit qui inclut les portes Hadamard initiales pour créer une superposition de tous les états possibles, et appliquons l'opérateur de Grover le nombre optimal de fois.

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

Nous avons construit notre circuit de Grover !

Étape 2 : Optimiser le problème pour l'exécution sur matériel quantique

Nous avons défini notre circuit quantique abstrait, mais nous devons le réécrire en termes de portes natives à l'ordinateur quantique que nous voulons réellement utiliser. Nous devons également spécifier quels qubits de l'ordinateur quantique doivent être utilisés. Pour ces raisons et d'autres, nous devons maintenant transpiler notre circuit. Commençons par spécifier l'ordinateur quantique que nous souhaitons utiliser.

Il y a du code ci-dessous pour sauvegarder tes identifiants lors de la première utilisation. Assure-toi de supprimer ces informations du notebook après les avoir sauvegardées dans ton environnement, afin que tes identifiants ne soient pas accidentellement partagés quand tu partages le notebook. Voir Configurer ton compte IBM Cloud et Initialiser le service dans un environnement non fiable pour plus de conseils.

# To run on hardware, select the backend with the fewest number of jobs in the queue
from qiskit_ibm_runtime import QiskitRuntimeService

# Syntax for first saving your token.  Delete these lines after saving your credentials.

# QiskitRuntimeService.save_account(channel='ibm_quantum_platform',
# instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

backend = service.least_busy(operational=True, simulator=False)
backend.name

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.

'ibm_brisbane'

Nous utilisons maintenant un gestionnaire de passes prédéfini pour optimiser notre circuit quantique pour le backend que nous avons sélectionné.

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

circuit_isa = pm.run(qc)
# The transpiled circuit will be very large. Only draw it if you are really curious.
# circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Il convient de noter à ce stade que la profondeur du circuit quantique transpilé est substantielle.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  439
The depth of two-qubit gates is  113

Ce sont en réalité des nombres assez grands, même pour ce cas simple. Puisque toutes les portes quantiques (et surtout les portes à deux qubits) subissent des erreurs et sont soumises au bruit, une série de plus de 100 portes à deux qubits ne produirait que du bruit si les qubits n'étaient pas extrêmement performants. Voyons comment celles-ci se comportent.

Étape 3 : Exécuter en utilisant les primitives Qiskit

Nous voulons faire de nombreuses mesures et voir quel état est le plus probable. Une telle amplification d'amplitude est un problème d'échantillonnage adapté à l'exécution avec la primitive Qiskit Runtime Sampler.

Note que la méthode run() du SamplerV2 de Qiskit Runtime prend un itérable de blocs unifiés primitifs (PUBs). Pour Sampler, chaque PUB est un itérable dans le format (circuit, parameter_values). Cependant, au minimum, il prend une liste de circuit(s) quantique(s).

# To run on a real quantum computer (this was tested on a Heron r2 processor and
# used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

Pour tirer le meilleur parti de cette expérience, nous te recommandons vivement d'exécuter tes expériences sur les vrais ordinateurs quantiques disponibles depuis IBM Quantum. Cependant, si tu as épuisé ton temps QPU, tu peux décommenter les lignes ci-dessous pour compléter cette activité en utilisant un simulateur.

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Étape 4 : Post-traitement et retour du résultat au format classique désiré

Nous pouvons maintenant tracer les résultats de notre échantillonnage dans un histogramme.

plot_distribution(dist)

On voit que l'algorithme de Grover a retourné l'état désiré avec la probabilité la plus élevée de loin, au moins un ordre de grandeur plus élevée que les autres options. Dans l'activité suivante, nous utiliserons l'algorithme d'une manière plus cohérente avec le flux de travail à deux parties d'un algorithme de requête.

Vérifie ta compréhension

Lis les questions ci-dessous, réfléchis à ta réponse, puis clique sur le triangle pour révéler la solution.

Nous venons de chercher une seule solution dans un ensemble de $2^4=16$ états possibles. Nous avons déterminé le nombre optimal de répétitions de l'opérateur de Grover à $t=3$. Ce nombre optimal aurait-il augmenté ou diminué si nous avions cherché (a) l'une parmi plusieurs solutions, ou (b) une seule solution dans un espace de plus d'états possibles ?

Réponse :

Rappelle-toi que tant que le nombre de solutions est petit par rapport à l'espace entier des solutions, on peut développer la fonction sinus autour des petits angles et utiliser

$$(2t+1)\theta = (2t+1) \sin^{-1}{\sqrt{\frac{|\mathcal{A}_1|}{N}}}\approx (2t+1) \sqrt{\frac{|\mathcal{A}_1|}{N}} \approx \pi/2\\ t \approx \frac{\pi}{4}\sqrt{\frac{N}{|\mathcal{A}_1|}}-\frac{1}{2}$$

(a) On voit à partir de l'expression ci-dessus qu'augmenter le nombre d'états solutions diminuerait le nombre d'itérations. À condition que la fraction $\frac{|\mathcal{A}_1|}{N}$ soit encore petite, on peut décrire comment $t$ diminuerait : $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

(b) À mesure que l'espace des solutions possibles ($N$) augmente, le nombre d'itérations requises augmente, mais seulement comme $t~\sqrt{N}$.

Suppose qu'on puisse augmenter la taille de la chaîne de bits cible de manière arbitraire et qu'on ait toujours le résultat que l'état cible a une amplitude de probabilité au moins un ordre de grandeur plus grande que tout autre état. Cela signifie-t-il qu'on pourrait utiliser l'algorithme de Grover pour trouver de manière fiable l'état cible ?

Réponse :

Non. Suppose qu'on répète la première activité avec 20 qubits, et qu'on exécute le circuit quantique un certain nombre de fois num_shots = 10,000. Une distribution de probabilité uniforme signifierait que chaque état a une probabilité de $10,000/2^{20}=0,00954$ d'être mesuré même une seule fois. Si la probabilité de mesurer l'état cible était 10 fois celle des non-solutions (et si la probabilité de chaque non-solution était diminuée en conséquence), il n'y aurait qu'environ 10 % de chance de mesurer l'état cible même une seule fois. Il serait très peu probable de mesurer l'état cible plusieurs fois, ce qui le rendrait indiscernable des nombreux états non-solutions obtenus aléatoirement. La bonne nouvelle est qu'on peut obtenir des résultats de fidélité encore plus élevée en utilisant la suppression et l'atténuation d'erreurs.

Activité 2 : Un flux de travail d'algorithme de requête précis

Nous allons commencer cette activité exactement comme la première, sauf que maintenant tu vas t'associer à un autre passionné de Qiskit. Tu vas choisir une chaîne de bits secrète, et ton partenaire va en choisir une (généralement) différente. Vous allez chacun générer un circuit quantique qui fonctionne comme un oracle, et vous allez les échanger. Tu utiliseras ensuite l'algorithme de Grover avec cet oracle pour déterminer la chaîne de bits secrète de ton partenaire.

Étape 1 : Mapper les entrées classiques vers un problème quantique

En utilisant la fonction grover_oracle définie ci-dessus, construis un circuit oracle pour un ou plusieurs états marqués. Assure-toi de dire à ton partenaire combien d'états tu as marqués, afin qu'il puisse appliquer l'opérateur de Grover le nombre optimal de fois. Ne rends pas ta chaîne de bits trop longue. 3 à 5 bits devraient fonctionner sans trop de difficulté. Des chaînes de bits plus longues résulteraient en des circuits profonds nécessitant des techniques plus avancées comme l'atténuation d'erreurs.

# Modify the marked states to mark those you wish to target.
marked_states = ["1000"]
oracle = grover_oracle(marked_states)

Tu as maintenant créé un circuit quantique qui retourne la phase de ton état cible. Tu peux sauvegarder ce circuit sous my_circuit.qpy en utilisant la syntaxe ci-dessous.

from qiskit import qpy

# Save to a QPY file at a location where you can easily find it.
# You might want to specify a global address.
with open("C:\\Users\\...put your own address here...\\my_circuit.qpy", "wb") as f:
    qpy.dump(oracle, f)

Envoie maintenant ce fichier à ton partenaire (par e-mail, service de messagerie, un dépôt partagé, etc.). Demande à ton partenaire de t'envoyer son circuit également. Assure-toi de sauvegarder le fichier quelque part où tu peux facilement le trouver. Une fois que tu as le circuit de ton partenaire, tu pourrais le visualiser — mais cela briserait le modèle de requête. C'est-à-dire que nous modélisons une situation dans laquelle tu peux interroger l'oracle (utiliser le circuit oracle) mais pas l'examiner pour déterminer quel état il cible.

from qiskit import qpy

# Load the circuit from your partner's qpy file from the folder where you saved it.
with open("C:\\Users\\...file location here...\\my_circuit.qpy", "rb") as f:
    circuits = qpy.load(f)

# qpy.load always returns a list of circuits
oracle_partner = circuits[0]

# You could visualize the circuit, but this would break the model of a query algorithm.
# oracle_partner.draw("mpl")

Demande à ton partenaire combien d'états cibles il a encodés et entre-le ci-dessous.

# Update according to your partner's number of target states.
num_marked_states = 1

Ceci est utilisé dans l'expression suivante pour déterminer le nombre optimal d'itérations de Grover.

grover_op = grover_operator(oracle_partner)
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_marked_states / 2**grover_op.num_qubits)))
)
qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

Étape 2 : Optimiser le problème pour l'exécution sur matériel quantique

Cela se passe exactement comme précédemment.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
backend.name

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_partner_isa = pm.run(qc)

Étape 3 : Exécuter en utilisant les primitives Qiskit

Ceci est également identique au processus de la première activité.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used
# 4 seconds of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_partner_isa]).result()
dist = result[0].data.meas.get_counts()

Étape 4 : Post-traitement et retour du résultat au format classique désiré

Maintenant, affiche un histogramme de tes résultats d'échantillonnage. Un ou plusieurs états devraient avoir une probabilité de mesure bien plus élevée que les autres. Rapporte ces résultats à ton partenaire et vérifie si tu as correctement déterminé les états cibles. Par défaut, l'histogramme affiché provient du même circuit de la première activité. Tu devrais obtenir des résultats différents à partir du circuit de ton partenaire.

plot_distribution(dist)

Vérifie ta compréhension

Lis les questions ou les invites ci-dessous, réfléchis à ta réponse ou discutes du processus avec ton partenaire. Clique sur le triangle pour des indices ou des suggestions.

Tu devrais avoir correctement obtenu les états cibles de ton partenaire. Si tu ne l'as pas fait, travaille avec ton partenaire pour identifier ce qui n'a pas fonctionné. Clique ci-dessous pour quelques idées.

Indices :

• Visualise/dessine le circuit de ton partenaire et assure-toi qu'il s'est chargé correctement.
• Compare les circuits utilisés et compare le résultat attendu à celui que tu as obtenu.
• Vérifie la profondeur des circuits utilisés pour t'assurer que la chaîne de bits n'était pas trop longue ou que le nombre d'itérations de Grover n'était pas trop élevé.

Si tu ne l'as pas déjà fait, dessine le circuit oracle que ton partenaire t'a envoyé. Vois si tu peux expliquer l'effet de chaque porte et argumenter quel devait être l'état cible. Ce sera beaucoup plus facile pour le cas d'un seul état marqué que pour plusieurs.

Indices :

• Rappelle-toi que le rôle de l'oracle est de retourner le signe sur l'état cible.
• Rappelle-toi que la MCMTGate retourne le signe sur un état si et seulement si tous les qubits impliqués dans le contrôle sont dans l'état $|1\rangle$.
• Si ton état cible aura déjà un $|1\rangle$ sur un qubit particulier, tu n'as pas besoin de faire quoi que ce soit à ce qubit. Si ta cible a un $|0\rangle$ sur un qubit particulier et que tu veux que la MCMTGate retourne le signe, tu dois appliquer une porte X à ce qubit dans ton oracle (puis défaire la porte X après la MCMTGate).

Répète l'expérience avec une itération de moins de l'opérateur de Grover. Obtiens-tu encore la bonne réponse ? Pourquoi ou pourquoi pas ?

Conseils :

Tu le feras probablement, bien que cela puisse dépendre du nombre de solutions encodées. Cela met en évidence une subtilité : le nombre « optimal » d'itérations de Grover est le nombre qui rend la probabilité de mesurer l'état marqué aussi élevée que possible. Mais un nombre d'itérations inférieur pourrait encore rendre l'état marqué substantiellement plus probable que les autres états. Par conséquent, tu pourrais t'en sortir avec moins d'itérations que le nombre optimal. Cela réduit la profondeur du circuit, et donc réduit les taux d'erreur.

Pourquoi quelqu'un voudrait-il utiliser moins d'itérations de Grover que le « nombre optimal » identifié ici ?

Réponse :

Le nombre « optimal » d'itérations de Grover est le nombre qui rend la probabilité de mesurer l'état marqué aussi élevée que possible en l'absence de bruit. Mais un nombre d'itérations inférieur pourrait encore rendre l'état marqué substantiellement plus probable que les autres états. Tu pourrais donc t'en sortir avec moins d'itérations que le nombre optimal. Cela réduit la profondeur du circuit, et donc réduit les taux d'erreur.

Activité 3 : Résoudre une grille du Démineur avec l'algorithme de Grover

Dans la section précédente, nous avons noté que l'algorithme de Grover devient vraiment utile quand nous pouvons construire un oracle à partir des contraintes d'un problème, plutôt que de la connaissance de la réponse. Le Démineur est un exemple parfait : les cellules numérotées nous indiquent combien de mines sont adjacentes, et ces contraintes déterminent entièrement où les mines doivent se trouver — mais trouver la configuration nécessite une recherche.

Il a été démontré que le Démineur est NP-complet : il est difficile à résoudre mais facile à vérifier. Cela en fait un candidat naturel pour l'algorithme de Grover. Bien sûr, nous ne pouvons pas encore résoudre une grille complète de 9$\times$9 sur un ordinateur quantique bruité — les circuits seraient bien trop profonds. Au lieu de cela, nous utiliserons une toute petite grille comme démonstration jouet de la façon dont on aborderait un plateau plus grand sur une future machine à tolérance aux pannes.

Quelques mises en garde importantes. L'algorithme de Grover ne fournit qu'une accélération quadratique par rapport à la recherche classique non structurée. Le Démineur a presque certainement une structure exploitable qu'un algorithme classique intelligent pourrait utiliser. Et pour un espace de recherche qui croît exponentiellement, même l'amélioration en $\sqrt{N}$ ne va qu'aussi loin. Mais mettons ces préoccupations de côté et utilisons ce problème jouet pour illustrer comment les contraintes d'un problème s'encodent dans un oracle quantique.

La grille

Voici notre petite grille du Démineur :

Chaque cellule vide peut être représentée par une variable binaire indiquant si elle contient une mine. Nous les notons $x_0$, $x_1$, et $x_2$, où $x_i = 1$ signifie qu'il y a une mine sur cette cellule et $x_i = 0$ signifie qu'il n'y en a pas :

Nous pourrions résoudre cela mentalement en une demi-seconde, mais nous utilisons ce problème jouet pour illustrer comment un plateau bien plus difficile pourrait être abordé avec un ordinateur quantique.

Encoder les contraintes

Chaque cellule numérotée impose une condition sur les cellules vides adjacentes. Nous devons exprimer ces conditions sous forme d'expressions booléennes pouvant être encodées dans un circuit quantique.

La cellule « 1 » adjacente à $x_0$ et $x_1$ indique qu'exactement l'une d'elles contient une mine. C'est précisément l'opération OU exclusif (XOR), $\oplus$, qui renvoie vrai quand exactement une de ses entrées est vraie :

$$(x_0 \oplus x_1)$$

De même, l'autre cellule « 1 » (adjacente à $x_1$ et $x_2$) nous donne :

$$(x_1 \oplus x_2)$$

La cellule « 2 » indique que deux des trois cellules vides doivent contenir des mines. Puisque XOR est une opération de parité, $x_0 \oplus x_1 \oplus x_2$ renvoie vrai quand un nombre impair de variables sont vraies. Nous voulons qu'un nombre pair (spécifiquement deux) soit vrai, donc nous nions avec $\lnot$ :

$$\lnot(x_0 \oplus x_1 \oplus x_2)$$

En elle-même, cette expression serait satisfaite soit par zéro, soit par deux qubits dans l'état $|1\rangle$, puisqu'il s'agit d'une affirmation sur la parité. Mais combinée aux deux autres clauses, qui exigent chacune au moins une mine, la seule assignation satisfaisante a exactement deux mines.

Les trois conditions doivent être satisfaites simultanément, donc nous les joignons avec des symboles et $\land$ :

$$(x_0 \oplus x_1) \;\land\; (x_1 \oplus x_2) \;\land\; \lnot(x_0 \oplus x_1 \oplus x_2)$$

Étape 1 : Mapper les entrées classiques vers un problème quantique

Nous devons maintenant encoder cette expression booléenne dans un circuit quantique qui sert d'oracle. La version quantique du XOR peut être accomplie avec des portes CX (CNOT) : l'application de deux portes CX depuis les qubits de données vers un qubit de travail (ancilla) calcule effectivement leur XOR et stocke le résultat dans l'ancilla.

Nous introduisons trois qubits de travail — un pour chaque clause. Nous stockons le résultat de chaque expression booléenne dans son qubit de travail correspondant, puis utilisons une porte Z multi-contrôlée pour inverser la phase de l'état à trois qubits qui rend tous les trois qubits de travail $|1\rangle$ (ce qui signifie que toutes les clauses sont satisfaites simultanément).

Dans la première cellule de code ci-dessous, nous construisons la moitié « calcul » de l'oracle — la partie qui évalue chaque clause et écrit le résultat dans les qubits de travail.

x = QuantumRegister(3, "x")
a = QuantumRegister(3, "a")
qc = QuantumCircuit(x, a)

# Clause 1: x0 XOR x1 -> stored in a[0]
qc.cx(x[0], a[0])
qc.cx(x[1], a[0])

# Clause 2: x1 XOR x2 -> stored in a[1]
qc.cx(x[1], a[1])
qc.cx(x[2], a[1])

# Clause 3: NOT(x0 XOR x1 XOR x2) -> stored in a[2]
qc.cx(x[0], a[2])
qc.cx(x[1], a[2])
qc.cx(x[2], a[2])
qc.x(a[2])  # The NOT

qc.draw("mpl", style="iqp")

À ce stade, le résultat de chaque clause est stocké dans son qubit de travail correspondant. Nous avons maintenant besoin que l'état à trois qubits de données qui rend tous les trois qubits de travail $|1\rangle$ acquière un signe moins. Nous faisons cela avec une porte Z multi-contrôlée (implémentée comme une porte MCX encadrée par des portes Hadamard sur la cible).

Après avoir appliqué le retournement de phase, nous devons décalculer — annuler toutes les étapes d'évaluation des clauses dans l'ordre inverse — pour réinitialiser les qubits de travail à $|0\rangle.$ C'est essentiel pour que les qubits de travail soient propres pour les itérations suivantes de l'opérateur de Grover.

# Multi-controlled Z: flip phase if all workspace qubits are |1>
qc.h(a[2])
qc.mcx([a[0], a[1]], a[2])
qc.h(a[2])

# Uncompute clause 3: NOT(x0 XOR x1 XOR x2)
qc.x(a[2])
qc.cx(x[2], a[2])
qc.cx(x[1], a[2])
qc.cx(x[0], a[2])

# Uncompute clause 2: x1 XOR x2
qc.cx(x[2], a[1])
qc.cx(x[1], a[1])

# Uncompute clause 1: x0 XOR x1
qc.cx(x[1], a[0])
qc.cx(x[0], a[0])

qc.draw("mpl", style="iqp")

Ce circuit est notre oracle : il inverse la phase de l'état des qubits de données qui satisfait toutes les trois contraintes du Démineur, et laisse les qubits de travail à $|0\rangle.$

Nous construisons maintenant l'opérateur de Grover complet à partir de cet oracle. Note l'argument reflection_qubits : nous ne passons que les qubits de données x, car les qubits de travail ne font pas partie de l'espace de recherche. Leur travail est terminé une fois que l'oracle a été appliqué.

grover_op = grover_operator(qc, reflection_qubits=x)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

Avec trois qubits de données et un état solution, le nombre optimal d'itérations de Grover est $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1,7$, donc nous utilisons deux itérations. Nous appliquons des portes Hadamard aux qubits de données pour créer la superposition initiale, composons l'opérateur de Grover deux fois, et mesurons uniquement les qubits de données.

x = QuantumRegister(3, "x")
a = QuantumRegister(4, "a")
meas = ClassicalRegister(3, "meas")

qc = QuantumCircuit(x, a, meas)
# Create superposition over the data qubits only
qc.h(x)
# Apply 2 iterations of the Grover operator
qc.compose(grover_op.power(2), inplace=True)
# Measure only the data qubits
qc.measure(x, meas)
qc.decompose().draw(output="mpl", style="iqp")

Étape 2 : Optimiser le problème pour l'exécution sur matériel quantique

Comme précédemment, nous transpilons le circuit pour le backend cible.

service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
print(backend.name)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

Nous pouvons maintenant vérifier la profondeur du circuit transpilé. Parce que l'oracle du Démineur utilise des qubits de travail et plusieurs portes CX, le circuit transpilé sera plus profond que ceux des activités précédentes.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

Étape 3 : Exécuter en utilisant les primitives Qiskit

# To run on a real quantum computer (this was tested on a Heron r2 processor and
#  used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Étape 4 : Post-traitement et retour du résultat au format classique désiré

plot_distribution(dist)

L'état 101 devrait apparaître avec une probabilité bien plus élevée que tout autre, indiquant que des mines sont situées en $x_0$ et $x_2$. Nous avons utilisé un ordinateur quantique pour résoudre une petite partie du Démineur !

Bien sûr, les meilleurs algorithmes classiques pour le Démineur sont meilleurs qu'une recherche par force brute à travers toutes les configurations de mines possibles — ils exploitent la structure de la grille. L'algorithme de Grover n'offrirait un avantage que sur des plateaux extrêmement difficiles conçus pour être maximalement ambigus, et même dans ce cas, l'accélération quadratique signifie qu'il ne peut pas suivre la croissance exponentielle indéfiniment. Mais la vraie leçon à retenir est la technique : encoder les contraintes d'un problème dans un oracle quantique est un schéma puissant qui s'étend à la satisfaction de contraintes, à l'optimisation combinatoire, et à de nombreux autres domaines.

Questions et concepts clés :

Concepts clés :

Dans ce module, nous avons appris quelques caractéristiques clés de l'algorithme de Grover :

• Alors que les algorithmes classiques de recherche non structurée nécessitent un nombre de requêtes qui évolue linéairement dans la taille de l'espace, $N,$ l'algorithme de Grover nécessite un nombre de requêtes qui évolue comme $\sqrt{N}.$
• L'algorithme de Grover implique de répéter une série d'opérations (communément appelées l'« opérateur de Grover ») un nombre de fois $t,$ choisi pour rendre les états cibles optimalement susceptibles d'être mesurés.
• L'algorithme de Grover peut être exécuté avec moins de $t$ itérations et amplifier quand même les états cibles.
• L'algorithme de Grover s'inscrit dans le modèle de requête de calcul et a le plus de sens quand une personne contrôle la recherche et une autre contrôle/construit l'oracle. Il peut également être utile comme sous-routine dans d'autres calculs quantiques.
• Un oracle peut être construit à partir des contraintes du problème plutôt que de la connaissance de la solution, comme démontré avec l'exemple du Démineur.

Questions V/F :

1. V/F L'algorithme de Grover offre une amélioration exponentielle par rapport aux algorithmes classiques dans le nombre de requêtes nécessaires pour trouver un seul état marqué dans une recherche non structurée.

2. V/F L'algorithme de Grover fonctionne en augmentant itérativement la probabilité qu'un état solution sera mesuré.

3. V/F Plus tu itères l'opérateur de Grover, plus la probabilité de mesurer un état solution est élevée.

Questions à choix multiples :

1. Sélectionne la meilleure option pour compléter la phrase. La meilleure stratégie pour utiliser avec succès l'algorithme de Grover sur les ordinateurs quantiques modernes est d'itérer l'opérateur de Grover...

• a. Une seule fois.
• b. Toujours $t$ fois, pour maximiser l'amplitude de probabilité des états solution(s).
• c. Jusqu'à $t$ fois, bien que moins puisse suffire pour que les états solutions se démarquent.
• d. Pas moins de 10 fois.

2. Un circuit de requête de phase est montré ici qui fonctionne comme un oracle pour marquer un certain état avec un retournement de phase. Lequel des états suivants est marqué par ce circuit ?

• a. $|0000\rangle$
• b. $|0101\rangle$
• c. $|0110\rangle$
• d. $|1001\rangle$
• e. $|1010\rangle$
• f. $|1111\rangle$

3. Suppose que tu veuilles chercher trois états marqués dans un ensemble de 128. Quel est le nombre optimal d'itérations de l'opérateur de Grover pour maximiser les amplitudes des états marqués ?

• a. 1
• b. 3
• c. 5
• d. 6
• e. 20
• f. 33

Questions de discussion :

1. Quels autres problèmes pourrais-tu formuler comme une recherche de Grover ? Pense à des problèmes où il est difficile de trouver une solution mais facile d'en vérifier une.

2. Vois-tu des problèmes liés à la mise à l'échelle de l'algorithme de Grover sur les ordinateurs quantiques modernes ?