教學課程：在 Q# 中實現 Grover 演算法的搜尋功能

在本教學課程中，您會在中 Q# 實作 Grover 的演算法，以解決以搜尋為基礎的問題。如需深入了解有關 Grover 演算法背後的理論，請參閱 Grover 演算法的理論。

在本教學課程中，您已：

定義搜尋問題的 Grover 演算法
請在Q#中實作 Grover 的演算法

必要條件

要在 Visual Studio Code（VS Code）中開發並執行範例程式碼，你需要安裝以下工具：

最新版的 VS Code，或開啟 VS Code for the Web。
最新版本 Microsoft Quantum Development Kit 的（QDK）擴充功能。安裝細節請參見設置 QDK。

定義問題

Grover 的演算法是量子運算中最著名的演算法之一。它解決的問題類型通常被稱為「搜尋資料庫」，但更準確的理解是從搜尋問題的角度來看。

任何搜尋問題都可以以數學方式使用接受搜尋專案$x$的抽象函式$f（x）$ 來制定。如果專案$x$ 是搜尋問題的解決方案，則$f（x）=1$。如果專案$x$ 不是解決方案，則 $f（x）=0$。搜尋問題包含尋找滿足$f(x_0)=1$的任何項目。

因此，你可以將任何搜尋問題表述為：給定一個經典函數 $f（x）：\{0,1\}^n \rightarrow\{0,1\}$，其中 $n$ 是搜尋空間的位元大小，找到一個輸入 $x_0$，使得 $f（x_0）=1$。

若要實作 Grover 的演算法來解決搜尋問題，您需要：

將問題轉換為Grover's 任務形式。例如，假設您想要使用 Grover 的演算法來尋找整數$M$ 的因素。您可以藉由建立函式 $$f_M（x）=1[r]，$$ 將整數分解問題轉換成 Grover 的工作，其中$1[r]=1$ 如果$r=0$ 和 $1[r]=0$，則為 $r\neq0$ 且 $r$ 是$M/x$ 的其餘部分。如此一來，讓 $f_M(x_i)=1$ 的 $x_i$ 是 $M$ 的因數，而您已將問題轉換為 Grover 算法的任務。
實作 Grover 工作的函式做為量子 Oracle。若要實作 Grover 的演算法，您必須將 Grover 工作的函式$f（x）$ 實作為量子 Oracle。
使用 Grover 的演算法與預言機來解決任務。擁有量子神諭之後，您可以將它插入 Grover 演算法的實作中，以解決問題並解釋輸出。

Grover 的演算法

假設搜尋問題有$N=2^n$個符合資格的項目，而且會透過將每個項目指派一個從$0$到$N-1$的整數進行索引。演算法的步驟如下：

從初始化為狀態 $\ket{0}$ 的 $n$ 量子位暫存器開始。
將 $H$ 套用至緩存器中的每個量子位，將緩存器準備成統一迭加：$$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
將下列作業套用至緩存器$N_{\text{optimal}}$ 次：
1. 相位預言機 $O_f$ 施加條件式的相位移位 $-1$ 給解。
2. 將 $H$ 套用至緩存器中的每個量子位。
3. 將 $-O_0$ 套用為 $-1$ 的條件式階段移轉至 $\ket{0}$ 以外的每個計算基礎狀態。
4. 將 $H$ 套用至緩存器中的每個量子位。
測量寄存器，以取得具有非常高機率的方案的項目的索引。
檢查項目，以確認其是否為有效的解決方案。如果沒有，請重新開始。

在Q#中撰寫 Grover 演算法的程式代碼

本節討論如何在Q#中實作演算法。實作格羅弗演算法時有幾點需要考慮。您需要定義您的標記狀態、如何思考該狀態，以及運行演算法的迭代次數。您也需要定義會實作 Grover 工作函式的 Oracle。

定義標示的狀態

首先，您會定義您在搜尋中嘗試尋找的輸入。若要這樣做，請撰寫並執行套用步驟b、c 和 d的操作。

這些步驟也稱為 Grover 的擴散運算符 $-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);
    }
}

作業 ReflectAboutMarked 會反映以零和一交替標記的基態。其方式是將 Grover 的擴散運算子套用至輸入量子位。作業會使用輔助量子位outputQubit，其藉由施加 $X$ 和 $H$ 閘門初始化為狀態 $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$。然後作業會將 $X$ 閘道套用至緩存器中所有其他量子位，這會翻轉量子位的狀態。最後，它會將受控制的 $X$ 閘道套用至輔助量子位和輸入量子位。只有在所有輸入量子位都處於 $\ket{1}$ 狀態時，此作業才會翻轉輔助量子位，也就是標示的狀態。

