Självstudier: Implementera Grovers sökalgoritm i Q#

I den här självstudien lär du dig att implementera Grovers algoritm i Q# för att lösa sökbaserade problem.

Grovers algoritm är en av de mest berömda algoritmerna inom kvantberäkning. Det problem som den löser kallas ofta för att "söka i en databas", men det är mer korrekt att tänka på det när det gäller sökproblemet.

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

Förutsättningar

• Installera Quantum Development Kit (QDK) med önskat språk och utvecklingsmiljö.
• Om du redan har installerat QDK kontrollerar du att du har uppdaterat till den senaste versionen.
• Skapa ett Q# projekt för antingen Q# ett program, med ett Python-värdprogrameller ett C#-värdprogram.

I den här självstudien får du lära dig att:

Grovers algoritmuppgift

Givet en klassisk funktion $f(x): \ {0,1 \ }^n \rightarrow \ {0,1 }$, där $n$ är sökutrymmets bitstorlek, hittar du indata \ $x_0$ som $f(x_0)=1$.

För att implementera Grovers algoritm för att lösa ett problem måste du:

1. Transformera problemet till formen av en Grover-uppgift: anta till exempel att vi vill hitta faktorerna för ett heltal $M$ med grover-algoritmen. Du kan omvandla heltalsfaktoriseringsproblemet till en Grovers 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 vi omvandlade problemet till en Grovers uppgift.
2. Implementera funktionen för Grover-uppgiften som ett kvantoraklet: För att implementera Grovers algoritm måste du implementera funktionen $f(x)$ för grover-uppgiften som ett kvantoraklet.
3. Använd Grovers algoritm med ditt orakel för att lösa uppgiften: när du har ett kvantoraklet kan du ansluta det till Grovers algoritmimplementering för att lösa problemet och tolka utdata.

Snabb översikt över Grovers algoritm

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

1. Börja med ett register $n$ qubits initierat 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. Tillämpa följande åtgärder på register-$N_{\text{optimal}}$ gånger:
   1. Fasaraklet $O_f$ som tillämpar en villkorlig fasväxling på $-1$ för lösningsobjekten.
   2. Tillämpa $H$ på varje qubit i registret.
   3. Tillämpa $-O_0$, en villkorlig fasförskjutning av $-1$ till varje beräkningsbastillstånd utom $\ket {0} $.
   4. Tillämpa $H$ på 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 om det är en giltig lösning. Om inte, börja om igen.

Skriva koden för Grovers algoritm

Nu ska vi se hur du implementerar algoritmen i Q# .

Grovers operator

Skriv först en åtgärd som tillämpar stegen b, c och d från loopen ovan. Tillsammans kallas de här stegen även Grover-operatorn $-H^{\otimes n} O_0 H^{\otimes n}$

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {

    within {
        ApplyToEachA(H, inputQubits);
        ApplyToEachA(X, inputQubits);
    } apply {
        Controlled Z(Most(inputQubits), Tail(inputQubits));
    }

}

Den här åtgärden använder satsen within-apply som implementerar den automatiska konjugationen av åtgärder som inträffar i Grovers operator för operatorn .

En bra övning för att förstå koden och åtgärderna är att kontrollera med penna och papper att åtgärden ReflectAboutUniform tillämpar Grovers operator. Observera att åtgärden bara har en annan effekt än identiteten om och bara om alla qubitar är i tillståndet Controlled Z(Most(inputQubits),Tail(inputQubits)) $\ket {1} $.

Du kan kontrollera vad var och en av de åtgärder och funktioner som används är genom att titta i API-dokumentationen:

• ApplyToEachA
• Most
• Tail

Åtgärden anropas eftersom den kan tolkas geometriskt som en reflektion i ReflectAboutUniform vektorutrymmet om det enhetliga superpositionstillståndet.

Antal iterationer

Grovers sökning 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}}$$

Om vi fortsätter att iterera förbi börjar antalet minska sannolikheten tills vi når nästan noll lyckade sannolikheter för iteration $2 N_{\text{optimal}}$. Därefter växer sannolikheten igen och util $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 progressivt öka gissningen i två (d.v.s. $1, 2, 4, 8, 16, ..., 2^n$). En av dessa gissningar är tillräckligt nära att algoritmen fortfarande hittar lösningen med ett genomsnittligt antal iterationer runt $\sqrt{\frac{N}{M}}$.

Slutföra Grovers åtgärd

Nu är du redo att skriva en Q# åtgärd för Grovers sökalgoritm. Den har tre indata:

