Algorithme de Grover

Pour ce module Qiskit in Classrooms, les étudiants doivent disposer d'un environnement Python fonctionnel avec les paquets 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 paquets ci-dessus, voir le guide d' installation de Qiskit. Afin d'exécuter des tâches sur de véritables ordinateurs quantiques, les étudiants devront créer un compte sur IBM Quantum® en suivant les étapes du guide Configurer votre 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; votre utilisation réelle peut varier.

# 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'

Présentation

L' algorithme de Grover est un algorithme quantique fondamental qui aborde le problème de la recherche non structurée : étant donné un ensemble d'éléments $N$ et un moyen de vérifier si un élément donné est celui que vous recherchez, en combien de temps pouvez-vous trouver l'élément désiré? En informatique classique, si les données ne sont pas triées et qu'il n'y a pas de structure à exploiter, la meilleure approche consiste à vérifier chaque élément un par un, ce qui entraîne une complexité d'interrogation de $O(N)$ - en moyenne, vous devrez vérifier environ la moitié des éléments avant de trouver la cible.

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

L'algorithme fonctionne dans le contexte suivant :

• Configuration du problème : Vous disposez d'une fonction $f(x)$ qui renvoie 1 si $x$ est l'élément que vous souhaitez, et 0 dans le cas contraire. Cette fonction est souvent appelée oracle ou boîte noire, car vous ne pouvez obtenir des informations sur les données qu'en interrogeant $f(x)$.
• Utilité du quantum : 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 grandes $N$.
• Comment cela fonctionne (à un niveau élevé) :
  • L'ordinateur quantique crée d'abord une superposition de tous les états possibles, représentant tous les éléments possibles à la fois.
  • 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 un nombre suffisant d'itérations, la mesure de l'état quantique donne la bonne réponse avec une forte probabilité.

Voici un schéma très basique de l'algorithme de Grover qui passe sous silence de nombreuses nuances. Pour un schéma plus détaillé, voir ce document.

