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

發行項
01/13/2025

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

在本教學課程中，您已：

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

提示

如果您想要加速量子運算旅程，請參閱使用 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$。搜尋問題包含尋找任何$x_0$ 的專案，例如$f（x_0）=1$。

因此，您可以制定任何搜尋問題，例如：假設傳統函式$f（x）：\{0,1\}^n \rightarrow\{0,1\}$，其中$n$ 是搜尋空間的位大小，請尋找輸入 $x_0$，其中$f（x_0）=1$。

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

將問題轉換為 Grover 工作的形式。例如，假設您想要使用 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。
搭配 Oracle 使用 Grover 的演算法來解決工作。擁有量子 Oracle 之後，您可以將它插入 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. 階段 oracle $O_f$，針對解決方案專案套用 $-1$ 的條件式階段移位。
2. 將 $H$ 套用至緩存器中的每個量子位。
3. 將 $-O_0$ 套用為 $-1$ 的條件式階段移轉至 $\ket{0}$ 以外的每個計算基礎狀態。
4. 將 $H$ 套用至緩存器中的每個量子位。
測量快取器，以取得具有非常高機率之方案之專案的索引。
檢查專案，以查看其是否為有效的解決方案。如果沒有，請重新開始。

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

本節討論如何在中 Q#實作演算法。實作 Grover 演算法時，需要考慮幾個事項。您需要定義標示的狀態、如何反映其內容，以及執行演算法的反覆項目數目。您也需要定義會實作 Grover 工作函式的 Oracle。

定義標示的狀態

首先，您會定義您在搜尋中嘗試尋找的輸入。若要這樣做，請撰寫作業，以套用 Grover 演算法的步驟 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 的擴散運算子套用至輸入量子位。作業會使用以 $\ketoutputQubit=\frac{-}{\sqrt{1}}（\ket-\ket{2}{0}）$ 狀態初始化的輔助量子位{1}，方法是套用 $X$ 和 $H$ 網關。然後作業會將 $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。
作業， phaseOracle : Qubit[] => Unit) : Result[]表示 Grover 工作的階段 Oracle。這項作業會套用泛型量子位緩存器上的一元轉換。

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 搜尋演算法特定實例並解決分解問題的所有要素。若要完成，作業會 Main 藉由指定量子位數目和反覆項目數目來設定問題

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 標誌按鈕，以在 Web 的 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#：不受限制。
若要執行程式，請從作業上方的命令清單中選取 [執行]，或按 Main。根據預設，編譯程式會在預設模擬器上執行 Main 作業或函式。
您的輸出會出現在終端機的偵錯控制台中。

注意

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

探索其他 Q# 教學課程：

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

共用方式為

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

必要條件

縮小問題的範圍

Grover 的演算法

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

定義標示的狀態

定義最佳反覆項目的數目

定義 Grover 的作業

執行最終程序代碼

執行程式

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

使用 Quantinuum 模擬器執行程式

意見反應

其他資源

共用方式為

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

必要條件

縮小問題的範圍

Grover 的演算法

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

定義標示的狀態

定義最佳反覆項目的數目

定義 Grover 的作業

執行最終程序代碼

執行程式

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

使用 Quantinuum 模擬器執行程式

相關內容

意見反應

其他資源

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