Övning – implementera ett kvantorakel för graffärgningsproblem

Slutförd

För tillfället kan du glömma brusmeddelanden och bandbredder och endast överväga färger och hörn. Du har en bild av punkter som är anslutna via kanter och du undrar hur du kan färga punkterna.

I den här delen implementerar du ett kvantorakkel för graffärgningsproblem.

Anteckning

I den här modulen fokuserar vi på beteende på hög nivå av kvantorakel och (i följande enheter) Grovers sökalgoritm. Vi rekommenderar att du utforskar koden djupare på egen hand, särskilt för att söka efter okända drift- och språkkonstruktioner i Q#-dokumentationen.

Skapa projektet

Börja med att skapa ett Q#-projekt enligt vad som beskrivs i modulen Skapa ditt första Q#-program med hjälp av Quantum Development Kit. Så här gör du:

  1. I menyn Visa väljer du Kommandopalett.
  2. Ange Q#: Skapa nytt projekt.
  3. Välj Fristående konsolprogram.
  4. Välj en katalog som ska innehålla projektet, till exempel din hemkatalog. Ange ExploringGroversSearch som projektnamn och välj sedan Skapa projekt.
  5. I det fönster som visas längst ned väljer du Öppna nytt projekt.

Du ser två filer: projektfilen och Program.qs, som innehåller startkod.

För varje kodfragment i den här modulen bör du kopiera hela kodfragmentet för att ersätta innehållet i filen Program.qs. Öppna sedan den integrerade terminalen (från menyn Terminal och välj Ny terminal) och kör dotnet run:

dotnet run

Representera grafen

Vi behöver två parametrar för att representera en graf: antalet hörn och listan med kanter.

I Q# lagrar vi antalet hörn som ett heltal och listan över kanter som en nVertices edges matris med tupplar. Varje tuppel beskriver en kant i grafen som ett par index med hörn som är anslutna via den här kanten. Vi använder nollbaserade index så att indexvärdet kan vara mellan 0 och nVertices - 1.

Bild som visar ett diagram.

Strukturen i vår exempelgraf kan visas på följande sätt:

namespace ExploringGroversSearchAlgorithm {
    @EntryPoint()
    operation SolveGraphColoringProblem() : Unit {
        // Graph description: hardcoded from the example
        // The number of vertices is an integer
        let nVertices = 5;
        // The list of edges is an array of tuples, and each tuple is a pair of integers
        let edges = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (3, 4)];
    }
}

Representera hörnfärgning

Vi beskriver vår graffärgning med en matris med nVertices färger. I vårt exempel letar vi efter en fyrafärgning av grafen – en färg som använder högst fyra färger, kodade med heltal 0 till 3.

Vi måste representera vår färgning i en bit-sträng, så vi använder en bit-sträng med längden 2 * nVertices, där det första paret bitar kodar färgen på hörn 0, det andra paret färgen på hörn 1 och så vidare. Vi lagrar våra bitar som booleska värden, där bitarna 0 och 1 är kodade som false respektive true. Bitparet kodar ett heltalsfärgindex med liten-endian-notation, d.v.s. ett heltal 1 som är kodat som 10, med minst signifikant bit lagrad först.

Så här kodas och tolkas färgningen av vårt exempeldiagram:

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


    @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)];

        // Graph coloring: hardcoded from the example
        let coloring = [false, false, true, false, false, true, true, true, true, false];
        let colors = ["red", "green", "blue", "yellow"];

        // Interpret the coloring: split the bit string into 2-bit fragments and convert them to colors.
        let colorBits = Chunks(2, coloring);
        for i in 0 .. nVertices - 1 {
            let colorIndex = BoolArrayAsInt(colorBits[i]);
            Message($"Vertex {i} - color #{colorIndex} ({colors[colorIndex]})");
        }
    }
}

Denna kod ger följande utdata:

Vertex 0 - color #0 (red)
Vertex 1 - color #1 (green)
Vertex 2 - color #2 (blue)
Vertex 3 - color #3 (yellow)
Vertex 4 - color #1 (green)

När vi arbetar med graffärgning i ett kvantprogram, använder vi samma kodning, men med grundtillstånden $|0\rangle$ och $|1\rangle$ i stället för de klassiska bitarna false och true. Samma färgning visas som ett 10-kvantbitstillstånd $|0010011110\rangle$.

Implementera oraklet

