Tutorial: Implementierung des Grover-Suchalgorithmus in Q#

Artikel
04/26/2024

Hinweis

Microsoft Quantum Development Kit (classic QDK) wird nach dem 30. Juni 2024 nicht mehr unterstützt. Wenn Sie bereits QDK-Entwickler sind, empfehlen wir Ihnen, zum neuen Azure Quantum Development Kit (Modern QDK) umzusteigen, um die Entwicklung von Quantenlösungen fortzusetzen. Weitere Informationen finden Sie unter Migrieren ihres Q# Codes zum modernen QDK.

In diesem Tutorial implementieren Sie den Grover-Algorithmus in 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 gehen Sie wie folgt vor:

Definieren Sie den Grover-Algorithmus für ein Suchproblem.
Implementieren Sie den Grover-Algorithmus in Q#.

Tipp

Wenn Sie Ihre Quantencomputing-Reise beschleunigen möchten, lesen Sie Code with Azure Quantum, ein einzigartiges Feature der Azure Quantum-Website. Hier können Sie integrierte Q# Beispiele oder Ihre eigenen Q# Programme ausführen, neuen Q# Code aus Ihren Eingabeaufforderungen generieren, Ihren Code in VS Code für das Web mit einem Klick öffnen und ausführen und Copilot Fragen zum Quantencomputing stellen.

Voraussetzungen

So führen Sie das Codebeispiel in Copilot in Azure Quantum aus:
- Ein Microsoft-E-Mail-Konto (MSA).
So entwickeln und führen Sie das Codebeispiel in Visual Studio Code aus:
- Die neueste Version von Visual Studio Code oder öffnen Sie VS Code im Web.
- Die neueste Version der Azure-Erweiterung Quantum Development Kit . Installationsdetails finden Sie unter Installieren des modernen QDK in VS Code.

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 als 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 so formulieren: Bei einer klassischen Funktion $f(x):\{0,1\}^n \rightarrow\{0,1\}$, wobei $n$ die Bitgröße des Suchraums ist, suchen Sie eine Eingabe $x_0$, für die $f(x_0)=1$.

Um den Grover-Algorithmus zum Lösen eines Suchproblems zu implementieren, müssen Sie Folgendes ausführen:

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.
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.
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:

Er beginnt mit einem Register aus $n$-Qubits, die mit dem Zustand „$\ket{0}$“ initiiert werden.
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$$
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.
Messen Sie das Register, um den Index eines Elements abzurufen, das eine Lösung mit sehr hoher Wahrscheinlichkeit ist.
Ü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 nur wenige Punkte zu berücksichtigen. Sie müssen definieren, was Ihr markierter Zustand ist, wie darüber reflektiert werden soll und für wie viele Iterationen der Algorithmus ausgeführt werden soll. Sie müssen auch das Orakel definieren, das die Funktion der Grover-Aufgabe implementiert.

Definieren des markierten Zustands

Zunächst definieren Sie, welche Eingabe 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 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 Einsen gekennzeichnet ist. Dazu wird der Diffusionsoperator des Grovers auf die Eingabequbits angewendet. Der Vorgang verwendet ein zusätzliches Qubit, outputQubit, das im Zustand $\ket{-}=\frac{1}{\sqrt{2}}(\ket-\ket{0}{1})$ initialisiert wird, indem die $X$ und $H$-Gates angewendet werden. Der Vorgang wendet dann das $X$-Gate auf jedes andere Qubit im Register an, wodurch der Zustand des Qubits umgedreht wird. Schließlich wendet es das kontrollierte $X$-Gate auf das Hilfsqubit und die Eingabequbits an. Bei diesem Vorgang wird das Hilfsqubit nur dann umgedreht, wenn sich alle Eingabequbits im Zustand $\ket{1}$befinden, was dem markierten Zustand entspricht.

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 fortfahren, die optimale Anzahl von Iterationen zu durchlaufen, beginnt diese Wahrscheinlichkeit zu verringern, bis Sie die Erfolgswahrscheinlichkeit von nahezu null bei iteration $2 N_{\text{optimal}}$ erreichen. 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.

Definieren des Grover-Vorgangs

Der Q# Vorgang für den Grover-Suchalgorithmus verfügt über drei Eingaben:

Die Anzahl der Qubits ( nQubits : Int) im Qubitregister. 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 das Phasenorakel für die Grover-Aufgabe 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 wiederholten Reflexionen über den markierten Zustand und den Startzustand, den Sie als for-Schleife ausschreiben Q# können. Schließlich misst es 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 "All-Ones" wider.

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

Der Vorgang ReflectAboutUniform spiegelt den einheitlichen Überlagerungszustand wider. Zunächst transformiert sie die einheitliche Überlagerung in "All-Zero". Anschließend transformiert er den Zustand "Alle Null" in "Alle 0". Schließlich spiegelt es den All-Eins-Zustand 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. Um den Vorgang abzuschließen, richtet der Main Vorgang das Problem ein, indem er die Anzahl von Qubits und die Anzahl der Iterationen angibt.

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

Sie können Ihren Q# Code mit copilot in Azure Quantum kostenlos testen. Sie benötigen lediglich ein Microsoft-E-Mail-Konto (MSA). Weitere Informationen zum Copilot in Azure Quantum finden Sie unter Erkunden von Azure Quantum.

Öffnen Sie copilot in Azure Quantum in Ihrem Browser.

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

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

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 auf die Schaltfläche VS Code-Logo klicken.

Ausführen des Programms mithilfe des In-Memory-Simulators

Wählen Sie In-Memory-Simulator aus.
Wählen Sie die Anzahl der auszuführenden Aufnahmen aus, und klicken Sie auf Ausführen.
Die Ergebnisse werden im Histogramm und in den Feldern Ergebnisse angezeigt.
Klicken Sie auf Code erklären , um Copilot aufzufordern, Ihnen den Code 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.

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

Öffnen Sie Visual Studio Code, und wählen Sie Datei > Neue Textdatei aus, um eine neue Datei zu erstellen.
Speichern Sie die Datei unter dem Namen GroversAlgorithm.qs. Diese Datei enthält den Q# Code für Ihr Programm.

Kopieren Sie den folgenden Code in die GroversAlgorithm.qs Datei.

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

Bevor Sie das Programm ausführen, müssen Sie das target Profil auf Uneingeschränkt festlegen. Wählen Sie Ansicht –> Befehlspalette aus, suchen Sie nach QIR, wählen SieQ# : Legen Sie das Azure Quantum QIR-Profil target fest, und wählen Sie dann : uneingeschränkt ausQ#.
Klicken Sie zum Ausführen des Programms in der Liste der Befehle unten @EntryPoint()auf Ausführen, oder drücken Sie STRG+F5. Das Programm führt den Vorgang oder die Funktion aus, die mit dem @EntryPoint() -Attribut im Standardsimulator gekennzeichnet ist.
Ihre Ausgabe wird in der Debugkonsole angezeigt.