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#
Conseil
Si vous souhaitez accélérer votre parcours d’informatique quantique, consultez 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 du nouveau Q# code à partir de vos invites, ouvrir et exécuter votre code dans VS Code pour le web en un 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 ouvrir VS Code sur le web.
- Dernière version de l’extension AzureQuantum Development Kit. Pour plus d’informations sur l’installation, consultez Installation du QDK 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$.
Par conséquent, 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 binaire 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 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$$
- Appliquez les opérations suivantes au registre $N_{\text{optimal}}$ fois :
- L’oracle de phase $O_f$ qui applique un décalage de phase conditionnel de $-1$ pour les éléments de la solution.
- Appliquer $H$ à chaque qubit dans le registre.
- Appliquer $-O_0$, un décalage de phase conditionnel de $-1$ à chaque état de base de calcul, sauf $\ket{0}$.
- 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 l’alterner des zéros et des zéros. Il le fait en appliquant l’opérateur de diffusion de Grover aux qubits d’entrée. L’opération utilise un qubit auxiliaire, outputQubitqui est initialisé dans l’état $\ket{-}=\frac{1}{\sqrt{2}}(\ket-\ket{0}{1})$ en appliquant les portes $X$ et $H$. L’opération applique ensuite la porte $X$ à tous les autres qubits du registre, 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 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 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 : Intdans le registre qubit. 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 spécifié d’itérations. La recherche elle-même se compose de réflexion répétée sur 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.
Étant donné un registre dans l’état des 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 é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 all-zero en tous-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
Sélectionnez la plateforme souhaitée pour exécuter votre programme.
Vous pouvez tester votre Q# code avec Le Copilot dans Azure Quantum gratuitement. Tout ce dont vous avez besoin est un compte de messagerie Microsoft (MSA). Pour plus d’informations sur le 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.
import Microsoft.Quantum.Convert.*; import Microsoft.Quantum.Math.*; import Microsoft.Quantum.Arrays.*; import Microsoft.Quantum.Measurement.*; import Microsoft.Quantum.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); } }
Conseil
À partir de Copilot dans Azure Quantum, vous pouvez ouvrir votre programme dans VS Code pour le web en sélectionnant le bouton du 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 sélectionnez Exécuter.
- Les résultats sont affichés dans l’histogramme et dans les champs Résultats .
- Sélectionnez Expliquer le code pour inviter Copilot à expliquer le code à vous.
Exécuter le programme à l’aide de l’émulateur Quantinuum H-Series
Vous pouvez également soumettre votre programme à l’émulateur gratuit quantinuum H-Series. L’émulateur simule un ordinateur quantique avec 20 qubits.
- Sélectionnez la liste déroulante Simulateur en mémoire, puis sélectionnez Émulateur Quantinuum H-Series.
- Sélectionnez le nombre d’essais (actuellement limités à 20), puis sélectionnez Exécuter.
Contenu connexe
Explorez les autres tutoriels Q# :
- L’inanglement quantique montre comment écrire un Q# programme qui manipule et mesure des qubits et illustre les effets de la superposition et de l’inanglement.
- Le générateur de nombres aléatoires quantiques montre comment écrire un Q# programme qui génère des nombres aléatoires hors qubits dans la superposition.
- Quantum Fourier Transform explore comment écrire un Q# programme qui traite directement des qubits spécifiques.
- Les katas quantiques sont des tutoriels auto-rythmes et des exercices de programmation visant à enseigner les éléments de l’informatique quantique et Q# de la programmation en même temps.