Freigeben über

Tutorial: Implementierung des Grover-Suchalgorithmus in Q#

  • Artikel

In diesem Lernprogramm implementieren Sie den Grover-Algorithmus Q# , um suchbasierte Probleme zu lösen. Eine ausführliche Erläuterung der Theorie hinter dem Grover-Algorithmus finden Sie unter Theorie des Grover-Algorithmus.

In diesem Tutorial:

  • Definieren des Grover-Algorithmus für ein Suchproblem
  • Implementieren des Grover-Algorithmus in Q#

Tipp

Wenn Sie Ihre Quantum Computing-Reise beschleunigen möchten, schauen Sie sich Code mit Azure Quantum an, einem einzigartigen Feature der Azure Quantum-Website. Hier können Sie integrierte Q# Beispiele oder Eigene Q# Programme ausführen, neuen Q# Code aus Ihren Eingabeaufforderungen generieren, Ihren Code in VS Code für das Web mit nur einem Klick öffnen und ausführen und Copilot fragen.

Voraussetzungen

Definieren des Problems

Der Grover-Algorithmus ist einer der bekanntesten Algorithmen im Quantencomputing. Die Art des Problems, das es löst, wird häufig als "Suchen einer Datenbank" bezeichnet, aber es ist genauer, es in Bezug auf das Suchproblem zu betrachten.

Jedes Suchproblem kann mit einer abstrakten Funktion $f(x)$ formuliert werden, die Suchelemente $x$ akzeptiert. Wenn das Element $x$ eine Lösung für das Suchproblem ist, $f(x)=1$. Wenn das element $x$ keine Lösung ist, ist $f(x)=0$. Das Suchproblem besteht darin, nach jedem Element $x_0$ zu suchen, für das $f(x_0)=1$ ist.

Daher können Sie das Suchproblem wie folgt formulieren: bei einer klassischen Funktion $f(x):\{0,1\}^n \rightarrow\{0,1\}$, wobei $n$ die Bitgröße des Suchbereichs ist, eine Eingabe $x_0$ finden, für die $f(x_0)=1$.

Um den Grover-Algorithmus zur Lösung eines Suchproblems zu implementieren, müssen Sie:

  1. das Problem in die Form einer Grover-Aufgabe transformieren. Nehmen wir zum Beispiel an, Sie möchten die Faktoren einer ganzen Zahl $M$ mit Hilfe des Grover-Algorithmus finden. Sie können das Ganzzahlfaktorisierungsproblem in eine Grover-Aufgabe transformieren, indem Sie eine Funktion $$f_M(x)=1[r],$$ erstellen, wobei $1[r]=1$ bei $r=0$ und $1[r]=0$ ist, wenn $r\neq0$ und $r$ der Rest von $M/x$ ist. Auf diese Weise sind die ganzen Zahlen $x_i$, die $f_M(x_i)=1$ machen, die Faktoren von $M$, und Sie haben das Problem in eine Grover-Aufgabe transformiert.
  2. Implementieren Sie die Funktion der Grover-Aufgabe als Quantenorakel. Um den Grover-Algorithmus zu implementieren, müssen Sie die Funktion $f(x)$ der Grover-Aufgabe als Quantenorakel implementieren.
  3. Verwenden Sie den Grover-Algorithmus mit Ihrem Oracle, um die Aufgabe zu lösen. Sobald Sie über ein Quantenorakel verfügen, können Sie es in die Implementierung des Grover-Algorithmus integrieren, um das Problem zu lösen und die Ausgabe zu interpretieren.

Der Grover-Algorithmus

Angenommen, es sind $N=2^n$ geeignete Elemente für das Suchproblem vorhanden, und sie werden indiziert, indem jedem Element eine ganze Zahl zwischen $0$ und $N-1$ zugewiesen wird. Allgemeine Schritte des Algorithmus:

  1. Er beginnt mit einem Register aus $n$-Qubits, die mit dem Zustand „$\ket{0}$“ initiiert werden.
  2. Bereiten Sie das Register in einer einheitlichen Superposition vor, indem Sie $H$ auf jedes Qubit im Register anwenden: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
  3. Wenden Sie die folgenden Vorgänge auf das Register $N_{\text{optimal}}$ mal an:
    1. Das Phasenorakel $O_f$, das eine bedingte Phasenverschiebung von $-1$ für die Lösungselemente anwendet.
    2. Wenden Sie $H$ auf jedes Qubit im Register an.
    3. Wenden Sie $-O_0$ an, eine bedingte Phasenverschiebung von $-1$ auf jeden Berechnungsbasiszustand mit Ausnahme von $\ket{0}$.
    4. Wenden Sie $H$ auf jedes Qubit im Register an.
  4. Messen Sie das Register, um den Index eines Elements abzurufen, das eine Lösung mit sehr hoher Wahrscheinlichkeit ist.
  5. Überprüfen Sie das Element, um zu überprüfen, ob es sich um eine gültige Lösung ist. Falls nicht, starten Sie erneut.

