Grover Algorithm

• 一 . 背景介紹
• 二 . 算法推導(dǎo)與實現(xiàn)
• • 1. 構(gòu)造疊加態(tài)
  • 2. 構(gòu)造 $Oracle$
  • 3. 構(gòu)造 $G$ 算子
  • 4. $G$ 的應(yīng)用
  • 5. 臨界條件

一 . 背景介紹

遍歷搜尋問題的任務(wù)是從一個海量元素的無序集合中，找到滿足某種要求的元素。要驗證給定元素是否滿足要求很容易，但反過來查找這些合乎要求的元素則很費事，因為這些元素并沒有按要求進行有序的排列，并且數(shù)量又很大。在經(jīng)典算法中，只能按逐個元素試下去，這也正是“遍歷搜尋”這一名稱的由來!

量子計算機比傳統(tǒng)計算機具有的眾多優(yōu)勢之一是其優(yōu)越的速度搜索數(shù)據(jù)庫。Grover的算法證明了這種能力。該算法可以二次加速非結(jié)構(gòu)化搜索問題，但其用途遠(yuǎn)不止于此。它可以用作一般技巧或子例程，以獲得各種其他算法的二次運行時間改進。這稱為幅度放大技巧！

什么是非結(jié)構(gòu)化搜索？

在上述大量排成一行的數(shù)據(jù)中，我們希望找到類似于圖中紫色框代表的數(shù)據(jù)，當(dāng)然，也有可能不止一個，要使用經(jīng)典計算找到紫色框（標(biāo)記項），則平均要檢查$\frac{N}{2}$這些框，最壞的情況是檢查所有 $N?1$ 個元素。 但是，在量子計算機上，我們可以使用Grover的幅度放大技巧以大約$\sqrt{N}$的步長找到標(biāo)記的項目。 二次加速確實是節(jié)省長列表中標(biāo)記項目的大量時間。 另外，該算法不使用列表的內(nèi)部結(jié)構(gòu)，這使其具有通用性。 這就是為什么它立即為許多經(jīng)典問題提供了二次量子加速的原因！

二 . 算法推導(dǎo)與實現(xiàn)

1. 構(gòu)造疊加態(tài)

假設(shè)被查找的集合為：$\{|i?\}=\{|0?,|1?,?|N?1?\}$，在開始查找之前，要對系統(tǒng)進行初始化，即對每一個$qubit$ 初態(tài)進行$Hadamard$ 變換，使之處于$$|{\phi }_0?=\frac{1}{\sqrt{N}}\sum _{i=0}^{N?1}|i?$$
牢記這個式子，后面都需要用上它！

這里我們可以通過一個小例子來理解：假設(shè)有一個映射$0,1,2,\dots ,N?\{0,1\}$，意思就是該映射函數(shù)為：$f(x)?\{0,1\}$：
$$\begin{array}{l}f(1)=0\\ f(2)=1\\ f(3)=0\\ f(4)=1\end{array}$$現(xiàn)在我們需要做的就是找到$f(x)=1$ 的解，當(dāng)然，我們這里是理想化模型，數(shù)據(jù)搞得少一點也是為了通俗易懂，那么顯然，當(dāng)$x=2，4$的時候，是我們需要的解，回過頭來，第一步就是創(chuàng)建疊加態(tài)，根據(jù)這個例子，創(chuàng)建好的疊加態(tài)如下：
$$|\psi ?=\frac{1}{2}(|00?+|01?+|10?+|11?)$$
這里因為輸入的數(shù)據(jù)數(shù)量相對來說是比較多的，我們用多體量子態(tài)來表示，位數(shù)也自然和我們整個輸入的數(shù)據(jù)多少直接相關(guān)了！

接下來的一步非常重要，是該算法的第一個關(guān)鍵點所在！

2. 構(gòu)造 $Oracle$