Följande är en typisk metod för att implementera ett kvantorakel för en specifik funktion:

  1. Dela upp den klassiska funktionen i små byggstenar som är enkla att implementera.
    Du kan använda primitiva logiska grindar för att implementera en boolesk funktion. Du kan antingen använda primitiva logiska grindar direkt för att få en bättre representation av funktionen eller dra nytta av byggstenar på högre nivå som implementeras av Q#-biblioteksåtgärder.

  2. Ersätt varje klassiskt block med en sekvens av kvantgrindar som implementerar den som ett markeringsorakel.
    Du kan implementera var och en av de primitiva logiska grindarna med en eller flera kvantgrindar. Ibland behöver vi allokera en extra qubit för att rymma resultatet av grinden. Exempel:

    • Den klassiska NOT-grinden motsvarar X-grinden.
    • Den klassiska XOR-grinden kan implementeras med CNOT-grinden (kontrollerad X-grind).
    • Deb klassiska AND-grind kan realiseras med hjälp av Toffoli-grinden (en dubbel-kontrollerad X-grind) och en extra qubit.
  3. Om algoritmen anropar ett fasorakel transformerar du markeringsoraklet till ett fasorakel.
    I det här steget används ett standardtrick som kallas kickback av fas: det innebär att tillämpa ett markeringsorakel till en indatamatris av kvantbitar och en målkvantbit i ett visst tillstånd kommer att ha samma effekt på indatamatrisen som att använda ett fasorakel.

Nu ska vi se hur den här metoden fungerar för vårt problem med hörnfärgning!

Steg 1. Kontrollera om färgerna på två hörn är identiska

Det minsta byggblocket för att kontrollera om den angivna graffärgen är giltig är att ta ett par hörn som är kopplade till en kant och kontrollerar om deras tilldelade färger är samma eller olika.

Den åtgärd som implementerar den här kontrollen (MarkColorEquality) måste ta två 2-kvantbitsmatriser som indata, som representerar färgerna på hörnen och en kvantbit som vi använder för att markera resultatet av jämförelsen genom att vända dess tillstånd om färgerna är desamma. För att jämföra kvantbitsmatriser, jämför vi deras motsvarande bitar med varandra. Om alla par av bitar är desamma, är matriserna samma och färgerna på hörnen som lagras i dessa matriser är desamma. För att jämföra ett par bitar kan vi beräkna deras XOR: om resultatet är 0 är bitarna desamma; annars är de olika.

Här är Q#-koden som implementerar den här kontrollen och använder den för att jämföra två qubit-matriser: den första i tillståndet $|00\rangle$ och den andra i en lika stor superposition för alla grundtillstånd.

namespace ExploringGroversSearchAlgorithm {
    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 {
            // Iterate over pairs of qubits in matching positions in c0 and c1.
            for (q0, q1) in Zipped(c0, c1) {
                // Compute XOR of bits q0 and q1 in place (storing it in q1).
                CNOT(q0, q1);
            }
        } apply {
            // If all computed XORs are 0, the bit strings are equal - flip the state of the target.
            (ControlledOnInt(0, X))(c1, target);
        }
    }


    @EntryPoint()
    operation ShowColorEqualityCheck() : Unit {
        use (c0, c1, target) = (Qubit[2], Qubit[2], Qubit());
        // Leave register c0 in the |00⟩ state.

        // Prepare a quantum state that is a superposition of all possible colors on register c1.
        ApplyToEach(H, c1);

        // Output the initial state of qubits c1 and target. 
        // We do not include the state of qubits in the register c0 for brevity, 
        // since they will remain |00⟩ throughout the program.
        Message("The starting state of qubits c1 and target:");
        DumpRegister((), c1 + [target]);

        // Compare registers and mark the result in target qubit.
        MarkColorEquality(c0, c1, target);

        Message("");
        Message("The state of qubits c1 and target after the equality check:");
        DumpRegister((), c1 + [target]);

        // Return the qubits to |0⟩ state before releasing them.
        ResetAll(c1 + [target]);
    }
}

within ... apply-instruktionen implementerar ett gemensamt mönster i kvantberäkning: använd instruktionerna för blocken within och apply, och ”ångra” block within. Vi använder den för att se till att det inte finns någon oväntad effekt på kvantbitarna.

Anteckning

Funktionen DumpRegister liknar funktionen DumpMachine som har använts i tidigare moduler. Den skriver dock ut informationen om tillståndet för en delmängd av kvantbitar, i stället för alla kvantbitar som används av programmet. I den aktuella implementeringen av simulatorn för det fullständiga tillståndet kan DumpRegister bara användas om registret inte är sammanflätat med resten av kvantbitarna.

Här är utdata från den här koden:

