Zelfstudie: Zoekalgoritme van Grover implementeren in Q#

In deze zelfstudie leert u hoe u het algoritme van Grover implementeert in om problemen op basis Q# van zoekopdrachten op te lossen.

Het algoritme van Grover is een van de meest beroemde algoritmen in kwantumcomputing. Het probleem dat wordt opgelost, wordt vaak aangeduid als 'zoeken in een database', maar het is nauwkeuriger om dit te zien in termen van het zoekprobleem.

Elke zoektaak kan wiskundig worden geformuleerd met een abstracte functie $f(x)$ die zoekitems accepteert $x$. Als het item $x$ een oplossing is voor de zoektaak, $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$.

Vereisten

• Installeer de Quantum Development Kit (QDK) met behulp van de taal en ontwikkelomgeving van uw voorkeur.
• Als u de QDK al hebt geïnstalleerd, moet u ervoor zorgen dat u hebt bijgewerkt naar de nieuwste versie.
• Maak een Q# project voor een toepassing Q# ,met een Python-hostprogrammaof een C#-hostprogramma.

In deze zelfstudie leert u het volgende:

Algoritmetaak van Grover

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 probleem op te lossen, moet u het volgende doen:

1. Transformeer het probleem in de vorm van de taak van Grover: stel bijvoorbeeld dat we de factoren van een geheel getal $M$ willen vinden met behulp van het algoritme van Grover. U kunt het probleem met integer factorization transformeren naar de 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$ zijn. Op deze manier zijn de gehele getallen $x_i$ die $f_M(x_i)=1$ maken de factoren van $M$ en hebben we het probleem omgezet in de taak van Grover.
2. Implementeert de functie van de taak van Grover als een kwantumakel: als u het algoritme van Grover wilt implementeren, moet u de functie $f(x)$ van de taak van grover implementeren als een kwantum oracle .
3. Gebruik het algoritme van Grover met uw orakel om de taak op te lossen: zodra u een kwantumorkel hebt, kunt u het in de algoritme-implementatie van grover aansluiten om het probleem op te lossen en de uitvoer te interpreteren.

Snel overzicht van het algoritme van Grover

Stel dat er $N=2^n$ in aanmerking komende items voor de zoektaak zijn en ze worden geïndexeerd door elk item een geheel getal van $0$ toe te wijzen aan $N-1$. De stappen van het algoritme zijn:

1. Begin met een register van $n$ qubits die zijn initialiseerd in de status $\ket {0} $.
2. 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$$
3. Pas de volgende bewerkingen toe op het register $N_{\text{optimal}}$ keer:
   1. Het faseakel $O_f$ dat een voorwaardelijke faseverschuiving van $-1$ voor de oplossingsitems van toepassing is.
   2. Pas $H$ toe op elke qubit in het register.
   3. Pas $-O_0$ toe, een voorwaardelijke faseverschuiving van $-1$ naar elke rekenkundige basistoestand, met uitzondering van $\ket {0} $.
   4. Pas $H$ toe op elke qubit in het register.
4. Meet het register om de index te verkrijgen van een item dat een oplossing is met een zeer hoge waarschijnlijkheid.
5. Controleer of het een geldige oplossing is. Zo niet, start u opnieuw.

De code schrijven voor het algoritme van Grover

Laten we nu eens kijken hoe u het algoritme implementeert in Q# .

De operator van Grover voor het maken van een fout

Schrijf eerst een bewerking die de stappen b, c en d uit de bovenstaande lus gebruikt. Samen worden deze stappen ook wel de grover operator $-H^{\otimes n} genoemd O_0 H^{\otimes n}$

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

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

}

Deze bewerking maakt gebruik van de within-apply-instructie die de automatische vervoeging implementeert van bewerkingen die plaatsvinden in de operator voor het gebruik van grover.

Een goede oefening om inzicht te krijgen in de code en de bewerkingen is om met pen en papier te controleren of de bewerking de operator voor het gebruik van ReflectAboutUniform grover's moet uitvoeren. U ziet dat de bewerking alleen een ander effect heeft dan de identiteit als en alleen als alle Controlled Z(Most(inputQubits),Tail(inputQubits)) qubits de status $\ket {1} $hebben.

U kunt controleren wat elk van de gebruikte bewerkingen en functies is door de API-documentatie te lezen:

• ApplyToEachA
• Most
• Tail

De bewerking wordt aangeroepen omdat deze geometrisch kan worden geïnterpreteerd als een reflectie in de ReflectAboutUniform vectorruimte over de uniforme superpositietoestand.

Aantal iteraties

