Övning – implementera Grovers algoritm för att lösa graffärgningsproblem

Slutförd

I den här modulen implementerar du slutligen Grovers sökalgoritm från orakeldefinitionen för graffärgningsproblem till logiken för att hantera algoritmens slumpmässiga natur.

Anteckning

Den övergripande koden i det här exemplet är av nödvändiga skäl ganska lång, eftersom den inte bara omfattar den generiska Grover-algoritmen utan även den problemspecifika orakelimplementeringen.

Den här enheten fokuserar på de viktigaste elementen i koden – den fullständiga kodanalysen ligger utanför den här modulens omfattning. Sammanfattningsavsnittet i den här modulen har dock länkar till material så att du kan gå djupare i de olika begreppen som beskrivs här.

Implementering av generisk kvantsökning

Här är den Q#-kod som implementerar kärnan i Grover-algoritmen.

namespace ExploringGroversSearchAlgorithm {
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Intrinsic;

    operation RunGroversSearch(register : Qubit[], phaseOracle : ((Qubit[]) => Unit is Adj), iterations : Int) : Unit {
        // Prepare an equal superposition of all basis states
        ApplyToEach(H, register);
        
        // Iterations of Grover's search
        for _ in 1 .. iterations {
            // Step 1: apply the oracle
            phaseOracle(register);
            // Step 2: reflection around the mean
            within {
                ApplyToEachA(H, register);
                ApplyToEachA(X, register);
            } apply {
                Controlled Z(Most(register), Tail(register));
            }
        }
    }
}

Låt oss belysa en viktig egenskap för den här koden: den här koden är generisk – den kan användas för att lösa alla sökproblem!

Vi lämnar över kvantoraklet – den enda åtgärd som förlitar sig på kunskapen om probleminstansen som vi vill lösa – som en parameter till sökkoden.

Anteckning

Med Q# kan vi ändra åtgärder och funktioner som värden, definiera variabler som lagrar anropsbara argument och lämna över dem som argument till andra åtgärder. De anropsbara argumenten kan sedan anropas i koden precis som andra åtgärder, så som vi ser i steg 1 i slingan.

Med den här funktionen kan vi skriva koncis algoritmkod på hög nivå och återanvända den för flera tillämpningar.

Koden tar också antalet iterationer som ska utföras som en parameter. Detta är återigen för att behålla logiken med att välja antal iterationer (antingen baserat på vår kunskap om problemet eller slumpmässigt) utanför den generiska implementeringen av algoritmen.

Slutligen hålls den problemspecifika logiken med att mäta resultatet och tolka det också utanför implementeringen. I stället tar åtgärden en kvantbitsmatris som en indata och koden som anropar den kan mäta tillståndet för dessa kvantbitar efteråt.

Anteckning

I det här läget definierar koden inte en @EntryPoint, eftersom ifall den körs på egen hand inte skulle göra något intressant. I nästa avsnitt ser vi hur vi förbereder alla nödvändiga parametrar och skickar dem till koden.

Vi löser graffärgningsproblemet!

Nu är du redo att sätta ihop allt du har lärt dig hittills och beräkna det minsta antalet olika bandbredder som vi måste tilldela till rymdstationer.

Antalet bandbredder varierar beroende på antalet stationer och hur nära de är varandra. Kom ihåg att det här problemet är en instans av graffärgningsproblem. Här står färgen för en specifik bandbredd. Vi rekommenderar starkt att du börjar lösa en mindre version av problemet och endast överväger att ha fem anslutna rymdstationer som de är i diagrammet i enhet 2.

Här är den fullständiga koden.

namespace ExploringGroversSearchAlgorithm {
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Diagnostics;
    open Microsoft.Quantum.Intrinsic;


    operation MarkColorEquality(c0 : Qubit[], c1 : Qubit[], target : Qubit) : Unit is Adj+Ctl {
        within {
            for (q0, q1) in Zipped(c0, c1) {
                CNOT(q0, q1);
            }
        } apply {
            (ControlledOnInt(0, X))(c1, target);
        }
    }