The starting state of qubits c1 and target:
# wave function for qubits with ids (least to most significant): 2;3;4
∣0❭:     0.500000 +  0.000000 i  ==     *****                [ 0.250000 ]     --- [  0.00000 rad ]
∣1❭:     0.500000 +  0.000000 i  ==     *****                [ 0.250000 ]     --- [  0.00000 rad ]
∣2❭:     0.500000 +  0.000000 i  ==     *****                [ 0.250000 ]     --- [  0.00000 rad ]
∣3❭:     0.500000 +  0.000000 i  ==     *****                [ 0.250000 ]     --- [  0.00000 rad ]
∣4❭:     0.000000 +  0.000000 i  ==                          [ 0.000000 ]
∣5❭:     0.000000 +  0.000000 i  ==                          [ 0.000000 ]
∣6❭:     0.000000 +  0.000000 i  ==                          [ 0.000000 ]
∣7❭:     0.000000 +  0.000000 i  ==                          [ 0.000000 ]

The state of qubits c1 and target after the equality check:
# wave function for qubits with ids (least to most significant): 2;3;4
∣0❭:     0.000000 +  0.000000 i  ==                          [ 0.000000 ]
∣1❭:     0.500000 +  0.000000 i  ==     *****                [ 0.250000 ]     --- [  0.00000 rad ]
∣2❭:     0.500000 +  0.000000 i  ==     *****                [ 0.250000 ]     --- [  0.00000 rad ]
∣3❭:     0.500000 +  0.000000 i  ==     *****                [ 0.250000 ]     --- [  0.00000 rad ]
∣4❭:     0.500000 +  0.000000 i  ==     *****                [ 0.250000 ]     --- [  0.00000 rad ]
∣5❭:     0.000000 +  0.000000 i  ==                          [ 0.000000 ]
∣6❭:     0.000000 +  0.000000 i  ==                          [ 0.000000 ]
∣7❭:     0.000000 +  0.000000 i  ==                          [ 0.000000 ]

Anteckning

Som en påminnelse kodas indexen i DumpMachine/DumpRegister-utdata i litet endian-läge. Därför motsvarar index |1❭ bitsträng 100, med den minst signifikanta biten lagrad först.

Vi ser att i början av systemets tillstånd är

$$|00\rangle_\textrm{c0} \otimes \frac12\big(|00\rangle + |10\rangle + |01\rangle + |11\rangle\big)_\textrm{c1} \otimes |0\rangle_\textrm{target}.$$

När vi har tillämpat likhetskontrollen ändras inte registrets tillstånd c0 (du kan kontrollera detta genom att lägga till ett annat DumpRegister-anrop), men amplituderna för det kombinerade tillståndet i registret c1 och target-kvantbiten ändras. Amplituden för tillståndet $|00\rangle_\textrm{c1} \otimes |0\rangle_\textrm{target}$ blir 0, och amplituden för tillståndet $|00\rangle_\textrm{c1} \otimes |1\rangle_\textrm{target}$ blir $0,25$. Observera att de två amplitudvärdena inte bara ändras utan byts ut när den här kontrollen tillämpas.

Eftersom färgerna som har kodats i tillståndet $|00\rangle_\textrm{c0} \otimes |00\rangle_\textrm{c1} \otimes |0\rangle_\textrm{target}$ är lika, vänds tillståndet för target-kvantbiten för detta grundtillstånd, vilket ger oss det resulterande tillståndet

$$|00\rangle_\textrm{c0} \otimes \frac12\big(|00\rangle_\textrm{c1} \otimes |1\rangle_\textrm{target} + |10\rangle_\textrm{c1} \otimes |0\rangle_\textrm{target} + |01\rangle_\textrm{c1} \otimes |0\rangle_\textrm{target} + |11\rangle_\textrm{c1} \otimes |0\rangle_\textrm{target} \big).$$

Anteckning

Observera att target-kvantbiten sammanflätas med registret c1: du kan inte längre separera deras tillstånd! Om värdet för den funktion som vi utvärderar är detsamma för alla indata, kommer målkvantbiten inte sammanflätas med indataregistret, vilket sparar detta värde i stället. I vårt fall ger vissa indata $f(x) = 0$ och viss kapacitet $f (x) = 1$, så du kan inte avgränsa informationen om indata från informationen om utdata längre.

Steg 2. Kontrollera om hörnfärgningen är giltigt

Nu när vi vet hur man kontrollerar att färgerna på två hörn är olika kan vi representera kontroll av hörnfärgning på följande sätt:

  1. Iterera över alla par med hörn som är sammankopplade med kanter.
  2. Kontrollera att färgerna för de här hörnen är olika för varje par.
  3. Om alla par med hörn uppfyller detta villkor är färgningen giltig.