De zoekopdracht van Grover heeft een optimaal aantal iteraties dat de hoogste waarschijnlijkheid van het meten van een geldige uitvoer oplevert. Als het probleem $N=2^n$ mogelijke in aanmerking komende items heeft, en $M$ ervan oplossingen voor het probleem zijn, is het optimale aantal iteraties:

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

Doorgaan met het itereren van dat getal begint die waarschijnlijkheid te verminderen totdat we bijna nul succeskans bereiken bij iteratie $2 N_{\text{optimal}}$. Daarna neemt de waarschijnlijkheid weer toe en gebruikt util $3 N_{\text{optimal}}$ en meer.

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 het 'raden' van het aantal oplossingen $M$ door de raden in twee machten progressief te verhogen (dat wil zeggen$ 1, 2, 4, 8, 16, ..., 2^n$). Een van deze gissen is voldoende dicht bij elkaar dat het algoritme de oplossing nog steeds zal vinden met een gemiddeld aantal iteraties rond $\sqrt{\frac{N}{M}}$.

De bewerking van Grover voltooien

U bent nu klaar om een bewerking te Q# schrijven voor het zoekalgoritme van Grover. Deze heeft drie invoer:

• Een qubit-matrix register : Qubit[] die in de status All moet worden Zero initialiseerd. Met dit register wordt de voorlopige oplossing voor het zoekprobleem gecodeerd. Na de bewerking wordt deze gemeten.
• Een bewerking phaseOracle : (Qubit[]) => Unit is Adj die het fase-orakel voor de taak van Grover vertegenwoordigt. Met deze bewerking wordt een unitaire transformatie toegepast op een algemeen qubitregister.
• Een geheel iterations : Int getal dat de iteraties van het algoritme vertegenwoordigt.

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

Het orakel implementeren

Een van de belangrijkste eigenschappen die het algoritme van Grover sneller maakt, is de mogelijkheid van kwantumcomputers om berekeningen uit te voeren, niet alleen op afzonderlijke invoer, maar ook op superposities van invoer. U moet de functie $f(x)$ berekenen die het exemplaar van een zoekprobleem beschrijft met behulp van alleen kwantumbewerkingen. Op deze manier kan deze worden berekend via een superpositie van invoer.

Er is helaas geen automatische manier om klassieke functies te vertalen naar kwantumbewerkingen. Het is een open onderzoeksveld in computerwetenschappen, omkeerbare computing genoemd.

Er zijn echter enkele richtlijnen die u kunnen helpen om uw functie $f(x)$ om te zetten in een kwantum oracle:

1. Splits de klassieke functie op in kleine bouwstenen die eenvoudig zijn te implementeren. U kunt bijvoorbeeld proberen om uw functie $f(x)$ op te maken in een reeks rekenkundige bewerkingen of Booleaanse logische poorten.
2. Gebruik de bouwstenen op een hoger niveau van de Q# bibliotheek om de tussenliggende bewerkingen te implementeren. Als u uw functie bijvoorbeeld hebt gedecomprimeerd in een combinatie van eenvoudige rekenkundige bewerkingen, kunt u de bibliotheek Numeriek gebruiken om de tussenliggende bewerkingen te implementeren.

De volgende equivalentietabel kan nuttig zijn bij het implementeren van Booleaanse functies in Q# .

Voorbeeld: Kwantumbewerking om te controleren of een getal een deler is

Laten we eens kijken hoe we de functie $f_M(x)=1[r]$ van het factoreringsprobleem uitdrukken als een kwantumbewerking in Q# .

In klassieke vorm berekent u de rest van de deling $M/x$ en controleert u of deze gelijk is aan nul. Als dat het is, wordt door het programma uitgevoerd en als dat niet het is, wordt 1 door het programma 0 uitgevoerd. U moet het volgende doen:

• Bereken de rest van de deling.
• Pas een gecontroleerde bewerking toe op de uitvoer-bit, zodat het 1 restant 0 is.

U moet dus een deling van twee getallen berekenen met een kwantumbewerking. Gelukkig hoeft u het circuit dat de deling implementeert niet helemaal zelf te schrijven. U kunt in plaats daarvan de bewerking uit de Bibliotheek voor numerieke gegevens DivideI gebruiken.

In de beschrijving van wordt vermeld dat er drie DivideI qubitregisters nodig zijn: de $n$-bitdivid , de xs $n$-bit-deler en de ys $n$-bit result die moet worden initialiseerd in de toestand Zero . De bewerking is Adj + Ctl , zodat we deze kunnen vervoegen en gebruiken in binnen-apply-instructies. In de beschrijving wordt ook vermeld dat het dividend in het invoerregister xs wordt vervangen door de rest. Dit is perfect omdat we uitsluitend geïnteresseerd zijn in de rest en niet in het resultaat van de bewerking.

