Samouczek: implementowanie algorytmu wyszukiwania Grovera w programie Q#

  • Artykuł

Uwaga

Zestaw Microsoft Quantum Development Kit (klasyczny zestaw QDK) nie będzie już obsługiwany po 30 czerwca 2024 r. Jeśli jesteś istniejącym deweloperem zestawu QDK, zalecamy przejście do nowej platformy Azure Quantum Development Kit (nowoczesnego zestawu QDK), aby kontynuować opracowywanie rozwiązań kwantowych. Aby uzyskać więcej informacji, zobacz Migrowanie Q# kodu do nowoczesnego zestawu QDK.

W tym samouczku zaimplementujesz algorytm Grovera w Q# celu rozwiązania problemów opartych na wyszukiwaniu. Szczegółowe wyjaśnienie teorii algorytmu Grovera można znaleźć w temacie Teoria algorytmu Grovera.

W tym samouczku wykonasz następujące elementy:

  • Zdefiniuj algorytm Grovera pod kątem problemu z wyszukiwaniem.
  • Zaimplementuj algorytm Grovera w pliku Q#.

Porada

Jeśli chcesz przyspieszyć podróż po obliczeniach kwantowych, zapoznaj się z kodem w usłudze Azure Quantum, unikatową funkcją witryny internetowej usługi Azure Quantum. W tym miejscu możesz uruchamiać wbudowane Q# przykłady lub własne Q# programy, generować nowy Q# kod z monitów, otwierać i uruchamiać kod w programie VS Code dla sieci Web za pomocą jednego kliknięcia i zadać Copilot wszelkie pytania dotyczące obliczeń kwantowych.

Wymagania wstępne

Definiowanie problemu

Algorytm Grovera jest jednym z najbardziej znanych algorytmów przetwarzania kwantowego. Typ problemu, który rozwiązuje, jest często określany jako "wyszukiwanie bazy danych", ale bardziej dokładne jest myślenie o nim pod względem problemu z wyszukiwaniem.

Każdy problem z wyszukiwaniem można matematycznie sformułować za pomocą funkcji abstrakcyjnej $f(x)$, która akceptuje elementy wyszukiwania $x$. Jeśli element $x$ jest rozwiązaniem problemu z wyszukiwaniem, $f(x)=1$. Jeśli element $x$ nie jest rozwiązaniem, $f(x)=0$. Problem z wyszukiwaniem polega na znalezieniu dowolnego elementu $x_0$, tak aby $f(x_0)=1$.

W związku z tym można sformułować dowolny problem z wyszukiwaniem jako: biorąc pod uwagę klasyczną funkcję $f(x):\{0,1\}^n \rightarrow\{0,1\}$, gdzie $n$ jest rozmiarem bitowym przestrzeni wyszukiwania, znajdź dane wejściowe $x_0$, dla których $f(x_0)=1$.

Aby zaimplementować algorytm Grovera w celu rozwiązania problemu z wyszukiwaniem, należy wykonać następujące kroki:

  1. Przekształć problem w postać zadania Grovera. Załóżmy na przykład, że chcesz znaleźć czynniki liczby całkowitej $M$ przy użyciu algorytmu Grovera. Problem z faktoryzacji liczby całkowitej można przekształcić w zadanie Grovera, tworząc funkcję $$f_M(x)=1[r],$$ gdzie $1[r]=1$ jeśli $r=0$ i $1[r]=0$ jeśli $r\neq0$ i $r$ jest resztą $M/x$. W ten sposób liczby całkowite $x_i$, które sprawiają, że $f_M(x_i)=1$ są czynnikami $M$ i przekształciliśmy problem w zadaniu Grovera.
  2. Zaimplementuj funkcję zadania Grovera jako wyrocznię kwantową. Aby zaimplementować algorytm Grovera, musisz zaimplementować funkcję $f(x)$ zadania Grovera jako wyroczni kwantowej.
  3. Użyj algorytmu Grovera z wyrocznią, aby rozwiązać to zadanie. Po utworzeniu wyroczni kwantowej możesz podłączyć ją do implementacji algorytmu Grovera, aby rozwiązać ten problem i interpretować dane wyjściowe.

Algorytm Grovera

