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.

Mathématiques

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®.

Mise en garde évidente

Pour appliquer l'algorithme de Grover, nous avons dû construire l'opérateur de Grover, ce qui signifie que nous devons être capables de retourner la phase sur les états qui satisfont nos critères de solution. Cela soulève la question : si nous connaissons si bien notre ensemble de solutions que nous pouvons concevoir un circuit quantique pour étiqueter chacune, que cherchons-nous ?! La réponse est triple, et nous y reviendrons tout au long du tutoriel :

(1) Ces types d'algorithmes de requête impliquent souvent deux parties : l'une qui possède l'oracle qui établit les critères de solution, et l'autre qui essaie de deviner/trouver un état solution. Le fait qu'une personne puisse construire l'oracle ne nie pas le besoin de recherche.

(2) Il existe des problèmes pour lesquels il est plus facile de spécifier un critère de solution que de trouver la solution. L'exemple le plus connu est probablement l'identification des facteurs premiers de grands nombres. L'algorithme de Grover n'est pas particulièrement efficace pour résoudre ce problème spécifique ; on utiliserait l'algorithme de Shor pour la factorisation première. C'est juste un exemple pour souligner que connaître le critère sur le comportement d'un état n'est pas toujours la même chose que connaître l'état.

(3) L'algorithme de Grover ne renvoie pas seulement des données classiques. C'est vrai, si on mesure l'état final après $t$ répétitions de l'opérateur de Grover, on est susceptible d'obtenir des informations classiques identifiant l'état solution. Mais si on ne veut pas d'informations classiques ; si on veut un état solution préparé sur un ordinateur quantique pour une utilisation ultérieure dans un autre algorithme ? L'algorithme de Grover produit en réalité un état quantique avec les solutions fortement pondérées. On peut donc s'attendre à trouver l'algorithme de Grover comme sous-routine dans des algorithmes quantiques plus complexes.

Avec cela à 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, et nous passerons à des exemples dans lesquels l'utilité de l'algorithme de Grover devient plus claire.

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
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 argumenté 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 peut être obtenu à partir de cette expression :

$$(2t+1)\theta = (2t+1)\sin^{-1}\left( \sqrt{\frac{|A_1|}{N}}\right) \approx (2t+1)\sqrt{\frac{|A_1|}{N}} \approx \frac{\pi}{2}\\ t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

Ici $A_1$ est le nombre de solutions ou d'états cibles. 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.

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 : Critère autre qu'une chaîne de bits spécifique

Comme illustration finale de la façon dont l'algorithme de Grover pourrait être utile dans le contexte d'une sous-routine, imaginons que nous ayons besoin d'états quantiques avec un certain nombre de 1 dans leur représentation en chaîne de bits. C'est courant dans les situations où des lois de conservation sont impliquées. Par exemple, dans le contexte de la chimie quantique, on mappe souvent un état 1 d'un qubit à l'occupation d'une orbitale électronique. Pour que la charge soit conservée, le nombre total de 1 doit également rester constant. De telles contraintes sont si courantes qu'elles ont un nom spécial : contraintes de poids de Hamming, et le nombre de 1 dans l'état est appelé le poids de Hamming.

Étape 1 :

Commençons par écrire une fonction qui marque les états avec le poids de Hamming désiré. Nous l'écrirons en général pour un nombre non spécifié de qubits num_qubits et un poids de Hamming cible target_weight.

from qiskit import QuantumCircuit

def grover_oracle_hamming_weight(num_qubits, target_weight):
    """
    Build a Grover oracle that marks all states with Hamming weight == target_weight.

    Parameters:
        num_qubits (int): Number of qubits in the circuit.
        target_weight (int): The Hamming weight to mark.

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle.
    """
    qc = QuantumCircuit(num_qubits)
    marked_count = 0
    marked_list = []
    for x in range(2**num_qubits):
        bitstr = format(x, f"0{num_qubits}b")
        if bitstr.count("1") == target_weight:
            # Count the number of target states
            marked_count = marked_count + 1
            marked_list.append(bitstr)
            # Reverse for Qiskit bit order (qubit 0 is rightmost)
            rev_target = bitstr[::-1]
            zero_inds = [i for i, b in enumerate(rev_target) if b == "0"]
            # Apply X gates to 'open' controls (where bit is 0)
            qc.x(zero_inds)
            # Multi-controlled Z (as MCX conjugated by H)
            if num_qubits == 1:
                qc.z(0)
            else:
                qc.h(num_qubits - 1)
                qc.mcx(list(range(num_qubits - 1)), num_qubits - 1)
                qc.h(num_qubits - 1)
            # Undo X gates
            qc.x(zero_inds)
    return qc, marked_count, marked_list

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(3, 2)
print(marked_states)
oracle.draw(output="mpl", style="iqp")

['011', '101', '110']

À partir de là, l'ensemble du processus est identique à celui des deux activités précédentes. Par souci de concision, les étapes des Qiskit patterns ne sont montrées qu'en commentaires de code ici.

from qiskit_ibm_runtime import SamplerV2 as Sampler

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(4, 2)
oracle.draw(output="mpl", style="iqp")

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(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()
qc.draw(output="mpl", style="iqp")

# Step 2: Optimize for running on real quantum computers

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)

# Step 3: Execute using Qiskit primitives
# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

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

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

ibm_brisbane

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  502
The depth of two-qubit gates is  130

num_marked_states

6

plot_distribution(dist)

Ici, l'algorithme de Grover a effectivement préparé les états avec un poids de Hamming de 2 pour qu'ils soient bien plus susceptibles d'être mesurés que tout autre état, environ un ordre de grandeur plus susceptibles.

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.

Questions

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. Quelles autres conditions pourrais-tu utiliser dans un oracle quantique ? Considère des conditions qui sont faciles à énoncer ou à imposer sur une chaîne de bits mais ne consistent pas simplement à écrire les chaînes de bits marquées.