Vervolgens kunt u een kwantumbewerking maken die het volgende doet:

1. Neemt drie invoer:
   • Het dividend, number : Int . Dit is de $M$ in $f_M(x)$.
   • Een qubit-matrix die de deler coderen, divisorRegister : Qubit[] . Dit is de $x$ in $f_M(x)$, mogelijk in een superpositietoestand.
   • Een doel-qubit, , die wordt ge flipt als de uitvoer van target : Qubit $f_M(x)$ $1$ is.
2. Berekent de deling $M/x$ met behulp van alleen omkeerbare kwantumbewerkingen en spiegelt de status van als en alleen als target de rest nul is.
3. Alle bewerkingen worden teruggedraaid, met uitzondering van het spiegelen van , zodat de gebruikte aanvullende qubits worden teruggedraaid naar de status nul zonder dat er onomkeerbare bewerkingen, zoals metingen, worden target uitgevoerd. Deze stap is belangrijk om verstrengeling en superpositie tijdens het proces te behouden.

De code voor het implementeren van deze kwantumbewerking is:

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

De bewerking transformeren naar een fase-orakel

De bewerking wordt een markeringsakel genoemd, omdat de geldige items met een verstrengelde MarkDivisor hulpqubit ( ) worden target markeert. Het algoritme van Grover heeft echter een fase-orakel nodig, dat wil zeggen, een orakel dat een voorwaardelijke fase shift van $-1$ voor de oplossingsitems past. Maar maak u geen angst, de bovenstaande bewerking is niet in de weg gelopen. Het is heel eenvoudig om over te schakelen van het ene oracletype naar het andere in Q# .

U kunt elk markerings oracle toepassen als een fase-orakel met de volgende bewerking:

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

Deze beroemde transformatie staat vaak bekend als de fase kickback en wordt veel gebruikt in veel kwantumcomputingalgoritmen. U vindt een gedetailleerde uitleg van deze techniek in deze Microsoft Learn module.

Getallen factoreren met de zoekopdracht van Grover

U hebt nu alle producten om een bepaald exemplaar van het zoekalgoritme van Grover te implementeren en het factorprobleem op te lossen.

Laten we het onderstaande programma gebruiken om een factor 21 te vinden. Ter vereenvoudiging van de code gaan we ervan uit dat we het aantal geldige items $M$ kennen. In dit geval $M =4$, omdat er twee factoren zijn: 3 en 7, plus 1 en 21 zelf.

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

Voer deze uit met Visual Studio of Visual Studio Code

Met het bovenstaande programma wordt de bewerking of functie uitgevoerd die is gemarkeerd met het kenmerk in een simulator of resource-estimator, afhankelijk van de projectconfiguratie en @EntryPoint() opdrachtregelopties.

dotnet build

dotnet run --no-build --number 21

In beide omgevingen wordt nu het volgende bericht weergegeven in de terminal:

The number 7 is a factor of 21.

Extra: de statistieken controleren met Python

Hoe kunt u controleren of het algoritme correct werkt? Als we de zoekopdracht van Grover bijvoorbeeld vervangen door een generator voor willekeurige getallen in de bovenstaande code, vindt deze na ~$N$ pogingen ook een factor.

Laten we een klein Python-script schrijven om te controleren of het programma naar eigen goed staat werkt.

Wijzig eerst onze hoofdbewerking om de lus repeat-until-success te laten slagen, in plaats daarvan het eerste metingsresultaat uit te voeren na het uitvoeren van de zoekopdracht van Grover:

@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.
    }

}

Houd er rekening mee dat het uitvoertype is gewijzigd van in . Dit Unit is handig voor het Int Python-programma. Het Python-programma is zeer eenvoudig; De bewerking wordt slechts enkele FactorizeWithGrovers2 keren aanroepen en de resultaten worden in een histogram uitgevoerd.

De code is als volgt:

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()

Het programma genereert het volgende histogram:

Zoals u in het histogram kunt zien, worden met het algoritme de oplossingen voor het zoekprobleem (1, 3, 7 en 21) uitgevoerd met een veel hogere waarschijnlijkheid dan de niet-oplossingen. U kunt het algoritme van Grover zien als een kwantum-randomgenerator die doelgericht is bevooroordeeld op indexen die oplossingen zijn voor het zoekprobleem.

Volgende stappen

Nu u weet hoe u het algoritme van Grover implementeert, kunt u proberen om een wiskundig probleem om te zetten in een zoektaak en op te lossen met en het algoritme Q# van Grover.