Zelfstudie: Het zoekalgoritme van Grover implementeren in Q#

Artikel
01/13/2024

Notitie

Quantum Development Kit Microsoft (klassieke QDK) wordt na 30 juni 2024 niet meer ondersteund. Als u een bestaande QDK-ontwikkelaar bent, raden we u aan over te stappen op de nieuwe Azure Quantum Development Kit (Moderne QDK) om door te gaan met het ontwikkelen van kwantumoplossingen. Zie Uw code migreren Q# naar de moderne QDK voor meer informatie.

In deze zelfstudie implementeert u het algoritme van Grover in Q# om problemen op basis van zoekopdrachten op te lossen. Zie de Theorie van het algoritme van Grover voor een uitgebreide uitleg van de theorie achter het algoritme van Grover.

In deze zelfstudie gaat u:

Definieer het algoritme van Grover voor een zoekprobleem.
Implementeer het algoritme van Grover in Q#.

Tip

Als u uw kwantumcomputingtraject wilt versnellen, raadpleegt 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 op basis van 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 De Copilot in Azure Quantum:
- Een E-mailaccount van Microsoft (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-extensie Quantum Development Kit . Zie Installing the Modern QDK on VS Code (De moderne QDK installeren op VS Code) voor installatiedetails.

Het probleem definiëren

Het algoritme van Grover is een van de beroemdste algoritmen in kwantumcomputing. Het type probleem dat hiermee wordt opgelost, wordt vaak aangeduid als 'een database doorzoeken', maar het is nauwkeuriger om het te zien 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$ zodanig dat $f(x_0)=1$.

U kunt elk zoekprobleem dus formuleren als: gezien 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 in 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 factorisatie van gehele getallen transformeren naar een taak van Grover door een functie $$f_M(x)=1[r],$$ te maken waarbij $1[r]=1$ als $r=0$ en $1[r]=0$ 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$ maken de factoren van $M$ en hebt u het probleem omgezet in de taak van een Grover.
Implementeer de functie van de taak van de Grover als een kwantumorakel. Als u het algoritme van Grover wilt implementeren, moet u de functie $f(x)$ van de taak van uw Grover implementeren als een kwantumorakel.
Gebruik het algoritme van Grover met uw orakel om de taak op te lossen. Zodra u een kwantumorakel hebt, kunt u deze 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 komen voor het zoekprobleem en dat ze worden geïndexeerd door elk item een geheel getal toe te wijzen van $0$ tot $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 de registratie $N_{\text{optimal}}$ keer:
1. De faseorakel $O_f$ die een voorwaardelijke faseverschuiving van $-1$ toepast op de oplossingsitems.
2. Pas $H$ toe op elke qubit in het register.
3. Pas $-O_0$ toe, een voorwaardelijke faseverschuiving van $-1$ op elke rekenkundige basisstatus behalve $\ket{0}$.
4. 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, dan 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 weinig dingen om rekening mee te houden bij het implementeren van het algoritme van Grover. U moet definiëren wat de gemarkeerde status is, hoe u erover nadenkt en voor hoeveel iteraties het algoritme moet worden uitgevoerd. U moet ook het orakel definiëren waarmee de functie van de taak van de Grover wordt geïmplementeerd.

De gemarkeerde status definiëren

Eerst definieert u welke invoer u wilt zoeken in de zoekopdracht. Schrijf hiervoor een bewerking die de stappen b, c en d van het algoritme van Grover toepast.

Samen worden deze stappen ook wel bekend als de S-diffusieoperator van 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);
    }
}

De ReflectAboutMarked bewerking geeft de basisstatus weer die wordt gemarkeerd door afwisselend nullen en enen. Dit doet u door de diffusieoperator van Grover toe te passen op de invoer-qubits. De bewerking maakt gebruik van een extra qubit, outputQubit, die is geïnitialiseerd in de status $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ door de poorten $X$ en $H$ 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 alleen gespiegeld 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 die de grootste kans opleveren voor het meten van een geldige uitvoer. Als het probleem $N=2^n$ mogelijke in aanmerking komende items heeft en $M$ oplossingen voor het probleem zijn, is het optimale aantal iteraties:

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

