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

發行項
07/03/2024

在本教學課程中，您會在中 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 擴充功能。如需安裝詳細數據，請參閱在 VS Code 上安裝 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 的擴散運算子套用至輸入量子位。作業會使用以 $\ket{-}=\frac{1}{\sqrt{2}}（\ket-\ket{0}{1}）$ 狀態初始化的輔助量子位outputQubit，方法是套用 $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。

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

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

提示

從 Azure Quantum 中的 Copilot，您可以按兩下程式代碼編輯器右上角的 VS Code 標誌按鈕，在 Web 的 VS Code 中開啟程式。

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

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

使用 Quantinuum H 系列模擬器執行程式

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

選取 [記憶體內部模擬器] 下拉式清單，然後選取 [Quantinuum H 系列模擬器]。
選取嘗試次數 (目前限制為 20 次)，然後選取 [執行]。

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

複製檔案中的 GroversAlgorithm.qs 下列程序代碼。

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

在執行程式之前，您必須將 target 設定檔設定為 [不受限制]。選取 [檢視 -> 命令選擇區]，搜尋 QIR，選取Q# ：設定 Azure Quantum QIR target 配置檔，然後選取 Q#：不受限制。
若要執行程式，請按下下方命令清單中的 [執行]，或按 Ctrl+F5。@EntryPoint() 程式會在預設模擬器上執行以 @EntryPoint() 屬性標示的作業或函式。
您的輸出會出現在偵錯控制台中。

注意

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

探索其他 Q# 教學課程：

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

共用方式為

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

必要條件

縮小問題的範圍

Grover 的演算法

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

定義標示的狀態

定義最佳反覆項目的數目

定義 Grover 的作業

執行最終程序代碼

執行程式

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

使用 Quantinuum H 系列模擬器執行程式

意見反應

其他資源

共用方式為

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

必要條件

縮小問題的範圍

Grover 的演算法

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

定義標示的狀態

定義最佳反覆項目的數目

定義 Grover 的作業

執行最終程序代碼

執行程式

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

使用 Quantinuum H 系列模擬器執行程式

相關內容

意見反應

其他資源

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