Załóżmy, że istnieją $N=2^n$ kwalifikujących się elementów do problemu wyszukiwania i są indeksowane przez przypisanie każdej jednostki całkowitej z $0$ do $N-1$. Kroki algorytmu to:

  1. Rozpocznij od rejestracji kubitów $n$ zainicjowanych w stanie $\ket{0}$.
  2. Przygotuj rejestr do jednolitego superpozycji, stosując $H$ do każdego kubitu w rejestrze: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
  3. Zastosuj następujące operacje do rejestru $N_{\text{optimal}}$ razy:
    1. Wyrocznia fazowa $O_f$, która stosuje zmianę fazy warunkowej $-1$ dla elementów rozwiązania.
    2. Zastosuj $H$ do każdego kubitu w rejestrze.
    3. Zastosuj $-O_0$, zmianę fazy warunkowej $-1$ na każdy stan podstawy obliczeniowej z wyjątkiem $\ket{0}$.
    4. Zastosuj $H$ do każdego kubitu w rejestrze.
  4. Zmierz rejestr, aby uzyskać indeks elementu, który jest rozwiązaniem z bardzo dużym prawdopodobieństwem.
  5. Sprawdź element, aby sprawdzić, czy jest to prawidłowe rozwiązanie. Jeśli nie, uruchom ponownie.

Pisanie kodu dla algorytmu Grovera w Q#

W tej sekcji omówiono sposób implementowania algorytmu w programie Q#. Podczas implementowania algorytmu Grovera należy wziąć pod uwagę kilka kwestii. Musisz zdefiniować stan oznaczony, sposób jego odzwierciedlenia oraz liczbę iteracji, dla których należy uruchomić algorytm. Należy również zdefiniować wyrocznię, która implementuje funkcję zadania Grovera.

Definiowanie oznaczonego stanu

Najpierw zdefiniuj dane wejściowe, które próbujesz znaleźć w wyszukiwaniu. W tym celu napisz operację, która stosuje kroki b, c i d z algorytmu Grovera.

Razem te kroki są również znane jako operator dyfuzji Grovera $-H^{\otimes n} O_0 H^{\otimes n}$.

operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
    Message("Reflecting about marked state...");
    use outputQubit = Qubit();
    within {
        // We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that
        // toggling it results in a (-1) phase.
        X(outputQubit);
        H(outputQubit);
        // Flip the outputQubit for marked states.
        // Here, we get the state with alternating 0s and 1s by using the X
        // operation on every other qubit.
        for q in inputQubits[...2...] {
            X(q);
        }
    } apply {
        Controlled X(inputQubits, outputQubit);
    }
}

Operacja ReflectAboutMarked odzwierciedla stan podstawy oznaczony przez przemienne zera i te. Robi to poprzez zastosowanie operatora dyfuzji Grovera do kubitów wejściowych. Operacja używa pomocniczego kubitu , outputQubitktóry jest inicjowany w stanie $\ket=\frac{1}{\sqrt{2}}(\ket{-}{0}-\ket{1})$, stosując bramy $X$ i $H$. Następnie operacja stosuje bramę $X$ do każdego innego kubitu w rejestrze, który przerzuca stan kubitu. Na koniec stosuje kontrolowaną bramę $X$ do kubitu pomocniczego i kubitów wejściowych. Ta operacja przerzuca pomocniczy kubit, jeśli i tylko wtedy, gdy wszystkie kubity wejściowe znajdują się w stanie $\ket{1}$, co jest stanem oznaczonym.

Definiowanie liczby optymalnych iteracji

Wyszukiwanie Grovera ma optymalną liczbę iteracji, która daje najwyższe prawdopodobieństwo pomiaru prawidłowych danych wyjściowych. Jeśli problem ma $N=2^n$ możliwe elementy kwalifikujące się, a $M$ to rozwiązania problemu, optymalną liczbą iteracji jest:

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

Kontynuując iterację po optymalnej liczbie iteracji, zaczyna zmniejszać to prawdopodobieństwo, dopóki nie osiągniesz prawie zerowego prawdopodobieństwa powodzenia w iteracji $2 N_{\text{optimal}}$. Następnie prawdopodobieństwo rośnie ponownie do $3 N_{\text{optimal}}$, itd.