Quelques remarques 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 permet qu'une accélération quadratique, et non exponentielle, contrairement à d'autres algorithmes quantiques (par exemple, l'algorithme de Shor pour la factorisation).
• Elle 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 casser la plupart des systèmes de cryptage modernes.

Pour les étudiants de premier cycle familiarisés avec les concepts informatiques de base et les modèles d'interrogation, l'algorithme de Grover illustre clairement comment l'informatique quantique peut surpasser les approches classiques pour certains problèmes, même lorsque l'amélioration n'est "que" quadratique. Il sert également de passerelle vers la compréhension d'algorithmes quantiques plus avancés et le potentiel plus large de l'informatique quantique.

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

Nous allons ici montrer comment construire des oracles de Grover et utiliser la bibliothèque de GroverOperator circuits Qiskit pour mettre facilement en place une instance de recherche de Grover. La primitive Sampler « IBM Quantum » permet l'exécution fluide des circuits de Grover.

théorie

Supposons qu'il existe une fonction $f$ qui convertit les chaînes binaires en une seule variable binaire, c'est-à-dire

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

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

Vous devez trouver les états quantiques correspondant aux arguments $x$ de $f(x)$ qui sont associés à 1. En d'autres termes, trouver tous les $\{x_1\}\in \Sigma^n$ tels que $f(x_1)=1$ (ou s'il n'y a pas de solution, le signaler). Nous ferions référence aux non-solutions en tant que $x_0$. Bien entendu, nous ferons cela sur un ordinateur quantique, en utilisant des états quantiques, et il est donc utile d'exprimer ces chaînes binaires sous forme d'états :

En utilisant la notation de l'état quantique (Dirac), nous recherchons 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 où les non-solutions sont notées $\{|x_0\rangle\}.$

Nous pouvons considérer que la fonction $f$ est fournie par un oracle : une boîte noire que nous pouvons interroger pour déterminer son effet sur un état $|x\rangle.$. Dans la pratique, nous connaissons souvent la fonction, mais elle peut être très compliquée à mettre en œuvre, ce qui signifie qu'il peut être important de réduire le nombre de requêtes ou d'applications de $f$. On peut également imaginer un paradigme dans lequel une personne interroge un oracle contrôlé par une autre personne, de sorte que nous ne connaissons pas la fonction de l'oracle, mais seulement son action sur des états particuliers à partir de l'interrogation.

Il s'agit d'un "problème de recherche non structuré", dans la mesure où $f$ ne présente aucune particularité susceptible de nous aider dans notre recherche. Les résultats ne sont pas triés et les solutions ne sont pas connues pour être regroupées, etc. Prenons l'exemple des vieux annuaires téléphoniques en papier. Cette recherche non structurée reviendrait à parcourir la liste à la recherche d'un certain numéro, et non à parcourir une liste de noms classés par ordre alphabétique.

Dans le cas où une solution unique est recherchée, il faut classiquement un nombre de requêtes linéaire en $N$. Il est clair que vous pouvez trouver une solution du premier coup, ou que vous pouvez ne trouver aucune solution dans les premières $N-1$ suppositions, de sorte que vous devez interroger l'entrée $N^{th}$ pour voir s'il y a une solution du tout. Comme les fonctions n'ont pas de structure exploitable, vous aurez besoin de $N/2$ devinettes en moyenne. L'algorithme de Grover nécessite un nombre de requêtes ou de calculs de $f$ qui évolue comme suit $\sqrt{N}.$

Esquisse des circuits dans l'algorithme de Grover

Une description mathématique complète de l'algorithme de Grover peut être trouvée, par exemple, dans Fundamentals of quantum algorithms, un cours de John Watrous sur IBM Quantum Learning. Un traitement condensé est fourni en annexe à la fin de ce module. Mais pour l'instant, nous nous contenterons d'examiner la structure globale du circuit quantique qui met en œuvre l'algorithme de Grover.

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

• Préparation d'une superposition initiale (application de portes de Hadamard à tous les qubits)
• "Marquer l'état ou les états cibles par une inversion de phase
• Une étape de "diffusion" au cours de laquelle des portes de Hadamard et une inversion de phase sont appliquées à tous les qubits.
• 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 constituées de $H,$ $Z_{\text{OR}},$ et $H$ sont collectivement désignées sous le nom d'"opérateur Grover". Dans ce diagramme, une seule répétition de l'opérateur de Grover est représentée.

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

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

Une propriété corollaire importante de la porte de Hadamard est que le fait d'agir une seconde fois peut annuler de tels états de superposition :

Ce point sera important dans un instant.

Vérifiez votre compréhension

En partant de la définition de la porte de Hadamard, démontrer qu'une deuxième application de la porte de Hadamard annule de telles superpositions comme indiqué ci-dessus.

• Réponse

  Lorsque nous appliquons X à l'état $|+\rangle$, nous obtenons la valeur et +1 et à l'état $|-\rangle$, nous obtenons -1, de sorte que si nous avions une distribution 50-50, nous obtiendrions une valeur d'espérance de 0.

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

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

Notez que cela a pour effet que $Z_f$ inverse le signe d'un état cible pour lequel $f(x) = 1$ et laisse les autres états inchangés.

À un niveau très élevé et abstrait, vous pouvez envisager les étapes du circuit de la manière suivante :

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

Exemple

Pour mieux comprendre le fonctionnement de l'algorithme de Grover, prenons un petit exemple à deux qubits. Ce cours 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 de manière substantielle avec des ordinateurs quantiques, ce livre est fortement recommandé.

Voici le schéma du circuit avec les états quantiques étiquetés à différents endroits. Notez qu'avec seulement deux qubits, il n'y a que quatre états possibles qui peuvent être mesurés en toutes circonstances : $|00\rangle$, $|01\rangle$, $|10\rangle$, et $|11\rangle$.

Supposons que l'oracle ( $Z_f$, inconnu de nous) marque l'état $|01\rangle$. Nous allons passer en revue les actions de chaque ensemble de portes quantiques, y compris l'oracle, et voir quelle distribution d'états possibles apparaît au moment de la mesure. Au tout début, nous avons

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

L'oracle marque maintenant l'état cible :

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

En combinant les termes similaires, nous obtenons

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

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

Il vaut la peine de travailler sur la combinaison de ces termes pour se convaincre que le résultat est bien celui-là :

En d'autres termes, 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 de zéro.

Cet exemple de deux qubits était un cas particulièrement net; l'algorithme de Grover ne fonctionnera pas toujours de manière à obtenir une probabilité de 100 % de mesurer l'état cible. Au contraire, elle amplifie la probabilité de mesurer l'état cible. En outre, il se peut que l'opérateur Grover doive être répété plus d'une fois.

Dans la section suivante, nous mettrons cet algorithme en pratique en utilisant de véritables ordinateurs quantiques IBM®.

L'image géométrique

L'exemple à deux qubits ci-dessus a montré comment l'algèbre s'applique dans un cas simple, mais il existe une manière bien plus intuitive de comprendre l'algorithme de Grover : en le considérant comme une succession de réflexions géométriques dans un plan bidimensionnel. Nous décrivons cette image ci-dessous. Vous pouvez également consulter le cours de John Watrous intitulé « Fundamentals of Quantum Algorithms » pour plus de détails.

Mise en place de l'avion. Nous pouvons décomposer l'état de superposition initial $|\psi\rangle$ en deux composantes. L'état correct — celui que nous recherchons — est appelé « état de l' $|A_1\rangle$ ». Tous les autres états, regroupés, sont appelés « état de l' $|A_0\rangle$ ». Par définition, l'« $|A_1\rangle$ » et l'« $|A_0\rangle$ » sont orthogonaux l'un par rapport à l'autre; nous pouvons donc les représenter sous forme d'axes perpendiculaires dans un espace abstrait à deux dimensions. Étant donné que $|\psi\rangle$ est une combinaison linéaire de ces deux composantes, il forme 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 se trouve dans la composante correcte $|A_1\rangle$.

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

reflète tout état situé sur l'axe défini par $|v\rangle.$ Pour comprendre pourquoi, considérons deux cas : un état situé sur $|v\rangle$ reste inchangé, tandis qu'un état perpendiculaire à $|v\rangle$ voit son signe s'inverser. Tout autre état peut être décomposé en ces deux composantes, et l'opérateur agit sur chacune d'elles en conséquence — ce qui correspond exactement à une réflexion sur l' $|v\rangle$

Il s'avère que tant l'étape de l'oracle que celle de la diffusion dans l'algorithme de Grover peuvent être représentées sous forme de réflexions dans ce schéma géométrique.

L'oracle comme reflet. L'oracle inverse le signe de l'état « $|A_1\rangle$ » et laisse tout le reste inchangé. Cela revient à une réflexion par rapport à l'axe d' $|A_0\rangle$.

La diffusion comme reflet. Il est un peu plus difficile de comprendre en quoi l'opérateur de diffusion est également une réflexion. L'opérateur de diffusion est

$Z_{\text{OR}}$ En soi, c'est une réflexion sur l'état tout à zéro, puisqu'elle inverse le signe de tout état qui n'est pas l' $|0\rangle^{\otimes n}$ e. On peut l'écrire ainsi : $2|0\rangle\langle 0| - I$. Les couches de Hadamard environnantes effectuent en fait un changement de base, transformant ainsi l'axe de réflexion. Rappelons que $H^{\otimes n}$ associe $|0\rangle^{\otimes n}$ à la superposition uniforme $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$. Comme l'opérateur de Hadamard est son propre inverse, l'expression complète devient

ce qui correspond à une réflexion sur $|u\rangle$. Étant donné que $|u\rangle$ est très proche de $|\psi\rangle$ (les deux se situent pratiquement sur $|A_0\rangle$ ), cette deuxième réflexion renvoie l'état à un angle $2\theta$ par rapport à son point de départ.

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

Nombre optimal d'itérations. Notre objectif est de faire pivoter l'état de manière à ce qu'il soit aussi proche que possible de $|A_1\rangle$, ce qui implique un pivotement total d'environ $\pi/2$ radians (un quart de tour). Si chaque itération apporte une amélioration de $2\theta$, le nombre optimal d'itérations $t$ satisfait

Pour une solution unique parmi les états d' $N$, l'angle initial est $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (pour une grande valeur de $N$ ). En substituant,

C'est de là que provient le célèbre gain de vitesse de l'algorithme « $\sqrt{N}$ » : il suffit de $O(\sqrt{N})$ itérations pour atteindre la cible, au lieu des $O(N)$ vérifications qu'exigerait une recherche classique.

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

Notez que si vous effectuez trop d'itérations, vous dépasserez le point d' $|A_1\rangle$, et la probabilité de trouver l'état recherché recommencera à diminuer. Il est important de déterminer le nombre adéquat d'itérations, même si, sur du matériel quantique sujet au bruit, le nombre optimal d'un point de vue expérimental peut s'écarter de cette formule idéale.

En quoi l'algorithme de Grover est-il utile?

À ce stade, vous vous demandez peut-être : nous venons de créer un oracle qui identifie un état cible, mais pour le créer, il fallait que nous connaissions cet état cible. Mais au fond, qu'est-ce qu'on cherche vraiment?

C'est une bonne question, et il y a plusieurs réponses valables.

• Le modèle de requête est un outil théorique. Le modèle de calcul par requêtes n'a jamais été conçu pour être directement applicable. Son objectif est de nous offrir un moyen simple d'analyser la complexité algorithmique en décomposant un problème en deux parties : l'oracle et tout le reste. La recherche est-elle difficile, étant donné que la vérification est gratuite? Comment le nombre de requêtes évolue-t-il en fonction de la taille des données d'entrée? Ce sont des questions pertinentes, même si aucun système concret ne fonctionne exactement de cette manière.

• On peut également considérer cela comme une activité à deux : l'une des personnes connaît l'état cible et construit l'oracle; l'autre a pour tâche de trouver la réponse en utilisant l'oracle comme une boîte noire, sans pouvoir en voir le contenu. Dans l'activité 2 ci-dessous, c'est exactement ce que vous allez faire avec un partenaire.

• L'amplification d'amplitude est une sous-routine très utile. Même si cette première démonstration semble circulaire, le mécanisme sous-jacent — appelé amplification d'amplitude — revient sans cesse dans l'informatique quantique. Ce que nous sommes en train de développer ici, c'est une compréhension intuitive d'un outil qui apparaît comme une sous-routine dans de nombreux algorithmes quantiques bien plus complexes.

• Il existe des problèmes pour lesquels on peut construire un oracle sans connaître la réponse. L'idée principale est qu'il existe toute une catégorie 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. Le calcul des facteurs est un exemple : étant donné le produit de deux grands nombres premiers, il est extrêmement difficile de déterminer quels sont ces nombres premiers, mais une fois qu'on les connaît, on peut facilement les multiplier pour vérifier. (Nous disposons d'un algorithme plus performant que celui de Grover pour la factorisation en particulier — voir l'algorithme de Shor — mais ce n'est de loin pas le seul problème lié à cette fonctionnalité.) Le sudoku, la résolution de contraintes et même le jeu classique du Démineur sont autant de problèmes difficiles à résoudre mais faciles à vérifier.

