Udostępnij za pośrednictwem

Samouczek: implementowanie algorytmu wyszukiwania Grovera w programie Q#

  • Artykuł

W tym samouczku zaimplementujesz algorytm Grovera w Q# celu rozwiązywania problemów opartych na wyszukiwaniu. Aby uzyskać szczegółowe wyjaśnienie teorii dotyczącej algorytmu Grovera, zobacz Teorię algorytmu Grovera.

W tym samouczku zostały wykonane następujące czynności:

  • Definiowanie algorytmu Grovera pod kątem problemu z wyszukiwaniem
  • Implementowanie algorytmu Grovera w programie Q#

Napiwek

Jeśli chcesz przyspieszyć podróż obliczeń kwantowych, zapoznaj się z kodem w usłudze Azure Quantum, unikatową funkcją witryny internetowej 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 jednym kliknięciem i zadawać Copilot wszelkie pytania dotyczące obliczeń kwantowych.

Wymagania wstępne

Definiowanie problemu

Algorytm Grovera jest jednym z najbardziej znanych algorytmów w obliczeniach kwantowych. Typ rozwiązywanego problemu 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, musisz:

  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. Możesz przekształcić problem z faktoryzacją całkowitą do zadania 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 zadanie Grovera.
  2. Zaimplementuj funkcję zadania Grovera jako wyrocznię kwantową. Aby zaimplementować algorytm Grovera, należy zaimplementować funkcję $f(x)$ zadania Grovera jako wyroczni kwantowej.
  3. Użyj algorytmu Grovera z wyrocznią, aby rozwiązać to zadanie. Gdy masz wyrocznię kwantową, możesz podłączyć ją do implementacji algorytmu Grovera, aby rozwiązać problem i zinterpretować dane wyjściowe.

Algorytm Grovera

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

  1. Zacznij od rejestru kubitów $n$ zainicjowanych w stanie $\ket{0}$.
  2. Przygotuj rejestr do jednolitej 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 $N_{\text{optimal}}$ razy:
    1. Wyrocznia fazowa $O_f$, która stosuje przesunięcie fazy warunkowej $-1$ dla elementów rozwiązania.
    2. Zastosuj $H$ do każdego kubitu w rejestrze.
    3. Zastosuj $-O_0$, warunkową zmianę fazy $-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 wysokim 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 programie 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 do uruchomienia algorytmu. Należy również zdefiniować wyrocznię, która implementuje funkcję zadania Grovera.

Definiowanie oznaczonego stanu

Najpierw należy zdefiniować 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.

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 naprzemienne 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{-}{\sqrt{1}}(\ket{2}-\ket{0}{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 kubit pomocniczy, jeśli i tylko wtedy, gdy wszystkie kubity wejściowe znajdują się w stanie $\ket{1}$, który 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 kwalifikujące się elementy, a $M$ to rozwiązania problemu, optymalna liczba iteracji wynosi:

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

Kontynuowanie iteracji po optymalnej liczbie iteracji zaczyna zmniejszać to prawdopodobieństwo, dopóki nie osiągniesz prawie zerowego prawdopodobieństwa sukcesu 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 stopniowe zwiększenie zgadywania uprawnień dwóch (tj. 1 USD, 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

Q# Operacja 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 ona 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 ramach ogólnego rejestru 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 jednolitej superpozycji, a następnie stosuje algorytm Grovera dla określonej liczby iteracji. Samo wyszukiwanie składa się z wielokrotnego odzwierciedlania oznaczonego stanu 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 pomocnika: 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. Po pierwsze przekształca jednolitą superpozycję na all-zero. Następnie przekształca stan all-zero na all-ones. Na koniec odzwierciedla stan wszystkich. Operacja jest wywoływana ReflectAboutUniform , ponieważ może być geometrycznie interpretowana 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 faktoringu. 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

Wybierz odpowiednią platformę do uruchomienia 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.

    import Microsoft.Quantum.Convert.*;
import Microsoft.Quantum.Math.*;
import Microsoft.Quantum.Arrays.*;
import Microsoft.Quantum.Measurement.*;
import Microsoft.Quantum.Diagnostics.*;

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

Napiwek

W aplikacji Copilot w usłudze Azure Quantum możesz otworzyć program w programie VS Code dla sieci Web , wybierają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 wybierz pozycję Uruchom.
  3. Wyniki są wyświetlane w histogramie i w polach Wyniki .
  4. Wybierz pozycję Wyjaśnij kod , aby wyświetlić monit Copilot o wyjaśnienie kodu.

Uruchamianie programu przy użyciu emulatora Quantinuum

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

  1. Rozwiń listę rozwijaną In-Memory symulatora i wybierz pozycję emulatora Quantinuum.
  2. Wybierz liczbę zdjęć (obecnie ograniczonych do 20) i wybierz pozycję Uruchom.

Powiązana zawartość

Zapoznaj się z innymi Q# samouczkami:

  • Splątanie kwantowe pokazuje, jak napisać Q# program, który manipuluje kubitami i mierzy je oraz demonstruje skutki 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 Katas to samouczki samodzielne i ćwiczenia programistyczne mające na celu nauczanie elementów obliczeń kwantowych i Q# programowania w tym samym czasie.