W przypadku zastosowań praktycznych zazwyczaj nie wiadomo, ile rozwiązań ma problem, zanim zostanie faktycznie rozwiązany. Efektywną strategią obsługi tego problemu jest "odgadnięcie" liczby rozwiązań $M$ przez postępowe zwiększenie odgadnięcia uprawnień dwóch (tj. $1, 2, 4, 8, 16, ..., 2^n$). Jedna z tych zgadni będzie wystarczająco blisko, że algorytm nadal znajdzie rozwiązanie ze średnią liczbą iteracji wokół $\sqrt{\frac{N}{M}}$.

Poniższa Q# funkcja oblicza optymalną liczbę iteracji dla danej liczby kubitów w rejestrze.

function CalculateOptimalIterations(nQubits : Int) : Int {
    if nQubits > 63 {
        fail "This sample supports at most 63 qubits.";
    }
    let nItems = 1 <<< nQubits; // 2^nQubits
    let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
    let iterations = Round(0.25 * PI() / angle - 0.5);
    return iterations;
}

Funkcja CalculateOptimalIterations używa powyższej formuły do obliczenia liczby iteracji, a następnie zaokrągla ją do najbliższej liczby całkowitej.

Definiowanie operacji Grovera

Operacja Q# algorytmu wyszukiwania Grovera ma trzy dane wejściowe:

  • Liczba kubitów, nQubits : Int, w rejestrze kubitów. Ten rejestr zakoduje wstępne rozwiązanie problemu z wyszukiwaniem. Po wykonaniu operacji zostanie zmierzona.
  • Liczba optymalnych iteracji, iterations : Int.
  • Operacja , phaseOracle : Qubit[] => Unit) : Result[]która reprezentuje wyrocznię fazową zadania Grovera. Ta operacja stosuje przekształcenie jednostkowe w ogólnym rejestrze kubitów.
operation GroverSearch( nQubits : Int, iterations : Int, phaseOracle : Qubit[] => Unit) : Result[] {

    use qubits = Qubit[nQubits];
    PrepareUniform(qubits);

    for _ in 1..iterations {
        phaseOracle(qubits);
        ReflectAboutUniform(qubits);
    }

    // Measure and return the answer.
    return MResetEachZ(qubits);
}

Operacja GroverSearch inicjuje rejestr kubitów $n$ w stanie $\ket{0}$, przygotowuje rejestr do jednolitego superpozycji, a następnie stosuje algorytm Grovera dla określonej liczby iteracji. Samo wyszukiwanie składa się z wielokrotnego odzwierciedlania stanu oznaczonego i stanu początkowego, w którym można zapisać jako Q# pętlę for. Na koniec mierzy rejestr i zwraca wynik.

Kod korzysta z trzech operacji pomocników: PrepareUniform, ReflectAboutUniformi ReflectAboutAllOnes.

Biorąc pod uwagę rejestr w stanie all-zeros, PrepareUniform operacja przygotowuje jednolitą superpozycję we wszystkich stanach bazowych.

operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
    for q in inputQubits {
        H(q);
    }
}

Operacja "ReflectAboutAllOnes" odzwierciedla stan wszystkich.

operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
    Controlled Z(Most(inputQubits), Tail(inputQubits));
}

Operacja ReflectAboutUniform odzwierciedla jednolity stan superpozycji. Najpierw przekształca jednolitą superpozycję na all-zero. Następnie przekształca stan all-zero na wszystkie. Na koniec odzwierciedla stan wszystkich. Operacja jest wywoływana ReflectAboutUniform , ponieważ można ją geometrycznie interpretować jako odbicie w przestrzeni wektorowej o stanie jednolitej superpozycji.

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
    within {
        Adjoint PrepareUniform(inputQubits);
        // Transform the all-zero state to all-ones
        for q in inputQubits {
            X(q);
        }
    } apply {
        ReflectAboutAllOnes(inputQubits);
    }
}

Uruchamianie końcowego kodu

Teraz masz wszystkie składniki, aby zaimplementować określone wystąpienie algorytmu wyszukiwania Grovera i rozwiązać problem z faktoringiem. Aby zakończyć, Main operacja konfiguruje problem, określając liczbę kubitów i liczbę iteracji

operation Main() : Result[] {
let nQubits = 5;
let iterations = CalculateOptimalIterations(nQubits);
Message($"Number of iterations: {iterations}");

// Use Grover's algorithm to find a particular marked state.
let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
return results;
}

Uruchamianie programu