En quoi cela est-il pertinent? Cela signifie que nous pouvons connaître toutes les conditions et exigences auxquelles une solution doit satisfaire, et que nous pouvons coder ces exigences dans un circuit quantique qui fait office d'oracle — même si nous ne connaissons pas la solution elle-même. L'algorithme de Grover le trouvera pour nous.

En gardant ces idées à l'esprit, examinons quelques exemples. Nous commencerons par un exemple dans lequel l'état de la solution est clairement défini, afin de pouvoir suivre la logique de l'algorithme. Nous passerons ensuite à une activité à deux participants, puis à un exemple dans lequel l'oracle est construit à partir des contraintes du problème plutôt qu'à partir de la connaissance de la réponse.

Importations générales et approche

Nous commençons par importer plusieurs paquets 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 cours et d'autres tutoriels, nous utiliserons un cadre pour l'informatique quantique connu sous le nom de "modèles Qiskit", qui décompose les flux de travail en plusieurs étapes :

• Etape 1 : Tracer un problème quantique à partir d'entrées classiques
• Étape 2 : Optimisation du problème pour l'exécution quantique
• Étape 3 : Exécution à l'aide des primitives « IBM Quantum »
• Étape 4 : Post-traitement et analyse classique

Nous suivons généralement ces étapes, même si nous ne les mentionnons pas toujours explicitement.

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

