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

Article
01/13/2024

Notes

Quantum Development Kit Microsoft (QDK classique) ne sera plus pris en charge après le 30 juin 2024. Si vous êtes un développeur QDK existant, nous vous recommandons de passer au nouvel Azure Quantum Development Kit (QDK moderne) pour continuer à développer des solutions quantiques. Pour plus d’informations, consultez Migrer votre Q# code vers le QDK moderne.

Dans ce tutoriel, vous implémentez l’algorithme de Grover dans Q# 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 didacticiel, vous allez :

Définissez l’algorithme de Grover pour un problème de recherche.
Implémentez l’algorithme de Grover dans Q#.

Conseil

Si vous souhaitez accélérer votre parcours d’informatique quantique, case activée code avec Azure Quantum, une fonctionnalité unique du site web Azure Quantum. Ici, vous pouvez exécuter des exemples intégrés Q# ou vos propres Q# programmes, générer un nouveau Q# code à partir de vos invites, ouvrir et exécuter votre code dans VS Code pour le web en un seul clic, et poser des questions à Copilot sur l’informatique quantique.

Prérequis

Pour exécuter l’exemple de code dans Copilot dans Azure Quantum :
- Un compte de messagerie Microsoft (MSA).
Pour développer et exécuter l’exemple de code dans Visual Studio Code :
- La dernière version de Visual Studio Code ou ouvrez VS Code sur le web.
- Dernière version de l’extension Azure Quantum Development Kit . Pour plus d’informations sur l’installation, consultez Installation du QDK moderne sur VS Code.

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 le 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 afin de résoudre un problème de recherche, vous devez :

Transformer le problème au format des tâches 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$$
Appliquer 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 éléments à prendre en compte lors de l’implémentation de l’algorithme de Grover. Vous devez définir quel est votre état marqué, comment y réfléchir 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 Grover’S $-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 l’alternance des zéros et des uns. Pour ce faire, il applique l’opérateur de diffusion de Grover aux qubits d’entrée. L’opération utilise un qubit auxiliaire, outputQubit, qui est initialisé à 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$ à tous les autres qubits du registre, ce qui retourne l’état du qubit. 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 seulement si tous les qubits d’entrée sont à 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 atteigniez 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 ci-dessus 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 : Int, dans le registre de qubits. Ce registre encodera la solution provisoire au problème de recherche. Après l’opération, elle sera mesurée.
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 de qubits 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 d’itérations spécifié. La recherche elle-même consiste à réfléchir à plusieurs reprises à l’état marqué et à l’état de début, que vous pouvez écrire en Q# tant que boucle for. Enfin, il mesure le registre et retourne le résultat.

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

Avec un registre à l’état tous les zéros, l’opération PrepareUniform prépare une superposition uniforme 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 uns.

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 total. Ensuite, il transforme l’état tout-zéro en tous-uns. Enfin, il reflète l’état de tous les uns. 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;
}

Vous pouvez tester gratuitement votre Q# code avec Copilot dans Azure Quantum. Il vous suffit d’un compte de messagerie Microsoft (MSA). Pour plus d’informations sur Copilot dans Azure Quantum, consultez Explorer Azure Quantum.

Ouvrez Copilot dans Azure Quantum dans votre navigateur.

Copiez et collez le code suivant dans l’éditeur de code.

namespace GroversTutorial {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    @EntryPoint()
    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);
        }
    }
}

Conseil

À partir de Copilot dans Azure Quantum, vous pouvez ouvrir votre programme dans VS Code pour le web en cliquant sur le bouton logo VS Code dans le coin droit de l’éditeur de code.

Exécuter le programme à l’aide du simulateur en mémoire

Sélectionnez Simulateur en mémoire.
Sélectionnez le nombre de captures à exécuter, puis cliquez sur Exécuter.
Les résultats sont affichés dans l’histogramme et dans les champs Résultats .
Cliquez sur Expliquer le code pour inviter Copilot à vous expliquer le code.

Exécuter le programme à l’aide de l’émulateur Quantinuum H-Series

Vous pouvez également soumettre votre programme à l’émulateur gratuit Quantinuum H-Series Emulator. L’émulateur simule un ordinateur quantique avec 20 qubits.

Sélectionnez la liste déroulante Simulateur en mémoire , puis Émulateur de série H Quantinuum.
Sélectionnez le nombre de captures (actuellement limité à 20), puis sélectionnez Exécuter.

Ouvrez Visual Studio Code et sélectionnez Fichier > Nouveau fichier texte pour créer un fichier.
Enregistrez le fichier sous le nom GroversAlgorithm.qs. Ce fichier contient le Q# code de votre programme.

Copiez le code suivant dans le GroversAlgorithm.qs fichier.

namespace GroversTutorial {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    @EntryPoint()
    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);
        }
    }
}

Avant d’exécuter le programme, vous devez définir le profil sur targetNon restreint. Sélectionnez Affichage -> Palette de commandes, recherchez QIR, sélectionnez Q#: Définir le profil QIR target Azure Quantum, puis sélectionnez Q#: non restreint.
Pour exécuter votre programme, sélectionnez Exécuter Q# le fichier dans la liste déroulante icône de lecture en haut à droite, ou appuyez sur Ctrl+F5. Le programme exécute l’opération ou la fonction marquée avec l’attribut @EntryPoint() sur le simulateur par défaut.
Votre sortie s’affiche dans la console de débogage.