Ćwiczenie — implementowanie algorytmu Grovera w celu rozwiązania problemu z kolorowaniem grafu

Ukończone

W tym module na koniec zaimplementujesz algorytm wyszukiwania Grovera — od definicji wyroczni problemu z kolorowaniem grafu do logiki radzenia sobie z losowym charakterem algorytmu.

Uwaga

Z konieczności cały kod w tym przykładzie jest dość długi, ponieważ zawiera nie tylko ogólną implementację algorytmu Grovera, ale również implementację wyroczni specyficzną dla problemu.

Ta lekcja koncentruje się na najważniejszych elementach kodu — pełna analiza kodu jest poza zakresem tego modułu. Sekcja podsumowania tego modułu zawiera jednak linki do materiałów, dzięki którym uzyskasz bardziej szczegółowe informacji na temat koncepcji omówionych w tym module.

Ogólna implementacja wyszukiwania kwantowego

Oto kod języka Q#, który implementuje rdzeń algorytmu Grovera.

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

Poświęćmy chwilę na wskazanie ważnej właściwości tego kodu: jest to kod ogólny — może służyć do rozwiązywania dowolnych problemów z wyszukiwaniem.

Przekazujemy wyrocznię kwantową — jedyną operację, która opiera się na znajomości wystąpienia problemu, które chcemy rozwiązać — jako parametr do kodu wyszukiwania.

Uwaga

Język Q# umożliwia manipulowanie operacjami i funkcjami jako wartościami przez definiowanie zmiennych jako elementów możliwych do wywołania i przekazywania ich jako argumentów do innych operacji. Możliwe do wywołania argumenty można następnie wywołać w kodzie podobnie jak inne operacje, jak widać w kroku 1 w treści pętli.

Ta funkcja pozwala nam napisać zwięzły kod algorytmu na wysokim poziomie i używać go ponownie dla wielu aplikacji.

Kod pobiera również liczbę iteracji do wykonania jako parametr. Dzięki temu możemy zachować logikę wyboru liczby iteracji (na podstawie naszej wiedzy o problemie lub losowo) poza implementacją algorytmu ogólnego.

Na koniec logika specyficzna dla problemu obejmująca mierzenie wyniku i interpretowanie go jest również utrzymywana poza implementacją. Zamiast tego operacja przyjmuje tablicę kubitów jako jedne z danych wejściowych, a kod, który je wywołuje, może później zmierzyć stan tych kubitów.

Uwaga

W tym momencie kod nie definiuje elementu @EntryPoint, ponieważ działanie samego kodu nie spowodowałoby osiągnięcia żadnych interesujących wyników. W następnej sekcji zobaczymy, jak przygotować wszystkie niezbędne parametry i przekazać je do kodu.

Rozwiążmy problem z kolorowaniem grafu.

Teraz możesz przygotować wszystko, czego nauczyliśmy się do tej pory i obliczyć minimalną liczbę różnych przepustowości, które musimy przypisać do stacji kosmicznych.

Liczba przepustowości będzie się różnić w zależności od liczby stacji i ich odległości od siebie. Pamiętaj, że ten problem jest wystąpieniem problemu z kolorowaniem grafu. Tutaj kolor oznacza określoną przepustowość. Zdecydowanie zalecamy rozpoczęcie rozwiązywania mniejszej wersji problemu i rozważenie tylko pięciu stacji kosmicznych połączonych, ponieważ znajdują się one na grafie w lekcji 2.

Oto pełny kod.

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

Uwaga

Ten fragment kodu nie jest obecnie uruchamiany w żadnych dostępnych elementach docelowych sprzętu usługi Azure Quantum, ponieważ można wywołać ResultArrayAsBoolArrayelement , a także ponowne przypisywanie zmiennych wewnątrz bloków zależnych ifod pomiarów, wymaga funkcji QPU z pełnym profilem obliczeń.