Étape 1 : Mettre en correspondance les entrées classiques avec un problème quantique

Nous avons besoin de la porte d'interrogation de phase pour mettre une phase globale (-1) sur les états de solution, et laisser les états de non solution non affectés. Une autre façon de le dire est que l'algorithme de Grover nécessite un oracle qui spécifie un ou plusieurs états de base de calcul marqués, où "marqué" signifie un état avec une phase de -1. Pour ce faire, on utilise une porte Z contrôlée, ou sa généralisation multi-contrôlée sur $N$ qubits. Pour voir comment cela fonctionne, prenons l'exemple spécifique d'une chaîne de bits {110}. Nous aimerions un circuit qui agisse 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, à cause de la notation dans Qiskit, qui place le qubit le moins significatif (souvent 0) à droite).

Nous voulons donc un circuit $Z_f$ qui réalise

Nous pouvons utiliser la porte à contrôle multiple et à cible multiple (MCMTGate) pour appliquer une porte Z contrôlée par tous les qubits (inverser la phase si tous les qubits sont dans l'état $|1\rangle$ ). Bien entendu, certains des qubits dans l'état désiré peuvent être $|0\rangle$. Par conséquent, pour ces qubits, nous devons d'abord appliquer une porte X, puis effectuer la porte Z contrôlée par le multiplicateur, puis appliquer une autre porte X pour annuler notre changement. Le site MCMTGate se présente comme suit :

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

Output:

Notez que plusieurs qubits peuvent être impliqués dans le processus de contrôle (ici trois qubits), mais qu'aucun qubit n'est désigné comme cible. En effet, l'état entier est affecté d'un signe "-" (inversion de phase); la porte affecte tous les qubits de manière équivalente. Cela diffère de beaucoup d'autres portes à qubits multiples, comme la porte CX , qui possède un seul qubit de contrôle et un seul qubit cible.

Dans le code suivant, nous définissons une porte d'interrogation de phase (ou oracle) qui fait ce que nous venons de décrire ci-dessus : marquer un ou plusieurs états de base d'entrée définis par leur représentation en chaîne de bits. La porte MCMT est utilisée pour mettre en œuvre 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

Nous choisissons maintenant un état "marqué" spécifique comme cible et appliquons la fonction que nous venons de définir. Voyons quel type de circuit il a créé.

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

Output:

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 fera basculer le qubit 0 dans l'état $|1\rangle$ et tous les qubits seront dans l'état $|1\rangle.$. Cela signifie que la porte MCMT appliquera un changement de signe global ou une inversion de phase, comme on le souhaite. Dans tous les autres cas, soit les qubits 1 à 3 sont dans l'état $|0\rangle$, soit le qubit 0 est basculé dans l'état $|0\rangle$, et l'inversion de phase ne sera pas appliquée. Nous voyons que ce circuit marque bien l'état désiré $|0111\rangle,$ ou la chaîne de bits {1110}.

L'opérateur de Grover complet se compose de la porte d'interrogation de phase (oracle), des couches de Hadamard et de l'opérateur $Z_\text{OR}$. Nous pouvons utiliser le site intégré grover_operator pour construire ceci à 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")

Output:

Comme nous l'avons vu dans l'illustration géométrique ci-dessus, il se peut que nous devions appliquer l'opérateur de Grover à plusieurs reprises. Le nombre optimal d'itérations $t$ pour maximiser l'amplitude de l'état cible en l'absence de bruit est

où $|A_1|$ correspond au nombre d'états de solution et $N=2^n$ au nombre total d'états. Sur les ordinateurs quantiques modernes, sujets au bruit, le nombre d’itérations optimal d’un point de vue expérimental pourrait être différent; mais ici, nous calculons et utilisons ce nombre optimal théorique à l’aide de l’algorithme de l’ $|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)