Om du vill implementera dessa steg som en kvantåtgärd måste du allokera extra kvantbitar för att lagra resultaten av de parvisa färgjämförelserna, en kvantbit per kant. Vi börjar med dessa kvantbitar i tillståndet $|0\rangle$ och jämför färgerna i hörnen i varje par med åtgärden MarkColorEquality som vi har sett ovan. Den vänder tillståndet för kvantbiten till $|1\rangle$ om färgerna på motsvarande par av hörn är desamma.

Slutligen beräknar vi slutresultatet. Om alla extra kvantbitar tilldelas i tillståndet $|0\rangle$, vänder vi tillståndet för vår målkvantbit för att indikera att hörnfärgningen är giltigt.

Här är Q#-koden som verifierar att hörnfärgningen är giltig.

namespace ExploringGroversSearchAlgorithm {
    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 {
            // Iterate over pairs of qubits in matching positions in c0 and c1.
            for (q0, q1) in Zipped(c0, c1) {
                // Compute XOR of bits q0 and q1 in place (storing it in q1).
                CNOT(q0, q1);
            }
        } apply {
            // If all computed XORs are 0, the bit strings are equal - flip the state of the target.
            (ControlledOnInt(0, X))(c1, target);
        }
    }


    operation MarkValidVertexColoring(
        edges : (Int, Int)[], 
        colorsRegister : Qubit[], 
        target : Qubit
    ) : Unit is Adj+Ctl {
        let nEdges = Length(edges);
        // Split the register that encodes the colors into an array of two-qubit registers, one per color.
        let colors = Chunks(2, colorsRegister);
        // Allocate one extra qubit per edge to mark the edges that connect vertices with the same color.
        use conflictQubits = Qubit[nEdges];
        within {
            for ((start, end), conflictQubit) in Zipped(edges, conflictQubits) {
                // Check that the endpoints have different colors: apply MarkColorEquality operation; 
                // if the colors are the same, the result will be 1, indicating a conflict.
                MarkColorEquality(colors[start], colors[end], conflictQubit);
            }
        } apply {
            // If there are no conflicts (all qubits are in 0 state), the vertex coloring is valid.
            (ControlledOnInt(0, X))(conflictQubits, target);
        }
    }


    @EntryPoint()
    operation ShowColoringValidationCheck() : 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)];

        // Graph coloring: hardcoded from the example
        let coloring = [false, false, true, false, false, true, true, true, false, true];

        use (coloringRegister, target) = (Qubit[2 * nVertices], Qubit());
        // Encode the coloring in the quantum register:
        // apply an X gate to each qubit that corresponds to "true" bit in the bit string.
        ApplyPauliFromBitString(PauliX, true, coloring, coloringRegister);

        // Apply the operation that will check whether the coloring is valid.
        MarkValidVertexColoring(edges, coloringRegister, target);

        // Print validation result.
        let isColoringValid = M(target) == One;
        Message($"The coloring is {isColoringValid ? "valid" | "invalid"}");

        // Return the qubits to |0⟩ state before releasing them.
        ResetAll(coloringRegister);
}
}

Anteckning

Det här kodfragmentet körs för närvarande inte på Azure Quantum maskinvarumål, eftersom allmänna resultatjämförelser för mått ( ) kräver en QPU med let isColoringValid = M(target) == One; fullständig beräkningsprofil.

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

Här är utdata från den här koden:

The coloring is valid

Bonusövningar

  • Experimentera med färgning och grafstrukturer för att se vilka som bedöms som giltiga och ogiltiga. Ett exempel på ogiltig färgning för den här grafen är [false, false, true, false, false, true, true, true, true, true], som beskriver en graf med hörn 3 och 4 tilldelade samma färg.
  • Ändra koden så att den körs på superpositioner för indata och se vad som händer.

Steg 3. Konvertera markeringsoraklet till fasoraklet

Nu har vi ett markeringsorakel, det vill säga en åtgärd som markerar de kvantbitstillstånd som representerar giltiga färger i tillståndet för en extra kvantbit. Hur kan vi använda det för att implementera ett fasorakel, det vill säga en annan åtgärd som skulle markera sådana tillstånd med hjälp av sina faser?

Vi kan göra det med hjälp av s.k. ”kickback av fas”:

  1. Allokera en extra qubit i tillståndet $\frac{1}{\sqrt2}(|0\rangle - |1\rangle)$.
  2. Använd markeringsoraklet $U_\textrm{mark}$ med denna extra qubit som mål.
    Vad händer med registret som kodar färgning i det här steget?
    • Om grundtillståndet $|x\rangle$ kodar en ogiltig färgning ändras inte tillståndet.
    • Om grundtillståndet $|x\rangle$ kodar en giltig färgning, vänder åtgärden $U_\textrm{mark}$ tillståndet för den extra kvantbiten och konverterar den till $\frac{1}{\sqrt2}(|1\rangle - |0\rangle)$, som motsvarar multiplicering av hela tillståndet med $-1$.

