Självstudie: Implementera Grover-sökalgoritmen i Q#

I den här självstudien implementerar du Grover-algoritmen i Q# för att lösa sökbaserade problem. En djupgående förklaring av teorin bakom Grover-algoritmen finns i Teorin om Grover-algoritmen.

I den här kursen får du:

Förutsättningar

• Så här kör du kodexemplet i Copilot i Azure Quantum:

  • Ett Microsoft-e-postkonto (MSA).

• Så här utvecklar och kör du kodexemplet i Visual Studio Code:

  • Den senaste versionen av Visual Studio Code eller öppna VS Code på webben.
  • Den senaste versionen av Azure-tilläggetQuantum Development Kit. Installationsinformation finns i Installera QDK på VS Code.

Definiera problemet

Grover-algoritmen är en av de mest kända algoritmerna inom kvantberäkning. Den typ av problem som det löser kallas ofta "söka i en databas", men det är mer korrekt att tänka på det när det gäller sökproblemet.

Alla sökproblem kan formuleras matematiskt med en abstrakt funktion $f(x)$ som accepterar sökobjekt $x$. Om objektet $x$ är en lösning på sökproblemet $f(x)=1$. Om objektet $x$ inte är en lösning $f(x)=0$. Sökproblemet består av att hitta objekt $x_0$ så att $f(x_0)=1$.

Därför kan du formulera alla sökproblem som: givet en klassisk funktion $f(x):\{0,1\}^n \rightarrow\{0,1\}$, där $n$ är bitstorleken för sökområdet, hittar du en indata $x_0$ som $f(x_0)=1$.

För att implementera Grover-algoritmen för att lösa ett sökproblem måste du:

1. Transformera problemet till formen av en Grover-uppgift. Anta till exempel att du vill hitta faktorerna i ett heltal $M$ med grover-algoritmen. Du kan omvandla heltalsfaktoriseringsproblemet till en Grover-uppgift genom att skapa en funktion $$f_M(x)=1[r],$$ där $1[r]=1$ om $r=0$ och $1[r]=0$ om $r\neq0$ och $r$ är resten av $M/x$. På så sätt är heltalen $x_i$ som gör $f_M(x_i)=1$ faktorerna för $M$ och du har omvandlat problemet till en Grover-uppgift.
2. Implementera funktionen för Grover-uppgiften som ett kvantorakel. För att implementera Grovers algoritm måste du implementera funktionen $f(x)$ av Grovers uppgift som ett kvantorakel.
3. Använd Grovers algoritm med ditt orakel för att lösa uppgiften. När du har ett kvantorakel kan du ansluta det till Grovers algoritmimplementering för att lösa problemet och tolka utdata.

Grover-algoritmen

Anta att det finns $N=2^n$ berättigade objekt för sökproblemet och att de indexeras genom att tilldela varje objekt ett heltal från $0$ till $N-1$. Stegen i algoritmen är:

1. Börja med ett register med $n$ qubits initierade i tillståndet $\ket{0}$.
2. Förbered registret i en enhetlig superposition genom att tillämpa $H$ på varje qubit i registret: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
3. Använd följande åtgärder för att registrera $N_{\text{optimal}}$ gånger:
   1. Fasoraklet $O_f$ som tillämpar en villkorlig fasförskjutning på $-1$ för lösningsobjekten.
   2. Använd $H$ för varje qubit i registret.
   3. Använd $-O_0$, en villkorsstyrd fasförskjutning på $-1$ till varje beräkningsbastillstånd utom $\ket{0}$.
   4. Använd $H$ för varje qubit i registret.
4. Mät registret för att hämta indexet för ett objekt som är en lösning med mycket hög sannolikhet.
5. Kontrollera objektet för att se om det är en giltig lösning. Annars startar du igen.

Skriv koden för Grover-algoritmen i Q#

I det här avsnittet beskrivs hur du implementerar algoritmen i Q#. Det finns få saker att tänka på när du implementerar Grover-algoritmen. Du måste definiera vad som är ditt markerade tillstånd, hur du ska reflektera över det och hur många iterationer du ska köra algoritmen för. Du måste också definiera oraklet som implementerar funktionen för Grover-uppgiften.

Definiera det markerade tillståndet

Först definierar du vilka indata du försöker hitta i sökningen. Det gör du genom att skriva en åtgärd som tillämpar stegen b, c och d från Grover-algoritmen.

Tillsammans kallas de här stegen även grover-diffusionsoperatorn $-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);
    }
}

