Grover 搜尋演算法的理論
在本文中，您將找到一個詳細的理論說明，說明讓 Grover 演演算法運作的數學原則。
如需 Grover 演演算法的實際實作來解決數學問題，請參閱 實作 Grover 的搜尋演算法。
問題的陳述
Grover 的演算法可加快非結構化數據搜尋（或 搜尋問題）的解決方案，以比任何傳統演算法可能更少的步驟執行搜尋。 任何搜尋工作都可以使用接受搜尋專案 $x$ 的抽象函式 $f（x）$ 來表示。 如果專案 $x$ 是搜尋工作的方案，則 $f（x）=1$。 如果專案 $x$ 不是方案，則 $f（x）=0$。 搜尋 問題 包含尋找任何專案 $x_0$ ， $例如 f（x_0）=1$。
任何可讓您檢查指定值 $x$ 是否為有效解決方案的問題（&引號;是或沒有問題&引號;）可以根據搜尋問題來制定。 下列是部份範例：
- 布爾值可滿足性問題：假設有一組布爾值，集合是否滿足指定的布爾公式？
- 旅行推銷員問題：連接所有城市的可能的最短路徑是什麼？
- 資料庫搜尋問題：資料庫資料表是否包含記錄 $x$？
- 整數分解問題：數字 $N$ 是否可以被數字 $x$整除？
Grover 演算法的目標工作可以如下表示：假設有一個傳統函$式 f（x）：\{0,1\}^n \rightarrow\{0,1\}$，其中 $n$ 是搜尋空間的位大小，請尋找 f（x_0）$1$ 的$輸入=x_0$。 演算法的複雜度是由函式 f（x）$ 的使用$次數來測量。 在最壞的情況下， $f（x）$ 必須總共 $評估 N-1$ 次，其中 $N=2^n$，嘗試所有可能性。 N-1$ 元素之後$，它必須是最後一個專案。 Grover 的量子演算法可以更快解決這個問題，提供二次加速。 此處的二次方表示，相較於 $\sqrt{N}$，只需要大約 $N$ 個評估。
演算法的大綱
假設搜尋工作有 $N=2^n$ 個符合資格的專案，而且會藉由將每個專案指派一個從 $0$ 到 $N-1$ 的整數來編製索引。 此外，假設有 $M$ 不同的有效輸入，表示有$$M 輸入，f$（x）=1$。 然後演算法的步驟如下：
- 從狀態初始化$的 $n$\ket{0}$ 量子位緩存器開始。
- 將 H 套用$至緩存器的每個量子位，將緩存器準備成統一迭加：$緩存$$|\text{器 N}\rangle=\frac{1}{\sqrt{}}_\sumx{0=^}N-1{x}|\rangle$$
- 將下列操作以最優次數套用至暫存器 $N_{\text{}}$次：
- 階段 oracle $O_f$ ，針對解決方案專案套用條件式階段移 $位 -1$ 。
- 將 H$ 套$用至緩存器中的每個量子位。
- 除了 以外的$每個計算基礎狀態，條件式階段移位為 $-1$\ket{0}$。 這可由單一運算 $-O_0$來表示，因為 $O_0$ 只表示條件式階段移位 $\ket{0}$ 。
- 將 H$ 套$用至緩存器中的每個量子位。
- 測量快取器，以取得具有非常高機率之方案之專案的索引。
- 檢查其是否為有效的解決方案。 如果沒有，請重新開始。
$N_{\text{最佳}}=\left\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{{1}{{2}\right\rfloor$ 是最大化通過測量暫存器來獲得正確項目的可能性的最佳迭代次數。
注意
步驟 3.b、3.c 和 3.d 的聯合應用通常稱為 Grover 的擴散運算子。
套用至緩存器的整體一元運算為：
$$（-H^ n{\otimesO_0H}^{\otimes n O_f}）^{N_{\text{最佳}}}H^{\otimes n}$$
依照註冊的狀態逐步執行
為了說明此程式，讓我們遵循緩存器狀態的數學轉換，簡單案例中只有兩個量子位，而有效元素為 $\ket{01}。$
暫存器開始於狀態：
$$\ket{\text{註冊}}=\ket{{00}$$
將 $H$ 套用至每個量子位之後，緩存器的狀態會轉換成：
$$\ket{\text{register}}=\frac{{1}{\sqrt{4}}\sum_{i \in \lbrace 0,1 \r大括弧}^2\ket{i}=\frac12（\ket{00}+\ket{01}+\ket{{10}+\ket{11}）$$
然後，會套用相位 Oracle 以獲得：
$$\ket{\text{註冊}}=\frac12（\ket{{00}-\ket{{01}+\ket{{10}+\ket{{11}）$$
然後，$H$ 會再次對每個量子位採取動作，以提供：
$$\ket{\text{註冊}}=\frac12（\ket{{00}+\ket{{01}-\ket{{10}+\ket{{11}）$$
現在，條件式階段轉移會套用至每個狀態，但 $\ket{00}$除外：
$$\ket{\text{註冊}}=\frac12（\ket{{00}-\ket{{01}+\ket{{10}-\ket{{11}）$$
最後，第一個 Grover 迭代會再次套用 $H$，以取得：
$$\ket{\text{註冊}}=\ket{{01}$$
遵循上述步驟，即可在單一反覆專案中找到有效的專案。 如您稍後所見，這是因為在 N=4 和單一有效項目中，最佳重複次數為 $N_{\text{，並且最優化在}}=1$中。
幾何說明
若要查看 Grover 演演算法的運作原因，讓我們從幾何角度來研究演算法。 假設有 $M$ 個有效解決方案，的所有非解量子狀態的迭加不構成 搜尋問題的解決方案：
$$\ket{\text{bad}}=\frac{{1}{\sqrt{N-M}}\sum_{x：f（x）=0}\ket{x}$$
所有 狀態的迭加 搜尋問題的解決方案：
$$\ket{\text{good}}=\frac{{1}{\sqrt{M}}\sum_{x：f（x）=1}\ket{x}$$
由於 良好 和 不良 是互斥的集合，因為一個項目不能同時有效和無效，因此這些狀態是正交的。 這兩種狀態都會形成向量空間中平面的正交基礎。 人們可以使用這個平面來可視化演算法。
現在，假設$\ket{\psi}$是一種任意狀態，存在於飛機上，跨越$\ket{\text{好}}$壞$\ket{\text{}}$。 生活在該平面中的任何狀態都可以以下列形式表示：
$$\ket{\psi} = \alpha \ket{\text{良好}} + \beta\ket{\text{壞}}$$
其中 $\alpha$ 和 $\beta$ 是實數。 現在，讓我們介紹反映運算符 $R_{\ket{\psi}}$，其中 $\ket{\psi}$ 是位於平面中的任何量子位狀態。 運算子定義為：
$$ {\ket{\psi}}=R_2\ket{\psi}\bra{\psi}-\mathcal{I}$$
它稱為反映運算符， $\ket{\psi}$ 因為它可以幾何方式解譯為有關 方向的 $\ket{\psi}$反映。 若要查看它，請採用 所 $\ket{\psi}$ 形成平面的正交基礎及其正交補 $\ket{\psi碼 ^{\perp}}$。 平面的任何狀態 $\ket{\習}$ 都可以以這類基礎分解：
$$\ket{\習}=\mu \ket{\psi} + \nu {\ket{\psi^{\perp}}}$$
如果運算子R_$套用{\ket{\psi}}$至 $\ket{\習}$：
$$ {\ket{\psi}}\ket{R_\習}=\mu \ket{\psi} - \nu {\ket{\psi^{\perp}}}$$
運算子 $R_{\ket{\psi}}$ 反轉元件正交， $\ket{\psi}$ 但讓 $\ket{\psi}$ 元件保持不變。 因此， $R_{\ket{\psi}}$ 是 關於的 $\ket{\psi}$反映。
Grover 的演算法，在每個量子位的第一個應用$$之後，會以所有狀態的統一迭加開始。 這可以撰寫為：
$$\ket{\text{all}}=\sqrt{\frac{M}{N}}\ket{\text{good}} + \sqrt{\frac{N-M}{N}}\ket{\text{bad}}$$
因此，國家住在飛機上。 請注意，從相等迭加測量時取得正確結果的機率只是 $|\bra{\text{好}}\ket{\text{全部}}|^2=M/N$，這是您從隨機猜測中預期的結果。
oracle $O_f$ 會將負階段新增至搜尋問題的任何解決方案。 因此，它可以寫入為不良$\ket{\text{座標軸的}}$反映：
$$O_f = R_{\ket{\text{壞}}}= 2\ket{\text{壞}}\bra{\text{壞}} - \mathbb{我}$$
同樣地，條件式階段轉移 $O_0$ 只是狀態 $\ket{0}$的反轉反映：
$$O_{0}= R_{\ket{0}}= -2\ket{{0}\bra{{0} + \mathbb{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}\mathbb{I}H^{\otimes n}= 2\ket{\text{所有}}\bra{\text{所有}} - \mathbb{I}= R_{\ket{\text{所有}}}$$
已示範 Grover 演算法的每個反覆專案都是兩個反映 $的組成，{\ket{\text{R_bad}}}$ 和 $R_{\ket{\text{all}}}$。
每個 Grover 反覆項目的組合效果是角度 $2\theta$ 的逆時針旋轉。 幸運的是，\theta$ 的角度$很容易找到。 因為 $\theta$ 只是所有$\ket{\text{與}}$壞$\ket{\text{之間的}}$角度，因此可以使用純量產品來尋找角度。 已知 $\cos{\theta}=\braket{\text{全都}|\text{不好}}$，所以一個人需要計算 $\braket{\text{所有}|\text{壞的}}$。 從壞和好方面分解$\ket{\text{一切}}$$\ket{\text{，它遵循：}}$$\ket{\text{}}$
$$\theta = \arccos{\left（\braket{\text{all}|\text{bad}}\right）}= \arccos{\left（\sqrt{\frac{N-M}{N}}\right）}$$
緩存器狀態與 $\ket{\text{良好}}$ 狀態之間的角度會隨著每個反覆項目而減少，因而產生較高的測量有效結果機率。 若要計算此機率，您只需要計算$|\braket{\text{良好的快取器}|\text{^2}}|$。 $\ket{\text{良好}}$ 與 $\ket{\text{寄存器}}$ 之間的角度表示為 $\gamma (k)$，其中 $k$ 是迭代計數：
$$\gamma = \frac{\pi}{2}-\theta -2k\theta =\frac{\pi}{{2} -（2k + 1） \theta $$
因此，成功的機率是：
$$P（\text{success}） = \cos^2（\gammak）） = \sin^2\left[（2k +1）\arccos \left（\sqrt{\frac{N-M}{N}}\right）]\right$$
最佳反覆項目數目
由於成功機率可以寫入為反覆項目數目的函式，因此可以藉由計算最小正整數來找出最佳反覆運算數N_${\text{最佳反覆運算數}}$，而此整數會最大化成功機率函式。
已知 $\sin^2{x}$ 達到 x$\pi=\frac{ 的第一個最大值}{2}$，因此：
$$\frac{\pi}{{2}=（2k_{\text{最佳}} +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{+} O（x^{3/2}）的位置。$
因此，您可以挑選 $N_{\text{最佳}}=\left\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{{1}{{2}\right\rfloor$。
複雜度分析
從先前的分析中，$需要 Oracle \leftO_f\sqrt{\frac{的 O}{（}}\rightN$M$）$ 查詢，才能尋找有效的專案。 不過，演算法是否可以在時間複雜度方面有效率地實作？ $ $O_0是以 n$ 位計算$布爾運算為基礎，已知可使用 O（n）$ 閘道實作$。 還有兩層 $n$ 哈達馬德門。 因此，這兩個元件只需要 $每個反覆專案的 O（n）$ 網關。 因為 $N=2^n$，所以遵循 $O（n）=O（log（N））。$ 因此，如果需要$每次反覆運算的 O（N\leftM\sqrt{\frac{）}{ 反覆運算和 }}\rightO$（$log（N）閘道$，則總時間複雜度（而不考慮 Oracle 實作）是 $O\left（N M\sqrt{\frac{記錄（}{N}}）\right$。
演演算法的整體複雜度最終取決於 oracle $O_f$ 實作的複雜性。 如果量子計算機上的函式評估比傳統計算機複雜得多，則整體演算法運行時間在量子案例中會更長，即使從技術上而言，它仍會使用較少的查詢。
參考資料
如果您想要繼續瞭解 Grover 的演算法，您可以檢查下列任何來源：
- 洛夫·格羅弗的原創論文
- 尼爾森的量子搜尋演算法區段，M. A. &放大器;莊， I. L. （2010 年） 。 量子計算和量子資訊。
- Grover 在 Arxiv.org 上的演算法