Ćwiczenie — implementowanie algorytmu Grovera w celu rozwiązania problemu z kolorowaniem grafu
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
markingOracleiphaseOracle— 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.MarkValidVertexColoringW związku z tym operacja przyjmuje trzy parametry (listę krawędzi grafu, rejestr wejściowy i kubit docelowy), podczas gdymarkingOracleoperacja 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 * nVerticesbitów można zinterpretować jako potencjalne kolorowanienVerticeswierzchoł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 ... untilobsł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, zmiennacorrectjest 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.
Potrzebujesz pomocy? Zobacz nasz przewodnik po rozwiązywaniu problemów lub prześlij szczegółową opinię, zgłaszając problem.