Kod możesz przetestować Q# za pomocą rozwiązania Copilot w usłudze Azure Quantum bezpłatnie — wystarczy konto e-mail microsoft (MSA). Aby uzyskać więcej informacji na temat rozwiązania Copilot w usłudze Azure Quantum, zobacz Eksplorowanie usługi Azure Quantum.

  1. Otwórz aplikację Copilot w usłudze Azure Quantum w przeglądarce.

  2. Skopiuj i wklej następujący kod do edytora kodu.

    namespace GroversTutorial {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    @EntryPoint()
    operation Main() : Result[] {
    let nQubits = 5;
    let iterations = CalculateOptimalIterations(nQubits);
    Message($"Number of iterations: {iterations}");

    // Use Grover's algorithm to find a particular marked state.
    let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
    return results;
    }

    operation GroverSearch(
        nQubits : Int,
        iterations : Int,
        phaseOracle : Qubit[] => Unit) : Result[] {

        use qubits = Qubit[nQubits];

        PrepareUniform(qubits);

        for _ in 1..iterations {
            phaseOracle(qubits);
            ReflectAboutUniform(qubits);
        }

        // Measure and return the answer.
        return MResetEachZ(qubits);
    }

    function CalculateOptimalIterations(nQubits : Int) : Int {
        if nQubits > 63 {
            fail "This sample supports at most 63 qubits.";
        }
        let nItems = 1 <<< nQubits; // 2^nQubits
        let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
        let iterations = Round(0.25 * PI() / angle - 0.5);
        return iterations;
    }

    operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
        Message("Reflecting about marked state...");
        use outputQubit = Qubit();
        within {
            // We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that
            // toggling it results in a (-1) phase.
            X(outputQubit);
            H(outputQubit);
            // Flip the outputQubit for marked states.
            // Here, we get the state with alternating 0s and 1s by using the X
            // operation on every other qubit.
            for q in inputQubits[...2...] {
                X(q);
            }
        } apply {
            Controlled X(inputQubits, outputQubit);
        }
    }

    operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
        for q in inputQubits {
            H(q);
        }
    }

    operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
        Controlled Z(Most(inputQubits), Tail(inputQubits));
    }

    operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
        within {
            // Transform the uniform superposition to all-zero.
            Adjoint PrepareUniform(inputQubits);
            // Transform the all-zero state to all-ones
            for q in inputQubits {
                X(q);
            }
        } apply {
            // Now that we've transformed the uniform superposition to the
            // all-ones state, reflect about the all-ones state, then let the
            // within/apply block transform us back.
            ReflectAboutAllOnes(inputQubits);
        }
    }
}

Porada

W aplikacji Copilot w usłudze Azure Quantum możesz otworzyć program w programie VS Code dla sieci Web , klikając przycisk logo programu VS Code w prawym rogu edytora kodu.

Uruchamianie programu przy użyciu symulatora w pamięci

  1. Wybierz pozycję Symulator w pamięci.
  2. Wybierz liczbę zdjęć do uruchomienia, a następnie kliknij przycisk Uruchom.
  3. Wyniki są wyświetlane na histogramie i w polach Wyniki .
  4. Kliknij przycisk Wyjaśnij kod , aby wyświetlić monit Copilot o wyjaśnienie kodu.

Uruchamianie programu przy użyciu emulatora serii H firmy Quantinuum

Możesz również przesłać swój program do bezpłatnego emulatora firmy Quantinuum H-Series. Emulator symuluje komputer kwantowy z 20 kubitami.

  1. Wybierz listę rozwijaną Symulator w pamięci i wybierz pozycję Quantinuum H-Series Emulator.
  2. Wybierz liczbę zdjęć (obecnie ograniczonych do 20) i wybierz pozycję Uruchom.

Następne kroki

Zapoznaj się z innymi Q# samouczkami:

  • Splątanie kwantowe pokazuje, jak napisać Q# program, który manipuluje kubitami i mierzy je oraz demonstruje efekty superpozycji i splątania.
  • Kwantowy generator liczb losowych pokazuje, jak napisać Q# program, który generuje losowe liczby z kubitów w superpozycji.
  • Quantum Fourier Transform bada sposób pisania Q# programu, który bezpośrednio dotyczy określonych kubitów.
  • Quantum Kata to samouczki realizowane samodzielnie i ćwiczenia programistyczne mające na celu nauczanie elementów obliczeń kwantowych i Q# programowania w tym samym czasie.