光子盒研究院出品

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

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

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

什么是Grover量子搜索算法？

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

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

具體算法如下：

（1）初始化,。應(yīng)用Oracle算子 ,，檢驗搜索元素是否是求解的實(shí)際問題中需要搜索的解,。

（2）進(jìn)行Grover迭代。將結(jié)果進(jìn)行Hadamard門變換,。

（3）結(jié)果進(jìn)行運(yùn)算,。

（4）結(jié)果進(jìn)行Hadamard門變換。

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

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

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

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

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

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

驗證與迭代

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

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

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

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

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

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

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

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

不足與缺陷

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

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

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

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

1．針對Grover算法的缺點(diǎn),，提出解決這個缺點(diǎn)的改進(jìn)算法：

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

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

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

后來,，清華大學(xué)龍桂魯團(tuán)隊通過大量的推理論證，最終得到了與Grover推斷完全相反的結(jié)果,。

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

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

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

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

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

3．將Grover算法應(yīng)用到其他領(lǐng)域,，去解決類似的問題：

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

近年來,，研究人員將Grover算法廣泛應(yīng)用于機(jī)器學(xué)習(xí)領(lǐng)域中,，提出了很多相關(guān)的量子機(jī)器學(xué)習(xí)算法。

主要應(yīng)用

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

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

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

密碼破譯

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

安全通信

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

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

優(yōu)化問題

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

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

機(jī)器學(xué)習(xí)

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

其中，很多量子機(jī)器學(xué)習(xí)算法以Grover算法為基礎(chǔ)提高了經(jīng)典算法的速率,，并且在其他領(lǐng)域有著非常廣泛的應(yīng)用,。

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

－End－

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