Output:

3

Construisons maintenant un circuit qui inclut les portes de 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")

Output:

Nous avons construit notre circuit Grover!

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

Nous avons défini notre circuit quantique abstrait, mais nous devons le réécrire en termes de portes natives de l'ordinateur quantique que nous voulons réellement utiliser. Nous devons également préciser quels qubits de l'ordinateur quantique doivent être utilisés. Pour ces raisons et d'autres encore, nous devons maintenant transposer notre circuit. Tout d'abord, spécifions l'ordinateur quantique que nous souhaitons utiliser.

Le code ci-dessous vous permet de sauvegarder vos données d'identification lors de la première utilisation. Veillez à supprimer ces informations du bloc-notes après l'avoir enregistré dans votre environnement, afin que vos informations d'identification ne soient pas accidentellement partagées lorsque vous partagez le bloc-notes. Voir Configurer votre compte IBM Cloud et Initialiser le service dans un environnement non fiable pour plus d'informations.

# 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

Output:

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 transposé est considérable.

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),
)

Output:

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

Il s'agit en fait de nombres assez importants, même pour ce cas simple. Étant donné que toutes les portes quantiques (et en particulier les portes à deux qubits) sont entachées d'erreurs et sujettes 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 ce qu'il en est.

Étape 3 : Exécution à l'aide des primitives « IBM Quantum »

Nous souhaitons effectuer de nombreuses mesures afin de déterminer quel état est le plus probable. Une telle amplification d'amplitude est un problème d'échantillonnage qui se prête bien à une exécution à l'aide de la primitive Sampler « IBM Quantum ».

Notez que la méthode run() IBM Quantum de SamplerV2 prend en paramètre un itérable de blocs unifiés primitifs (PUB). Pour Sampler, chaque « PUB » est un objet itérable au format (circuit, parameter_values). Toutefois, il faut au minimum une liste de circuits quantiques.

# 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 vous recommandons vivement de réaliser vos expériences sur les véritables ordinateurs quantiques disponibles sur IBM Quantum. Cependant, si vous avez épuisé votre temps QPU, vous pouvez décommenter les lignes ci-dessous pour réaliser cette activité à l'aide d'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 restitution du résultat dans le format classique souhaité

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

plot_distribution(dist)

Output:

Nous constatons que l'algorithme de Grover renvoie l'état souhaité avec la probabilité la plus élevée, au moins un ordre de grandeur plus élevé que les autres options. Dans l'activité suivante, nous utiliserons l'algorithme d'une manière plus cohérente avec le flux de travail bipartite d'un algorithme de requête.

Vérifiez votre compréhension

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

• Réponse

  Rappelons que tant que le nombre de solutions est faible par rapport à l'ensemble de l'espace des solutions, nous pouvons développer la fonction sinus autour de petits angles et utiliser la fonction

  $$(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) L'expression ci-dessus montre que l'augmentation du nombre d'états de solution diminue le nombre d'itérations. Pour autant que la fraction $\frac{|\mathcal{A}_1|}{N}$ soit encore petite, nous pouvons décrire comment $t$ diminuerait : $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

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

Supposons que nous puissions augmenter la taille de la chaîne de bits cible pour qu'elle soit arbitrairement longue et que nous obtenions toujours le résultat que l'état cible a une amplitude de probabilité qui est au moins un ordre de grandeur plus grand que n'importe quel autre état. Cela signifie-t-il que nous pourrions utiliser l'algorithme de Grover pour trouver de manière fiable l'état cible?