定義最佳反覆項目的數目

Grover 的搜尋具有最佳的迭代次數，可以產生測量有效輸出的最高機率。如果問題有$N=2^n$ 可能符合資格的專案，且其中$M$ 是解決問題的解決方案，則最佳反復專案數目為：

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

繼續超過最佳迭代次數進行迭代會開始降低成功的機率，直到在迭代次數達到 $2 N_{\text{optimal}}$ 時成功機率接近零。之後，機率會再次成長，直到 $3 N_{\text{optimal}}$等等。

在實際的應用中，您通常不會在解決您的問題之前知道有多少個解決方案。一種有效處理此問題的策略是通過將猜測按二的冪次遞增（即$1、2、4、8、16、...、2^n$）來“猜測”解的數目 $M$。其中一個猜測將足夠接近，使得演算法仍能以大約 $\sqrt{\frac{N}{M}}$ 的平均迭代次數找到解決方案。

以下 Q# 函式會計算暫存器中指定量子位數目的最佳迭代次數。

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

該 CalculateOptimalIterations 函數使用先前所示的公式計算迭代次數，然後將其四捨五入至最接近的整數。

定義 Grover 的運算

Q# Grover 搜尋演算法的操作有三個輸入：

量子位緩存器中的量子位 nQubits : Int數目。此暫存器編碼搜尋問題的暫定解，並在操作後進行測量。
最佳迭代次數，iterations : Int。
表示 Grover 演算法的相位預言機的作業phaseOracle : Qubit[] => Unit) : Result[]。此操作對通用量子位暫存器進行酉轉換。

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

此 GroverSearch 作業會初始化狀態 $\ket{0}$ 中的 $n$ 量子位元暫存器，將暫存器準備成統一疊加，然後針對指定的反覆運算次數套用 Grover 演算法。搜尋本身是由反覆思考標示狀態和起始狀態所組成，您可以在Q#中將其寫成一個 for 迴圈。最後，它會測量緩存器並傳回結果。

程式代碼會使用三個協助程式作業： PrepareUniform、 ReflectAboutUniform和 ReflectAboutAllOnes。

假設暫存器處於全零狀態，PrepareUniform 操作會生成所有基礎狀態的均勻疊加。

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

該 ReflectAboutAllOnes 運算反映於全一狀態。

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

此作業 ReflectAboutUniform 會反映統一迭加狀態。首先，它會將均勻疊加態轉換為全零狀態。然後，它會將全零狀態轉換成全一狀態。最後，它會反映全一狀態。此操作被稱為 ReflectAboutUniform，因為在幾何上可以解釋為在向量空間中相對於均勻迭加狀態的反射。

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

執行最終程序代碼

現在，您擁有實現 Grover 搜索演算法一個特定實例並解決因式分解問題的所有要素。若要完成，該操作會藉由指定量子位的數目和迭代次數來設定問題。

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

執行程式

在 VS Code 中，打開檔案選單並選擇 新文字檔案 以建立新檔案。
將檔案儲存為 GroversAlgorithm.qs。此檔案包含程式 Q# 程式代碼。

將下列程式碼複製至 GroversAlgorithm.qs 檔案。


import Std.Convert.*;
import Std.Math.*;
import Std.Arrays.*;
import Std.Measurement.*;
import Std.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);
    }
}

要執行程式，請從操作選單中選擇Main，或按 Ctrl + F5。根據預設，編譯程式會在預設模擬器上執行 Main 作業或函式。
你的輸出會顯示在終端機的除錯控制台。

注意

如果 QIR target 設定檔未設定為 [不受限制]，則在執行程式時會收到錯誤。對於此程式，編譯器會自動將 target 設定檔設定為 Unrestricted ，除非您自己設定設定檔。

探索其他 Q# 教學課程：

量子糾纏示範如何撰寫 Q# 程式，以操作和測量量子位，並示範迭加和糾纏的效果。
量子隨機數產生器示範如何撰寫Q#程式，以從處於疊加狀態的量子位中產生隨機數。
Quantum Fourier Transform 會探索如何撰寫 Q# 直接尋址特定量子位的程式。
Quantum Katas 是自我節奏的教學課程和程序設計練習，旨在同時教學量子運算和Q#程序設計元素。

意見反應

此頁面對您有幫助嗎？

上次更新時間： 2026-05-20