Als u het optimale aantal iteraties blijft doorlopen, wordt deze kans verkleind totdat u bijna nul succeskans bereikt op de 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 om dit probleem aan te pakken, is het 'raden' van het aantal oplossingen $M$ door de schatting in krachten van twee geleidelijk te verhogen (d.w.w. $1, 2, 4, 8, 16, ..., 2^n$). Een van deze schattingen is zo dichtbij dat het algoritme de oplossing nog steeds kan vinden met een gemiddeld aantal iteraties rond $\sqrt{\frac{N}{M}}$.

De volgende Q# functie berekent het optimale aantal iteraties voor een bepaald aantal qubits in een register.

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 De Grover definiëren

De Q# bewerking voor het zoekalgoritmen van Grover heeft drie invoerwaarden:

Het aantal qubits, nQubits : Int, in het qubitregister. Met dit register wordt de voorlopige oplossing voor het zoekprobleem gecodeerd. Na de bewerking wordt deze gemeten.
Het aantal optimale iteraties, iterations : Int.
Een bewerking, phaseOracle : Qubit[] => Unit) : Result[], die het faseorakel voor de taak van Grover vertegenwoordigt. 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 op het opgegeven aantal iteraties. De zoekopdracht zelf bestaat uit herhaaldelijk reflecteren over de gemarkeerde status en de beginstatus, die u kunt uitschrijven Q# als een for-lus. Ten slotte wordt het register gemeten en wordt het resultaat geretourneerd.

De code maakt gebruik van drie helperbewerkingen: PrepareUniform, ReflectAboutUniformen ReflectAboutAllOnes.

Gegeven een register met de status alle nullen, bereidt de PrepareUniform bewerking een uniforme superpositie voor over alle basistoestanden.

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

De bewerking ''ReflectAboutAllOnes' geeft de status all-en weer.

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

De bewerking ReflectAboutUniform weerspiegelt de status van de uniforme superpositie. Ten eerste transformeert het de uniforme superpositie naar volledig nul. Vervolgens wordt de all-zero-status omgezet in all-enen. Ten slotte reflecteert het over de all-en-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 uiteindelijke code uitvoeren

U hebt nu 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;
}

U kunt uw Q# code gratis testen met de Copilot in Azure Quantum. U hebt alleen een E-mailaccount van Microsoft (MSA) nodig. Zie Azure Quantum verkennen voor meer informatie over de Copilot in Azure Quantum.

Open de 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 voor het web door te klikken op de knop VS Code-logo in de rechterhoek van de code-editor.

Het programma uitvoeren met behulp van de in-memory simulator

Selecteer In-memory Simulator.
Selecteer het aantal opnamen dat u wilt uitvoeren en klik op Uitvoeren.
De resultaten worden weergegeven in het histogram en in de velden Resultaten .
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.

Open Visual Studio Code en selecteer Bestand > Nieuw tekstbestand om een nieuw bestand te maken.
Sla het bestand op als GroversAlgorithm.qs. Dit bestand bevat de Q# code voor uw programma.

Kopieer de volgende code in het GroversAlgorithm.qs bestand.

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);
        }
    }
}

Voordat u het programma uitvoert, moet u het target profiel instellen op Onbeperkt. Selecteer Weergave -> Opdrachtpalet, zoek naar QIR, selecteer Q#: Stel het Azure Quantum QIR-profiel target in en selecteer Q#vervolgens : onbeperkt.
Als u het programma wilt uitvoeren, selecteert u Bestand uitvoeren Q# in de vervolgkeuzelijst met het afspeelpictogram in de rechterbovenhoek of drukt u op Ctrl+F5. Het programma voert de bewerking of functie uit die is gemarkeerd met het @EntryPoint() kenmerk in de standaardsimulator.
De uitvoer wordt weergegeven in de console voor foutopsporing.