Poznaj kod modułu, który nie zawiera takiego powiadomienia, jest wykonywalny dla bieżących elementów docelowych sprzętu.

Prawdopodobnie rozpoznasz trzy pierwsze operacje jako implementację wyroczni z lekcji 4 oraz czwartą operację jako ogólny algorytm wyszukiwania, który został zaimplementowany wcześniej w trakcie tej lekcji.

Zostanie nam tylko ostatnia operacja, która definiuje rozwiązywany przez nas problem, tworzy wszystkie niezbędne parametry, wywołuje ogólną implementację wyszukiwania i interpretuje wyniki.

  • Zwróć uwagę na definicję zmiennych markingOracle i phaseOracle — dwóch wariantów implementacji naszego problemu jako operacji kwantowej. Obie zmienne używają aplikacji częściowej, czyli naprawiają kilka parametrów operacji w celu utworzenia innej operacji z mniejszą liczbą parametrów. MarkValidVertexColoring W związku z tym operacja przyjmuje trzy parametry (listę krawędzi grafu, rejestr wejściowy i kubit docelowy), podczas gdy markingOracle operacja przyjmuje tylko dwa parametry (rejestr wejściowy i kubit docelowy) z listą krawędzi grafu ustalonych dla zmiennejedges.

  • Jak widzieliśmy w poprzedniej lekcji, optymalna liczba iteracji zależy od rozmiaru obszaru wyszukiwania i liczby rozwiązań.

    Pierwszy z tych elementów jest łatwy do zdefiniowania — dowolny ciąg bitowy składający się z 2 * nVertices bitów można zinterpretować jako potencjalne kolorowanie nVertices wierzchołków, więc istnieje $2^{2\textrm{nVertices}} = 1024$ kandydatów.

    Liczba rozwiązań jest trudniejsza do oszacowania, ale w naszym przykładzie struktura grafu jest łatwa do przeanalizowania. Wierzchołki 0–3 składają się na pełny graf, dlatego muszą mieć przypisane różne kolory w dowolnej kolejności — ponieważ dostępne są łącznie cztery kolory, istnieje następująca liczba sposobów wykonania tej czynności: $4!$. Wierzchołek 4 jest połączony tylko z wierzchołkiem 3, więc może przyjąć dowolny kolor z wyjątkiem koloru wierzchołka 3, co daje nam trzy opcje dla każdego kolorowania innych wierzchołków. Łączna liczba rozwiązań wynosi $4! \cdot 3 = 72$.

    Biorąc to pod uwagę, uruchomimy następującą liczbę iteracji: $\frac{\pi}{4} \sqrt{\frac{N}{M}} = 2.96 \approx 3$.

  • Pętla repeat ... until obsługuje możliwość uzyskania nieprawidłowej odpowiedzi podczas pierwszego uruchomienia algorytmu. Treść pętli uruchamia algorytm raz, mierzy rejestr kubitów, aby uzyskać wynik, a następnie sprawdza, czy jest to rozwiązanie problemu. Jeśli tak, zmienna correct jest aktualizowana w celu odzwierciedlenia tego faktu, a wyniki pomiaru są konwertowane na tablicę bitową. W przeciwnym razie algorytm jest uruchamiany ponownie.

Jeśli uruchomisz algorytm, zobaczysz dane wyjściowe podobne do następujących:

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

W przypadku pięciu stacji kosmicznych o tych cechach musimy przypisać cztery różne przepustowości na podstawie tych wyników.

Obserwowanie amplitud

Przyjrzyjmy się teraz zachowaniu amplitud stanów bazowych w kluczowych punktach podczas wykonywania algorytmu.

Gratulacje! Zaimplementowano pierwszy algorytm wyszukiwania kwantowego i użyto go w celu rozwiązania niewielkiego problemu.

W następnej lekcji rozważysz inne przykłady i przyjrzysz się rodzajom rzeczywistych problemów lub nie są dobrym rozwiązaniem do ich rozwiązania przy użyciu algorytmu Grovera.