Tutoriel : Implémenter l’algorithme de recherche de Grover dans Q#

Dans ce tutoriel, vous implémentez l’algorithme Q# de Grover pour résoudre les problèmes basés sur la recherche. Pour une explication détaillée de la théorie sous-jacente de l’algorithme de Grover, consultez la théorie de l’algorithme de Grover.

Dans ce tutoriel, vous allez :

Définir l’algorithme de Grover pour un problème de recherche
Implémenter l’algorithme de Grover dans Q#

Prérequis

Pour développer et exécuter l’exemple de code dans Visual Studio Code (VS Code), vous devez installer les outils suivants :

Dernière version de VS Code ou ouvrir VS Code pour le web.
La plus récente version de l'extension QDK. Pour plus d’informations sur l’installation, consultez Configurer le QDK.

Définir le problème

L’algorithme de Grover est l’un des algorithmes les plus connus en calcul quantique. Le type de problème qu’il résout est souvent appelé « recherche dans une base de données », mais il est plus précis de le considérer en termes de problème de recherche.

Tout problème de recherche peut être formulé de façon mathématique à l’aide d’une fonction abstraite $f(x)$ qui accepte des éléments de recherche $x$. Si l’élément $x$ est une solution du problème de recherche, alors $f(x)=1$. Si l’élément $x$ n’est pas une solution, alors $f(x)=0$. Le problème de recherche consiste à trouver tout élément $x_0$ tel que $f(x_0)=1$.

Ainsi, vous pouvez formuler n’importe quel problème de recherche comme suit : étant donné une fonction classique $f(x) :\{0,1\}^n \rightarrow\{0,1\}$, où $n$ est la taille de bits de l’espace de recherche, recherchez une entrée $x_0$ pour laquelle $f(x_0)=1$.

Pour implémenter l’algorithme de Grover pour résoudre un problème de recherche, vous devez :

Transformer le problème sous la forme d'une tâche de Grover. Par exemple, supposons que vous souhaitiez trouver les facteurs d’une entier $M$ à l’aide de l’algorithme de Grover. Vous pouvez transformer le problème de factorisation des entiers en une tâche de Grover en créant une fonction $$f_M(x)=1[r],$$ où $1[r]=1$ si $r=0$ et $1[r]=0$ si $r\neq0$ et $r$ est le reste de $M/x$. De cette façon, les entiers $x_i$ qui figurent dans $f_M(x_i)=1$ sont les facteurs de $M$ et vous avez transformé le problème en une tâche de Grover.
Implémentez la fonction de la tâche de Grover en tant qu’oracle quantique. Pour implémenter l’algorithme de Grover, vous devez implémenter la fonction $f(x)$ de votre tâche de Grover en tant qu’oracle quantique.
Utilisez l’algorithme de Grover avec votre oracle pour résoudre la tâche. Une fois que vous avez un oracle quantique, vous pouvez le connecter à l’implémentation de votre algorithme de Grover pour résoudre le problème et interpréter la sortie.

Algorithme de Grover

Supposons que nous avons $N=2^n$ éléments éligibles pour le problème de recherche et que nous les indexons en affectant à chaque élément un entier compris entre $0$ et $N-1$. Les étapes de l’algorithme sont les suivantes :

Commencer avec un registre de $n$ qubits initialisés à l’état $\ket{0}$.
Préparer le registre dans une superposition uniforme en appliquant $H$ à chaque qubit dans le registre : $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
Appliquez les opérations suivantes au registre $N_{\text{optimal}}$ fois :
1. L’oracle de phase $O_f$ qui applique un décalage de phase conditionnel de $-1$ pour les éléments de la solution.
2. Appliquer $H$ à chaque qubit dans le registre.
3. Appliquer $-O_0$, un décalage de phase conditionnel de $-1$ à chaque état de base de calcul, sauf $\ket{0}$.
4. Appliquer $H$ à chaque qubit dans le registre.
Mesurer le registre pour obtenir l’index d’un élément qui est une solution avec une très grande probabilité.
Vérifiez l’élément pour voir s’il s’agit d’une solution valide. Si ce n’est pas le cas, recommencer.

Écrire le code de l’algorithme de Grover dans Q#

Cette section explique comment implémenter l’algorithme dans Q#. Il existe quelques points à prendre en compte lors de l’implémentation de l’algorithme de Grover. Vous devez définir l’état marqué, le mode de réflexion et le nombre d’itérations pour lesquelles exécuter l’algorithme. Vous devez également définir l’oracle qui implémente la fonction de la tâche de Grover.

Définir l’état marqué

Tout d’abord, vous définissez l’entrée que vous essayez de trouver dans la recherche. Pour ce faire, écrivez une opération qui applique les étapes b, c et d à partir de l’algorithme de Grover.

Ensemble, ces étapes sont également appelées opérateur de diffusion de Grover $-H^{\otimes n} O_0 H^{\otimes n}$.

operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
    Message("Reflecting about marked state...");
    use outputQubit = Qubit();
    within {
        // We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that
        // toggling it results in a (-1) phase.
        X(outputQubit);
        H(outputQubit);
        // Flip the outputQubit for marked states.
        // Here, we get the state with alternating 0s and 1s by using the X
        // operation on every other qubit.
        for q in inputQubits[...2...] {
            X(q);
        }
    } apply {
        Controlled X(inputQubits, outputQubit);
    }
}

L’opération ReflectAboutMarked reflète l’état de base marqué par une alternance de zéros et de uns. Il le fait en appliquant l’opérateur de diffusion de Grover aux qubits d’entrée. L’opération utilise un qubit auxiliaire, outputQubit, qui est initialisé dans l’état $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ en appliquant les portes $X$ et $H$. L’opération applique ensuite la porte $X$ à un qubit sur deux dans le registre, retournant ainsi l’état de chaque qubit concerné. Enfin, il applique la porte $X$ contrôlée au qubit auxiliaire et aux qubits d’entrée. Cette opération retourne le qubit auxiliaire si et uniquement si tous les qubits d’entrée sont dans l’état $\ket{1}$, qui est l’état marqué.

Définir le nombre d’itérations optimales

La recherche de Grover a un nombre optimal d’itérations qui offre la probabilité la plus élevée de mesurer une sortie valide. Si le problème comporte $N=2^n$ éléments éligibles possibles, dont $M$ d’entre eux constituent des solutions au problème, le nombre optimal d’itérations est :

$$N_{\text{optimal}}\approx\frac{\pi}{4}\sqrt{\frac{N}{M}}$$

Continuer à itérer au-delà du nombre optimal d’itérations commence à réduire cette probabilité jusqu’à ce que vous atteignez une probabilité de réussite presque nulle sur l’itération $2 N_{\text{optimal}}$. Après cela, la probabilité augmente à nouveau jusqu’à $3 N_{\text{optimal}}$, et ainsi de suite.

Dans les applications pratiques, on ne connaît généralement pas le nombre de solutions au problème avant de le résoudre. Une stratégie efficace pour gérer ce problème consiste à « deviner » le nombre de solutions $M$ en augmentant progressivement l’estimation selon des puissances de deux (p. ex. $1, 2, 4, 8, 16, ..., 2^n$). L’une de ces estimations sera suffisamment proche pour que l’algorithme trouve encore la solution avec un nombre moyen d’itérations proche de $\sqrt{\frac{N}{M}}$.

La fonction suivante Q# calcule le nombre optimal d’itérations pour un nombre donné de qubits dans un registre.

function CalculateOptimalIterations(nQubits : Int) : Int {
    if nQubits > 63 {
        fail "This sample supports at most 63 qubits.";
    }
    let nItems = 1 <<< nQubits; // 2^nQubits
    let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
    let iterations = Round(0.25 * PI() / angle - 0.5);
    return iterations;
}

La CalculateOptimalIterations fonction utilise la formule indiquée précédemment pour calculer le nombre d’itérations, puis l’arrondit à l’entier le plus proche.

Définir l’opération de Grover

L’opération Q# pour l’algorithme de recherche de Grover a trois entrées :

Nombre de qubits, nQubits : Intdans le registre qubit. Cet enregistrement encode la solution provisoire au problème de recherche et est mesuré après l’opération.
Nombre d’itérations optimales, iterations : Int.
Opération, phaseOracle : Qubit[] => Unit) : Result[] qui représente l’oracle de phase pour la tâche de Grover. Cette opération applique une transformation unitaire sur un registre qubit générique.

operation GroverSearch( nQubits : Int, iterations : Int, phaseOracle : Qubit[] => Unit) : Result[] {

    use qubits = Qubit[nQubits];
    PrepareUniform(qubits);

    for _ in 1..iterations {
        phaseOracle(qubits);
        ReflectAboutUniform(qubits);
    }

    // Measure and return the answer.
    return MResetEachZ(qubits);
}

L’opération GroverSearch initialise un registre de qubits $n$ dans l’état $\ket{0}$, prépare le registre dans une superposition uniforme, puis applique l’algorithme de Grover pour le nombre spécifié d’itérations. La recherche elle-même consiste à appliquer à plusieurs reprises des réflexions sur l'état marqué et l'état de départ, que vous pouvez exprimer dans Q# comme une boucle for. Enfin, il mesure le registre et retourne le résultat.

Le code utilise trois opérations d’assistance : PrepareUniform, ReflectAboutUniformet ReflectAboutAllOnes.

Étant donné un registre dans l’état tout-zéros, l’opération PrepareUniform prépare une superposition égale sur tous les états de base.

operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
    for q in inputQubits {
        H(q);
    }
}

L’opération ReflectAboutAllOnes reflète l’état de tous les éléments.

operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
    Controlled Z(Most(inputQubits), Tail(inputQubits));
}