• En register : Qubit[] qubit-matris som ska initieras i tillståndet Zero alla. Det här registret kodar den trevande lösningen på sökproblemet. Efter åtgärden mäts den.
• En åtgärd phaseOracle : (Qubit[]) => Unit is Adj som representerar fasoraklet för Grover-uppgiften. Den här åtgärden tillämpar en enhetstransformering över ett allmänt qubitregister.
• Ett heltal iterations : Int som representerar iterationerna av algoritmen.

operation RunGroversSearch(register : Qubit[], phaseOracle : (Qubit[]) => Unit is Adj, iterations : Int) : Unit {
    // Prepare register into uniform superposition.
    ApplyToEach(H, register);
    // Start Grover's loop.
    for _ in 1 .. iterations {
        // Apply phase oracle for the task.
        phaseOracle(register);
        // Apply Grover's diffusion operator.
        ReflectAboutUniform(register);
    }
}

Implementera oraklet

En av de viktigaste egenskaperna som gör Grovers algoritm snabbare är möjligheten för kvantdatorer att utföra beräkningar inte bara på enskilda indata, utan även på superpositioner av indata. Du behöver beräkna funktionen $f(x)$ som beskriver instansen av ett sökproblem med endast kvantåtgärder. På så sätt kan den beräknas över en superposition av indata.

Tyvärr finns det inget automatiskt sätt att översätta klassiska funktioner till kvantåtgärder. Det är ett öppet forskningsområde inom datavetenskap som kallas reversibel databehandling.

Det finns dock vissa riktlinjer som kan hjälpa dig att översätta funktionen $f(x)$ till ett kvantakel:

1. Dela upp den klassiska funktionen i små byggstenar som är enkla att implementera. Du kan till exempel försöka att delar upp funktionen $f(x)$ i en serie aritmetiska åtgärder eller booleska logikgrindar.
2. Använd byggblocken på högre nivå i biblioteket Q# för att implementera mellanliggande åtgärder. Om du till exempel delar upp funktionen i en kombination av enkla aritmetiska åtgärder kan du använda biblioteket Numeriska för att implementera de mellanliggande åtgärderna.

Följande likvärdighetstabell kan vara användbar när du implementerar booleska funktioner i Q# .

Exempel: Kvantåtgärd för att kontrollera om ett tal är en divisor

Vi kan till exempel se hur vi uttrycker funktionen $f_M(x)=1[r]$ för faktoriseringsproblemet som en kvantåtgärd i Q# .

Klassiskt skulle du beräkna resten av divisionen $M/x$ och kontrollera om den är lika med noll. Om det är det matar programmet ut 1 , och om det inte är det matar programmet ut 0 . Du måste:

• Beräkna resten av divisionen.
• Tillämpa en kontrollerad åtgärd över utdatabiten så att det 1 är om resten är 0 .

Därför måste du beräkna en division av två tal med en kvantåtgärd. Som tur är behöver du inte skriva kretsen som implementerar divisionen från grunden, du kan använda åtgärden från biblioteket DivideI Numeriska i stället.

När vi tittar på beskrivningen av står det att den behöver DivideI tre qubit-register: $n$-bit-t dividend xs , $n$-bit divisor och ys den $n$-bit som måste result initieras i tillståndet Zero . Åtgärden är Adj + Ctl , så vi kan konjugera den och använda den i tillämpa-instruktioner. I beskrivningen står det också att t dividenden i indataregistret xs ersätts med resten. Detta är perfekt eftersom vi uteslutande är intresserade av resten och inte av resultatet av åtgärden.

Du kan sedan skapa en kvantåtgärd som gör följande:

1. Tar tre indata:
   • T dividend, number : Int . Det här är $M$ i $f_M(x)$.
   • En qubitmatris som kodar divisorn, divisorRegister : Qubit[] . Det här är $x$ i $f_M(x)$, möjligen i ett superpositionstillstånd.
   • En målqubit, , som vänder om utdata för target : Qubit $f_M(x)$ är $1$.
2. Beräknar divisionen $M/x$ med endast omvändbara kvantåtgärder och vänder tillståndet för om och endast om target resten är noll.
3. Återställer alla åtgärder utom vända för , för att returnera de extra qubits som används till tillståndet noll utan att införa target oåterkalleliga åtgärder, till exempel mätning. Det här steget är viktigt för att bevara entanglementering och superposition under processen.

Koden för att implementera den här kvantåtgärden är:

operation MarkDivisor (
    dividend : Int,
    divisorRegister : Qubit[],
    target : Qubit
) : Unit is Adj + Ctl {
    // Calculate the bit-size of the dividend.
    let size = BitSizeI(dividend);
    // Allocate two new qubit registers for the dividend and the result.
    use dividendQubits = Qubit[size];
    use resultQubits = Qubit[size];
    // Create new LittleEndian instances from the registers to use DivideI
    let xs = LittleEndian(dividendQubits);
    let ys = LittleEndian(divisorRegister);
    let result = LittleEndian(resultQubits);

    // Start a within-apply statement to perform the operation.
    within {
        // Encode the dividend in the register.
        ApplyXorInPlace(dividend, xs);
        // Apply the division operation.
        DivideI(xs, ys, result);
        // Flip all the qubits from the remainder.
        ApplyToEachA(X, xs!);
    } apply {
        // Apply a controlled NOT over the flipped remainder.
        Controlled X(xs!, target);
        // The target flips if and only if the remainder is 0.
    }
}

Omvandla åtgärden till ett fasakel

Åtgärden kallas för ett markeringskel eftersom den markerar giltiga objekt med MarkDivisor en sammantrasslad extra qubit ( target ). Grovers algoritm behöver dock ett fasorakel, det vill säga ett orakel som tillämpar en villkorlig fasförskjutning på $-1$ för lösningsobjekten. Men oroa dig inte, åtgärden ovan skrevs inte i onödan. Det är mycket enkelt att växla från en orakeltyp till en annan i Q# .

Du kan använda val annat markeringsakel som ett fasakel med följande åtgärd:

operation ApplyMarkingOracleAsPhaseOracle(
    markingOracle : (Qubit[], Qubit) => Unit is Adj,
    register : Qubit[]
) : Unit is Adj {
    use target = Qubit();
    within {
        X(target);
        H(target);
    } apply {
        markingOracle(register, target);
    }
}

Den här berömda omvandlingen kallas ofta för en kickback-fas och används ofta i många kvantberäkningsalgoritmer. Du hittar en detaljerad förklaring av den här tekniken i den här Microsoft Learn modulen.

Räkna siffror med Grovers sökning

Nu har du alla komponenter för att implementera en viss instans av Grovers sökalgoritm och lösa faktoriseringsproblemet.

Vi använder programmet nedan för att hitta faktorn 21. För att förenkla koden antar vi att vi känner till antalet $M$ av giltiga objekt. I det här fallet $M =4$, eftersom det finns två faktorer, 3 och 7, plus 1 och 21 själv.

namespace GroversTutorial {
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Arithmetic;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Preparation;

    @EntryPoint()
    operation FactorizeWithGrovers(number : Int) : Unit {

        // Define the oracle that for the factoring problem.
        let markingOracle = MarkDivisor(number, _, _);
        let phaseOracle = ApplyMarkingOracleAsPhaseOracle(markingOracle, _);
        // Bit-size of the number to factorize.
        let size = BitSizeI(number);
        // Estimate of the number of solutions.
        let nSolutions = 4;
        // The number of iterations can be computed using the formula.
        let nIterations = Round(PI() / 4.0 * Sqrt(IntAsDouble(size) / IntAsDouble(nSolutions)));

        // Initialize the register to run the algorithm
        use (register, output) = (Qubit[size], Qubit());
        mutable isCorrect = false;
        mutable answer = 0;
        // Use a Repeat-Until-Succeed loop to iterate until the solution is valid.
        repeat {
            RunGroversSearch(register, phaseOracle, nIterations);
            let res = MultiM(register);
            set answer = BoolArrayAsInt(ResultArrayAsBoolArray(res));
            // Check that if the result is a solution with the oracle.
            markingOracle(register, output);
            if MResetZ(output) == One and answer != 1 and answer != number {
                set isCorrect = true;
            }
            ResetAll(register);
        } until isCorrect;

        // Print out the answer.
        Message($"The number {answer} is a factor of {number}.");

    }

    operation MarkDivisor (
        dividend : Int,
        divisorRegister : Qubit[],
        target : Qubit
    ) : Unit is Adj+Ctl {
        let size = BitSizeI(dividend);
        use (dividendQubits, resultQubits) = (Qubit[size], Qubit[size]);
        let xs = LittleEndian(dividendQubits);
        let ys = LittleEndian(divisorRegister);
        let result = LittleEndian(resultQubits);
        within{
            ApplyXorInPlace(dividend, xs);
            DivideI(xs, ys, result);
            ApplyToEachA(X, xs!);
        }
        apply{
            Controlled X(xs!, target);
        }
    }

    operation PrepareUniformSuperpositionOverDigits(digitReg : Qubit[]) : Unit is Adj + Ctl {
        PrepareArbitraryStateCP(ConstantArray(10, ComplexPolar(1.0, 0.0)), LittleEndian(digitReg));
    }

