量子游走相關(guān)算法研究進展

李萌 孫曉明,2

(1.中國科學(xué)院計算技術(shù)研究所 處理器芯片全國重點實驗室，北京 100190；2.中國科學(xué)院大學(xué)，北京 100049)

0 引言

量子計算的發(fā)展趨勢欣欣向榮，量子比特本身的存在就意味著相較于經(jīng)典計算所具有的指數(shù)增加的運算空間和相應(yīng)強大的并行性，有指數(shù)加速的潛力，未來能夠被應(yīng)用于密碼破譯、量子化學(xué)、工程計算、人工智能、材料模擬、金融經(jīng)濟等方面，甚至可以突破經(jīng)典計算的瓶頸。雖然量子計算由于量子力學(xué)所特有的量子疊加和量子糾纏使得其在某些具體問題上的解決速度和效果大大提升，但如何發(fā)揮其并行優(yōu)勢，提高普遍計算力是當下最為關(guān)鍵的挑戰(zhàn)之一。同時，真正通用的量子計算機還未建造成功，甚至一個在規(guī)模上有限制的通用物理設(shè)備仍有待設(shè)計和構(gòu)建，量子計算優(yōu)越性的充分體現(xiàn)更要依賴于量子算法的巧妙構(gòu)思。

近年來量子算法的設(shè)計需要和應(yīng)用需求不斷增長。無論是有直接加速效果的，還是可以在帶噪音中等規(guī)模量子設(shè)備(Noisy Intermediate-Scale Quantum Technology，NISQ)上運行展示優(yōu)越性的量子算法，其研究從未中斷。Shor算法在多項式時間內(nèi)解決了大數(shù)因子分解問題[1]；Grover算法對于無結(jié)構(gòu)數(shù)據(jù)庫的搜索問題相較于經(jīng)典算法可以達到平方加速的效果[2]。除了這些早期的著名量子算法，還有一類以量子游走為基礎(chǔ)的量子算法在蓬勃發(fā)展，且在實驗和應(yīng)用方面展示出了巨大的活力和潛力。

經(jīng)典的隨機游走可以用作設(shè)計隨機算法的計算框架，因此被廣泛應(yīng)用到包括計算機學(xué)科在內(nèi)的許多學(xué)科中。量子游走刻畫了微觀世界中波函數(shù)的動力學(xué)演化過程，是經(jīng)典隨機游走在量子世界的對應(yīng)和推廣，但二者卻很不一樣。比如經(jīng)典隨機游走的概率分布是高斯型，而在量子情況下它具有多個峰值，不斷震蕩，擴散速度呈現(xiàn)平方式的增長。量子疊加和量子干涉特性使得量子游走有著顯著區(qū)別于經(jīng)典隨機游走的優(yōu)勢?；诖丝梢岳昧孔佑巫唛_發(fā)高效量子算法，例如量子搜索算法、元素區(qū)分等，這些量子游走算法的性能表現(xiàn)相較于經(jīng)典算法均會有加速效果。同時，隨著研究的深入，量子游走陸續(xù)被證明是一種通用的量子計算模型。任何量子過程都可以理解為系統(tǒng)的動力學(xué)演化，進一步可以用量子游走來模擬。因此，量子游走為量子信息處理提供了一個直觀的框架，是基礎(chǔ)的量子算法設(shè)計工具之一，也是創(chuàng)新量子技術(shù)的核心之一[3-6]。

本文將首先介紹量子游走的基本概念和基本原理；然后介紹基于量子游走的幾種搜索算法的發(fā)展，以及量子游走在其他相關(guān)應(yīng)用中的關(guān)鍵進展；最后對量子游走未來的發(fā)展進行總結(jié)和展望。

1 量子游走簡介

