格羅弗搜尋演算法的理論
在本文中，您將找到可運算格羅弗演算法的數學準則詳細理論說明。
如需 Grover 演演算法的實際實作來解決數學問題，請參閱 實作 Grover 的搜尋演算法。
問題的陳述
任何搜尋工作都可以使用可接受搜尋項目 $x$ 的抽象函式 $f(x)$ 來表示。 如果項目 $x$ 是搜尋工作的解決方案，則 $f(x)=1$。 如果項目 $x$ 不是解決方案，則 $f(x)=0$v。 搜尋問題包括尋找任何項目 $x_0$，以致 $f(x_0)=1$。
格羅弗演算法所要解決的目標工作可以如下表示：指定傳統函式 $f(x):\{0,1\}^n \rightarrow\{0,1\}$，其中 $n$ 是搜尋空間的位元大小，請尋找 $x_0$ 的輸入 (其 $f(x_0)=1$)。 演算法的複雜度是以函式 $f(x)$ 的使用次數來測量。 傳統方式在最糟的情況下，$f(x)$ 總共必須評估 $N-1$ 次 (其中 $N=2^n$)，以嘗試所有可能性。 在 $N-1$ 個元素之後，其必須是最後一個元素。 格羅弗的量子演算法可以更快地解決此問題，並提供二倍的速度。 這裡有二個暗示，相較於 $N$，只需要 $\sqrt{N}$ 次評估。
演算法的大綱
假設有 $N=2^n$ 個符合搜尋工作的項目，並為每個項目指派從 $0$ 到 $N-1$ 的整數來編制索引。 此外，假設有 $M$ 個不同的有效輸入，表示 $f(x)=1$ 的輸入為 $M$。 演算法的步驟如下所示：
- 從具有以 $\ket{0}$ 狀態所起始 $n$ 個量子位元的暫存器開始。
- 將 $H$ 套用至暫存器的每個量子位，以準備註冊到統一的疊加：$$|\text{register}\rangle=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle$$
- 將下列作業套用至暫存器 $N_{\text{optimal}}$ 次：
- Oracle $O_f$ 的階段，適用於解決方案項目的 $-1$ 條件式階段移位。
- 將 $H$ 套用至暫存器中的每個量子位元。
- 將 $-1$ 的條件式階段移位移至每個計算基礎狀態，但 $\ket{0}$ 除外。 這可由單一作業 $-O_0$ 表示，因為 $O_0$ 表示條件式階段僅限轉換為 $\ket{0}$。
- 將 $H$ 套用至暫存器中的每個量子位元。
- 測量暫存器以取得具有極高機率解決方案的項目索引。
- 檢查其是否為有效的解決方案。 如果不是，請重新開始。
$N_\text{optimal}=\left\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{1}{{2}\right\rfloor$ 是最佳的反覆運算次數，可透過測量暫存器來最大化取得正確項目的可能性。
注意
步驟 3.b、3.c 和 3.d 的聯結應用程式通常是以格羅弗擴散運算子的形式進行識別。
套用至暫存器的整體單一作業為：
$$(-H^{\otimes n}O_0H^{\otimes n}O_f)^{N_{\text{optimal}}}H^{\otimes n}$$
遵循暫存器的狀態逐步解說
為了說明此程序，讓我們針對只有兩個量子位元且有效元素為 $\ket{01}.$ 的簡單案例，遵循暫存器狀態的數學轉換
暫存器會以下列狀態開始：$$|\text{register}\rangle=|00\rangle$$
在將 $H$ 套用至每個量子位元之後，暫存器的狀態轉換為：$$|\text{register}\rangle=\frac{{1}{\sqrt{{4}}\sum_{i \in \{0,1\}^2}|i\rangle=\frac12(\ket{00}+\ket{01}+\ket{10}+\ket{11})$$
然後，套用 Oracle 的階段以取得：$$|\text{register}\rangle=\frac12(\ket{{00}-\ket{{01}+\ket{{10}+\ket{{11})$$
然後 $H$ 再次在每個量子位上運作，以提供：$$|\text{register}\rangle=\frac12(\ket{{00}+\ket{{01}-\ket{{10}+\ket{{11})$$
現在，條件階段移位會套用至每個狀態，但 $\ket{00}$: $$|\text{register}\rangle=\frac12(\ket{{00}-\ket{{01}+\ket{{10}-\ket{{11})$$ 除外
最後，第一個格羅弗反覆運算的結束方式是再次套用 $H$ 以取得：$$|\text{register}\rangle=\ket{{01}$$
遵循上述步驟，即可在單一反覆運算中找到有效的項目。 如您稍後所見，這是因為 N=4 和單一有效專案 $N_\text{最佳}=1$。
幾何說明
為了解格羅弗演算法的運作方式，讓我們從幾何觀點來研究演算法。 使 $\ket{\text{bad}}$ 成為非搜尋問題解決方案的所有狀態疊加。 假設有 $M$ 個有效的解決方案：
$$\ket{\text{bad}}=\frac{{1}{\sqrt{N-M}}\sum_{x:f(x)=0}\ket{x}$$
$\ket{\text{good}}$ 狀態定義為屬於搜尋問題解決方案所有狀態的疊加：
$$\ket{\text{good}}=\frac{{1}{\sqrt{M}}\sum_{x:f(x)=1}\ket{x}$$
由於 good 和 bad 是互斥的集合，因為某個項目不能為有效且無效，所以 $\ket{\text{good}}$ 和 $\ket{\text{bad}}$ 狀態 }}$ 是正向的。 這兩個狀態會形成向量空間中平面的正向基礎。 您可以使用此平面將演算法視覺化。
現在假設 $\ket{\psi}$ 是 $\ket{\text{good}}$ 和 $\ket{\text{bad}}$ 在平面上所合併的任意狀態。 在該平面中的任何狀態都可以表示為：
$$\ket{\psi}=\alpha\ket{\text{good}} + \beta\ket{\text{bad}}$$
其中 $\alpha$ 和 $\beta$ 是實數。 現在，讓我們介紹反映運算子 $R_{\ket{\psi}}$，其中 $\ket{\psi}$ 是在平面中的任何量子位元狀態。 運算子定義為：
$$R_{\ket{\psi}}=2\ket{\psi}\bra{\psi}-\mathcal{I}$$
其稱為 $\ket{\psi}$ 反映運算子，因為其可以幾何解譯為 $\ket{\psi}$ 方向的反映。 若要加以查看，請採用 $\ket{\psi}$ 形成的正交基平面，以及其正交補餘 $\ket{\psi^{\perp}}$。 平面的任何狀態 $\ket{\xi}$ 都可依下列方式分解：
$$\ket{\xi}=\mu \ket{\psi} + \nu {\ket{\psi^{\perp}}}$$
如果您將運算子 $R_{\ket{\psi}}$ 套用至 $\ket{\xi}$：
$$R_{\ket{\psi}}\ket{\xi}=\mu \ket{\psi} - \nu {\ket{\psi^{\perp}}}$$
運算子 $R_\ket{\psi}$ 反轉元件正交為 $\ket{\psi}$，但使 $\ket{\psi}$ 元件保持不變。 因此，$R_\ket{\psi}$ 是 $\ket{\psi}$ 的反映。
格羅弗的演算法，在第一次將 $H$ 應用程式新增至每個量子位元之後，就會以所有狀態的統一疊加開始。 其可撰寫如下：
$$\ket{\text{all}}=\sqrt{\frac{M}{N}}\ket{\text{good}} + \sqrt{\frac{N-M}{N}}\ket{\text{bad}}$$
因此，狀態會存留在平面中。 請注意，從相等迭量測量時取得正確結果的機率只是$|\braket{\text{}|{\text{好所有}}}|^2=M/N$，這是您預期隨機猜測的結果。
Oracle $O_f$ 會將負階新增至搜尋問題的任何解決方案。 因此，其可以撰寫為關於 $\ket{\text{bad}}$ 軸的反映：
$$O_f = R_{\ket{\text{bad}}}= 2\ket{\text{bad}}\bra{\text{bad}} - \mathcal{I}$$
類似，條件式階段移位 $O_0$ 只是狀態 $\ket{0}$ 的反向反映：
$$O_0 = R_{\ket{0}}= -2\ket{{0}\bra{0} + \mathcal{I}$$
知道這一點，就很容易能確認格羅弗擴散作業 $-H^{\otimes n} O_0 H^{\otimes n}$ 也是 $\ket{all}$ 狀態 }$ 的反映。 只需要：
$$-H^{\otimes n} O_0 H^{\otimes n}=2H^{\otimes n}\ket{0}\bra{{0}H^{\otimes n} -H^{\otimes n}\mathcal{I}H^{\otimes n}= 2\ket{\text{all}}\bra{\text{all}} - \mathcal{I}= R_{\ket{\text{all}}}$$
我們已示範格羅弗演算法的每個反覆項目都是 $R_\ket{\text{bad}}$ 和 $R_\ket{\text{all}}$ 這兩個反映的組合。
每個格羅弗反覆項目的組合效果是以逆時針旋轉的角度 $2\theta$。 所幸，角度 $\theta$ 很容易找到。 由於 $\theta$ 只是 $\ket{\text{all}}$ 與 $\ket{\text{bad}}$ 之間的角度，因此您可以使用純量積來尋找角度。 已知 $\cos{\theta}=\braket{\text{all}|\text{bad}}$，因此需要計算 $\braket{\text{all}|\text{bad}}$。 從 $\ket{\text{bad}}$ 和 $\ket{\text{good}}$ 的分解 $\ket{\text{all}}$，如下所示：
$$\theta = \arccos{\left(\braket{\text{all}|\text{bad}}\right)}= \arccos{\left(\sqrt{\frac{N-M}{N}}\right)}$$
緩存器狀態與 $\ket{\text{良好}}$ 狀態之間的角度會隨著每個反覆項目而減少，因此測量有效結果的機率較高。 若要計算此機率，您只需要計算$|\braket{\text{良好的快取器}}|^2$}|\text{。 表示 $\ket{\text{good}}$ 與 $\ket{\text{register}}$$\gamma (k)$ 之間的角度，其中 $k$ 是反覆運算計數：
$$\gamma (k) =\frac{\pi}{2}-\theta -k2\theta =\frac{\pi}{{2} -(2k + 1) \theta $$
因此，成功的機率為：
$$P(\text{success}) = \cos^2(\gamma(k)) = \sin^2\left[(2k +1)\arccos \left( \sqrt{\frac{N-M}{N}}\right)\right]$$
反覆運算的最佳次數
由於成功的機率可以撰寫為反覆運算次數的函式，因此您可以計算最大的正整數，以找出 (大約) 最大化成功機率函式的最小正整數，以找出最佳的反覆運算 $N_{\text{optimal}}$。
已知 $\sin^2{x}$ 達到 $x=\frac{\pi}{2}$ 的第一個最大值，因此：
$$\frac{\pi}{{2}=(2k_{\text{optimal}} +1)\arccos \left( \sqrt{\frac{N-M}{N}}\right)$$
這會提供：
$$k_{\text{optimal}}=\frac{\pi}{4\arccos\left(\sqrt{1-M/N}\right)}-1/2 =\frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{1}{2}-O\left(\sqrt\frac{M}{N}\right)$$
在最後一個步驟中，$\arccos \sqrt{1-x}=\sqrt{x} + O(x^{3/2})$。
因此，您可以挑選$N_最佳N_optimal$=\left\text{}$}\lfloor \frac{\pi{4}\sqrt{\frac{}{N}{M}}-{1}{2}\right\frac{\rfloor。$\text{
複雜性分析
從先前的分析開始，需要 Oracle $O_f$ 的 $O\left(\sqrt{\frac{N}{M}}\right)$ 查詢，才能找到有效的項目。 不過，演算法是否可以在時間複雜性方面有效率地執行？ $O_0$ 是以 $n$ 位元的運算布林值作業為基礎，且已知為可使用 $O(n)$ 閘道實作。 另外還有兩個 $n$ 層級的 Hadamard 閘道。 因此，這兩個元件都只需要每個反覆運算 $O(n)$ 閘道。 因為 $N=2^n$，所以會遵循該 $O(n)=O(log(N))$。 因此，如果需要每個反覆運算的 $O\left(\sqrt{\frac{N}{M}}\right)$ 反覆運算和 $O(log(N))$ 閘道，則總時間複雜性 (不考慮 Oracle 實作) 是 $O\left(\sqrt{\frac{N}{M}}log(N)\right)$。
演演算法的整體複雜度最終取決於 oracle $O_f$ 實作的複雜度。 如果量子計算機上的函式評估比傳統計算機更複雜，則整體演算法運行時間在量子案例中會較長，即使技術上來說，它還是會使用較少的查詢。
參考資料
如果您想要繼續了解格羅弗的演算法，您可以檢查下列任何來源：
- Lov K. Grover 所著的原始論文
- Nielsen M. A. A 的量子搜尋演算法區段。 &放大器;Chuang， I. L. (2010) 。 量子計算和量子資訊。
- Arxiv.org 上的格羅弗演算法
下一步
意見反應
即將登場：在 2024 年，我們將逐步淘汰 GitHub 問題作為內容的意見反應機制，並將它取代為新的意見反應系統。 如需詳細資訊，請參閱：https://aka.ms/ContentUserFeedback。
提交並檢視相關的意見反應