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

2025-03-25

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

在本教學課程中，您已：

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

提示

如果您想要加速量子運算旅程，請參閱使用 Azure Quantum 撰寫程式代碼，這是 Azure Quantum 網站的獨特功能。在這裡，您可以執行內建Q#範例或您自己的Q#程式、從提示產生新的Q#程式碼、按一下即可在 VS Code for the Web 中開啟並執行程式碼，並詢問 Copilot 任何有關量子運算的問題。

必要條件

若要在 Azure Quantum 的 Copilot 中執行程式代碼範例：
- Microsoft （MSA）電子郵件帳戶。
若要在 Visual Studio Code 中開發和執行程式碼範例：
- 最新版的 Visual Studio Code 或開啟 Web上的 VS Code。
- 最新版的 Azure Quantum Development Kit 擴充功能。如需安裝詳細資料，請參閱設定 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 演算法時，需要考慮幾個事項。您需要定義您的標記狀態、如何思考該狀態，以及運行演算法的迭代次數。您也需要定義會實作 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 作業會將一個 $n$ 量子位的寄存器初始化為狀態 $\ket{0}$，準備成均勻疊加態，然後針對指定的迭代次數應用 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;
}

執行程式

選取想要執行程序的平臺。

Azure Quantum 中的 Copilot
Visual Studio Code

您可以在 Azure Quantum 中免費使用 Copilot 測試 Q# 代碼，只需要一個 Microsoft 帳戶（MSA）電子郵件。如需 Azure Quantum 中 Copilot 的詳細資訊，請參閱探索 Azure Quantum。

在瀏覽器中開啟 Azure Quantum 中的 Copilot。

將下列程式代碼複製並貼到程式碼編輯器中。

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

提示

從 Azure Quantum 的 Copilot 中，您可以在程式碼編輯器右上角選取 VS Code 標誌按鈕，以在 VS Code 網頁版中開啟程式。

使用記憶體內部模擬器執行程式

選取 [記憶體內部模擬器]。
選取要執行的拍攝次數，然後選取 [ 執行]。
結果會顯示在直方圖和 [結果] 欄位中。
選取 [說明程序代碼 ] 以提示 Copilot 向您說明程式代碼。

使用 Quantinuum 模擬器執行程式

您也可以將程式提交至免費的 Quantinuum 模擬器。模擬器會模擬具有 20 個量子位的量子計算機。

選擇 [In-Memory 模擬器] 下拉式列表，然後選擇 [Quantinuum 模擬器]。
選取嘗試次數 (目前限制為 20 次)，然後選取 [執行]。

開啟 Visual Studio Code，然後選取 [檔案 > 新增文字檔] 以建立新的檔案。
將檔案儲存為 GroversAlgorithm.qs。此檔案將包含 Q# 程式的程序代碼。

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


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

執行程式之前，請確定 target 配置檔已設定為 [不受限制]。選取 [檢視 -> 命令選擇區]，搜尋 QIR，選取Q# ：設定 Azure Quantum QIR target 配置檔，然後選取 Q#：不受限制。
若要執行程式，請從操作區上方的命令清單中選取 [執行]，或按 Ctrl+F5。根據預設，編譯程式會在預設模擬器上執行 Main 作業或函式。
您的輸出會出現在終端機的偵錯控制台中。

注意

target如果設定檔未設定為 [不受限制]，當您執行程式時會收到錯誤。

探索其他 Q# 教學課程：

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

共用方式為