光子盒研究院出品

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

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

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

什么是Grover量子搜索算法？

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

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

具體算法如下：

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

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

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

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

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

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

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

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

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

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

驗(yàn)證與迭代

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

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

2009年，Yu Dong Zhang等人針對(duì)Grover算法成功概率隨解數(shù)的增加而降低的問(wèn)題，提出了基于擴(kuò)大搜索空間的改進(jìn)算法。2010年，葉峰在對(duì)AES算法的密鑰搜索算法進(jìn)行了量子線路設(shè)計(jì)，成功使用量子搜索算法攻擊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ǔ)上，提出了一種動(dòng)態(tài)的量子搜索算法，算法通過(guò)將原始的靜態(tài)選擇函數(shù)替換為動(dòng)態(tài)選擇函數(shù)來(lái)處理非結(jié)構(gòu)化數(shù)據(jù)庫(kù)，使Grover算法的應(yīng)用擴(kuò)展到隨機(jī)搜索算法領(lǐng)域。

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

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

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

不足與缺陷

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

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

另外，Grover自己在做相位推廣時(shí)犯了錯(cuò)誤，即允許兩個(gè)相位取反為任意相位轉(zhuǎn)動(dòng)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

主要應(yīng)用

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

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

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

密碼破譯

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

安全通信

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

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

優(yōu)化問(wèn)題

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

這一領(lǐng)域的應(yīng)用潛力極大，因?yàn)榕c物流、投資組合管理、原料計(jì)劃和電信網(wǎng)絡(luò)管理等非常廣泛的業(yè)務(wù)問(wèn)題緊密相關(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算法雖然沒(méi)有使算法的時(shí)間復(fù)雜度從指數(shù)級(jí)降低為多項(xiàng)式級(jí)，但其加速效果仍然相當(dāng)可觀，并且由于搜索問(wèn)題在日常生活中的廣泛應(yīng)用，Grover算法的前景值得期待。

－End－

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