    operation MarkValidVertexColoring(
        edges : (Int, Int)[], 
        colorsRegister : Qubit[], 
        target : Qubit
    ) : Unit is Adj+Ctl {
        let nEdges = Length(edges);
        let colors = Chunks(2, colorsRegister);
        use conflictQubits = Qubit[nEdges];
        within {
            for ((start, end), conflictQubit) in Zipped(edges, conflictQubits) {
                MarkColorEquality(colors[start], colors[end], conflictQubit);
            }
        } apply {
            (ControlledOnInt(0, X))(conflictQubits, target);
        }
    }


    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);
            within {
                ApplyToEachA(H, register);
                ApplyToEachA(X, register);
            } apply {
                Controlled Z(Most(register), Tail(register));
            }
        }
    }


    @EntryPoint()
    operation SolveGraphColoringProblem() : Unit {
        // Graph description: hardcoded from the example.
        let nVertices = 5;
        let edges = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (3, 4)];

        // Define the oracle that implements this graph coloring.
        let markingOracle = MarkValidVertexColoring(edges, _, _);
        let phaseOracle = ApplyMarkingOracleAsPhaseOracle(markingOracle, _);

        // Define the parameters of the search.
        
        // Each color is described using 2 bits (or qubits).
        let nQubits = 2 * nVertices;

        // The search space is all bit strings of length nQubits.
        let searchSpaceSize = 2 ^ (nQubits);

        // The number of solutions is the number of permutations of 4 colors (over the first four vertices) = 4!
        // multiplied by 3 colors that vertex 4 can take in each case.
        let nSolutions = 72;

        // The number of iterations can be computed using a formula.
        let nIterations = Round(PI() / 4.0 * Sqrt(IntAsDouble(searchSpaceSize) / IntAsDouble(nSolutions)));

        mutable answer = new Bool[nQubits];
        use (register, output) = (Qubit[nQubits], Qubit());
        mutable isCorrect = false;
        repeat {
            RunGroversSearch(register, phaseOracle, nIterations);
            let res = MultiM(register);
            // Check whether the result is correct.
            markingOracle(register, output);
            if (MResetZ(output) == One) {
                set isCorrect = true;
                set answer = ResultArrayAsBoolArray(res);
            }
            ResetAll(register);
        } until (isCorrect);
        // Convert the answer to readable format (actual graph coloring).
        let colorBits = Chunks(2, answer);
        Message("The resulting graph coloring:");
        for i in 0 .. nVertices - 1 {
            Message($"Vertex {i} - color {BoolArrayAsInt(colorBits[i])}");
        }
    }
}

Anteckning

Det här kodfragmentet körs för närvarande inte på några tillgängliga Azure Quantum-maskinvarumål eftersom de anropbara , samt variabelomtilldelingarna i ResultArrayAsBoolArray måttberoende -block, kräver en QPU med fullständig if beräkningsprofil .

Learn-modulkoden som inte innehåller något sådant meddelande är körbar på aktuella maskinvarumål.

Du bör känna igen de tre första åtgärderna som orakelimplementering från enhet 4 och den fjärde åtgärden som den generiska sökalgoritm som vi implementerade tidigare i den här enheten.

Detta lämnar oss med den senaste åtgärden, som definierar problemet som vi löser, skapar alla nödvändiga parametrar, anropar den allmänna sökimplementeringen och tolkar resultaten.

  • Observera definitionen av variabler markingOracle och phaseOracle – de två varianterna av att implementera vårt problem som en kvantåtgärd. Båda variablerna använder delvis tillämpning, det vill säga åtgärdar flera parametrar för en åtgärd för att skapa en annan åtgärd som kräver färre parametrar. Så åtgärden tar tre parametrar (listan över grafkanter, indataregistret och målqubiten), medan åtgärden bara tar två parametrar (indataregistret och målkvanterarbiten) med listan över grafkanter som är fixerade för MarkValidVertexColoring markingOracle edges variabeln.

  • Som vi sett i föregående enhet beror det optimala antalet iterationer på både storleken på sökutrymmet och antalet lösningar.

    Det första är enkelt att definiera – valfri bitsträng av 2 * nVertices bitar kan tolkas som en potentiell färg på nVertices hörn, så det finns $2^{2\textrm{nVertices}} = 1024$ kandidater.

    Det är svårare att uppskatta antalet lösningar, men i vårt exempel är grafstrukturen enkel att analysera. Hörnen 0-3 bildar en hel graf, så de måste tilldelas distinkta färger i vilken ordning som helst, eftersom vi har totalt fyra tillgängliga färger, det finns $4!$ sätt att göra detta på. Hörn 4 är bara kopplat till hörn 3, så det kan ha alla färger förutom färgen för hörn 3, vilket ger oss tre alternativ för varje färg för de andra hörnen. Det totala antalet lösningar är $4! \cdot 3 = 72$.

    Vi börjar med att använda $\frac{\pi}{4} \sqrt{\frac{N}{M}} = 2,96 \approx 3$ iterationer.

  • repeat ... until-slingan hanterar möjligheten att få ett felaktigt svar på den första körningen av algoritmen. Loopens brödtext kör algoritmen en gång, mäter qubitregistret för att få resultatet och kontrollerar sedan om det är en lösning på problemet. Om så är fallet uppdateras variabeln correct för att avspegla detta och mätresultatet konverteras till en bitmatris. Annars körs algoritmen igen.

Om du kör algoritmen visas utdata som liknar följande:

The resulting graph coloring:
Vertex 0 - color 0
Vertex 1 - color 2
Vertex 2 - color 1
Vertex 3 - color 3
Vertex 4 - color 2

För fem rymdstationer med dessa egenskaper måste vi tilldela fyra olika bandbredder baserat på dessa resultat.

Titta på amplituderna

Nu ska vi ta en titt på hur amplituderna i grundtillstånden är i nyckelpunkterna vid körningen av algoritmen.

Grattis! Du har implementerat din första kvantsökalgoritm och använde den för att lösa ett litet problem.

I nästa enhet tittar du på andra exempel och tar en titt på vilka typer av verkliga problem som är, eller inte är, ett bra sätt att använda Grovers algoritm för att lösa dem.