Åtgärden ReflectAboutMarked återspeglar bastillståndet som markeras med alternerande nollor och nollor. Det gör den genom att tillämpa Grover-diffusionsoperatorn på indatakvabitarna. Åtgärden använder en extra qubit, outputQubit, som initieras i tillståndet $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ genom att tillämpa portarna $X$ och $H$ . Åtgärden tillämpar sedan $X$-grinden på alla andra kvantbitar i registret, vilket vänder qubitens tillstånd. Slutligen tillämpas den kontrollerade $X$-grinden på den extra kvantbiten och indatakvabitarna. Den här åtgärden vänder extra qubiten om och endast om alla indatakviffbitar är i tillståndet $\ket{1}$, vilket är det markerade tillståndet.

Definiera antalet optimala iterationer

Grover-sökningen har ett optimalt antal iterationer som ger den högsta sannolikheten att mäta giltiga utdata. Om problemet har $N=2^n$ möjliga berättigade objekt, och $M$ av dem är lösningar på problemet, är det optimala antalet iterationer:

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

Att fortsätta iterera förbi det optimala antalet iterationer börjar minska sannolikheten tills du når nästan noll sannolikhet för lyckad iteration $2 N_{\text{optimal}}$. Därefter ökar sannolikheten igen tills $3 N_{\text{optimal}}$, och så vidare.

I praktiska tillämpningar vet du normalt inte hur många lösningar ditt problem har innan du löser det. En effektiv strategi för att hantera det här problemet är att "gissa" antalet lösningar $M$ genom att gradvis öka gissningen i två (dvs. $1, 2, 4, 8, 16, ..., 2^n$). En av dessa gissningar är tillräckligt nära för att algoritmen fortfarande ska hitta lösningen med ett genomsnittligt antal iterationer runt $\sqrt{\frac{N}{M}}$.

Följande Q# funktion beräknar det optimala antalet iterationer för ett visst antal kvantbitar i ett 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;
}

Funktionen CalculateOptimalIterations använder formeln ovan för att beräkna antalet iterationer och avrundar den sedan till närmaste heltal.

Definiera Grover-åtgärden

Åtgärden Q# för Grover-sökalgoritmen har tre indata:

• Antalet qubits, nQubits : Int, i qubitregistret. Det här registret kodar den preliminära lösningen på sökproblemet. Efter åtgärden mäts den.
• Antalet optimala iterationer, iterations : Int.
• En åtgärd, phaseOracle : Qubit[] => Unit) : Result[], som representerar fasoraklet för Grover-aktiviteten. Den här åtgärden tillämpar en enhetlig transformering över ett allmänt 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);
}

Åtgärden GroverSearch initierar ett register med $n$ qubits i tillståndet $\ket{0}$, förbereder registret till en enhetlig superposition och tillämpar sedan Grover-algoritmen för det angivna antalet iterationer. Själva sökningen består av att upprepade gånger reflektera över det markerade tillståndet och starttillståndet, som du kan skriva ut som Q# en for-loop. Slutligen mäter den registret och returnerar resultatet.

Koden använder tre hjälpåtgärder: PrepareUniform, ReflectAboutUniformoch ReflectAboutAllOnes.

Med tanke på ett register i tillståndet PrepareUniform alla nollor förbereder åtgärden en enhetlig superposition över alla bastillstånd.

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

Åtgärden "ReflectAboutAllOnes" återspeglar alla-ett-tillståndet.

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

Åtgärden ReflectAboutUniform återspeglar det enhetliga superpositionstillståndet. Först omvandlar den den enhetliga superpositionen till all-zero. Sedan omvandlas tillståndet all-zero till alla-ettor. Slutligen reflekterar det över alla-ett-tillståndet. Åtgärden anropas ReflectAboutUniform eftersom den kan tolkas geometriskt som en reflektion i vektorutrymmet om det enhetliga superpositionstillståndet.

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

Kör den sista koden

Nu har du alla ingredienser för att implementera en viss instans av Grover-sökalgoritmen och lösa factoringproblemet. För att slutföra åtgärden Main konfigurerar åtgärden problemet genom att ange antalet kvantbitar och antalet iterationer

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

Köra programmet

Välj önskad plattform för att köra programmet.

Relaterat innehåll

Utforska andra Q# självstudier:

• Kvantsammanflätning visar hur du skriver ett Q# program som manipulerar och mäter kvantbitar och visar effekterna av superposition och sammanflätning.
• Slumptalsgenerator för kvant visar hur du skriver ett Q# program som genererar slumpmässiga tal av kvantbitar i superposition.
• Quantum Fourier Transform utforskar hur du skriver ett Q# program som direkt adresserar specifika kvantbitar.
• Quantum Katas är självstudier och programmeringsövningar som syftar till att lära ut elementen i kvantberäkning och Q# programmering på samma gång.