光子盒研究院出品

在上個月，歐洲核子研究組織（CERN）報道了一篇關于量子搜索算法在造價30億歐元的大型強子對撞機（LHC）高能物理數(shù)據(jù)中的應用。

科學家們展示了Grover量子搜索算法的一種新應用，在CERN大型強子對撞機13 TeV開放數(shù)據(jù)下，搜索質子－質子碰撞中的罕見情況。最終，在搜索碰撞數(shù)據(jù)集過程中發(fā)現(xiàn)了四個輕子，這證明了Grover算法可以在未排序的數(shù)據(jù)集中可以進行正確的選擇。

這一案例展示了量子計算在高能物理中的廣闊前景。

什么是Grover量子搜索算法？

繼Peter Shor于1994年提出Shor算法后，Lov Kumar Grover于1996年提出Grover算法，這一算法被認為是量子計算中的第二個主要算法（第一個是Shor算法）。

由于Grover算法沒有使用具體問題的特殊結構信息，因此它是一種通用的算法，提供了一個普適的框架。

具體算法如下：

（1）初始化。應用Oracle算子 ，檢驗搜索元素是否是求解的實際問題中需要搜索的解。

（2）進行Grover迭代。將結果進行Hadamard門變換。

（3）結果進行運算。

（4）結果進行Hadamard門變換。

Grover量子搜索算法能夠實現(xiàn)在未整理數(shù)據(jù)庫中對滿足條件的目標成功搜索，并對計算復雜度為NP的問題有重要加速作用，實現(xiàn)了數(shù)據(jù)檢索的二次加速。

搜索數(shù)據(jù)庫是計算機科學中的一項基本任務，它涉及從查找電話號碼到破解密碼的所有工作。因此，任何提速都是一項重大進步。

1999年，Zalka等人更是證明了Grover算法為最優(yōu)量子搜索算法。

涉及到搜索問題，其主要任務是從一個巨大的無序數(shù)據(jù)庫當中能高效的找到滿足特定要求的元素或由某些特定元素構成的元素子集。我們知道，驗證一個給定的元素或子集是否滿足特定要求是相對容易的，但是從一個巨大的無序數(shù)據(jù)庫當中找到這些滿足特定要求的元素或子集就不是那么容易了，特別是隨著數(shù)據(jù)庫的增大，搜索任務會更加艱巨。

在經典算法中，要從一個無序數(shù)據(jù)庫中找出滿足特定要求的元素或子集，一般是對所有元素進行逐個順序檢查，把滿足特定要求的元素或子集篩選出來，比如一個元素容量為N的數(shù)據(jù)庫，由于經典搜索算法執(zhí)行步驟n與數(shù)據(jù)庫中元素數(shù)目N一般成線性正比例關系，所以要找到滿足特定要求的元素，平均地需要對這個數(shù)據(jù)庫進行N／2次查詢，最壞的情況下，需要對這個數(shù)據(jù)庫進行N次查詢。這樣會導致算法搜索效率不高，而且浪費計算資源。

直到Grover提出了基于量子計算并行性原理的量子搜索算法。該算法只需要對這個無序數(shù)據(jù)庫進行次查詢，就能以接近于100％的概率把滿足特定要求的元素或子集找出來。由此可見，與經典算法相比，Grover量子搜索算法的效率是非常高的，而且隨著N越大，Grover算法的優(yōu)越性體現(xiàn)的越明顯。

驗證與迭代

1998年，Cuang I． L． 等人利用核磁共振（NMR）技術完成了兩個量子比特的Grover算法的演示性實驗。當N＝4時（兩個量子比特）時，在經典搜索中，平均要嘗試9／4次才能成功，而NMR實驗表明，量子搜索僅一次就可找到目標。

2000年，Brassard G等人利用振幅放大加速搜索過程；2006年，Phaneendr H．D等人提出了利用Grover算法攻擊三重DES算法；2007年，Younes A提出了固定相位Grover算法，將成功概率提升到98％以上。

2009年，Yu Dong Zhang等人針對Grover算法成功概率隨解數(shù)的增加而降低的問題，提出了基于擴大搜索空間的改進算法。2010年，葉峰在對AES算法的密鑰搜索算法進行了量子線路設計，成功使用量子搜索算法攻擊AES算法。

2013年，研究者將Grover算擴展到機器學習領域，如Aimeur E等人提出了快速尋找聚類算法中最大距離點的方法，該方法核心是利用Durr C等人提出的Grover變體算法，快速尋找到數(shù)據(jù)集中距離最遠的兩點。

2017年，Chakrabarty I等人在Grover算法的基礎上，提出了一種動態(tài)的量子搜索算法，算法通過將原始的靜態(tài)選擇函數(shù)替換為動態(tài)選擇函數(shù)來處理非結構化數(shù)據(jù)庫，使Grover算法的應用擴展到隨機搜索算法領域。

除了在量子計算機上可以驗證Grover算法，如今量子仿真作為量子算法研究最有力的手段和工具，也成為實現(xiàn)Grover算法的途徑之一。

2013年，呂相文等人利用GPU開展的量子仿真實驗，提出了兩種關于Grover算法特征的仿真工作流程方案，實現(xiàn)了存儲空間和存儲器訪問的優(yōu)化，仿真了最高25量子比特的Grover量子搜索算法，仿真加速比達到了23倍。

隨著IBM、英特爾、微軟、谷歌、阿里巴巴、百度、華為等國內外科技巨頭相繼發(fā)布量子計算云平臺，實現(xiàn)Grover算法的平臺和途徑也在逐漸增多。

不足與缺陷

Grover算法在應用中也有它的局限性，盡管極具應用潛力，但是由于涉及重大的技術挑戰(zhàn)，實施Grover算法仍然需要時間。第一臺能夠實現(xiàn)它的量子計算機于1998年問世，但第一臺可擴展版本直到2017年才出現(xiàn)。