Om du tillämpar dessa steg i ett grundtillstånd kan du inte se skillnaden – den globala fasen kan inte observeras. Men om du använder de här stegen till ett tillstånd i superposition, ser du att grundtillstånden som kodar giltiga färger erhåller den relativa fasen $-1$ – precis den effekt vi behöver att faståtgärden har!

Så här ser kickback-tricket ut i Q#. Vi använder den åtgärd som implementerar färgkontroll, vilket gör att effekterna blir enklare att se i resultaten, men du kan använda samma trick för alla åtgärder som implementerar ett markeringsorakel.

namespace ExploringGroversSearchAlgorithm {
    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 {
            // Iterate over pairs of qubits in matching positions in c0 and c1.
            for (q0, q1) in Zipped(c0, c1) {
                // Compute XOR of bits q0 and q1 in place (storing it in q1).
                CNOT(q0, q1);
            }
        } apply {
            // If all computed XORs are 0, the bit strings are equal - flip the state of the target.
            (ControlledOnInt(0, X))(c1, target);
        }
    }


    operation ApplyMarkingOracleAsPhaseOracle(
        markingOracle : ((Qubit[], Qubit[], Qubit) => Unit is Adj), 
        c0 : Qubit[],
        c1 : Qubit[]
    ) : Unit is Adj {
        use target = Qubit();
        within {
            // Put the target qubit into the |-⟩ state.
            X(target);
            H(target);
        } apply {
            // Apply the marking oracle; since the target is in the |-⟩ state,
            // flipping the target if the register state satisfies the condition 
            // will apply a -1 relative phase to the register state.
            markingOracle(c0, c1, target);
        }
    }


    @EntryPoint()
    operation ShowPhaseKickbackTrick() : Unit {
        use (c0, c1) = (Qubit[2], Qubit[2]);
        // Leave register c0 in the |00⟩ state.

        // Prepare a quantum state that is a superposition of all possible colors on register c1.
        ApplyToEach(H, c1);

        // Output the initial state of qubits c1. 
        // We do not include the state of qubits in the register c0 for brevity, 
        // since they will remain |00⟩ throughout the program.
        Message("The starting state of qubits c1:");
        DumpRegister((), c1);

        // Compare registers and mark the result in their phase.
        ApplyMarkingOracleAsPhaseOracle(MarkColorEquality, c0, c1);

        Message("");
        Message("The state of qubits c1 after the equality check:");
        DumpRegister((), c1);

        // Return the qubits to |0⟩ state before releasing them.
        ResetAll(c1);
    }
}
The starting state of qubits c1:
# wave function for qubits with ids (least to most significant): 2;3
∣0❭:     0.500000 +  0.000000 i  ==     *****                [ 0.250000 ]     --- [  0.00000 rad ]
∣1❭:     0.500000 +  0.000000 i  ==     *****                [ 0.250000 ]     --- [  0.00000 rad ]
∣2❭:     0.500000 +  0.000000 i  ==     *****                [ 0.250000 ]     --- [  0.00000 rad ]
∣3❭:     0.500000 +  0.000000 i  ==     *****                [ 0.250000 ]     --- [  0.00000 rad ]

The state of qubits c1 after the equality check:
# wave function for qubits with ids (least to most significant): 2;3
∣0❭:    -0.500000 +  0.000000 i  ==     *****                [ 0.250000 ] ---     [  3.14159 rad ]
∣1❭:     0.500000 +  0.000000 i  ==     *****                [ 0.250000 ]     --- [  0.00000 rad ]
∣2❭:     0.500000 +  0.000000 i  ==     *****                [ 0.250000 ]     --- [  0.00000 rad ]
∣3❭:     0.500000 +  0.000000 i  ==     *****                [ 0.250000 ]     --- [  0.00000 rad ]

Du kan se att amplituden för tillståndet $|00\rangle$ har ändrats till $-0,5$, så dess relativa fas jämfört med andra grundtillstånd är nu $-1$.

Grattis, Space Explorer! Nu vet du hur du skapar ett fullständigt kvantorakel för ett graffärgningsproblem!

I nästa enhet implementerar du slutligen Grovers sökalgoritm i praktiken för att fastställa det minsta antalet bandbredder som vi måste tilldela.