教學課程:以 Q# 執行格羅弗搜尋演算法
注意
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 或開啟 Web 上的 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$ 是搜尋空間的位大小,請尋找$f (x_0) =1$ 的輸入 $x_0$。
若要實作 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}}$ 次:
- Oracle $O_f$ 的階段,適用於解決方案項目的 $-1$ 條件式階段移位。
- 將 $H$ 套用至暫存器中的每個量子位元。
- 套用 $-O_0$,將 $-1$ 的條件式階段移位移至每個計算基礎狀態,但 $\ket{0}$ 除外。
- 將 $H$ 套用至暫存器中的每個量子位元。
- 測量暫存器以取得具有極高機率解決方案的項目索引。
- 檢查項目,查看其是否為有效的解決方案。 如果不是,請重新開始。
在中撰寫 Grover 演演算法的程式代碼 Q#
本節討論如何在 Q# 中實作演算法。 實作 Grover 的演算法時,需要考慮幾個事項。 您必須定義標示的狀態、如何反映狀態,以及執行演算法的反覆項目數目。 您也需要定義實作 Grover 工作的函式的 Oracle。
定義標示的狀態
首先,您會定義您在搜尋中嘗試尋找的輸入。 若要這樣做,請撰寫作業,以套用 Grover 演算法中的步驟 b、c 和 d。
這些步驟一起稱為 Grover'S O_0 H^{\otimes n}$的 Grover'S 操作運算符 $-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
會反映以交替零和 1 標記的基礎狀態。 其作法是將 Grover 的擷取運算子套用至輸入量子位。 作業會使用輔助量子位 ,outputQubit
它會套用 $X$ 和 $H$ 閘道,以狀態 $\ket{-}=\frac{1}{\sqrt{2}} (\ket-\ket{0}{1}) $ 初始化。 然後,此作業會將 $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。
將下列程式代碼複製並貼到程式碼編輯器中。
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 () 的快照數,然後選取 [執行]。
後續步驟
探索其他 Q# 教學課程:
- 量子糾纏 示範如何撰寫 Q# 可操作和測量量子位的程式,並示範迭加和糾纏的效果。
- 量子隨機數產生器 示範如何撰寫 Q# 程式,以在迭加中產生量子位的隨機數。
- Quantum Fourier Transform 會探索如何撰寫 Q# 直接解決特定量子位的程式。
- Quantum Katas 是自我步調教學課程和程序設計練習,旨在同時教學量子運算和Q#程序設計的專案。
意見反應
https://aka.ms/ContentUserFeedback。
即將登場:在 2024 年,我們將逐步淘汰 GitHub 問題作為內容的意見反應機制,並將它取代為新的意見反應系統。 如需詳細資訊,請參閱:提交並檢視相關的意見反應