Schreiben sie den Code für den Grover-Algorithmus in Q#

In diesem Abschnitt wird erläutert, wie der Algorithmus in Q# implementiert wird. Bei der Implementierung des Grover-Algorithmus sind einige Dinge zu berücksichtigen. Sie müssen definieren, was Ihr markierter Zustand ist, wie sie darüber reflektieren und wie viele Iterationen der Algorithmus ausgeführt werden soll. Sie müssen auch das Oracle definieren, das die Funktion der Grover-Aufgabe implementiert.

Definieren des markierten Zustands

Zunächst definieren Sie, welche Eingaben Sie in der Suche finden möchten. Schreiben Sie dazu einen Vorgang, der die Schritte b, c und d aus dem Grover-Algorithmus anwendet.

Zusammen werden diese Schritte auch als der Grover'S Diffusionsoperator $-H^{\otimes n} O_0 H^{\otimes n}$ bezeichnet.

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

Der ReflectAboutMarked Vorgang spiegelt den Basiszustand wider, der durch abwechselnde Nullen und solche gekennzeichnet ist. Dies geschieht durch Anwendung des Grover-Diffusionsoperators auf die Eingangsqubits. Der Vorgang verwendet einen Hilfs-Qubit, der im Zustand $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ initialisiert wird, outputQubitindem die $X$- und $H$-Gates angewendet werden. Der Vorgang wendet dann das $X$-Gate auf jedes andere Qubit im Register an, das den Zustand des Qubits kippt. Schließlich wendet es das kontrollierte $X$ Gate auf das Hilfs-Qubit und die Eingabe-Qubits an. Dieser Vorgang kippt das Hilfs-Qubit, wenn und nur, wenn sich alle Eingabe-Qubits im Zustand "$\ket{1}$" befinden. Dies ist der markierte Zustand.

Definieren der Anzahl der optimalen Iterationen

Die Grover-Suche verfügt über eine optimale Anzahl von Iterationen, die die höchste Wahrscheinlichkeit ergeben, eine gültige Ausgabe zu messen. Wenn unser Problem $N=2^n$ mögliche Variablenzuweisungen aufweist und $M$ davon Lösungen des Problems sind, beträgt die optimale Anzahl von Iterationen:

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

Wenn Sie über die optimale Anzahl von Iterationen fortfahren, wird diese Wahrscheinlichkeit reduziert, bis Sie die Erfolgswahrscheinlichkeit für die Iteration $2 N_{\text{optimal}}$erreicht haben. Danach steigt die Wahrscheinlichkeit erneut an bis $3 N_{\text{optimal}}$ usw.

In praktischen Anwendungen wissen Sie in der Regel nicht, wie viele Lösungen Ihr Problem hat, bevor Sie es lösen. Eine effiziente Strategie zur Handhabung dieses Problems besteht darin, die Anzahl der Lösungen $M$ zu „erraten“, indem die Schätzung der Zweierraten schrittweise erhöht wird (d. h. $1, 2, 4, 8, 16, ..., 2^n$). Eine dieser Schätzung ist nah genug, so dass der Algorithmus die Lösung mit einer durchschnittlichen Anzahl von Iterationen um $\sqrt{\frac{N}{M}}$ findet.

Die folgende Q# Funktion berechnet die optimale Anzahl von Iterationen für eine bestimmte Anzahl von Qubits in einem Register.

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

Die CalculateOptimalIterations Funktion verwendet die obige Formel, um die Anzahl der Iterationen zu berechnen, und rundet sie dann auf die nächste ganze Zahl ab.

Definieren des Grover-Vorgangs

Der Q# Suchalgorithmus von Grover hat drei Eingaben:

  • Die Anzahl der Qubits, nQubits : Intim Qubit-Register. Dieses Register codiert die vorläufige Lösung für das Suchproblem. Nach dem Vorgang wird er gemessen.
  • Die Anzahl der optimalen Iterationen, iterations : Int.
  • Ein Vorgang, phaseOracle : Qubit[] => Unit) : Result[]der die Phase Oracle für die Aufgabe von Grover darstellt. Dieser Vorgang wendet eine unitäre Transformation auf ein generisches Qubit-Register an.
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);
}

