Zelfstudie: Het zoekalgoritme van Grover implementeren in Q#
In deze zelfstudie implementeert u het algoritme Q# van Grover om op zoek gebaseerde problemen op te lossen. Zie de theorie van het algoritme van Grover voor een diepgaande uitleg van de theorie achter het algoritme van Grover.
In deze zelfstudie hebt u:
- Het algoritme van Grover definiëren voor een zoekprobleem
- Het algoritme van Grover implementeren in Q#
Tip
Als u uw kwantumcomputingtraject wilt versnellen, bekijkt u Code met Azure Quantum, een unieke functie van de Azure Quantum-website. Hier kunt u ingebouwde Q# voorbeelden of uw eigen Q# programma's uitvoeren, nieuwe Q# code genereren vanuit uw prompts, uw code openen en uitvoeren in VS Code voor het web met één klik en Copilot vragen stellen over kwantumcomputing.
Vereisten
Het codevoorbeeld uitvoeren in Copilot in Azure Quantum:
- Een Microsoft-e-mailaccount (MSA).
Het codevoorbeeld ontwikkelen en uitvoeren in Visual Studio Code:
- De nieuwste versie van Visual Studio Code of open VS Code op het web.
- De nieuwste versie van de Azure-extensieQuantum Development Kit. Zie QDK installeren in VS Code voor installatiedetails.
Het probleem definiëren
Het algoritme van Grover is een van de bekendste algoritmen in kwantumcomputing. Het type probleem dat wordt opgelost, wordt vaak aangeduid als 'een database doorzoeken', maar het is nauwkeuriger om het te beschouwen in termen van het zoekprobleem.
Elk zoekprobleem kan wiskundig worden geformuleerd met een abstracte functie $f(x)$ die zoekitems accepteert $x$. Als het item $x$ een oplossing is voor het zoekprobleem, $f(x)=1$. Als het item $x$ geen oplossing is, $f(x)=0$. Het zoekprobleem bestaat uit het vinden van een item $x_0$ zodat $f(x_0)=1$.
U kunt dus elk zoekprobleem formuleren als: gegeven een klassieke functie $f(x):\{0,1\}^n \rightarrow\{0,1\}$, waarbij $n$ de bitgrootte van de zoekruimte is, zoekt u een invoer $x_0$ waarvoor $f(x_0)=1$.
Als u het algoritme van Grover wilt implementeren om een zoekprobleem op te lossen, moet u het volgende doen:
- Transformeer het probleem naar de vorm van een Grover-taak. Stel dat u de factoren van een geheel getal $M$ wilt vinden met behulp van het algoritme van Grover. U kunt het probleem met de gehele factorisatie transformeren naar de taak van een Grover door een functie $$f_M(x)=1[r],$$ te maken waarbij $1[r]=1$ als $r=0$ en $1[r]=0$ is als $r\neq0$ en $r$ de rest van $M/x$ is. Op deze manier zijn de gehele getallen $x_i$ die $f_M(x_i)=1$ de factoren zijn van $M$ en hebt u het probleem omgezet in de taak van een Grover.
- Implementeer de functie van de taak van Grover als een kwantumorakel. Als u het algoritme van Grover wilt implementeren, moet u de functie implementeren $f(x)$ van de taak van uw Grover als een kwantumorakel.
- Gebruik het algoritme van Grover met uw oracle om de taak op te lossen. Zodra u een kwantumorakel hebt, kunt u het aansluiten op de implementatie van uw Grover-algoritme om het probleem op te lossen en de uitvoer te interpreteren.
Het algoritme van Grover
Stel dat er $N=2^n$ in aanmerking komende items zijn voor het zoekprobleem en dat ze worden geïndexeerd door elk item een geheel getal van $0$ toe te wijzen aan $N-1$. De stappen van het algoritme zijn:
- Begin met een register van $n$ qubits geïnitialiseerd in de status $\ket{0}$.
- Bereid het register voor in een uniforme superpositie door $H$ toe te passen op elke qubit in het register: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
- Pas de volgende bewerkingen toe op het register $N_{\text{optimal}}$ keer:
- Het faseorakel $O_f$ die een voorwaardelijke faseverschuiving van $-1$ toepast voor de oplossingsitems.
- Pas $H$ toe op elke qubit in het register.
- Pas $-O_0$, een voorwaardelijke faseverschuiving van $-1$ toe op elke rekenbasisstatus, behalve $\ket{0}$.
- Pas $H$ toe op elke qubit in het register.
- Meet het register om de index te verkrijgen van een item dat een oplossing met zeer hoge waarschijnlijkheid is.
- Controleer het item om te zien of het een geldige oplossing is. Zo niet, start u opnieuw.
Schrijf de code voor het algoritme van Grover in Q#
In deze sectie wordt beschreven hoe u het algoritme implementeert in Q#. Er zijn enkele dingen die u moet overwegen bij het implementeren van het algoritme van Grover. U moet definiëren wat de gemarkeerde status is, hoe u erover moet nadenken en hoeveel iteraties u moet uitvoeren voor het algoritme. U moet ook het oracle definiëren waarmee de functie van de taak van Grover wordt geïmplementeerd.
De gemarkeerde status definiëren
Eerst definieert u welke invoer u zoekt in de zoekopdracht. Hiervoor schrijft u een bewerking waarmee de stappen b, c en d van het algoritme van Grover worden toegepast.
Samen worden deze stappen ook wel bekend als de diffusieoperator $-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);
}
}
De ReflectAboutMarked bewerking weerspiegelt de basisstatus die is gemarkeerd door afwisselende nullen en nullen. Dit doet u door de diffusieoperator van Grover toe te passen op de invoer qubits. De bewerking maakt gebruik van een hulp-qubit, outputQubitdie wordt geïnitialiseerd in de toestand $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ door de $X$ en $H$ poorten toe te passen. De bewerking past vervolgens de $X$-poort toe op elke andere qubit in het register, waardoor de status van de qubit wordt gespiegeld. Ten slotte wordt de gecontroleerde $X$ poort toegepast op de hulp-qubit en de invoer-qubits. Met deze bewerking wordt de hulp-qubit gespiegeld als en alleen als alle invoer-qubits de status $\ket{1}$hebben, wat de gemarkeerde status is.
Het aantal optimale iteraties definiëren
De zoekopdracht van Grover heeft een optimaal aantal iteraties dat de hoogste kans oplevert om een geldige uitvoer te meten. Als het probleem $N=2^n$ mogelijke in aanmerking komende items heeft en $M$ van deze items oplossingen voor het probleem zijn, is het optimale aantal iteraties:
$$N_{\text{optimal}}\approx\frac{\pi}{4}\sqrt{\frac{N}{M}}$$
Doorgaan met herhalen van het optimale aantal iteraties begint die kans te verminderen totdat u bijna nul succeskans bereikt op iteratie $2 N_{\text{optimal}}$. Daarna neemt de kans weer toe tot $ 3 N_{\text{optimal}}$, enzovoort.
Bij praktische toepassingen weet u doorgaans pas hoeveel oplossingen er voor het probleem zijn als u het hebt opgelost. Een efficiënte strategie voor het afhandelen van dit probleem is door het aantal oplossingen $M$ te "raden" door de schatting geleidelijk te verhogen in bevoegdheden van twee (d.w.w.v. $ 1, 2, 4, 8, 16, ..., 2^n$). Een van deze schattingen is dicht genoeg om de oplossing nog steeds te vinden met een gemiddeld aantal iteraties rond $\sqrt{\frac{N}{M}}$.
Met de volgende Q# functie wordt het optimale aantal iteraties voor een bepaald aantal qubits in een register berekend.
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;
}
De CalculateOptimalIterations functie gebruikt de bovenstaande formule om het aantal iteraties te berekenen en rondt deze vervolgens af op het dichtstbijzijnde gehele getal.
De bewerking van Grover definiëren
De Q# bewerking voor het zoekalgoritmen van Grover heeft drie invoerwaarden:
- Het aantal qubits,
nQubits : Intin het qubitregister. Met dit register wordt de voorlopige oplossing gecodeerd voor het zoekprobleem. Na de bewerking wordt deze gemeten. - Het aantal optimale iteraties,
iterations : Int. - Een bewerking,
phaseOracle : Qubit[] => Unit) : Result[]die het faseorakel vertegenwoordigt voor de taak van Grover. Met deze bewerking wordt een eenheidstransformatie toegepast op een algemeen qubitregister.
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);
}
De GroverSearch bewerking initialiseert een register van $n$ qubits in de status $\ket{0}$, bereidt het register voor in een uniforme superpositie en past vervolgens het algoritme van Grover toe voor het opgegeven aantal iteraties. De zoekopdracht zelf bestaat uit herhaaldelijk weerspiegeling van de gemarkeerde status en de beginstatus, waarin u kunt uitschrijven Q# als een for-lus. Ten slotte meet het register en retourneert het resultaat.
De code maakt gebruik van drie helperbewerkingen: PrepareUniform, ReflectAboutUniformen ReflectAboutAllOnes.
Gezien een register in de status all-zeros, bereidt de PrepareUniform bewerking een uniforme superpositie voor op alle basisstatussen.
operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
for q in inputQubits {
H(q);
}
}
De bewerking ''ReflectAboutAllOnes' weerspiegelt de status All-Ones.
operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
Controlled Z(Most(inputQubits), Tail(inputQubits));
}
De bewerking ReflectAboutUniform weerspiegelt zich over de uniforme superpositiestatus. Ten eerste transformeert het de uniforme superpositie naar all-zero. Vervolgens transformeert het de status all-zero naar all-ones. Ten slotte weerspiegelt het zich over de all-ones-status. De bewerking wordt aangeroepen ReflectAboutUniform omdat deze geometrisch kan worden geïnterpreteerd als een weerspiegeling in de vectorruimte over de uniforme superpositietoestand.
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);
}
}
De laatste code uitvoeren
Nu hebt u alle ingrediënten om een bepaald exemplaar van het zoekalgoritmen van Grover te implementeren en het factoringprobleem op te lossen. Om te voltooien, stelt de Main bewerking het probleem in door het aantal qubits en het aantal iteraties op te geven
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;
}
Het programma uitvoeren
Selecteer het gewenste platform om uw programma uit te voeren.
U kunt uw Q# code gratis testen met Copilot in Azure Quantum. U hebt alleen een Microsoft-e-mailaccount (MSA) nodig. Zie Azure Quantum verkennen voor meer informatie over Copilot in Azure Quantum.
Open Copilot in Azure Quantum in uw browser.
Kopieer en plak de volgende code in de code-editor.
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); } } }
Tip
Vanuit Copilot in Azure Quantum kunt u uw programma openen in VS Code for the Web door te klikken op de knop VS Code-logo in de rechterhoek van de code-editor.
Het programma uitvoeren met behulp van de simulator in het geheugen
- Selecteer In-memory Simulator.
- Selecteer het aantal schermafbeeldingen dat u wilt uitvoeren en klik op Uitvoeren.
- De resultaten worden weergegeven in het histogram en in de resultatenvelden .
- Klik op Code uitleggen om Copilot te vragen de code aan u uit te leggen.
Het programma uitvoeren met behulp van de Quantinuum H-Series Emulator
U kunt uw programma ook indienen bij de gratis Quantinuum H-Series Emulator. De emulator simuleert een kwantumcomputer met 20 qubits.
- Selecteer de vervolgkeuzelijst In-Memory Simulator en selecteer Quantinuum H-Series Emulator.
- Selecteer het aantal opnamen (momenteel beperkt tot 20) en selecteer Uitvoeren.
Gerelateerde inhoud
Bekijk andere Q# zelfstudies:
- Kwantumverstrengeling laat zien hoe u een Q# programma schrijft dat qubits bewerkt en meet en de effecten van superpositie en verstrengeling demonstreert.
- Kwantumgenerator voor willekeurige getallen laat zien hoe u een Q# programma schrijft waarmee willekeurige getallen uit qubits in superpositie worden gegenereerd.
- Quantum Fourier Transform verkent hoe u een Q# programma schrijft waarmee specifieke qubits rechtstreeks worden aangepakt.
- De Quantum Katas zijn zelfstudies in eigen tempo en programmeeroefeningen die zijn gericht op het leren van de elementen van kwantumcomputing en Q# programmeren op hetzelfde moment.