經(jīng)典隨機游走在數(shù)學(xué)上刻畫了一系列隨機步驟演變的過程。這一隨機過程通常被描述為馬爾可夫過程，游走者的下一個位置只取決于它當前的位置，不依賴于游走者之前時刻的任何信息。像花粉的布朗運動、波動的股票價格，以及高爾頓釘板和醉漢問題均屬于經(jīng)典隨機游走。在經(jīng)典的隨機游走中，游走者本身占據(jù)一定的狀態(tài)，狀態(tài)間的隨機躍遷導(dǎo)致了隨機性的產(chǎn)生。這一概念最初由Pearson引入[7]，隨后逐漸被用作計算機科學(xué)和各類算法發(fā)展的基本框架之一，且在計算機科學(xué)中有著廣泛的應(yīng)用，比如PageRank[8]、計算機視覺[9]和復(fù)雜社交網(wǎng)絡(luò)分析[10]等。

Aharonov等人于1993年將量子物理與經(jīng)典隨機游走結(jié)合起來，首次提出量子游走模型[11]。量子狀態(tài)的疊加和確定可逆的酉演化產(chǎn)生了隨機性。與經(jīng)典隨機游走類似，量子游走可以分為離散時間量子游走和連續(xù)時間量子游走，二者在具體形式上有明顯的差異。相比于連續(xù)時間量子游走，量子硬幣為離散時間量子游走提供了額外的自由度，因此二者在性質(zhì)上也有一定的差異和聯(lián)系[12]。下面對二者做一些簡單刻畫[13]。

連續(xù)時間量子游走(Continuous Time Quantum Walk)依賴于圖的拓撲結(jié)構(gòu)。對于給定的圖G=(V,E)，其鄰接矩陣A和拉普拉斯矩陣L均是一|V|×|V|的矩陣，具體如下：

(1)

其中，deg(i)是頂點i的度。連續(xù)時間量子游走則發(fā)生于頂點對應(yīng)的標準正交基態(tài)所張成的希爾伯特空間中，對于任意給定的初態(tài)|φ(0)〉，t步演化時間后的量子態(tài)為|φ(t)〉=e-iLt|φ(0)〉。

量子游走是基于量子力學(xué)的隨機游走，其中游走者演化的初始狀態(tài)和最終狀態(tài)之間通過遍歷圖的邊，在離散時間節(jié)點或通過基于圖鄰接矩陣的哈密頓量進行連續(xù)演化。此外，還有一些其他的量子游走模型。下面對Staggered量子游走(Staggered Quantum Walk)[14]和Szegedy’s量子游走(Szegedy’s Quantum Walk)[15]做一簡單介紹。

(2)

由此定義兩個反射算子：

(3)

一步量子游走演化算子即為：

U=RYRX

(4)

鑒于經(jīng)典隨機游走在數(shù)學(xué)、物理和計算機等學(xué)科領(lǐng)域的廣泛應(yīng)用，量子游走的應(yīng)用研究也引發(fā)了極大的關(guān)注。受到量子干涉的影響，與經(jīng)典隨機游走相比，量子游走的擴散速度會明顯變快，有平方級別的加速效果。因此，下面就基于量子游走的搜索算法和其他相關(guān)應(yīng)用進行一一介紹。

2 基于量子游走的搜索算法

空間搜索問題是利用經(jīng)典隨機游走來解決的一類常見問題。在這類問題中，無向圖G中有一個由標記頂點組成的頂點子集M，游走的方式由無向圖G的邊決定?？臻g搜索問題的目標是通過沿著圖的邊對圖遍歷以期用最短的時間來找到其中一個被標記的頂點。尋找標記頂點的一個簡單策略是對圖G進行隨機游走，反復(fù)應(yīng)用一些隨機矩陣，直到達到其中一個標記頂點。相應(yīng)地，量子游走也被用來解決空間搜索問題，并相較經(jīng)典隨機游走情形有一定的加速效果。這里將對兩種關(guān)鍵框架(基于馬爾可夫鏈的和基于不同圖結(jié)構(gòu)的)下量子游走搜索算法的由來、發(fā)展和現(xiàn)狀做簡要介紹。

然而，以上方法只能在非常有限的情況下找到被標記的頂點，要么對圖結(jié)構(gòu)有限制，要么對標記點的個數(shù)或分布有要求?；诖耍珹mbainis等人通過引入每步量子游走停留在標記點的概率p，利用插值的思想，基于量子游走并結(jié)合Quantum Fast-forwarding技術(shù)，在任意圖上對于任意數(shù)量和排布方式的標記點，相比于經(jīng)典搜索算法均可以實現(xiàn)平方加速的效果[25]。

