如今的許多高科技都依賴于各種大資料，是以，資料庫的搜尋速度至關重要。量子計算機搜尋資料庫的速度更快，是其相對經典計算機的衆多優勢之一，本篇将介紹的Grover量子搜尋算法便展示了這種能力。
01
搜尋問題（經典和量子）
警察追蹤一個男性罪犯，最後罪犯進了一個小區，逃回了家。這個小區有400個單元，每個單元住一對夫婦，是以共有400個男人。警方有逃犯的照片，在警方資料庫中也有這400個人的照片。那麼，如何從這400個嫌疑人中找出這個罪犯呢？這是一個搜尋問題，假設資料庫中的400張男性照片是完全無序的，那麼，這是一個非結構化搜尋問題。
Grover量子搜尋算法也是用來解決這一類的搜尋問題。下面是更為一般的描述：
假設給你一個很大的N個項目清單，其中有一項是我們希望找到具有獨特屬性的。我們把這一項稱為“獲勝者”，用w表示。或者用剛才那個最簡單的比喻，假設我們是要在許多嫌疑人中搜尋一個逃犯，w表示的就是逃犯。
考慮最簡單的情況：N個嫌疑人x中隻有一個罪犯w，如圖1a所示。首先将清單中的每個候選者标以特定顔色，逃犯w為紅色，所有其他人x都标以灰色。我們可以規定某種方法判定逃犯，例如可以采取比較照片的方法等。
或者可以考慮一個與“計算”有關的方法：假設我們知道罪犯的身份證号碼w，可将它與所有嫌疑人的号碼x比較，即做減法計算（x-w）。計算的結果可以用一個二進制目标檢驗函數f(x)表示：如果x不等于w，f(x)=0；如果x是逃犯，即x= w，f(x)=1。
▲圖1：搜尋問題和檢驗函數f(x)
因為嫌疑人的資料x是無序的，如果使用經典的方法，要找到逃犯的号碼w，隻能一個一個地做減法。最壞情況需檢查所有N個嫌疑人，最好情況也得檢查1個，平均而言必須做N/2次減法。是以，經典搜尋的運算次數與N的關系是線性的：O(N)。
那麼現在考慮，如果是量子搜尋，是否可以降低搜尋運算的複雜度呢？
量子搜尋的優越性是在于利用量子比特的疊加性，如圖1b所示，量子計算中的“資料庫”，是由量子比特可能處于的所有計算基組成的。例如如果我們有3個量子比特，計算基清單就是：|000>, |001>,……|111>，即從0到7八個值。而量子搜尋與經典搜尋不同之處是：量子計算可以操作這8個寄存器同時工作，如同是8個寄存器同時進行平行運算。寄存器越多，就越能展現這種平行運算“加速”的威力。
與經典計算不同的另外一點是：量子實體是機率性的，表征量子态的數值是一串機率幅。例如，一開始我們并不知道要找的逃犯w在哪裡，所有的嫌疑人都有可能是罪犯。也就是說，8個寄存器給出的初始量子态是機率均等的，每個寄存器是w（逃犯）的機率輻是一樣的。
我們再用剛才那個找逃犯的過程來比喻說明一下經典搜尋和量子搜尋的差別。
經典情況，假設資料庫中的照片一次隻能拿出一張，是以沒有什麼更好的辦法，隻能用逃犯的照片與其一張一張地比對。最好的情況做1次，最壞情況做400次，平均200次。
量子情況，就好比是有了一個所有照片都能放在一起的魔法大平台，這樣就能将逃犯的照片同時比較資料庫裡所有的。不過，你也不要高興太早了！大平台容易塌，不能随便打開，并且，雖然400張照片都在，但每張照片都有不同的亮度，每張照片以不同的機率被照亮，這個機率會根據逃犯資訊的暴露程度而改變，比如說，一開始時，完全不知逃犯在哪裡，是以，機率（亮度）均分在400張照片上，如果這時候打開看，全都看不清楚。
科學家們總有他們獨特的辦法。Grover就找到一種方法，在打開這個大平台之前，他對平台上所有的照片，反複地進行某些“運算”或“比對”操作，使得照片被照亮的機率輻變化，變化的趨勢是使得越來越多的機率輻集中到資料庫中對應逃犯照片的那個位置上。這樣一來，最後打開平台時，就幾乎隻有那一個位置的照片被照亮。于是，就抓住逃犯了！
重要的是，Grover這個辦法，對400張照片的情況，隻需要20（400的平方根）次的比對操作，就搜尋到了目标，而不是經典搜尋的平均200次。這就表現出了量子算法的優越性。
02
Grover尋找量子算法
洛夫·格羅弗（Lov Grover，1961年—）是一名印度裔美國計算機科學家。他因為于1996年發明的量子算法赢得了聲譽，格羅弗算法是繼1994年的秀爾算法之後，為量子計算提出的第二個主要算法，2017年才終于在可擴充的實體量子系統中實作。
格羅弗于1981年獲得印度理工學院德裡分校的學士學位，并于1985年獲得斯坦福大學電氣工程博士學位。1984年，他進入貝爾實驗室。1987年至1994年，他擔任康奈爾大學的客座教授。他于2008年退休，成為一名獨立研究員。
2001年，Lov Grover 寫了一篇論文，介紹他如何提出了量子搜尋算法。
格羅弗的靈感，來源于實體和數學兩方面。從實體角度：無論是經典系統還是量子系統，最後都“移動”到勢能最低的點，這是一個普适的實體規律。就像經典小球滾入勢能較低的區域一樣，在薛定谔方程下演化的均勻量子疊加态也将被引向勢能較低的區域。見圖2。
▲圖2：格羅弗量子搜尋算法
格羅弗研究了薛定谔方程無限短時間内的演化問題，還考慮了有限點集上的量子态。他試圖找到一種量子算法，來有效地實作在搜尋問題中量子态的演化過程。比如，圖2中所示的“機率均分”态，對應的“勢能”比較高，而要搜尋的、标記了目标的量子态，對應的“勢能”較低。是以，搜尋問題就是要找出一種幺正算子的交替疊代變換方法，實施與薛定谔方程演化類似的過程，使得勢能高的量子态，逐漸演化到“勢能”更低的量子态。最後得到勢能最低的量子态，也就是目标位置具有最大機率輻的狀态。這樣就完成了搜尋任務。
我們經常強調量子計算中是“機率輻”而不是“機率”本身，雖然是一字之差，但這卻是量子計算與經典計算的一個重要差別。機率是機率輻的平方。經典實體中，疊加的是機率；而量子實體中的疊加态，是機率幅的疊加。正是基于這個特點，才能使得Grover算法搜尋的複雜度從O(N)降低到O(sqrt(N))。
量子計算還有一個不可忽略的特性，就是在運算過程中，不友善對量子态進行測量，測量将引起波函數塌縮而破壞量子态。是以，一般隻在最後進行測量。
總結Grover算法的中心思想是：利用量子疊加态的平行運算功能，經過數次反複疊代後，放大提高“标記”處w的機率幅而降低其它位置的機率幅，最後進行測量，波函數塌縮到機率輻最大的狀态，即w态。
可以證明，Grover算法隻要計算sqrt(N)次就可以找到w。聽起來加速不多，僅僅是平方級的加速。但實際上是我們所能期望的搜尋算法最大加速。并且當N很大時，二次加速确實可以節省大量時間。比如有100個嫌疑人，身份證号碼1到100，随機無序地分布在100個寄存器中，找出某個特别數字，經典方法平均需要50次操作，量子算法隻需10次！此外，該算法的用途不止于資料搜尋，還可以為各種其他算法獲得二次運作的時間改進。
03
Grover算法的具體步驟
▲圖3：Grover算法步驟示意圖
綜上所述，Grover算法的核心就是振幅放大：将目标w的機率幅放大，而将其它所有“非目标項”x的機率幅縮小。整個過程如圖3所示，從通過H門制備初始量子态開始，中間的疊代循環便是振幅放大，循環結束後的最後一步，是測量。
初始狀态是一個均勻量子疊加态，表示所有嫌疑人是罪犯的機率相等。均勻态|s>可以很容易地從n個H門作用于n個量子比特基态|0>上構造出來。
然後就想辦法讓機率變化，同時對N個寄存器反複進行某種操作，使得目标項w的機率幅|w>不斷放大，其他的機率幅|x>不斷縮小，這個“振幅放大”過程需要重複進行直到找到w為止。
循環的振幅放大過程分為兩步：量子黑箱函數U（預言機），和擴散算符操作U。
▲圖4：振幅放大的幾何解釋
“振幅放大”算法有很好的幾何解釋，表示為态矢量在一個二維平面中産生旋轉，如圖4所示。初始狀态是一個均勻疊加态|s>，|w>和|s>張成向量空間中的一個二維平面，兩個向量|w>和|s>并不完全垂直，因為|w>也以N的機率輻出現在疊加态|s>中。然而，我們可以引入一個額外的狀态|s‘>，它位于|w>和|s>構成的二維平面上但垂直于|w>。
初始狀态如圖4左圖所示。在|w>和|s‘>構成的平面坐标下，初始狀态|s>可以表示為：
|s> = sinT |w> + cosT |s‘>,
角T = arcsin(s在w的投影) = arcsin(1/ N)，圖4左下圖形是均勻疊加态|s>的bar圖。
疊代中的兩步：
步驟1，應用黑箱函數U将狀态|s>翻轉，見圖4的中圖：U的作用是将目标狀态|w>反相，其它狀态不變。從幾何上講，這對應于|s>态關于|s‘>軸的翻轉。這意味着狀态|s>中|w>的幅度變為負值，也意味着平均幅度（由虛線表示）的降低。
步驟2，現在關于狀态|s>應用另一個擴散算符U。此轉換将|s>映射到狀态UU|s>。兩次反射U和U對應一個旋轉，将初始狀态|s>旋轉得更接近|w>，見圖4右圖。
幅度條形圖中U的反射操作可以了解為關于平均幅度（虛線）的反射。由于第一次反射降低了平均振幅，這變換将|w>的振幅提高到其原值的數倍，同時也降低了其他振幅，故稱為振幅放大。
然後重複步驟1和步驟2，繼續振幅放大的過程直到達到要求。
圖4所示的過程的确可将振幅放大，但到此為止我們有兩個問題：一是圖中的黑箱函數U和擴散算符U具體是什麼？二是此過程要重複幾次才能找到w呢？
Grover算法的預言機Oracle函數U所做的，是給解|w>添加了一個負相位，也就是說，對于計算基中的任何狀态|x>，可以建立一個函數U：U (x) = x，如果|x>不等于|w>；而U(x) = -x，如果|x>等于|w>，如圖5a所示。該函數被稱為Oracle。
▲圖5：a）黑箱函數将w反相；b）相位黑箱函數
圖5a中，黑箱函數U可以表達為一個對角矩陣，其中對應于目标項w的值為-1，其它為1。圖5a下圖表示三個量子位的U矩陣。進一步具體而言，Oracle可以用圖5b中所示的經典檢驗函數f(x)構成的相位函數來實作。
也許有人會說，既然U可以将w那一項反相，不是已經知道了w的位置嗎？那還搜尋什麼呢？這是初學Grover算法時經常感覺困惑的問題。這兒需要再次強調量子計算的特點：可以讓多個寄存器同時運算但不能檢查每個寄存器的結果。是以，雖然我們說U能夠将w反号，但因為沒有進行測量，我們并不知道是哪個寄存器的結果反相了。反相的結果是每個寄存器根據它自己内部的資料檢驗函數f(x)而回報回來的。
說通俗點：每個嫌疑人自己知道他是不是罪犯，但我們并不知道，除非進行測量！
即使進行測量，僅僅是将|w>反号這一個操作，也不能确定w的位置。因為|w>是機率輻，而測量得到的是機率，即機率輻的平方。|w>符号的改變使機率輻反相，但并不會影響機率。Grover算法巧妙之處是在步驟3中我們又應用了一個擴散函數U = 2 |s><s|-1。其作用是将态矢量關于平均幅度進行反射，反射後w的機率幅被放大了。是以，步驟2和3的共同作用U=UU，使得測量後塌縮到|w>的機率被放大了。
那麼，現在回到第二個問題：此過程U要重複多少次才能使w的機率幅達到最大值呢？
每一步過程U，都使态矢量的位置更接近|w>的位置，假設每次改變的角度是均勻的2θ，對初始态|s>作用t次之後：|ψ>= (UU)|s>。最後需要的次數可用圖6的描述來粗略地了解。
▲圖6：Grover算法
事實也證明旋轉N^1/2次就足夠了。能從經典的N次減到N^1/2次，原因是由于處理的是機率輻而不是機率，即被放大的是機率幅而不僅是機率，這也是量子計算秘訣所在。
參考資料：
【1】Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
【2】From Schrödinger's Equation to the Quantum Search Algorithm, Lov K. Grover (Bell Labs, Murray Hill, NJ), https://arxiv.org/abs/quant-ph/0109116
來源：墨子沙龍
原标題：量子計算機能更快地找出罪犯嗎？｜量子計算群英會（十）
編輯：virens