L’opération ReflectAboutUniform reflète l’état de superposition uniforme. Tout d’abord, elle transforme la superposition uniforme en zéro. Ensuite, il transforme l'état tout-zéro en tout-uns. Enfin, il reflète l’état de tous les éléments. L’opération est appelée ReflectAboutUniform, car elle peut être interprétée géométriquement comme une réflexion dans l’espace vectoriel au sujet de l’état de superposition uniforme.

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
    within {
        Adjoint PrepareUniform(inputQubits);
        // Transform the all-zero state to all-ones
        for q in inputQubits {
            X(q);
        }
    } apply {
        ReflectAboutAllOnes(inputQubits);
    }
}

Exécuter le code final

Vous disposez à présent de tous les ingrédients requis pour implémenter une instance particulière de l’algorithme de recherche de Grover et résoudre le problème de factorisation. Pour terminer, l’opération Main configure le problème en spécifiant le nombre de qubits et le nombre d’itérations

operation Main() : Result[] {
    let nQubits = 5;
    let iterations = CalculateOptimalIterations(nQubits);
    Message($"Number of iterations: {iterations}");
    
    // Use Grover's algorithm to find a particular marked state.
    let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
    return results;
}

Exécuter le programme

Dans VS Code, ouvrez le menu Fichier et choisissez Nouveau fichier texte pour créer un fichier.
Enregistrez le fichier sous le nom GroversAlgorithm.qs. Ce fichier contient le code Q# de votre programme.

Copiez le code suivant dans le fichier GroversAlgorithm.qs.


import Std.Convert.*;
import Std.Math.*;
import Std.Arrays.*;
import Std.Measurement.*;
import Std.Diagnostics.*;


operation Main() : Result[] {
    let nQubits = 5;
    let iterations = CalculateOptimalIterations(nQubits);
    Message($"Number of iterations: {iterations}");

    // Use Grover's algorithm to find a particular marked state.
    let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
    return results;
}

operation GroverSearch(
    nQubits : Int,
    iterations : Int,
    phaseOracle : Qubit[] => Unit) : Result[] {

    use qubits = Qubit[nQubits];

    PrepareUniform(qubits);

    for _ in 1..iterations {
        phaseOracle(qubits);
        ReflectAboutUniform(qubits);
    }

    // Measure and return the answer.
    return MResetEachZ(qubits);
}

function CalculateOptimalIterations(nQubits : Int) : Int {
    if nQubits > 63 {
        fail "This sample supports at most 63 qubits.";
    }
    let nItems = 1 <<< nQubits; // 2^nQubits
    let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
    let iterations = Round(0.25 * PI() / angle - 0.5);
    return iterations;
}

operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
    Message("Reflecting about marked state...");
    use outputQubit = Qubit();
    within {
        // We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that
        // toggling it results in a (-1) phase.
        X(outputQubit);
        H(outputQubit);
        // Flip the outputQubit for marked states.
        // Here, we get the state with alternating 0s and 1s by using the X
        // operation on every other qubit.
        for q in inputQubits[...2...] {
            X(q);
        }
    } apply {
        Controlled X(inputQubits, outputQubit);
    }
}

operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
    for q in inputQubits {
        H(q);
    }
}

operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
    Controlled Z(Most(inputQubits), Tail(inputQubits));
}

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
    within {
        // Transform the uniform superposition to all-zero.
        Adjoint PrepareUniform(inputQubits);
        // Transform the all-zero state to all-ones
        for q in inputQubits {
            X(q);
        }
    } apply {
        // Now that we've transformed the uniform superposition to the
        // all-ones state, reflect about the all-ones state, then let the
        // within/apply block transform us back.
        ReflectAboutAllOnes(inputQubits);
    }
}

Pour exécuter votre programme, choisissez Exécuter dans le menu de l’opération Main , ou appuyez sur Ctrl + F5. Par défaut, le compilateur exécute l’opération ou la Main fonction sur le simulateur par défaut.
Votre sortie s’affiche dans la console de débogage dans le terminal.

Remarque

Si le profil QIR target n’est pas défini sur Non restreint, vous obtenez une erreur lorsque vous exécutez le programme. Pour ce programme, le compilateur définit automatiquement le target profil sur Non restreint , sauf si vous définissez le profil vous-même.

Explorez les autres tutoriels Q# :

L'intrication quantique montre comment écrire un Q# programme qui manipule et mesure des qubits et illustre les effets de la superposition et de l'intrication.
Le générateur quantique de nombres aléatoires montre comment écrire un Q# programme qui génère des nombres aléatoires à partir de qubits en superposition.
Quantum Fourier Transform explore comment écrire un Q# programme qui traite directement des qubits spécifiques.
Les katas quantiques sont des tutoriels auto-rythmés et des exercices de programmation visant à enseigner les éléments de l’informatique quantique et de la programmation simultanément.

Commentaires

Cette page a-t-elle été utile ?

Last updated on 2026-05-19