除了以上基于馬爾可夫鏈發(fā)展出的量子游走搜索算法以外，還有諸多工作是圍繞不同的圖展開的。基本的做法一般是初始化整個量子系統(tǒng)到均衡疊加態(tài)，連續(xù)作用量子游走搜索算子，對位置寄存器進行測量，檢查被測量頂點是否為標記點。主要的技術(shù)手段就是基于空間結(jié)構(gòu)和標記點的分布特點對空間中的點進行分類，以此得到量子游走搜索算子的歸約不變子空間，從而達到降維的目的、簡化計算，然后可直接進行譜分解對演化過程進行清晰刻畫，同時可以結(jié)合增加自環(huán)、調(diào)整權(quán)重等手段提高搜索算法的成功概率。這一研究工作很大地依賴于圖的對稱性，目前業(yè)界對完全二分圖[26-27]、Kroneckor圖[28]、Johnson圖[29]和強正則圖[30]等均有研究。

3 量子游走相關(guān)應(yīng)用

量子游走除了搜索，在其他方面也有諸多應(yīng)用，如元素區(qū)分、測量、通用計算模型、完美狀態(tài)傳輸和量子隱形傳輸?shù)韧ㄐ湃蝿?wù)。

3.1 元素區(qū)分

元素區(qū)分問題是指對于給定的一列元素，判斷這些元素是否均不同。即，對于給定的一個有限集X={x1,x2, … ,xn}，一個黑盒函數(shù)f:{1, 2,… ,n}→X，確定是否有兩個不同的輸入i≠j，有f(i)=f(j)，即xi=xj。

為了在經(jīng)典計算機中解決這個問題，可查詢有限集X中的所有元素，并對這些元素進行存儲和排序，再遍歷這個排序列表，來檢查是否有重復(fù)的元素，因此需要Ω(n)次查詢。

考慮這些元素兩兩組合構(gòu)成的數(shù)對空間，即{(xi,xj):1≤i

Aaronson和Shi對區(qū)分一對一函數(shù)和兩對一函數(shù)，證明了碰撞問題的Ω(n1/3)下界，由此進一步推出元素區(qū)分問題Ω(n2/3)的下界[32]。Ambainis等人主要借鑒了Grover算法和振幅放大等技巧，將該問題有效地轉(zhuǎn)化為在圖上搜索標記點的問題，利用量子游走搜索算法和在圖上的量子游走得到問題的解，提出了具有加速效果的量子算法，其復(fù)雜度為O(n2/3)[33]。該算法從圖中所有頂點的均勻疊加態(tài)開始；然后對非標記頂點執(zhí)行一個轉(zhuǎn)移規(guī)則，對標記頂點執(zhí)行另一個轉(zhuǎn)移規(guī)則；檢查當前的頂點和移動到相鄰的頂點都要花費一個時間步長；經(jīng)過O(n2/3)步量子游走后，振幅聚集在標記頂點上，此時以常數(shù)概率測量得到標記狀態(tài)。當然，這一算法也可以使用Staggered量子游走模型來實現(xiàn)[14]。

另外，該問題也可推廣至判斷在x1,x2,… ,xn中是否存在k個元素是相同的，對此基于量子游走的搜索算法的查詢復(fù)雜度是O(nk/(k+1))[33]。類似地，量子游走算法也被用于解決找三角形問題[34]等。

3.2 通用計算

近年來量子游走陸續(xù)被證明是一種通用的計算模型。對于不同的量子游走模型，為證明其通用性，均是將量子計算編碼到一個由量子線連接的圖中，再基于此設(shè)計構(gòu)成通用量子門集合的部件。由于量子計算到圖的映射是等價的，從而可以證明這些量子游走模型均是通用計算模型。

Feynman為了給量子計算機這種計算設(shè)備提供一個物理上合理的描述，構(gòu)造了一個哈密頓量來實現(xiàn)任意量子電路[35]。Childs擴展了Feynman的這一結(jié)果，首次證明了連續(xù)時間量子游走是一種通用的計算模型，即量子游走和量子電路本質(zhì)上具有同樣的能力，任意一個可以用通用量子計算機完成的任務(wù)也可以利用連續(xù)時間量子游走來完成[36]。事實上，對于一般的連續(xù)時間量子游走模型加以限制，即在稀疏圖(低度的非加權(quán)圖)上的量子游走對于量子計算均是通用的。Childs用虛擬量子線來表示計算基態(tài)，并通過散射理論討論連接在導(dǎo)線上的小部件實現(xiàn)了3個量子門，即受控非門、π/8門和交換兩個計算基的量子門。π/8門和交換兩個計算基的量子門連續(xù)作用可以生成阿達瑪門，而受控非門，阿達瑪門和π/8門構(gòu)成了一組通用量子門集合，故稀疏圖上的連續(xù)時間量子游走可以有效地模擬任何量子電路，從而是一種通用的計算模型。

但是，用于對n個量子比特進行計算的圖的規(guī)模關(guān)于n是指數(shù)級別的，而圖中的各個頂點占據(jù)不同的空間位置，故量子游走不能有效地實現(xiàn)。鑒于此，Childs等人考慮了以上連續(xù)時間量子游走模型的推廣，其中有許多相互作用的游走者；利用散射理論證明了多粒子量子游走能夠?qū)崿F(xiàn)通用的量子計算[37]，此時僅使用了多項式大小的圖，故較之文獻[36]更易于實驗實現(xiàn)，并且可以作為構(gòu)建一個可伸縮的量子計算機的架構(gòu)，而不需要依賴時間的控制。