    operation ApplyMarkingOracleAsPhaseOracle(
        markingOracle : (Qubit[], Qubit) => Unit is Adj,
        register : Qubit[]
    ) : Unit is Adj {
        use target = Qubit();
        within {
            X(target);
            H(target);
        } apply {
            markingOracle(register, target);
        }
    }

    operation RunGroversSearch(register : Qubit[], phaseOracle : ((Qubit[]) => Unit is Adj), iterations : Int) : Unit {
        ApplyToEach(H, register);
        for _ in 1 .. iterations {
            phaseOracle(register);
            ReflectAboutUniform(register);
        }
    }

    operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
        within {
            ApplyToEachA(H, inputQubits);
            ApplyToEachA(X, inputQubits);
        } apply {
            Controlled Z(Most(inputQubits), Tail(inputQubits));
        }
    }
}

Kör den med Visual Studio eller Visual Studio Code

Programmet ovan kör åtgärden eller funktionen som är markerad med attributet på en simulator eller resursberäknare, beroende på @EntryPoint() projektkonfigurationen och kommandoradsalternativen.

dotnet build

dotnet run --no-build --number 21

I båda miljöerna bör du nu se följande meddelande i terminalen:

The number 7 is a factor of 21.

Extra: kontrollera statistiken med Python

Hur kan du kontrollera att algoritmen fungerar korrekt? Om vi till exempel ersätter Grovers sökning med en slumptalsgenerator i koden ovan, kommer den efter ~$N$-försök också att hitta en faktor.

Nu ska vi skriva ett litet Python-skript för att kontrollera att programmet fungerar som det ska.

Först ändrar du huvudåtgärden för att ta bort loopen repeat-until-success, i stället för att mata ut det första måttresultatet när du har kört Grovers sökning:

@EntryPoint()
operation FactorizeWithGrovers2(number : Int) : Int {

    let markingOracle = MarkDivisor(number, _, _);
    let phaseOracle = ApplyMarkingOracleAsPhaseOracle(markingOracle, _);
    let size = BitSizeI(number);
    let nSolutions = 4;
    let nIterations = Round(PI() / 4.0 * Sqrt(IntAsDouble(size) / IntAsDouble(nSolutions)));

    use register = Qubit[size] {
        RunGroversSearch(register, phaseOracle, nIterations);
        let res = MultiM(register);
        return ResultArrayAsInt(res);
        // Check whether the result is correct.
    }

}

Observera att utdatatypen har ändrats Unit från till , vilket är Int användbart för Python-programmet. Python-programmet är mycket enkelt. Den anropar bara åtgärden FactorizeWithGrovers2 flera gånger och ritar resultatet i ett histogram.

Koden är följande:

import qsharp
qsharp.packages.add("Microsoft.Quantum.Numerics")
qsharp.reload()
from GroversTutorial import FactorizeWithGrovers2
import matplotlib.pyplot as plt
import numpy as np

def main():

    # Instantiate variables
    frequency =  {}
    N_Experiments = 1000
    results = []
    number = 21

    # Run N_Experiments times the Q# operation.
    for i in range(N_Experiments):
        print(f'Experiment: {i} of {N_Experiments}')
        results.append(FactorizeWithGrovers2.simulate(number = number))

    # Store the results in a dictionary
    for i in results:
        if i in frequency:c
            frequency[i]=frequency[i]+1
        else:
            frequency[i]=1

    # Sort and print the results
    frequency = dict(reversed(sorted(frequency.items(), key=lambda item: item[1])))
    print('Output,  Frequency' )
    for k, v in frequency.items():
        print(f'{k:<8} {v}')

    # Plot an histogram with the results
    plt.bar(frequency.keys(), frequency.values())
    plt.xlabel("Output")
    plt.ylabel("Frequency of the outputs")
    plt.title("Outputs for Grover's factoring. N=21, 1000 iterations")
    plt.xticks(np.arange(1, 33, 2.0))
    plt.show()

if __name__ == "__main__":
    main()

Programmet genererar följande histogram:

Som du ser i histogrammet matar algoritmen ut lösningarna på sökproblemet (1, 3, 7 och 21) med mycket högre sannolikhet än icke-lösningarna. Du kan tänka på Grovers algoritm som en kvants slumpgenerator som är målmedveten för de index som är lösningar på sökproblemet.

Nästa steg

Nu när du vet hur du implementerar Grovers algoritm kan du försöka omvandla ett matematiskt problem till en sökuppgift och lösa det med Q# Grovers algoritm.