為了將我們需要尋找的數(shù)據(jù)和其他的數(shù)據(jù)分開，此時需要一個$Oracle$，，那么分開的標(biāo)識是什么呢？其實最簡單的方法就是將目標(biāo)值變換相位，也就是增加一個負(fù)號，即：
$$O_{\omega }|x?=\{\begin{array}{rl}|x?& \text{?if?}x=\omega \\ ?|x?& \text{?if?}x=\omega \end{array}$$

非常的簡單，當(dāng)遍歷不是我們需要的值就不動，反之當(dāng)找到$x=\omega$時變號，這個就有點難，因為不僅需要我們構(gòu)造類似于一個單位陣一樣的算符，且能在指定位置變號！$In$ $fact$,$i{t}^{\prime }s$ $very$ $simple$:
$$\hat{O}=1?2|x??x|$$
也闊以寫成矩陣的形式，如果是雙量子比特的話，$Like$ $this:$

顯然，這里我們需要找的是 $|10?$，我們發(fā)現(xiàn)構(gòu)成該矩陣的行和列都是對應(yīng)的向量，那么，如果是三量子比特的話，$O$算符又是啥樣的呢？

感興趣的小可耐們可以自己動手操作一下！

到這一步，我們似乎能簡單的理解了 $Grover$ 搜索算法的強大之處在于它將問題簡單化了，也就是根據(jù)量子固有的特性將我們需要查找的值與其余值分開了，從另一個角度來說，我們都知道往往去尋找解決問題的答案是非常困難的，而驗證解決方案的正確與否相對來說會簡單很多，這便是$Grover$算法的思想精髓！

好，上述我們已經(jīng)成功的得到了置關(guān)重要的$Oracle$，進一步，可以得到：

$$O_{\omega }|x?=(?1{)}^{f(x)}|x?$$
道理是一樣的，即$f(x)=1$時變號，等于0時不變，同樣的矩陣表示為：
$$O_{\omega }=?\begin{array}{cccc}(?1{)}^{f(0)}& 0& ?& 0\\ 0& (?1{)}^{f(1)}& ?& 0\\ ?& 0& ?& ?\\ 0& 0& ?& (?1{)}^{f\left(2^n\right)}\end{array}?$$

3. 構(gòu)造 $G$ 算子

其實算法的主要過程只有兩個步驟，第一步剛剛已經(jīng)順利實現(xiàn)，而接下來的第二步才是靈魂！

我們接下里需要構(gòu)建$G$算子：

$$G=(2|\psi ??\psi |?I)O$$

其中，$O$就是上面說的$Oracle$算符，$I$為單位算符，現(xiàn)把算符$G$反復(fù)作用在 $|{\phi }_0?$上，并稱一次作用為一次“迭代”，根據(jù)情況的不同，通過多次次數(shù)不同的“迭代”，最終就能找到我們需要的 $\omega$了，具體的操作又是怎樣的呢？

在前面的學(xué)習(xí)和操作中，相信大家都明白了我們主要目的之一就是 根據(jù)我們尋找的目標(biāo)，將整個量子態(tài)代表的數(shù)據(jù)中 需要的 和不需要的分開，所以可以將原來的疊加態(tài)寫成這樣：
$$|{\phi }_0?=\frac{1}{\sqrt{N}}|x?+\frac{1}{\sqrt{N}}\sum _{\genfrac{}{}{0ex}{}{i=0}{(i=x)}}^{N?1}|i?\equiv |\beta ?+|\alpha ?$$

稍微變形一下可以得到：$$\begin{array}{c}|\beta ?=\frac{1}{\sqrt{M}}{\sum }_x|x?\\ |\alpha ?=\frac{1}{\sqrt{N?M}}{\sum }_x|x?\end{array}$$

其中，我們應(yīng)當(dāng)知道$N=2^n$，最終的得到：$|\psi ?=\sqrt{\frac{N?M}{N}}|\alpha ?+\sqrt{\frac{M}{N}}|\beta ?$

可以結(jié)合我們博客開頭舉得小例子強化理解：

$$\begin{array}{l}|00?\to 0\\ |01?\to 1\\ |10?\to 0\\ |11?\to 1\\ |\alpha ?=\frac{1}{\sqrt{2}}(|00?+|10?)\\ |\beta ?=\frac{1}{\sqrt{2}}(|01?+|11?)\end{array}$$

4. $G$ 的應(yīng)用

先將$O$算符作用在初始量子疊加態(tài)上以實現(xiàn)我們分開的目的，系數(shù)分別用$a，b$來表示：
$$O(a|\alpha ?+b|\beta ?)=a|\alpha ??b|\beta ?$$
我們通常狀況下可以假設(shè)：$a=\cos (\theta /2)=\sqrt{(N?M)/N},b=\sin (\theta /2)=\sqrt{M/N}$

問題來了，我們這要做的目的到底是什么？為啥要單獨將原始疊加態(tài)分開呢，仔細(xì)觀察不難發(fā)現(xiàn)，在未使用 $O$ 算符之前，我們可以將$|\psi ?$ 看成一個二維矢量，而分開得到的$|\alpha ?,|\beta ?$是組成它的二個基矢！看圖說話:

我們從圖中可以非常清晰的看到，$O$ 算子作用到$|\psi ?$ 上變相之后關(guān)于$|\alpha ?$ 對稱之后得到$O|\psi ?$，再關(guān)于原來的$|\psi ?$對稱得到$G|\psi ?$，這兩步相當(dāng)于我們用準(zhǔn)備好的$G$算子進行一次迭代作用，得到的新矢量為：
$$G|\psi ?=\cos \left(\frac{3\theta }{2}\right)|\alpha ?+\sin \left(\frac{3\theta }{2}\right)|\beta ?$$

這是第一次的迭代結(jié)果，當(dāng)次數(shù)增多時，數(shù)學(xué)表達(dá)為：

$$G^k|\psi ?=\cos \left(\frac{2k+1}{2}\theta \right)|\alpha ?+\sin \left(\frac{2k+1}{2}\theta \right)|\beta ?$$

這樣多次迭代的目的也是顯而易見的，就是讓我們的 $|\psi ?$ 能夠不斷的向 $|\beta ?$ 靠近，最終就能得到我們想要的$|\beta ?$ 了。

我們還可以從振幅的角度來理解這個算法的核心，并且搭配二維坐標(biāo)系的翻轉(zhuǎn)過程，配合食用，效果更佳哦（這里的$U$就是$O$算符）：

其中虛線代表振幅的平均值，使用$O$ 算符作用之后，我們得到的結(jié)果為：

相位變換以后，顯然，振幅的平均值下降了一些，接下來：

上一步我們根據(jù)各個基態(tài)的振幅值計算出平均值之后，根據(jù)均值的鏡像翻轉(zhuǎn)各個基態(tài)的振幅值就會得到上面的圖片！

5. 臨界條件

我們完全有理由認(rèn)為如果迭代次數(shù)過多，會導(dǎo)致 $|\psi ?$ 翻轉(zhuǎn)到 $|\beta ?$ 的右邊，增加誤差，除此之外，我們還應(yīng)當(dāng)想到的就是這個翻轉(zhuǎn)角度 $\theta$ ，過大的話也會導(dǎo)致誤差過大。

現(xiàn)在回過頭來看這個式子：$|\psi ?=\sqrt{\frac{N?M}{N}}|\alpha ?+\sqrt{\frac{M}{N}}|\beta ?$，其中 $N$ 是我們早已確定的，不能更改， 關(guān)鍵就在于這個 $M$，先假設(shè)我們已經(jīng)知道有 $M$ 個 $i$ 使得 $f(i)=1$，根據(jù)$a=\cos (\theta /2)=\sqrt{(N?M)/N},b=\sin (\theta /2)=\sqrt{M/N}$，就能直接得到$\theta$ 的大小！

我們可以根據(jù)，$M,N，\theta$ 的值算出需要迭代的次數(shù)：
$$\sin (\theta )=\frac{2\sqrt{M(N?M)}}{N}\to R=CI\left(\frac{\arccos (\sqrt{M/N})}{\theta }\right)$$

其中 $R$ 就是我們需要迭代的次數(shù)，例如：$CI(4.5)=4$。

除此之外，隱藏條件$\theta <\frac{\pi }{2}$ 也是需要知道的，而且當(dāng) $\theta$ 越小時，我們得到的搜索結(jié)果越準(zhǔn)確！

如果當(dāng)我們需要搜所的值個數(shù)$M$ 非常少的話，即$M?N\to \theta \approx \sin (\theta )\approx 2\sqrt{M/N}$ ，那么測量的誤差角度最大為 $\theta /2\approx \sqrt{M/N}$ !

再結(jié)合$\theta <\frac{\pi }{2}$ 可得：
$$R??\frac{\pi }{4}\sqrt{\frac{N}{M}}?$$
注意，這里是上天花板函數(shù)符號，舍棄小數(shù)點后的數(shù)字！

最后我們用一張圖簡單的總結(jié)一下量子 $Grover$ 算法的整個流程：

總結(jié)

以上是生活随笔為你收集整理的量子搜索算法(Grover Algorithm)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。