Der GroverSearch Vorgang initialisiert ein Register von $n$qubits im Zustand $\ket{0}$, bereitet das Register auf eine einheitliche Überlagerung vor und wendet dann den Grover-Algorithmus für die angegebene Anzahl von Iterationen an. Die Suche selbst besteht aus wiederholter Reflexion über den markierten Zustand und den Startzustand, in Q# den Sie als Schleife schreiben können. Schließlich misst sie das Register und gibt das Ergebnis zurück.

Der Code verwendet drei Hilfsvorgänge: PrepareUniform, , ReflectAboutUniformund ReflectAboutAllOnes.

Bei einem Register im Zustand "Alle Nullen" bereitet der PrepareUniform Vorgang eine einheitliche Überlagerung über alle Basiszustände vor.

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

Der Vorgang "ReflectAboutAllOnes" spiegelt den Zustand aller Wider.

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

Der Vorgang ReflectAboutUniform spiegelt den einheitlichen Überlagerungszustand wider. Zunächst wandelt sie die einheitliche Überlagerung in alle Null um. Anschließend wird der Zustand "Alle Null" in alle transformiert. Schließlich spiegelt sie den Zustand aller Widersen wider. Der Vorgang ReflectAboutUniform wird aufgerufen, da er geometrisch als Reflektion im Vektorraum über den einheitlichen Superpositionszustand interpretiert werden kann.

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

Ausführen des endgültigen Codes

Nun sind alle Voraussetzungen erfüllt, um eine bestimmte Instanz des Grover-Suchalgorithmus zu implementieren und das Faktorisierungsproblem zu lösen. Zum Abschluss richtet der Main Vorgang das Problem ein, indem die Anzahl der Qubits und die Anzahl der Iterationen angegeben wird.

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

Ausführen des Programms

Wählen Sie die gewünschte Plattform aus, um Ihr Programm auszuführen.

Sie können Ihren Q# Code mit dem Copilot in Azure Quantum kostenlos testen – alles, was Sie benötigen, ist ein Microsoft-E-Mail-Konto (MSA). Weitere Informationen zum Copilot in Azure Quantum finden Sie unter Explore Azure Quantum.

  1. Öffnen Sie den Copilot in Azure Quantum in Ihrem Browser.

  2. Kopieren Sie den folgenden Code, und fügen Sie ihn in den Code-Editor ein.

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

Tipp

Über Copilot in Azure Quantum können Sie Ihr Programm in VS Code für das Web öffnen, indem Sie in der rechten Ecke des Code-Editors die Schaltfläche "VS Code-Logo" auswählen.

Ausführen des Programms mithilfe des Speichersimulators

  1. Wählen Sie den In-Memory-Simulator aus.
  2. Wählen Sie die Anzahl der auszuführenden Aufnahmen und dann "Ausführen" aus.
  3. Die Ergebnisse werden im Histogramm und in den Feldern "Ergebnisse " angezeigt.
  4. Wählen Sie "Erklären"-Code aus, um Copilot aufzufordern, den Code Ihnen zu erläutern.

Ausführen des Programms mit dem Quantinuum H-Series Emulator

Sie können Ihr Programm auch an den kostenlosen Quantinuum H-Series Emulator übermitteln. Der Emulator simuliert einen Quantencomputer mit 20 Qubits.

  1. Wählen Sie die Dropdownliste In-Memory Simulator und dann Quantinuum H-Series-Emulator aus.
  2. Wählen Sie die Anzahl der Aufnahmen (derzeit auf 20 beschränkt) und dann Ausführen aus.

Zugehöriger Inhalt

Sehen Sie sich weitere Q#-Tutorials an:

  • Quantenanglement zeigt, wie ein Q# Programm geschrieben wird, das Qubits bearbeitet und misst und die Auswirkungen von Superposition und Veranglement veranschaulicht.
  • Der Quantum random number generator zeigt, wie ein Q# Programm geschrieben wird, das Zufallszahlen aus Qubits in Superposition generiert.
  • Quantum Fourier Transform untersucht, wie ein Q# Programm geschrieben wird, das direkt bestimmte Qubits adressiert.
  • Die Quantum Katas sind selbstgesteuerte Lernprogramme und Programmierübungen, die darauf abzielen, die Elemente von Quantencomputing und Q# Programmierung gleichzeitig zu unterrichten.