Lovett等人利用離散時間量子游走代替連續(xù)量子游走[36]，給出了一組同樣的通用門集的等價構(gòu)造，即受控非門、阿達瑪門和π/8門，由此證明了離散時間量子游走和連續(xù)時間量子游走都是計算元件，具有通用性[38]。在連續(xù)時間量子游走的情況下[36]，圖中任意頂點的最大度為3。而在離散時間的情況下，要用具有更高度的頂點來確保定向傳播[38]。

一方面，量子游走是一種通用計算模型；另一方面，利用光學(xué)、離子阱、超導(dǎo)比特等在物理系統(tǒng)中實現(xiàn)量子游走的實驗實現(xiàn)也有廣泛的探索和深入的研究。因此，利用量子游走來實現(xiàn)量子門、量子電路，對于量子計算機的設(shè)計具有重要的潛力和較高的可行性，是未來研究的重要領(lǐng)域之一。

3.3 測量

量子測量在量子力學(xué)和量子信息處理中均起著基本的作用。半正定算子測量(Positive Operator Value Measure，POVM)相較于標準的馮諾伊曼投影測量會獲得更多的信息。Kurzyński等人利用離散時間量子游走中游走者的概率振幅之間的干涉現(xiàn)象，證明了一維離散時間量子游走可以用來實現(xiàn)在單個量子比特上POVM的廣義測量[40]。對于單個量子比特上任何秩1和秩2的POVM元素集{Ei}，都可以通過巧妙選取依賴于時間和位置空間的硬幣算子以恰當工程化的量子游走來生成。在這種情況下，對游走者在位置x=i處的測量對應(yīng)于在量子比特上的POVM元素Ei的測量。

隨后在實驗方面，Zhao等人使用光學(xué)設(shè)置，將量子比特編碼在單個光子的偏振狀態(tài)上，把量子游走的各個位置在光子路徑上實現(xiàn)，給出了基于量子游走進行一個單量子比特上廣義POVM測量的實驗實現(xiàn)[41]。Bian等人也在光學(xué)系統(tǒng)中實現(xiàn)了基于量子游走的廣義測量，關(guān)鍵是通過與位置相關(guān)的硬幣旋轉(zhuǎn)來控制硬幣的內(nèi)部動力學(xué)演化，進一步影響游走者的演化[42]。