• Réponse

  Non. Supposons que nous ayons répété la première activité avec 20 qubits et que nous exécutions 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é ne serait-ce qu'une seule fois. Si la probabilité de mesurer l'état cible était 10 fois supérieure à celle des non-solutions (et que la probabilité de chaque non-solution était en conséquence légèrement diminuée), il n'y aurait qu'environ 10 % de chances de mesurer l'état cible ne serait-ce qu'une seule fois. Il serait très improbable de mesurer l'état cible plusieurs fois, ce qui le rendrait indiscernable des nombreux états de non-solution obtenus de manière aléatoire. La bonne nouvelle est que nous pouvons obtenir des résultats encore plus fidèles en utilisant la suppression et l'atténuation des erreurs.

Activité 2 : un algorithme de requête précis

Nous commencerons cette activité exactement comme la première, sauf que vous ferez maintenant équipe avec un autre enthousiaste du Qiskit. Vous choisirez une chaîne de bits secrète et votre partenaire choisira une chaîne de bits (généralement) différente. Vous générerez chacun un circuit quantique qui fonctionnera comme un oracle, et vous les échangerez. Vous utiliserez ensuite l'algorithme de Grover avec cet oracle pour déterminer la chaîne de bits secrète de votre partenaire.

Étape 1 : Mettre en correspondance les entrées classiques avec un problème quantique

En utilisant la fonction grover_oracle définie ci-dessus, construire un circuit oracle pour un ou plusieurs états marqués. Veillez à indiquer à votre partenaire le nombre d'états que vous avez marqués, afin qu'il puisse appliquer l'opérateur de Grover le nombre optimal de fois. Ne rendez pas votre chaîne de bits trop longue. 3-5 bits devraient fonctionner sans trop de difficultés. Des chaînes de bits plus longues donneraient lieu à des circuits profonds qui nécessiteraient des techniques plus avancées telles que l'atténuation des erreurs.

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

Vous avez maintenant créé un circuit quantique qui inverse la phase de votre état cible. Vous pouvez enregistrer 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)

Envoyez ensuite ce fichier à votre partenaire (par courrier électronique, service de messagerie, dépôt partagé, etc.) Demandez à votre partenaire de vous envoyer également son circuit. Veillez à enregistrer le fichier dans un endroit où vous pourrez facilement le retrouver. Une fois que vous avez le circuit de votre partenaire, vous pouvez le visualiser, mais cela rompt le modèle d'interrogation. En d'autres termes, nous modélisons une situation dans laquelle vous pouvez interroger l'oracle (utiliser le circuit de l'oracle) mais pas l'examiner pour déterminer l'état qu'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")

Demandez à votre partenaire combien d'états cibles il a encodés et inscrivez-le ci-dessous.

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

Cette valeur est utilisée 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 du matériel quantique

La procédure est la même que 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écution à l'aide des primitives « IBM Quantum »

Ce processus est également identique à celui 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 restitution du résultat dans le format classique souhaité

Affichez maintenant un histogramme de vos résultats d'échantillonnage. Un ou plusieurs états devraient avoir une probabilité de mesure beaucoup plus élevée que les autres. Signalez-les à votre partenaire et vérifiez si vous avez correctement déterminé les états cibles. Par défaut, l'histogramme affiché est celui du même circuit que celui de la première activité. Vous devriez obtenir des résultats différents du circuit de votre partenaire.

plot_distribution(dist)

Output:

Vérifiez votre compréhension

Vous devez avoir obtenu correctement le(s) État(s) cible(s) de votre partenaire. Si ce n'est pas le cas, identifiez avec votre partenaire ce qui n'a pas fonctionné. Vous trouverez ci-dessous quelques idées.

• Astuces
  • Visualisez/dessinez le circuit de votre partenaire et assurez-vous qu'il se charge correctement.
  • Comparez les circuits utilisés et comparez le résultat attendu à celui que vous avez obtenu.
  • Vérifiez la profondeur des circuits utilisés pour vous assurer que la chaîne de bits n'est pas trop longue ou que le nombre d'itérations de Grover n'est pas prohibitif.

Si vous ne l'avez pas encore fait, dessinez le circuit oracle que votre partenaire vous a envoyé. Voyez si vous pouvez parler de l'effet de chaque porte et expliquer quel devait être l'état cible. Cela sera beaucoup plus facile dans le cas d'un seul État marqué que dans le cas de plusieurs États.

• Astuces
  • Rappelons que le rôle de l'oracle est d'inverser le signe sur l'état cible.
  • Rappelons que la porte MCMTGate inverse le signe d'un état si et seulement si tous les qubits impliqués dans le contrôle sont dans l'état $|1\rangle$.
  • Si votre état cible a déjà un $|1\rangle$ sur un qubit particulier, vous n'avez rien à faire sur ce qubit. Si votre cible a un $|0\rangle$ sur un qubit particulier et que vous voulez que le MCMTGate inverse le signe, vous devez appliquer une porte X à ce qubit dans votre oracle (puis annuler la porte X après le MCMTGate).