Grover量子搜索算法是一個近似算法，它的成功概率并不是100％。當搜索目標大于數(shù)據(jù)庫記錄數(shù)的1／4時，搜索成功的概率快速降低；當搜索的目標大于數(shù)據(jù)庫記錄數(shù)的一半時，搜索徹底失效。

另外，Grover自己在做相位推廣時犯了錯誤，即允許兩個相位取反為任意相位轉動。

雖然學者們對其己經做了很多的研究并取得了大量成果，但仍不能滿足時代的需求?，F(xiàn)階段主要從以下幾個方面對Grover算法進行了研究：

1．針對Grover算法的缺點，提出解決這個缺點的改進算法：

就在Grover發(fā)表他的研究成果幾年后，班加羅爾印度科學研究所的Apoorva Patel解釋了：當有四個選擇時，使用Grover算法可以在一步中區(qū)分四個選擇，也就是在四個選擇里搜索一個的準確率是100％。

而在其他搜索過程中，如在結構化搜索中，總的成功率是每個成分的搜索成功率的乘積，這成功率相乘下來后，失敗概率就非常大了。

而Grover自己在做相位推廣時做了誤判，他認為將兩個相位取反換成任意相角轉動皆可構造量子搜索算法，但采用其他角度時效率較低，最好選擇180度。

后來，清華大學龍桂魯團隊通過大量的推理論證，最終得到了與Grover推斷完全相反的結果。

1999年，龍桂魯?shù)热酥赋鲈贕rover量子搜索算法中使用任意的相位旋轉時，若想以較高的概率得到想要搜索的目標項，則兩次旋轉相位的取值必須滿足一定的匹配條件：目標項的旋轉相位與非目標項的旋轉相位須彼此相等。

2004年，龍桂魯?shù)热穗S后提出滿足相位匹配條件的零失誤率的Grover算法，該算法通過將反轉相位轉化為與數(shù)據(jù)庫大小相關的角度，來提高算法的成功率。

2．基于Grover算法，利用新的量子工具，設計新型的量子搜索算法：

Korepin等人提出了用于部分搜索的量子算法，這個算法降低了算法的迭代次數(shù)。

周日貴等人提出了多模式高概率的量子搜索算法，該算法能以高概率解決量子神經網(wǎng)絡中的多模式問題。

3．將Grover算法應用到其他領域，去解決類似的問題：

學者們針對不同的問題提出了很多優(yōu)化，如最小值問題、排序問題、最短路徑問題和圖像檢索等問題。

近年來，研究人員將Grover算法廣泛應用于機器學習領域中，提出了很多相關的量子機器學習算法。

主要應用

Grover算法的實現(xiàn)相對量子傅里葉變換來說要簡單得多，而且它對于無序數(shù)據(jù)集的搜索問題，如果忽略常系數(shù)，則屬于最優(yōu)的算法之一。

更重要的是量子系統(tǒng)要與外界環(huán)境耦合，極不穩(wěn)定，消相干是指數(shù)級的，因此量子力學計算機對外界擾動是極其敏感的。這樣一來，在存在大量噪音的環(huán)境中要想使系統(tǒng)正常工作，就更需要考慮算法的魯棒性。

Grover指出，對某些擾動，他的量子搜索算法可以具有一定的魯棒性。由于實現(xiàn)簡單、具有魯棒性，Grover算法現(xiàn)已廣泛應用于各種問題。

密碼破譯

Grover算法不僅可應用于求解圖的著色、子集和最短路徑和排序等問題，還可應用于破譯密碼學中的DES（數(shù)據(jù)加密標準）密碼體系，在搜索密碼系統(tǒng)的密鑰方面有很大的潛能。

安全通信

2010年，Wang，C等人提出了一個基于Grover量子搜索算法的量子直接通信方案。該方案采用雙量子比特作為初態(tài)，秘密信息通過雙量子比特酉運算進行編碼和譯碼，并且兩個通信方Alice和Bob可以直接進行信息交換。

2012年，Tseng，H．Y等人提出了基于Grover量子搜索算法的受控量子確定性安全通信協(xié)議（CDSQC），該協(xié)議具有信息傳輸效率高和量子存儲器少等優(yōu)點，而且在噪聲環(huán)境下該協(xié)議也能有效抵制來自外部的竊聽者。

優(yōu)化問題

優(yōu)化問題是一個非常普遍的領域，量子算法有望顯著提高計算速度，雖然Grover算法只是得到平方增長，但是它和其推廣還可用于提升優(yōu)化問題的性能，包括模式匹配、全局優(yōu)化、三元可滿足性和最小值等問題。

這一領域的應用潛力極大，因為與物流、投資組合管理、原料計劃和電信網(wǎng)絡管理等非常廣泛的業(yè)務問題緊密相關。

機器學習

現(xiàn)階段Grover算法多應用于機器學習領域，衍生出非常多的新型的量子算法，例如量子分裂聚類算法、量子聯(lián)想記憶、量子神經網(wǎng)絡和量子K均值聚類等。

其中，很多量子機器學習算法以Grover算法為基礎提高了經典算法的速率，并且在其他領域有著非常廣泛的應用。

值得注意的是，Grover算法雖然沒有使算法的時間復雜度從指數(shù)級降低為多項式級，但其加速效果仍然相當可觀，并且由于搜索問題在日常生活中的廣泛應用，Grover算法的前景值得期待。

－End－

1930年秋，第六屆索爾維會議在布魯塞爾召開。早有準備的愛因斯坦在會上向玻爾提出了他的著名的思想實驗——“光子盒”，公眾號名稱正源于此。