Li等人進一步將理論結(jié)果從量子比特(Qubit)推廣至Qudit，即基于量子游走實現(xiàn)了在Qudit上的廣義測量，其中量子游走的步數(shù)是測量結(jié)果數(shù)目的兩倍[43]。當然，除了POVM測量，利用量子游走也陸續(xù)實現(xiàn)了其他測量。在預(yù)先準備的相同的量子系統(tǒng)上的集體測量(Collective Measurement)就可以比局部測量(Local Measurement)提取更多的信息。Hou等人基于量子游走對兩個相同的量子比特實現(xiàn)了確定性集體測量，并通過光量子游走實驗實現(xiàn)了一個高保真度的集體測量，同時將其應(yīng)用于量子態(tài)層析中[44]。

3.4 通信協(xié)議

量子游走是實現(xiàn)很多量子通信協(xié)議的有力工具之一，這里僅就量子游走在量子隱形傳輸和完美狀態(tài)傳輸兩方面的應(yīng)用做簡單介紹。

Wang等人基于兩硬幣量子游走提出了一種實現(xiàn)量子隱形傳輸?shù)姆椒╗45]。區(qū)別于傳統(tǒng)的量子隱形傳輸協(xié)議，這一方案并不需要預(yù)先準備糾纏態(tài)，而是通過一步量子游走由條件移位算子就可以直接產(chǎn)生所需要的糾纏資源。此外，聯(lián)合測量可以被兩個投影測量替代，因此在實現(xiàn)上會更加簡單。隨后，Chatterjee等人在IBM量子平臺上對這一協(xié)議提供了具體的實驗展示[46]：主要利用IBM量子平臺的五量子比特的機器和32比特的模擬器實現(xiàn)了k個量子比特的隱形傳輸，其中k=1, 2, 3，特別展示了Bell態(tài)、W態(tài)和GHZ態(tài)的隱形傳輸實驗。同時，Li等人利用多游走者量子游走模型在直線、圈和帶自環(huán)的兩點完全圖這3種圖結(jié)構(gòu)上實現(xiàn)了多比特量子態(tài)的隱形傳輸任務(wù)[47]。

除了以上利用量子游走在各個節(jié)點動態(tài)調(diào)控硬幣操作來實現(xiàn)完美狀態(tài)傳輸?shù)姆椒ㄒ酝?，量子游走搜索算法也可以用來實現(xiàn)完美狀態(tài)傳輸這一協(xié)議。考慮有兩個標記頂點(發(fā)送點和接收點)的量子游走搜索算法，通過在標記頂點和非標記頂點處分別選取合適的硬幣操作，可以較高概率地從發(fā)送頂點到達接收頂點。tefaňák等人討論了星形圖和帶自環(huán)的完全圖上的狀態(tài)傳輸[52]。完全二部圖[53-54]和完全多部圖[55]上的完美狀態(tài)傳輸也陸續(xù)得到分析。此外，在糾纏交換框架下，量子游走可以避開聯(lián)合貝爾測量實現(xiàn)難這一瓶頸，在遠距離幾方之間實現(xiàn)糾纏的制備[56]。

4 結(jié)束語

量子游走作為一種有效的算法工具，本身具有強大的計算能力和應(yīng)用潛力，在很多具體問題中的應(yīng)用開發(fā)和算法設(shè)計都值得深入研究和探索。量子游走本身在實驗方面的進展也令人欣喜，包括光子[57-59]、離子阱[60]、超導(dǎo)量子比特[61-62]和原子系統(tǒng)[63]等量子游走方案被先后提出。因此，基于量子游走的算法設(shè)計可行性高且效果前景好。

本文對量子游走做了簡單介紹，列舉了量子游走在搜索、元素區(qū)分、通用計算、通信協(xié)議和測量等方面的應(yīng)用，希望可以啟發(fā)研究人員將量子游走框架應(yīng)用于量子信息處理和量子算法的設(shè)計之中，借助量子游走這一工具開發(fā)出更多能夠體現(xiàn)量子優(yōu)勢的實用量子算法，實現(xiàn)相比于經(jīng)典算法有多項式級別甚至指數(shù)級別的加速效果，實現(xiàn)量子游走在不同場景的應(yīng)用，促進這一研究領(lǐng)域的不斷向前發(fā)展。