Répétez l'expérience avec une itération de moins de l'opérateur de Grover. Obtenez-vous toujours la bonne réponse? Pourquoi ?

• Conseils

  C'est probablement le cas, mais cela peut dépendre du nombre de solutions encodées. Ceci 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 peut encore rendre l'état marqué nettement plus probable que d'autres états. Par conséquent, il est possible de s'en sortir avec un nombre d'itérations inférieur au nombre optimal. Cela réduit la profondeur du circuit et donc 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 peut encore rendre l'état marqué nettement plus probable que d'autres états. Il est donc possible de s'en sortir avec un nombre d'itérations inférieur au nombre optimal. Cela réduit la profondeur du circuit et donc les taux d'erreur.

Activité 3 : Résoudre une grille de Démineur à l'aide de l'algorithme de Grover

Dans la section précédente, nous avons noté que l'algorithme de Grover devient véritablement utile lorsque l'on peut construire un oracle à partir des contraintes d'un problème, plutôt qu'à partir de la connaissance de la réponse. Le Démineur en est un parfait exemple : les cases numérotées nous indiquent combien de mines se trouvent à proximité, et ces contraintes déterminent entièrement l'emplacement des mines — mais pour trouver la configuration, il faut effectuer une recherche.

Il a été démontré que le Démineur est un problème NP-complet : il est difficile à résoudre, mais facile à vérifier. Cela en fait donc un candidat tout désigné pour l'algorithme de Grover. Bien sûr, nous ne pouvons pas encore résoudre une grille complète 9 $\times$ 9 sur un ordinateur quantique bruyant — les circuits seraient beaucoup trop profonds. Nous utiliserons plutôt une petite grille pour illustrer, à titre d'exemple, comment on pourrait aborder un tableau plus grand sur une future machine tolérante aux pannes.

Quelques précisions importantes. L'algorithme de Grover n'offre qu'un gain de vitesse quadratique par rapport à la recherche classique non structurée. Il est presque certain que le Démineur présente une structure exploitable qu'un algorithme classique bien conçu pourrait mettre à profit. Et dans un espace de recherche qui croît de manière exponentielle, même l'amélioration apportée par l' $\sqrt{N}$ e a ses limites. Mais mettons ces préoccupations de côté et utilisons ce problème fictif pour illustrer comment les contraintes d'un problème sont encodées dans un oracle quantique.

La grille

Voici notre grille de Démineur pour enfants :

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

Nous pourrions résoudre ce problème mentalement en une demi-seconde environ, mais nous utilisons cet exemple simplifié pour montrer comment un problème bien plus complexe pourrait être abordé à l'aide d'un ordinateur quantique.

Encodez les contraintes

Chaque case numérotée impose une condition aux cases vides adjacentes. Nous devons exprimer ces conditions sous forme d'expressions booléennes pouvant être codées dans un circuit quantique.

La case « 1 » située à côté de $x_0$ et $x_1$ indique qu'exactement l'une d'entre elles contient une mine. Il s'agit précisément de l'opération « OU exclusif » (XOR), $\oplus$, qui renvoie « vrai » lorsque n'exactement qu'une seule de ses entrées est vraie :

De même, l'autre cellule contenant un « 1 » (à côté de $x_1$ et $x_2$ ) nous donne :

La case « 2 » indique que deux des trois cases vides doivent contenir des mines. Comme l'opération XOR est une opération de parité, la fonction « $x_0 \oplus x_1 \oplus x_2$ » renvoie « vrai » lorsqu'un nombre impair de variables est vrai. Nous voulons qu'un nombre pair (plus précisément deux) soit vrai, nous appliquons donc la négation à l'aide de l' $\lnot$ :

En soi, cette expression serait satisfaite soit par zéro, soit par deux qubits dans l'état d' $|1\rangle$, puisqu'il s'agit d'une affirmation concernant la parité. Mais si l'on tient compte des deux autres conditions, qui exigent chacune au moins une mine, la seule solution valable comporte exactement deux mines.

Ces trois conditions doivent être remplies simultanément; nous les relions donc à l'aide des symboles « et » $\land$ :

Étape 1 : Mettre en correspondance les entrées classiques avec un problème quantique

Nous devons maintenant traduire cette expression booléenne en un circuit quantique qui servira d'oracle. La version quantique de la fonction XOR peut être réalisée à l'aide de portes CX (CNOT) : l'application de deux portes CX entre les qubits de données et un qubit de l'espace de travail (ancilla) permet de calculer efficacement leur XOR et de stocker le résultat dans l'ancilla.

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

