{ "cells": [ { "cell_type": "markdown", "id": "76d7b924", "metadata": {}, "source": [ "---\n", "title: \"Algorithme de Grover\"\n", "description: \"Utilisez l'algorithme de Grover pour effectuer une recherche dans une base de données non structurée avec un gain de vitesse quadratique.\"\n", "---\n", "\n", "{/* cspell:ignore fontsize */}\n", "\n", "\n", "\n", "# Algorithme de Grover\n", "\n", "*Estimation du temps d'exécution : moins d'une minute sur un processeur Eagle r3 (REMARQUE : il s'agit uniquement d'une estimation. (Votre temps d'exécution peut varier.)*\n", "\n" ] }, { "cell_type": "markdown", "id": "88aa4204", "metadata": {}, "source": [ "\n", "\n", "## Résultats d'apprentissage\n", "\n", "À l'issue de ce tutoriel, vous devriez être en mesure de comprendre les points suivants :\n", "\n", "* Comment construire des oracles de Grover qui marquent un ou plusieurs états de la base de calcul\n", "* Comment utiliser la `grover_operator()` fonction de la bibliothèque de circuits Qiskit\n", "* Comment déterminer le nombre optimal d'itérations de Grover pour un problème donné\n", "* Comment mettre en œuvre l'algorithme de Grover à l'aide de la primitive « Sampler » de l' IBM Quantum\n", "\n", "\n", "\n", "## Prérequis\n", "\n", "Nous vous recommandons de vous familiariser avec les sujets suivants :\n", "\n", "* [Principes fondamentaux des algorithmes quantiques : l'algorithme de Grover](/learning/courses/fundamentals-of-quantum-algorithms/grover-algorithm/introduction)\n", "* [Notions de base sur l’information quantique](/learning/courses/basics-of-quantum-information)\n", "\n", "\n", "\n", "## Arrière-plan\n", "\n", "L'amplification d'amplitude est un algorithme quantique polyvalent, ou sous-programme, qui permet d'obtenir un gain de vitesse quadratique par rapport à plusieurs algorithmes classiques. [L'algorithme de Grover](https://arxiv.org/abs/quant-ph/9605043) a été le premier à démontrer ce gain de vitesse pour les problèmes de recherche non structurés. Pour formuler un problème de recherche de Grover, il faut une fonction oracle qui identifie un ou plusieurs états de la base de calcul comme étant ceux que l'on cherche à trouver, ainsi qu'un circuit d'amplification qui augmente l'amplitude des états identifiés, supprimant ainsi les états restants.\n", "\n", "Nous montrons ici comment construire des oracles de Grover et utiliser la bibliothèque de circuits Qiskit pour mettre en place facilement une instance de recherche de Grover [`grover_operator()`](/docs/api/qiskit/qiskit.circuit.library.grover_operator) de la bibliothèque de circuits Qiskit pour mettre en place facilement une instance de recherche de Grover. La primitive `Sampler` permet l'exécution transparente des circuits Grover.\n", "\n" ] }, { "cell_type": "markdown", "id": "5bbba268", "metadata": {}, "source": [ "\n", "\n", "## Exigences\n", "\n", "Avant de commencer ce tutoriel, assurez-vous d'avoir installé les éléments suivants :\n", "\n", "* Qiskit SDK v2.0 ou version ultérieure, avec prise en charge [de la visualisation](/docs/api/qiskit/visualization)\n", "* Qiskit Runtime v0.22 ou version ultérieure (`pip install qiskit-ibm-runtime`)\n", "\n" ] }, { "cell_type": "markdown", "id": "bfccad15", "metadata": {}, "source": [ "\n", "\n", "## Configuration\n", "\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "e2cb0472", "metadata": {}, "outputs": [], "source": [ "# Built-in modules\n", "import math\n", "\n", "# Imports from Qiskit\n", "from qiskit import QuantumCircuit\n", "from qiskit.circuit.library import grover_operator, MCMTGate, ZGate\n", "from qiskit.visualization import plot_distribution\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "\n", "# Imports from qiskit-ibm-runtime\n", "from qiskit_ibm_runtime import QiskitRuntimeService\n", "from qiskit_ibm_runtime import SamplerV2 as Sampler\n", "\n", "\n", "def grover_oracle(marked_states):\n", " \"\"\"Build a Grover oracle for multiple marked states\n", "\n", " Here we assume all input marked states have the same number of bits\n", "\n", " Parameters:\n", " marked_states (str or list): Marked states of oracle\n", "\n", " Returns:\n", " QuantumCircuit: Quantum circuit representing Grover oracle\n", " \"\"\"\n", " if not isinstance(marked_states, list):\n", " marked_states = [marked_states]\n", " # Compute the number of qubits in circuit\n", " num_qubits = len(marked_states[0])\n", "\n", " qc = QuantumCircuit(num_qubits)\n", " # Mark each target state in the input list\n", " for target in marked_states:\n", " # Flip target bit-string to match Qiskit bit-ordering\n", " rev_target = target[::-1]\n", " # Find the indices of all the '0' elements in bit-string\n", " zero_inds = [\n", " ind\n", " for ind in range(num_qubits)\n", " if rev_target.startswith(\"0\", ind)\n", " ]\n", " # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)\n", " # where the target bit-string has a '0' entry\n", " if zero_inds:\n", " qc.x(zero_inds)\n", " qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)\n", " if zero_inds:\n", " qc.x(zero_inds)\n", " return qc" ] }, { "cell_type": "markdown", "id": "77e41aba", "metadata": {}, "source": [ "\n", "\n", "## Exemple de simulateur à petite échelle\n", "\n", "Dans cette section, nous passons en revue chaque étape de l'algorithme de Grover à petite échelle à l'aide d'un simulateur local, avant d'appliquer ce même problème à du matériel quantique réel.\n", "\n" ] }, { "cell_type": "markdown", "id": "0c0fb667", "metadata": {}, "source": [ "\n", "\n", "### Étape 1 : Mettre en correspondance les entrées classiques avec un problème quantique\n", "\n", "L'algorithme de Grover nécessite un [oracle](/learning/modules/computer-science/grovers#introduction) qui spécifie un ou plusieurs états de base de calcul « marqués », le terme « marqué » désignant un état dont la phase est égale à -1. Une porte à Z contrôlé, ou sa généralisation à contrôles multiples sur des qubits d' $N$, définit l'état d' $2^{N}-1$ (`'1'`\\*chaîne de bits $N$ ). Pour marquer les états de base avec un ou plusieurs `'0'` dans la représentation binaire, il faut appliquer des portes X aux qubits correspondants avant et après la porte Z contrôlée, ce qui revient à appliquer une commande ouverte à ce qubit. Dans le code suivant, nous définissons un oracle qui identifie un ou plusieurs états de base d'entrée définis par leur représentation sous forme de chaîne binaire. Cette `MCMT` porte sert à mettre en œuvre la porte Z à commandes multiples.\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "id": "bca14740", "metadata": {}, "source": [ "\n", "\n", "### Cas spécifique de Grover\n", "\n", "Maintenant que nous disposons de la fonction oracle, nous pouvons définir une instance spécifique de la recherche de Grover. Dans cet exemple, nous marquerons deux états de calcul sur les huit disponibles dans un espace de calcul à trois qubits :\n", "\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "c150298f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "marked_states = [\"011\", \"100\"]\n", "\n", "oracle = grover_oracle(marked_states)\n", "oracle.draw(output=\"mpl\", style=\"iqp\")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "25487b93", "metadata": {}, "source": [ "\n", "\n", "### opérateur Grover\n", "\n", "La fonction intégrée Qiskit `grover_operator()` prend un circuit d'oracle et renvoie un circuit composé du circuit d'oracle lui-même et d'un circuit qui amplifie les états marqués par l'oracle. Ici, nous utilisons la méthode `decompose()` pour voir les portes à l'intérieur de l'opérateur :\n", "\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "283d5265", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "grover_op = grover_operator(oracle)\n", "grover_op.decompose().draw(output=\"mpl\", style=\"iqp\")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "83c34dc9", "metadata": {}, "source": [ "Les applications répétées de ce circuit `grover_op` amplifient les états marqués, ce qui en fait les chaînes de bits les plus probables dans la distribution de sortie du circuit. Le nombre optimal de ces applications est déterminé par le rapport entre les états marqués et le nombre total d'états de calcul possibles :\n", "\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "f4c3d4b5", "metadata": {}, "outputs": [], "source": [ "optimal_num_iterations = math.floor(\n", " math.pi\n", " / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))\n", ")" ] }, { "attachments": {}, "cell_type": "markdown", "id": "e06c8238", "metadata": {}, "source": [ "\n", "\n", "### Circuit Grover complet\n", "\n", "Une expérience de Grover complète commence par une porte de Hadamard sur chaque qubit, créant une superposition paire de tous les états de base de calcul, suivie de l'opérateur de Grover (`grover_op`) répété le nombre optimal de fois. Nous utilisons ici la méthode `QuantumCircuit.power(INT)` pour appliquer de manière répétée l'opérateur de Grover.\n", "\n" ] }, { "cell_type": "code", "execution_count": 5, "id": "4933ae44", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "qc = QuantumCircuit(grover_op.num_qubits)\n", "# Create even superposition of all basis states\n", "qc.h(range(grover_op.num_qubits))\n", "# Apply Grover operator the optimal number of times\n", "qc.compose(grover_op.power(optimal_num_iterations), inplace=True)\n", "# Measure all qubits\n", "qc.measure_all()\n", "qc.draw(output=\"mpl\", style=\"iqp\")" ] }, { "cell_type": "markdown", "id": "0649c854", "metadata": {}, "source": [ "\n", "\n", "### Étape 2 : Optimiser le problème pour l'exécution sur du matériel quantique\n", "\n", "Pour la simulation à petite échelle, nous compilons le circuit sans le destiner à un matériel spécifique.\n", "\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "c4f67f35", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pm = generate_preset_pass_manager(optimization_level=3)\n", "circuit_isa = pm.run(qc)\n", "circuit_isa.draw(output=\"mpl\", idle_wires=False, style=\"iqp\")" ] }, { "cell_type": "markdown", "id": "4e0d4d90", "metadata": {}, "source": [ "\n", "\n", "### Étape 3 : Exécutez à l'aide d' Qiskit primitives\n", "\n", "L'amplification d'amplitude est un problème d'échantillonnage qui se prête bien à une exécution à l'aide de la [`SamplerV2`](/docs/api/qiskit-ibm-runtime/sampler-v2) primitive. Ici, nous utilisons le `StatevectorSampler` de `qiskit.primitives` pour la simulation locale.\n", "\n" ] }, { "cell_type": "code", "execution_count": 7, "id": "7666ad7c", "metadata": {}, "outputs": [], "source": [ "from qiskit.primitives import StatevectorSampler\n", "\n", "sampler = StatevectorSampler()\n", "result = sampler.run([circuit_isa], shots=10_000).result()\n", "dist = result[0].data.meas.get_counts()" ] }, { "cell_type": "markdown", "id": "5c8263c7", "metadata": {}, "source": [ "\n", "\n", "### Étape 4 : Post-traitement et restitution du résultat dans le format classique souhaité\n", "\n" ] }, { "cell_type": "code", "execution_count": 8, "id": "a5ef9913", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "plot_distribution(dist)" ] }, { "cell_type": "markdown", "id": "2b45b2ee", "metadata": {}, "source": [ "\n", "\n", "## Exemple de matériel\n", "\n" ] }, { "cell_type": "markdown", "id": "5fb22680", "metadata": {}, "source": [ "\n", "\n", "### Étapes 1 à 4\n", "\n", "L'algorithme de Grover est fondamentalement un algorithme tolérant aux pannes : les portes Z à contrôles multiples qui constituent le cœur de l'oracle et de l'opérateur de diffusion entraînent des profondeurs de porte à deux qubits qui augmentent très rapidement avec le nombre de qubits (comme nous le montrerons dans la section suivante). Cela signifie que l'algorithme ne s'adapte pas bien au matériel actuel, souvent sujet à des interférences. C'est pourquoi nous présentons l'exécution matérielle à la même petite échelle que l'exemple de simulation ci-dessus, plutôt que de nous attaquer à un problème de plus grande envergure.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "be3c3d9e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# -------------------------Step 1-------------------------\n", "marked_states = [\"011\", \"100\"]\n", "\n", "oracle = grover_oracle(marked_states)\n", "grover_op = grover_operator(oracle)\n", "\n", "optimal_num_iterations = math.floor(\n", " math.pi\n", " / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))\n", ")\n", "\n", "qc = QuantumCircuit(grover_op.num_qubits)\n", "qc.h(range(grover_op.num_qubits))\n", "qc.compose(grover_op.power(optimal_num_iterations), inplace=True)\n", "qc.measure_all()\n", "\n", "# -------------------------Step 2-------------------------\n", "service = QiskitRuntimeService()\n", "backend = service.least_busy(\n", " operational=True, simulator=False, min_num_qubits=127\n", ")\n", "\n", "target = backend.target\n", "pm = generate_preset_pass_manager(target=target, optimization_level=3)\n", "circuit_isa = pm.run(qc)\n", "\n", "# -------------------------Step 3-------------------------\n", "sampler = Sampler(mode=backend)\n", "sampler.options.default_shots = 10_000\n", "sampler.options.environment.job_tags = [\"TUT-GA\"]\n", "result = sampler.run([circuit_isa]).result()\n", "dist = result[0].data.meas.get_counts()\n", "\n", "# -------------------------Step 4-------------------------\n", "plot_distribution(dist)" ] }, { "cell_type": "markdown", "id": "12e72eab", "metadata": {}, "source": [ "\n", "\n", "## Discussion : Évolution de la profondeur des portes à deux qubits\n", "\n", "L'une des principales raisons pour lesquelles l'algorithme de Grover est considéré comme un algorithme tolérant aux pannes réside dans la croissance rapide de la profondeur des portes à deux qubits du circuit à mesure que le nombre de qubits augmente. La porte Z à contrôles multiples, qui est au cœur à la fois de l'oracle et de l'opérateur de diffusion, se décompose en un nombre de portes à deux qubits qui croît de manière exponentielle avec le nombre de qubits de contrôle. Si l'on ajoute à cela le fait que le nombre optimal d'itérations de Grover augmente lui-même selon une loi de l'ordre de $O(\\sqrt{2^n})$, la profondeur totale à deux qubits devient rapidement irréalisable sur du matériel sujet au bruit.\n", "\n", "Ci-dessous, nous construisons des circuits de Grover pour un nombre croissant de qubits, nous les transposons, puis nous représentons graphiquement la profondeur des portes à deux qubits obtenue afin d'illustrer cette évolutivité.\n", "\n" ] }, { "cell_type": "code", "execution_count": 10, "id": "abc6b43c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n=3: optimal_iters=2, 2Q depth=39\n", "n=4: optimal_iters=3, 2Q depth=111\n", "n=5: optimal_iters=4, 2Q depth=466\n", "n=6: optimal_iters=6, 2Q depth=1646\n", "n=7: optimal_iters=8, 2Q depth=3550\n", "n=8: optimal_iters=12, 2Q depth=7989\n", "n=9: optimal_iters=17, 2Q depth=14824\n" ] }, { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import matplotlib.pyplot as plt\n", "\n", "num_qubits_list = list(range(3, 10))\n", "two_q_depths = []\n", "backend = service.least_busy(\n", " operational=True, simulator=False, min_num_qubits=127\n", ")\n", "for n in num_qubits_list:\n", " # Mark a single state for simplicity\n", " marked = [\"1\" * n]\n", " oracle_n = grover_oracle(marked)\n", " grover_op_n = grover_operator(oracle_n)\n", "\n", " # Optimal number of iterations\n", " num_iters = math.floor(\n", " math.pi / (4 * math.asin(math.sqrt(len(marked) / 2**n)))\n", " )\n", "\n", " # Build the full Grover circuit\n", " qc_n = QuantumCircuit(n)\n", " qc_n.h(range(n))\n", " qc_n.compose(grover_op_n.power(num_iters), inplace=True)\n", " qc_n.measure_all()\n", "\n", " # Transpile to a basis gate set and count 2Q depth\n", " pm_n = generate_preset_pass_manager(backend=backend, optimization_level=3)\n", " qc_transpiled = pm_n.run(qc_n)\n", "\n", " # Compute depth restricted to 2-qubit operations\n", " depth_2q = qc_transpiled.depth(lambda x: x.operation.num_qubits == 2)\n", "\n", " two_q_depths.append(depth_2q)\n", " print(f\"n={n}: optimal_iters={num_iters}, 2Q depth={depth_2q}\")\n", "\n", "# Plot\n", "fig, ax = plt.subplots(figsize=(8, 5))\n", "ax.plot(\n", " num_qubits_list,\n", " two_q_depths,\n", " \"o-\",\n", " linewidth=2,\n", " markersize=8,\n", " color=\"#6929C4\",\n", ")\n", "ax.set_xlabel(\"Number of qubits\", fontsize=13)\n", "ax.set_ylabel(\"Two-qubit gate depth\", fontsize=13)\n", "ax.set_title(\"Grover's algorithm: 2Q depth scaling\", fontsize=14)\n", "ax.set_yscale(\"log\")\n", "ax.grid(True, alpha=0.3)\n", "ax.set_xticks(num_qubits_list)\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "f3ddda55", "metadata": {}, "source": [ "Comme le montre le graphique, la profondeur des portes à deux qubits augmente extrêmement rapidement avec le nombre de qubits — de manière à peu près exponentielle. Cela rend l'algorithme de Grover inutilisable sur le matériel quantique actuel, sujet au bruit, sauf pour des problèmes de très petite taille. Cet algorithme reste un objectif majeur pour les futurs ordinateurs quantiques tolérants aux pannes, où la correction d'erreurs permettra d'exécuter de manière fiable des circuits complexes.\n", "\n" ] }, { "cell_type": "markdown", "id": "cf6e8fe6", "metadata": {}, "source": [ "\n", "\n", "## Etapes suivantes\n", "\n", "\n", " Si ce travail vous a paru intéressant, les ressources suivantes pourraient vous intéresser :\n", "\n", " * [Bibliothèque de circuits Qiskit : `grover_operator()` Référence de l'API](/docs/api/qiskit/qiskit.circuit.library.grover_operator)\n", " * [Le tutoriel](/docs/tutorials/quantum-approximate-optimization-algorithm) sur le QAOA et [la leçon sur le QAOA à l'échelle industrielle](/learning/courses/quantum-computing-in-practice/utility-scale-qaoa) fournissent des exemples concrets d'optimisation à l'aide d'ordinateurs quantiques\n", " * Pour en savoir plus sur les algorithmes à court terme, consultez le cours [« L'informatique quantique en pratique »](/learning/courses/quantum-computing-in-practice)\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3" }, "hours": 1, "qpuSeconds": 60 }, "nbformat": 4, "nbformat_minor": 5 }