教學課程：以 Q# 執行格羅弗搜尋演算法

發行項
04/13/2024

注意

2024 年 6 月 30 日之後，將不再支援 Microsoft Quantum Development Kit (傳統 QDK) 。如果您是現有的 QDK 開發人員，建議您轉換至新的 Azure Quantum Development Kit (Modern QDK) ，以繼續開發量子解決方案。如需詳細資訊，請參閱將您的程式 Q# 代碼移轉至新式 QDK。

在本教學課程中，您會在中 Q# 實作 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 或開啟網路上的 VS Code。
- 最新版的 Azure Quantum Development Kit 擴充功能。如需安裝詳細數據，請參閱在 VS Code 上安裝新式 QDK。

定義問題

格羅弗的演算法是量子運算中最著名的演算法之一。其解決的問題類型通常稱為「搜尋資料庫」，但就 搜尋問題而言更精確。

任何搜尋問題都可以使用接受搜尋項目 $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 的演算法來解決搜尋問題，您需要：

將問題轉換成格羅弗工作的形式。例如，假設您想要使用格羅弗的演算法尋找整數 $M$ 的因數。您可以藉由建立函式 $$f_M(x)=1[r],$$，其中 $1[r]=1$ (若 $r=0$) 及 $1[r]=0$ (若 $r\neq0$) 且 $r$ 為 $M/x$ 的餘數，將整數分解問題轉換成格羅弗的工作。如此一來，使 $f_M(x_i)=1$ 的整數 $x_i$ 為 $M$ 的因數是 $M$ 的因數，而您已將問題轉換成格羅弗的工作。
將格羅弗的工作函式實作為「量子 Oracle」。若要實作格羅弗的演算法，您必須將格羅弗工作的函式 $f(x)$ 實作為量子 Oracle。
使用格羅弗的演算法搭配您的 Oracle 來解決此工作。一旦您擁有量子 Oracle 之後，您可以將其插入格羅弗的演算法實作，以解決問題並解讀輸出。

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}$ 狀態時，此作業才會翻轉輔助量子位，也就是標示的狀態。

定義最佳反覆項目的數目

格羅弗的搜尋有最佳的反覆運算次數，可產生測量有效輸出的最高可能性。如果問題有 $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);
    }
}

執行最後的程式碼

現在您已有所有的要素可實作格羅弗搜尋演算法的特定執行個體，並解決分解問題。若要完成，作業 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 免費測試程式 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#[不受限制]。
若要執行程式，請從右上方的播放圖示下拉式清單中選取 [ 執行 Q# 檔案 ]，或按 Ctrl+F5。程式會在預設模擬器上執行以屬性標示 @EntryPoint() 的作業或函式。
您的輸出會出現在偵錯控制台中。

注意

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

後續步驟

探索其他 Q# 教學課程：

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