Dans la première cellule de code ci-dessous, nous construisons la partie « calcul » de l'oracle — celle qui évalue chaque clause et enregistre le résultat dans les qubits de l'espace 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 le qubit correspondant de l'espace de travail. Il nous faut maintenant l'état de données à trois qubits qui fait que les trois qubits de l'espace de travail, tous d' $|1\rangle$, prennent un signe négatif. Pour ce faire, nous utilisons une porte Z à contrôles multiples (implémentée sous la forme d'une porte MCX encadrée par des portes de Hadamard sur la cible).

Après avoir appliqué l'inversion de phase, il faut «** défaire le calcul** » — c'est-à-dire annuler toutes les étapes d'évaluation des clauses dans l'ordre inverse — afin de réinitialiser les qubits de l'espace de travail à l'état « $|0\rangle.$ ». Cette opération est essentielle pour que les qubits de l'espace 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 du qubit de données qui satisfait aux trois contraintes du Démineur, et ramène les qubits de l'espace de travail à l' $|0\rangle.$

Nous allons maintenant construire l'opérateur de Grover complet à partir de cet oracle. xRemarque concernant reflection_qubits l'argument : nous ne transmettons que les qubits de données, car les qubits de l'espace 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 de solution, le nombre optimal d'itérations de Grover est de $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$; nous utilisons donc deux itérations. Nous appliquons des portes de Hadamard aux qubits de données pour créer la superposition initiale, nous composons deux fois l'opérateur de Grover, puis nous 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 du 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é. Étant donné que l'oracle « Démineur » utilise des qubits d'espace 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écution à l'aide des primitives « IBM Quantum »

# 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 restitution du résultat dans le format classique souhaité

plot_distribution(dist)

L'état 101 devrait apparaître avec une probabilité bien plus élevée que tout autre, ce qui indique que les mines se trouvent à $x_0$ et $x_2$. Nous avons utilisé un ordinateur quantique pour résoudre une petite partie de Démineur!

Bien sûr, les meilleurs algorithmes classiques pour le Démineur sont plus efficaces qu'une recherche par force brute passant en revue toutes les configurations possibles de mines : ils tirent parti de la structure de la grille. L'algorithme de Grover n'offrirait un avantage que sur des tableaux extrêmement complexes, conçus pour être aussi ambigus que possible; et même dans ce cas, son gain de vitesse quadratique signifie qu'il ne peut pas suivre indéfiniment une croissance exponentielle. Mais ce qu'il faut surtout retenir, c'est la technique : l'encodage des contraintes d'un problème dans un oracle quantique est un modèle puissant qui s'applique à la satisfaction de contraintes, à l'optimisation combinatoire et à bien d'autres domaines.

Questions et notions clés :

Concepts essentiels :

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 en fonction de la taille de l'espace, l'algorithme de Grover ( $N,$ ) nécessite un nombre de requêtes qui évolue de la manière suivante $\sqrt{N}.$
• L'algorithme de Grover consiste à répéter une série d'opérations (communément appelées "opérateur de Grover") un certain nombre de fois $t,$ choisies pour que les états cibles aient une probabilité optimale d'être mesurés.
• L'algorithme de Grover peut être exécuté avec moins de $t$ itérations et amplifier encore les états cibles.
• L'algorithme de Grover s'inscrit dans le modèle d'interrogation de l'informatique et prend tout son sens lorsqu'une personne contrôle la recherche et qu'une autre contrôle/construit l'oracle. Il peut également être utile en tant que sous-programme dans d'autres calculs quantiques.
• Un oracle peut être construit à partir des contraintes du problème plutôt qu'à partir de la connaissance de la solution, comme le montre l'exemple du Démineur.

Questions vrai/faux :

1. T/F L'algorithme de Grover apporte une amélioration exponentielle par rapport aux algorithmes classiques en ce qui concerne le nombre de requêtes nécessaires pour trouver un seul état marqué dans le cadre d'une recherche non structurée.

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

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

Questions du MC :

1. Sélectionnez 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 consiste à itérer l'opérateur de Grover...

• a. Une seule fois.
• b. Toujours $t$ fois, pour maximiser l'amplitude de la probabilité de l'état ou des états de la solution.
• c. Jusqu'à $t$ fois, mais un nombre inférieur peut suffire à faire ressortir les États de la solution.
• d. Pas moins de 10 fois.

2. Un circuit d'interrogation de phase est montré ici, qui fonctionne comme un oracle pour marquer un certain état avec un changement de phase. Parmi les états suivants, lesquels sont marqués par ce circuit?

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

3. Supposons que vous souhaitiez rechercher trois états marqués parmi 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 à débattre :

1. Quels autres problèmes pourriez-vous formuler sous forme de recherche de Grover? Pensez à des problèmes pour lesquels il est difficile de trouver une solution, mais facile d'en vérifier une.

2. La mise à l'échelle de l'algorithme de Grover sur les ordinateurs quantiques modernes pose-t-elle des problèmes?