連續(xù)時(shí)間量子行走算法在截?cái)鄦涡尉Ц裆系乃阉餮芯?/h1>
2024-06-03 09:11:36朱軒民張德政
現(xiàn)代信息科技 2024年6期
朱軒民 張德政
收稿日期：2023-11-06
DOI：10.19850/j.cnki.2096-4706.2024.06.017
摘? 要：為證明連續(xù)時(shí)間量子行走算法在結(jié)構(gòu)型數(shù)據(jù)庫上的搜索可以實(shí)現(xiàn)二次加速的效果，對(duì)結(jié)構(gòu)型數(shù)據(jù)庫中的截?cái)鄦涡尉Ц耦愋?，進(jìn)行了連續(xù)時(shí)間量子行走算法的應(yīng)用研究。首先對(duì)截?cái)鄦涡尉Ц襁M(jìn)行對(duì)稱性分析，確定系統(tǒng)演化所處的希爾伯特空間，然后用哈密頓量本征態(tài)與基礎(chǔ)態(tài)的平方疊加、和簡并微擾理論兩種方法來求解系統(tǒng)演化需要的臨界跳躍率。最后通過對(duì)圖中的邊進(jìn)行加權(quán)的方法，合并了量子搜索的步驟，縮短了系統(tǒng)演化的時(shí)間，從而實(shí)現(xiàn)了平方加速的效果，并表明了邊的權(quán)重對(duì)量子搜索過程的影響。
關(guān)鍵詞：量子計(jì)算；量子搜索；連續(xù)時(shí)間量子行走算法；結(jié)構(gòu)型數(shù)據(jù)庫
中圖分類號(hào)：TP391? ? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：2096-4706（2024）06-0074-05
Research on Continuous-time Quantum Walk Algorithm Searching on Truncated Simplex Lattices
ZHU Xuanmin， ZHANG Dezheng
（Guizhou University of Finance and Economics， Guiyang? 550025， China）
Abstract： To demonstrate the quadratic speedup effect of the continuous-time quantum walk algorithm searching in structural database， this study delves into its application specifically for the truncated simplex lattice within structural databases. Initially， the determination of the Hilbert space in which the system evolves is based on an analysis of the symmetry of the truncated simplex lattice. Subsequently， the critical jumping rate for system evolution is derived by utilizing the square overlaps between the eigenstates of the Hamiltonian and the basis states， and employing degenerate perturbation theory. Ultimately， by assigning weights to the graph's edges， the stages of the quantum search are merged， thereby shortening the system evolution time and manifesting a quadratic speedup. This exploration elucidates the impact of weighted edges on the quantum search process.
Keywords： quantum computation; quantum search; continuous-time quantum walk algorithm; structured database
0? 引? 言
自從Feynman在1981年提出量子計(jì)算的概念以來，量子游走算法一直被認(rèn)為是實(shí)現(xiàn)量子計(jì)算的一個(gè)關(guān)鍵組成部分。特別是當(dāng)Grover量子搜索算法在結(jié)構(gòu)型數(shù)據(jù)庫中表現(xiàn)出的局限性，使其不能實(shí)現(xiàn)二次加速的最佳效果時(shí)，量子游走算法成為提高量子搜索效率的潛力算法[1，2]。
量子游走，又稱量子隨機(jī)行走算法，是經(jīng)典隨機(jī)行走的量子版本。量子隨機(jī)行走算法分為離散時(shí)間量子行走和連續(xù)時(shí)間量子行走[3]。其中連續(xù)時(shí)間量子行走的思路來源于經(jīng)典的連續(xù)型馬爾可夫過程，所以常借助于圖來進(jìn)行描述，所以也更適合求解能夠表示成結(jié)構(gòu)圖的問題，在量子領(lǐng)域中包括搜索、模擬、優(yōu)化和圖論問題。在量子搜索的問題上，可以代替Grover算法在結(jié)構(gòu)型數(shù)據(jù)庫中實(shí)現(xiàn)二次加速的搜索效果[4，5]。
本論文的目的是研究連續(xù)時(shí)間量子行走算法在截?cái)鄦涡芯Ц裰?，解決量子搜索問題的應(yīng)用。我們討論了階截?cái)鄦涡尉Ц竦慕Y(jié)構(gòu)特點(diǎn)，然后運(yùn)用連續(xù)時(shí)間量子行走算法實(shí)現(xiàn)量子搜索.這一過程包括分析對(duì)晶格結(jié)構(gòu)進(jìn)行對(duì)稱性分析，并討論了尋找系統(tǒng)演化需要的臨界跳躍率的兩種方法。最后，我們通過對(duì)晶格上特定的邊進(jìn)行加權(quán)對(duì)量子搜索的影響，并壓縮系統(tǒng)演化的時(shí)間，實(shí)現(xiàn)平方加速效果。
1? 連續(xù)時(shí)間量子行走算法在截?cái)鄦涡尉Ц裰械膽?yīng)用
截?cái)鄦涡尉Ц褚蚱渚哂杏行У姆钦S數(shù)而得到了廣泛的關(guān)注[6]。一個(gè)零階截?cái)郙維單形晶格是指一個(gè)由（M+1）個(gè)結(jié)點(diǎn)構(gòu)成的完全圖，如圖1是一個(gè)零階6維單形晶格，其中用雙線圈圍成的點(diǎn)是目標(biāo)態(tài)| a〉。單線圈圍成的點(diǎn)為演化相同的點(diǎn)，表示| b〉。當(dāng)該完全圖上的各點(diǎn)均被一個(gè)M維完全圖取代時(shí)，就可以得到一個(gè)一階截?cái)郙維單形晶格，如圖2是一個(gè)一階6維單形晶格。以此類推，一個(gè)r階截?cái)郙維單形晶格是由一個(gè)（r-1）階晶格上的各點(diǎn)由M維完全圖取代得來。其中雙線圈圍成的點(diǎn)為標(biāo)記點(diǎn)a，其余點(diǎn)，根據(jù)對(duì)稱性分析，演化情況相同的用相同的字母表示。
在量子系統(tǒng)中，信息用量子態(tài)表示。當(dāng)結(jié)構(gòu)型數(shù)據(jù)庫用圖表示時(shí)，圖中的結(jié)點(diǎn)表示系統(tǒng)的各量子態(tài)，即對(duì)應(yīng)不同的信息。當(dāng)數(shù)據(jù)庫用截?cái)鄦涡尉Ц癖硎緯r(shí)，系統(tǒng)演化需要的哈密頓量可以用圖的拉普拉斯算子表示H = -γL，其中L = A - D。γ表示單位時(shí)間內(nèi)，系統(tǒng)在鄰接點(diǎn)之間進(jìn)行演化的概率振幅，被稱為跳躍率；A表示圖的鄰接矩陣；D表示以各點(diǎn)度數(shù)為對(duì)角元的對(duì)角矩陣。
因?yàn)榻財(cái)鄦涡尉Ц袷钦齽t圖，即每個(gè)頂點(diǎn)都有相同的度數(shù)。在哈密頓量H的表達(dá)式中，D成為單位矩陣的整數(shù)倍。當(dāng)省略D時(shí)，對(duì)搜索的效果并沒有影響。所以哈密頓量H中的拉普拉斯算符L可以用圖的鄰接矩陣A替代，即H = -γA。并且，在正則圖上使用連續(xù)時(shí)間量子行走算法時(shí)，用鄰接矩陣A或拉普拉斯算子L構(gòu)造哈密頓量H，對(duì)實(shí)驗(yàn)的結(jié)果并沒有影響[7]。
其次，為了表示我們需要搜索的目標(biāo)態(tài)，我們將其在圖上對(duì)應(yīng)的結(jié)點(diǎn)設(shè)置為標(biāo)記點(diǎn)，如圖1中的點(diǎn)a。為了使系統(tǒng)演化到目標(biāo)態(tài)，我們需要在哈密頓量H中引入一個(gè)oracle項(xiàng)，此時(shí)哈密頓量H可以表示為 [8]。
連續(xù)時(shí)間量子行走相較于離散時(shí)間量子行走，不需要硬幣空間，也不需要拋硬幣，但是需要找到一個(gè)合適的γ值，即臨界跳躍率γc，使系統(tǒng)可以從所處的初始狀態(tài)朝目標(biāo)態(tài)的方向進(jìn)行演化。接下來，我們將具體討論臨界跳躍率γc的求解過程。
1.1? 結(jié)構(gòu)型數(shù)據(jù)庫的結(jié)構(gòu)分析
對(duì)于如圖1所示的零階截?cái)郚維單形晶格，即一個(gè)擁有（N+1）個(gè)結(jié)點(diǎn)的完全圖，我們可以將該系統(tǒng)對(duì)應(yīng)的哈密頓量H表示為：
相應(yīng)的，系統(tǒng)演化所處的希爾伯特空間是N+1維。
但是當(dāng)系統(tǒng)較為復(fù)雜，N的數(shù)目較大時(shí)，處理N維矩陣就顯得較為困難。為此，我們需要對(duì)希爾伯特空間進(jìn)行降維。設(shè)我們的目標(biāo)態(tài)為| a〉，如圖1中的點(diǎn)a為我們目標(biāo)態(tài)對(duì)應(yīng)的標(biāo)記點(diǎn)。此時(shí)圖1中的對(duì)稱性將被打破：標(biāo)記點(diǎn)對(duì)應(yīng)的態(tài)為| a〉；而其他非標(biāo)記點(diǎn)因其對(duì)稱性相同，且晶格的對(duì)稱性和系統(tǒng)的演化情況之間具有一致性，所以它們的演化情況都相同，可以用同一個(gè)基礎(chǔ)態(tài)來表示：。由此，我們就可以用| a〉 和| b〉 來構(gòu)成我們的希爾伯特空間。對(duì)應(yīng)的哈密頓量就可以表示為：
希爾伯特空間就從原來的N+1維降為了2維[9]。
圖1? 零階6維單形晶格
類似的，我們可以用這種對(duì)稱性分析的方法處理更復(fù)雜的圖，如圖2的一階截?cái)?維單形晶格。該圖共有42個(gè)點(diǎn)。但是當(dāng)我們引入標(biāo)記點(diǎn)a，然后根據(jù)對(duì)稱性分析，我們可以將系統(tǒng)演化的希爾伯特空間降至7維，由{ | a〉 ，| b〉 ，| c〉 ，| d 〉 ，| e〉 ，| f 〉 ，| g〉 }組成。且分析證明，即使該一階截?cái)鄦涡尉Ц竦木S數(shù)M增大時(shí)，這個(gè)7維不變子空間仍然適用。且這種對(duì)稱性分析的方法適用于其他正則圖結(jié)構(gòu)如超立方體圖，和非正則圖結(jié)構(gòu)如樹[10，11]。
圖2? 一階截?cái)?維單形晶格
1.2? 算法應(yīng)用
當(dāng)在結(jié)構(gòu)型數(shù)據(jù)庫中進(jìn)行搜索時(shí)，因?yàn)椴恢篮湍繕?biāo)態(tài)有關(guān)的信息，所以我們選擇一個(gè)初態(tài)，使系統(tǒng)的概率是平均分配到圖上的每個(gè)點(diǎn)，即每個(gè)點(diǎn)或每個(gè)狀態(tài)都有可能是我們的目標(biāo)。該初態(tài)也是物理實(shí)驗(yàn)中較常采用和較易制備的，可以表示為 。如圖1的完全圖中，標(biāo)記點(diǎn)用a表示，非標(biāo)記點(diǎn)用b表示。系統(tǒng)哈密頓量可以表示為H = -γA - | a〉 〈a |。當(dāng)結(jié)點(diǎn)數(shù)目很多時(shí)候，b點(diǎn)的數(shù)目N - 1≈N，所以初態(tài)| s〉 ≈| b〉。
我們解跳躍率γ取不同值時(shí)，哈密頓量H的本征值和本征態(tài)，并求本征態(tài)與基礎(chǔ)態(tài)的平方疊加，H = 100維的完全圖上如圖3所示。從圖中我們可以看出，當(dāng)Nγ = 1，亦即γ = 1 / N時(shí)，H的本征態(tài)為 ，且兩本征態(tài)之間的能量差值最小為 。這里，γc = 1 / N即完成搜索需要的臨界跳躍率。此時(shí)，初態(tài)和系統(tǒng)的狀態(tài)可以表示為? 和
，系統(tǒng)狀態(tài)
會(huì)隨著時(shí)間的推移而在? 和? 之間進(jìn)行周期性振動(dòng)，
對(duì)應(yīng)概率可以表示為 和 ，其中?E10 = E1 - E0。令
|〈a | Ψ （t）〉 | 2 = 1，得t = π / ?E10。所以，當(dāng)γ = 1 / N時(shí)，經(jīng)t = π / ?E10后，系統(tǒng)可以從| s〉? 演化到| a〉，搜索完成[5]。
圖3? 哈密頓量H的本征態(tài)和基礎(chǔ)態(tài)之間的平方疊加
除了上述取多個(gè)γ值，然后求哈密頓量本征態(tài)和基礎(chǔ)態(tài)之間平方疊加的方法外，我們還可以將簡并微擾理論應(yīng)用到連續(xù)時(shí)間量子行走算法中，來求解臨界跳躍率γc和系統(tǒng)演化的時(shí)間t [10]。仍以圖1的完全圖為例，我們根據(jù)簡并微擾理論，將哈密頓量H拆分為H = H （0） + H （1）。其中? 是領(lǐng)先項(xiàng)， 是微擾項(xiàng)。領(lǐng)先項(xiàng)H （0）的本征態(tài)即| a〉 和| b〉 ，對(duì)應(yīng)的本征值，即對(duì)應(yīng)的能量為-1和-γN。當(dāng)使兩本征態(tài)對(duì)應(yīng)能量相等時(shí)，γ = γc = 1 / N，再引入微擾項(xiàng)H （1），系統(tǒng)的本征態(tài)可以用αa | a〉 + αb | b〉 表示。以{ | a〉，| b〉 }為計(jì)算基，將哈密頓量H重新展開，得本征態(tài)和本征值為? 和 。同樣的，取時(shí)間 ，系統(tǒng)可以從| b〉 演化到| a〉。因?yàn)楫?dāng)完全圖的點(diǎn)足夠多時(shí)，| s〉 ≈| b〉 。所以當(dāng)γ = 1 / N時(shí)，經(jīng) ，系統(tǒng)可從初態(tài)| s〉 演化到目標(biāo)態(tài)| a〉 。
當(dāng)晶格階數(shù)增加，從零階增至一階時(shí)，系統(tǒng)的搜索需要兩步來完成。并且每一步需要的臨界跳躍率γc將有所不同。在使用簡并微擾理論進(jìn)行求解時(shí)，也將需要對(duì)哈密頓量進(jìn)行不同的拆分，且每一步選擇的領(lǐng)先項(xiàng)也將有所不同。特別是階數(shù)升至二階甚至更高階時(shí)，領(lǐng)先項(xiàng)的選擇將需要明顯參照系統(tǒng)演化發(fā)生的局部結(jié)構(gòu)。總結(jié)規(guī)律得，設(shè)截?cái)鄦涡途Ц竦碾A數(shù)為r，則搜索需要的步驟為步，對(duì)應(yīng)的臨界跳躍率分別為γc1 = （r + 1） / M，γc2 = r / M，…，1 / M，所需時(shí)間為t ∝ M （2r + 1） / 2，M （2r + 1） / 2，…，M 1 / 2，即t ∝ N （2r + 1） / （2r + 2），N （2r - 1） / （2r + 2），…，N 1 / （2r + 2）。其中M為截?cái)鄦涡尉Ц竦木S數(shù)，N是晶格所有結(jié)點(diǎn)的數(shù)量N = （M + 1） M r。當(dāng)階數(shù)增加時(shí)，系統(tǒng)演化需要的時(shí)間也將增加，不能實(shí)現(xiàn)平方加速。我們可以通過增加圖中邊的權(quán)重，來縮短時(shí)間，我們?cè)谙乱还?jié)中進(jìn)行討論[11，12]。
除了截?cái)鄦涡尉Ц褚酝猓渌麍D如超立方體圖、樹、d維拉丁圖和Johnson圖等也實(shí)現(xiàn)了用連續(xù)時(shí)間行走算法完成量子搜索[5，13-17]。連續(xù)時(shí)間量子行走算法的使用中，解哈密頓量H本征態(tài)和基礎(chǔ)態(tài)平方疊加的方法尋找臨界跳躍率γc應(yīng)用較為廣泛，而簡并微擾理論目前只在截?cái)鄦涡尉Ц窈统⒎襟w圖上得以成功運(yùn)用[10]。
2? 實(shí)現(xiàn)平方加速
在截?cái)鄦涡尉Ц裆鲜褂眠B續(xù)時(shí)間量子行走算法時(shí)，若晶格階數(shù)超過0時(shí)，系統(tǒng)演化將不能實(shí)現(xiàn)時(shí)間上的平方加速效果。如圖2的一階截?cái)?維晶格上，系統(tǒng)從初態(tài)? 演化到目標(biāo)態(tài)| a〉，需要兩個(gè)步驟| s〉 → | b〉 → | a〉。兩個(gè)步驟對(duì)應(yīng)的臨界跳躍率為γc1 = 2 / M和γc2 = 1 / M，對(duì)應(yīng)的時(shí)間為t1 =
πM 3/2 / 4和t2 = πM 1/2 / 2。整個(gè)搜索過程系統(tǒng)演化需要的時(shí)間為t = t1 + t2 = πM 3/2 / 4 + πM 1/2 / 2 = Θ （M 3/2） = Θ（N3/4）。可見，此時(shí)的量子搜索不能達(dá)到平方加速的效果。
為了縮短量子搜索的時(shí)間，我們首先將一階截?cái)郙維單形晶格看成是M + 1個(gè)“零階截?cái)鄦涡尉Ц瘛北舜诉B接構(gòu)成。我們稱這M + 1個(gè)“零階截?cái)鄦涡尉Ц瘛睘椤傲汶A完全子圖”。一階截?cái)鄦涡尉Ц裆系膬刹窖莼校谝徊窖莼枰臅r(shí)間較長，并且是造成量子搜索不能達(dá)到平方加速效果的原因。而第一步從| s〉 ≈| g〉 演化到 | b〉 的過程，可以看成是兩個(gè)零階完全子圖之間的演化。然后我們選擇在零階完全子圖之間的邊上增加權(quán)值，即在圖2所示的虛線上增加權(quán)重ω。
用簡并微擾理論求解系統(tǒng)演化第一步的臨界跳躍率為γc1 = （1 + 1 / ω） / M，此時(shí)演化所需的時(shí)間為t1 = πM 3/2 / [2 （1 + ω）]。而第二步的演化是 | b〉 → | a〉，在圖2中是同一個(gè)零階完全子圖中不同點(diǎn)之間的演化，所以不受權(quán)值為ω邊的影響，所以系統(tǒng)演化的總時(shí)間為t′ = t1′+t2 = πM 3/2 / [2 （1 + ω）] + πM 1/2 / 2。當(dāng)ω = 1時(shí)，γc1 = 2 / M，且系統(tǒng)演化的時(shí)間為t1 = πM 3/2 / 4。但是我們?cè)黾应氐娜≈禃r(shí)，t1就可以減小。當(dāng)我們?nèi)? 時(shí)，就可以使 ，從而實(shí)現(xiàn)平方加速的效果[18]。
但是這樣的加速需要以降低系統(tǒng)演化成功的概率為代價(jià)。當(dāng)? 時(shí)，雖然系統(tǒng)演化的時(shí)間被縮短了，但是 | s〉 → | b〉 〉演化成功的概率從不加權(quán)時(shí)的接近100%降低到了30%左右。而其余70%左右的概率分別以40%左右的概率演化到了 | a〉 和30%左右的概率停留在了 | s〉。當(dāng)我們繼續(xù)增加ω到M時(shí)，取γc1 = 2 / 3M + 2 / M 2，系統(tǒng)經(jīng)時(shí)間t = πM / 1.83，以更高的概率演化到了 | a〉，而演化到 | b〉 的概率幾乎為0。如圖4所示，Pa表示系統(tǒng)演化到 | a〉 的概率，而Pb表示系統(tǒng)演化到 | b〉 的概率。此時(shí)，系統(tǒng)已經(jīng)從 | s〉 → | b〉 → | a〉 的兩步搜索合并成了 | s〉 → | a〉 的一步搜索，且時(shí)間 ，實(shí)現(xiàn)了平方加速的效果[12]。
圖4? 一階截?cái)鄦涡尉Ц裆舷到y(tǒng)演化的變化情況
3? 結(jié)? 論
連續(xù)時(shí)間量子行走算法是基于經(jīng)典馬爾可夫過程，對(duì)經(jīng)典游走的量子模擬算法。因其更適合解決圖表示的問題，所以相比較于Grover算法，更適合解決在結(jié)構(gòu)型數(shù)據(jù)庫上實(shí)現(xiàn)平方加速搜索的問題。
本文討論了通過對(duì)稱性分析對(duì)結(jié)構(gòu)型數(shù)據(jù)庫的結(jié)構(gòu)進(jìn)行分析，實(shí)現(xiàn)了系統(tǒng)演化所處希爾伯特空間的降維，并提供了確定臨界跳躍率γc的兩種方法，進(jìn)一步求得系統(tǒng)演化所需的時(shí)間，使系統(tǒng)能夠以較高概率演化到目標(biāo)狀態(tài)。最后我們討論了給圖上的邊增加權(quán)重對(duì)量子搜索的影響，并通過加權(quán)壓縮了系統(tǒng)演化的步驟，縮短了系統(tǒng)演化的時(shí)間，實(shí)現(xiàn)了平方加速。
雖然連續(xù)時(shí)間量子行走這一算法不是適用于所有搜索問題的通用解決方案，但它為解決一系列結(jié)構(gòu)型數(shù)據(jù)庫上的搜索問題提供了一種新的思路。至于進(jìn)一步探索其他確定臨界跳躍率γc的更簡便方法，以及連續(xù)時(shí)間量子行走算法在搜索問題上、或其他領(lǐng)域中的應(yīng)用等問題，對(duì)該算法的未來研究發(fā)展和進(jìn)一步拓展探究都具有重要作用。
參考文獻(xiàn)：
[1] GROVER K L. Quantum Mechanics Helps in Searching for a Needle in a Haystack [C]//Quantum Entanglement and Quantum Information--Proceedings of CCAST （World Laboratory） Workshop.Beijing：中國高等科學(xué)技術(shù)中心，1999：100-103.
[2] GROVER L K .Quantum Computers Can Search Arbitrarily Large Databases by a Single Query [J].Physical Review Letters，1997，79（23）：4709-4712.
[3] 薛鵬，王坤坤.量子行走 [J].光學(xué)學(xué)報(bào)，2024，44（2）：9-17.
[4] FARHI E，GUTMANN S .Quantum Computation and Decision Trees [J].Phys.rev.a，1997，58（2）：915-928.
[5] APERS S，CHAKRABORTY S，NOVO L，et al. Quadratic speedup for spatial search by continuous-time quantum walk [J/OL].Physical Review A，2021，95（3）：（2017-05-02）.https：//link.aps.org/doi/10.1103/PhysRevA.95.032301.
[6] DHAR D. Erratum：Lattices of effectively nonintegral dimensionality [J].J. Math. Phys.1977，18（12）：2520-2520.
[7] WONG T G，TARRATACA，LU?S TARRATACA，NAHIMOV N. Laplacian versus Adjacency Matrix in Quantum Walk Search [J]. Quantum Inf Process，2016，15：4029-4048.
[8] MOCHON C. Hamiltonian Oracles [J].Physical Review A，2007，75（4）：810-814.
[9] WANG Y，WU S. Role of symmetry in quantum search via continuous-time quantum walk [J/OL].SPIN，2021，11 （3）：2140002.https：//doi.org/10.1142/S2010324721400026.
[10] WONG，THOMAS G. Diagrammatic approach to quantum search [J].Quantum Information Processing，2015，14（6）：1767-1775.
[11] WANG Y，WU S，WANG W. Controlled quantum search on structured databases [J/OL].arXiv：2106.08398 [quant-ph].（2021-06-15）.https：//arxiv.org/abs/2106.08398.
[12] CHILDS A M. Optimal Quantum Adversary Lower Bounds for Ordered Search [C]//ICALP '08：Proceedings of the 35th international colloquium on Automata，Languages and Programming.Heidelberg：Springer-Verlag，2008：869–880.
[13] JANMARK J，MEYER D A，WONG T G .Global Symmetry is Unnecessary for Fast Quantum Search [J/OL].Physical Review Letters，2014，112（21）：210502（2014-05-28）.https：//link.aps.org/doi/10.1103/PhysRevLett.112.210502.
[14] MEYER D A，WONG T G. Connectivity is a poor indicator of fast quantum search [J/OL].Physical Review Letters，2015，114（11）：110503（2015-05-18）. https：//link.aps.org/doi/10.1103/PhysRevLett.114.110503
[15] CHAKRABORTY S，NOVO L，AMBAINIS A，et al. Spatial search by quantum walk is optimal for almost all graphs [J/OL].Physical Review Letters，2016，116（10）：100501 （2016-05-11）.https：//link.aps.org/doi/10.1103/PhysRevLett.116.100501.
[16] TANAKA H，SABRI M，PORTUGAL R. Spatial search on Johnson graphs by continuous-time quantum walk [J/OL].Quantum Information Processing，2022，21：74（2022-01-28）.https：//doi.org/10.1007/s11128-022-03417-9.
[17] APERS S，CHAKRABORTY S，NOVO L，et al. Quadratic speedup for spatial search by continuous-time quantum walk [J/OL].arXiv：2112.12746 [quant-ph].（2021-12-23）.https：//arxiv.org/abs/2112.12746.
[18] WONG，THOMAS G .Faster Quantum Walk Search on a Weighted Graph[J/OL].Physical Review A，2015，92（3）：032320 （2015-09-21）.https：//link.aps.org/doi/10.1103/PhysRevA.92.032320.
作者簡介：朱軒民（1983—）男，漢族，河南周口人，副教授，博士，研究方向：量子計(jì)算與量子信息；張德政（1998—），男，漢族，河北石家莊人，碩士在讀，研究方向：量子計(jì)算與量子信息。
- 現(xiàn)代信息科技的其它文章
- 基于深度神經(jīng)網(wǎng)絡(luò)的戰(zhàn)場(chǎng)信息網(wǎng)信息群發(fā)現(xiàn)技術(shù)
- 基于圖像重建的代謝腫瘤總體積分級(jí)模型
- 基于YOLOv7的礦工吸煙識(shí)別方法研究
- 基于區(qū)塊鏈的水下無線傳感器網(wǎng)絡(luò)惡意節(jié)點(diǎn)檢測(cè)機(jī)制
- 基于EWT和NeuralProphet-MLP的蜂窩網(wǎng)絡(luò)流量長期預(yù)測(cè)方法
- 中國通號(hào)FZL-300信號(hào)系統(tǒng)ATS分機(jī)設(shè)備原理及故障處理分析
朱軒民 張德政
收稿日期：2023-11-06
DOI：10.19850/j.cnki.2096-4706.2024.06.017
摘? 要：為證明連續(xù)時(shí)間量子行走算法在結(jié)構(gòu)型數(shù)據(jù)庫上的搜索可以實(shí)現(xiàn)二次加速的效果，對(duì)結(jié)構(gòu)型數(shù)據(jù)庫中的截?cái)鄦涡尉Ц耦愋?，進(jìn)行了連續(xù)時(shí)間量子行走算法的應(yīng)用研究。首先對(duì)截?cái)鄦涡尉Ц襁M(jìn)行對(duì)稱性分析，確定系統(tǒng)演化所處的希爾伯特空間，然后用哈密頓量本征態(tài)與基礎(chǔ)態(tài)的平方疊加、和簡并微擾理論兩種方法來求解系統(tǒng)演化需要的臨界跳躍率。最后通過對(duì)圖中的邊進(jìn)行加權(quán)的方法，合并了量子搜索的步驟，縮短了系統(tǒng)演化的時(shí)間，從而實(shí)現(xiàn)了平方加速的效果，并表明了邊的權(quán)重對(duì)量子搜索過程的影響。
關(guān)鍵詞：量子計(jì)算；量子搜索；連續(xù)時(shí)間量子行走算法；結(jié)構(gòu)型數(shù)據(jù)庫
中圖分類號(hào)：TP391? ? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：2096-4706（2024）06-0074-05
Research on Continuous-time Quantum Walk Algorithm Searching on Truncated Simplex Lattices
ZHU Xuanmin， ZHANG Dezheng
（Guizhou University of Finance and Economics， Guiyang? 550025， China）
Abstract： To demonstrate the quadratic speedup effect of the continuous-time quantum walk algorithm searching in structural database， this study delves into its application specifically for the truncated simplex lattice within structural databases. Initially， the determination of the Hilbert space in which the system evolves is based on an analysis of the symmetry of the truncated simplex lattice. Subsequently， the critical jumping rate for system evolution is derived by utilizing the square overlaps between the eigenstates of the Hamiltonian and the basis states， and employing degenerate perturbation theory. Ultimately， by assigning weights to the graph's edges， the stages of the quantum search are merged， thereby shortening the system evolution time and manifesting a quadratic speedup. This exploration elucidates the impact of weighted edges on the quantum search process.
Keywords： quantum computation; quantum search; continuous-time quantum walk algorithm; structured database
0? 引? 言
自從Feynman在1981年提出量子計(jì)算的概念以來，量子游走算法一直被認(rèn)為是實(shí)現(xiàn)量子計(jì)算的一個(gè)關(guān)鍵組成部分。特別是當(dāng)Grover量子搜索算法在結(jié)構(gòu)型數(shù)據(jù)庫中表現(xiàn)出的局限性，使其不能實(shí)現(xiàn)二次加速的最佳效果時(shí)，量子游走算法成為提高量子搜索效率的潛力算法[1，2]。
量子游走，又稱量子隨機(jī)行走算法，是經(jīng)典隨機(jī)行走的量子版本。量子隨機(jī)行走算法分為離散時(shí)間量子行走和連續(xù)時(shí)間量子行走[3]。其中連續(xù)時(shí)間量子行走的思路來源于經(jīng)典的連續(xù)型馬爾可夫過程，所以常借助于圖來進(jìn)行描述，所以也更適合求解能夠表示成結(jié)構(gòu)圖的問題，在量子領(lǐng)域中包括搜索、模擬、優(yōu)化和圖論問題。在量子搜索的問題上，可以代替Grover算法在結(jié)構(gòu)型數(shù)據(jù)庫中實(shí)現(xiàn)二次加速的搜索效果[4，5]。
本論文的目的是研究連續(xù)時(shí)間量子行走算法在截?cái)鄦涡芯Ц裰?，解決量子搜索問題的應(yīng)用。我們討論了階截?cái)鄦涡尉Ц竦慕Y(jié)構(gòu)特點(diǎn)，然后運(yùn)用連續(xù)時(shí)間量子行走算法實(shí)現(xiàn)量子搜索.這一過程包括分析對(duì)晶格結(jié)構(gòu)進(jìn)行對(duì)稱性分析，并討論了尋找系統(tǒng)演化需要的臨界跳躍率的兩種方法。最后，我們通過對(duì)晶格上特定的邊進(jìn)行加權(quán)對(duì)量子搜索的影響，并壓縮系統(tǒng)演化的時(shí)間，實(shí)現(xiàn)平方加速效果。
1? 連續(xù)時(shí)間量子行走算法在截?cái)鄦涡尉Ц裰械膽?yīng)用
截?cái)鄦涡尉Ц褚蚱渚哂杏行У姆钦S數(shù)而得到了廣泛的關(guān)注[6]。一個(gè)零階截?cái)郙維單形晶格是指一個(gè)由（M+1）個(gè)結(jié)點(diǎn)構(gòu)成的完全圖，如圖1是一個(gè)零階6維單形晶格，其中用雙線圈圍成的點(diǎn)是目標(biāo)態(tài)| a〉。單線圈圍成的點(diǎn)為演化相同的點(diǎn)，表示| b〉。當(dāng)該完全圖上的各點(diǎn)均被一個(gè)M維完全圖取代時(shí)，就可以得到一個(gè)一階截?cái)郙維單形晶格，如圖2是一個(gè)一階6維單形晶格。以此類推，一個(gè)r階截?cái)郙維單形晶格是由一個(gè)（r-1）階晶格上的各點(diǎn)由M維完全圖取代得來。其中雙線圈圍成的點(diǎn)為標(biāo)記點(diǎn)a，其余點(diǎn)，根據(jù)對(duì)稱性分析，演化情況相同的用相同的字母表示。
在量子系統(tǒng)中，信息用量子態(tài)表示。當(dāng)結(jié)構(gòu)型數(shù)據(jù)庫用圖表示時(shí)，圖中的結(jié)點(diǎn)表示系統(tǒng)的各量子態(tài)，即對(duì)應(yīng)不同的信息。當(dāng)數(shù)據(jù)庫用截?cái)鄦涡尉Ц癖硎緯r(shí)，系統(tǒng)演化需要的哈密頓量可以用圖的拉普拉斯算子表示H = -γL，其中L = A - D。γ表示單位時(shí)間內(nèi)，系統(tǒng)在鄰接點(diǎn)之間進(jìn)行演化的概率振幅，被稱為跳躍率；A表示圖的鄰接矩陣；D表示以各點(diǎn)度數(shù)為對(duì)角元的對(duì)角矩陣。
因?yàn)榻財(cái)鄦涡尉Ц袷钦齽t圖，即每個(gè)頂點(diǎn)都有相同的度數(shù)。在哈密頓量H的表達(dá)式中，D成為單位矩陣的整數(shù)倍。當(dāng)省略D時(shí)，對(duì)搜索的效果并沒有影響。所以哈密頓量H中的拉普拉斯算符L可以用圖的鄰接矩陣A替代，即H = -γA。并且，在正則圖上使用連續(xù)時(shí)間量子行走算法時(shí)，用鄰接矩陣A或拉普拉斯算子L構(gòu)造哈密頓量H，對(duì)實(shí)驗(yàn)的結(jié)果并沒有影響[7]。
其次，為了表示我們需要搜索的目標(biāo)態(tài)，我們將其在圖上對(duì)應(yīng)的結(jié)點(diǎn)設(shè)置為標(biāo)記點(diǎn)，如圖1中的點(diǎn)a。為了使系統(tǒng)演化到目標(biāo)態(tài)，我們需要在哈密頓量H中引入一個(gè)oracle項(xiàng)，此時(shí)哈密頓量H可以表示為 [8]。
連續(xù)時(shí)間量子行走相較于離散時(shí)間量子行走，不需要硬幣空間，也不需要拋硬幣，但是需要找到一個(gè)合適的γ值，即臨界跳躍率γc，使系統(tǒng)可以從所處的初始狀態(tài)朝目標(biāo)態(tài)的方向進(jìn)行演化。接下來，我們將具體討論臨界跳躍率γc的求解過程。
1.1? 結(jié)構(gòu)型數(shù)據(jù)庫的結(jié)構(gòu)分析
對(duì)于如圖1所示的零階截?cái)郚維單形晶格，即一個(gè)擁有（N+1）個(gè)結(jié)點(diǎn)的完全圖，我們可以將該系統(tǒng)對(duì)應(yīng)的哈密頓量H表示為：
相應(yīng)的，系統(tǒng)演化所處的希爾伯特空間是N+1維。
但是當(dāng)系統(tǒng)較為復(fù)雜，N的數(shù)目較大時(shí)，處理N維矩陣就顯得較為困難。為此，我們需要對(duì)希爾伯特空間進(jìn)行降維。設(shè)我們的目標(biāo)態(tài)為| a〉，如圖1中的點(diǎn)a為我們目標(biāo)態(tài)對(duì)應(yīng)的標(biāo)記點(diǎn)。此時(shí)圖1中的對(duì)稱性將被打破：標(biāo)記點(diǎn)對(duì)應(yīng)的態(tài)為| a〉；而其他非標(biāo)記點(diǎn)因其對(duì)稱性相同，且晶格的對(duì)稱性和系統(tǒng)的演化情況之間具有一致性，所以它們的演化情況都相同，可以用同一個(gè)基礎(chǔ)態(tài)來表示：。由此，我們就可以用| a〉 和| b〉 來構(gòu)成我們的希爾伯特空間。對(duì)應(yīng)的哈密頓量就可以表示為：
希爾伯特空間就從原來的N+1維降為了2維[9]。
圖1? 零階6維單形晶格
類似的，我們可以用這種對(duì)稱性分析的方法處理更復(fù)雜的圖，如圖2的一階截?cái)?維單形晶格。該圖共有42個(gè)點(diǎn)。但是當(dāng)我們引入標(biāo)記點(diǎn)a，然后根據(jù)對(duì)稱性分析，我們可以將系統(tǒng)演化的希爾伯特空間降至7維，由{ | a〉 ，| b〉 ，| c〉 ，| d 〉 ，| e〉 ，| f 〉 ，| g〉 }組成。且分析證明，即使該一階截?cái)鄦涡尉Ц竦木S數(shù)M增大時(shí)，這個(gè)7維不變子空間仍然適用。且這種對(duì)稱性分析的方法適用于其他正則圖結(jié)構(gòu)如超立方體圖，和非正則圖結(jié)構(gòu)如樹[10，11]。
圖2? 一階截?cái)?維單形晶格
1.2? 算法應(yīng)用
當(dāng)在結(jié)構(gòu)型數(shù)據(jù)庫中進(jìn)行搜索時(shí)，因?yàn)椴恢篮湍繕?biāo)態(tài)有關(guān)的信息，所以我們選擇一個(gè)初態(tài)，使系統(tǒng)的概率是平均分配到圖上的每個(gè)點(diǎn)，即每個(gè)點(diǎn)或每個(gè)狀態(tài)都有可能是我們的目標(biāo)。該初態(tài)也是物理實(shí)驗(yàn)中較常采用和較易制備的，可以表示為 。如圖1的完全圖中，標(biāo)記點(diǎn)用a表示，非標(biāo)記點(diǎn)用b表示。系統(tǒng)哈密頓量可以表示為H = -γA - | a〉 〈a |。當(dāng)結(jié)點(diǎn)數(shù)目很多時(shí)候，b點(diǎn)的數(shù)目N - 1≈N，所以初態(tài)| s〉 ≈| b〉。
我們解跳躍率γ取不同值時(shí)，哈密頓量H的本征值和本征態(tài)，并求本征態(tài)與基礎(chǔ)態(tài)的平方疊加，H = 100維的完全圖上如圖3所示。從圖中我們可以看出，當(dāng)Nγ = 1，亦即γ = 1 / N時(shí)，H的本征態(tài)為 ，且兩本征態(tài)之間的能量差值最小為 。這里，γc = 1 / N即完成搜索需要的臨界跳躍率。此時(shí)，初態(tài)和系統(tǒng)的狀態(tài)可以表示為? 和
，系統(tǒng)狀態(tài)
會(huì)隨著時(shí)間的推移而在? 和? 之間進(jìn)行周期性振動(dòng)，
對(duì)應(yīng)概率可以表示為 和 ，其中?E10 = E1 - E0。令
|〈a | Ψ （t）〉 | 2 = 1，得t = π / ?E10。所以，當(dāng)γ = 1 / N時(shí)，經(jīng)t = π / ?E10后，系統(tǒng)可以從| s〉? 演化到| a〉，搜索完成[5]。
圖3? 哈密頓量H的本征態(tài)和基礎(chǔ)態(tài)之間的平方疊加
除了上述取多個(gè)γ值，然后求哈密頓量本征態(tài)和基礎(chǔ)態(tài)之間平方疊加的方法外，我們還可以將簡并微擾理論應(yīng)用到連續(xù)時(shí)間量子行走算法中，來求解臨界跳躍率γc和系統(tǒng)演化的時(shí)間t [10]。仍以圖1的完全圖為例，我們根據(jù)簡并微擾理論，將哈密頓量H拆分為H = H （0） + H （1）。其中? 是領(lǐng)先項(xiàng)， 是微擾項(xiàng)。領(lǐng)先項(xiàng)H （0）的本征態(tài)即| a〉 和| b〉 ，對(duì)應(yīng)的本征值，即對(duì)應(yīng)的能量為-1和-γN。當(dāng)使兩本征態(tài)對(duì)應(yīng)能量相等時(shí)，γ = γc = 1 / N，再引入微擾項(xiàng)H （1），系統(tǒng)的本征態(tài)可以用αa | a〉 + αb | b〉 表示。以{ | a〉，| b〉 }為計(jì)算基，將哈密頓量H重新展開，得本征態(tài)和本征值為? 和 。同樣的，取時(shí)間 ，系統(tǒng)可以從| b〉 演化到| a〉。因?yàn)楫?dāng)完全圖的點(diǎn)足夠多時(shí)，| s〉 ≈| b〉 。所以當(dāng)γ = 1 / N時(shí)，經(jīng) ，系統(tǒng)可從初態(tài)| s〉 演化到目標(biāo)態(tài)| a〉 。
當(dāng)晶格階數(shù)增加，從零階增至一階時(shí)，系統(tǒng)的搜索需要兩步來完成。并且每一步需要的臨界跳躍率γc將有所不同。在使用簡并微擾理論進(jìn)行求解時(shí)，也將需要對(duì)哈密頓量進(jìn)行不同的拆分，且每一步選擇的領(lǐng)先項(xiàng)也將有所不同。特別是階數(shù)升至二階甚至更高階時(shí)，領(lǐng)先項(xiàng)的選擇將需要明顯參照系統(tǒng)演化發(fā)生的局部結(jié)構(gòu)。總結(jié)規(guī)律得，設(shè)截?cái)鄦涡途Ц竦碾A數(shù)為r，則搜索需要的步驟為步，對(duì)應(yīng)的臨界跳躍率分別為γc1 = （r + 1） / M，γc2 = r / M，…，1 / M，所需時(shí)間為t ∝ M （2r + 1） / 2，M （2r + 1） / 2，…，M 1 / 2，即t ∝ N （2r + 1） / （2r + 2），N （2r - 1） / （2r + 2），…，N 1 / （2r + 2）。其中M為截?cái)鄦涡尉Ц竦木S數(shù)，N是晶格所有結(jié)點(diǎn)的數(shù)量N = （M + 1） M r。當(dāng)階數(shù)增加時(shí)，系統(tǒng)演化需要的時(shí)間也將增加，不能實(shí)現(xiàn)平方加速。我們可以通過增加圖中邊的權(quán)重，來縮短時(shí)間，我們?cè)谙乱还?jié)中進(jìn)行討論[11，12]。
除了截?cái)鄦涡尉Ц褚酝猓渌麍D如超立方體圖、樹、d維拉丁圖和Johnson圖等也實(shí)現(xiàn)了用連續(xù)時(shí)間行走算法完成量子搜索[5，13-17]。連續(xù)時(shí)間量子行走算法的使用中，解哈密頓量H本征態(tài)和基礎(chǔ)態(tài)平方疊加的方法尋找臨界跳躍率γc應(yīng)用較為廣泛，而簡并微擾理論目前只在截?cái)鄦涡尉Ц窈统⒎襟w圖上得以成功運(yùn)用[10]。
2? 實(shí)現(xiàn)平方加速
在截?cái)鄦涡尉Ц裆鲜褂眠B續(xù)時(shí)間量子行走算法時(shí)，若晶格階數(shù)超過0時(shí)，系統(tǒng)演化將不能實(shí)現(xiàn)時(shí)間上的平方加速效果。如圖2的一階截?cái)?維晶格上，系統(tǒng)從初態(tài)? 演化到目標(biāo)態(tài)| a〉，需要兩個(gè)步驟| s〉 → | b〉 → | a〉。兩個(gè)步驟對(duì)應(yīng)的臨界跳躍率為γc1 = 2 / M和γc2 = 1 / M，對(duì)應(yīng)的時(shí)間為t1 =
πM 3/2 / 4和t2 = πM 1/2 / 2。整個(gè)搜索過程系統(tǒng)演化需要的時(shí)間為t = t1 + t2 = πM 3/2 / 4 + πM 1/2 / 2 = Θ （M 3/2） = Θ（N3/4）。可見，此時(shí)的量子搜索不能達(dá)到平方加速的效果。
為了縮短量子搜索的時(shí)間，我們首先將一階截?cái)郙維單形晶格看成是M + 1個(gè)“零階截?cái)鄦涡尉Ц瘛北舜诉B接構(gòu)成。我們稱這M + 1個(gè)“零階截?cái)鄦涡尉Ц瘛睘椤傲汶A完全子圖”。一階截?cái)鄦涡尉Ц裆系膬刹窖莼校谝徊窖莼枰臅r(shí)間較長，并且是造成量子搜索不能達(dá)到平方加速效果的原因。而第一步從| s〉 ≈| g〉 演化到 | b〉 的過程，可以看成是兩個(gè)零階完全子圖之間的演化。然后我們選擇在零階完全子圖之間的邊上增加權(quán)值，即在圖2所示的虛線上增加權(quán)重ω。
用簡并微擾理論求解系統(tǒng)演化第一步的臨界跳躍率為γc1 = （1 + 1 / ω） / M，此時(shí)演化所需的時(shí)間為t1 = πM 3/2 / [2 （1 + ω）]。而第二步的演化是 | b〉 → | a〉，在圖2中是同一個(gè)零階完全子圖中不同點(diǎn)之間的演化，所以不受權(quán)值為ω邊的影響，所以系統(tǒng)演化的總時(shí)間為t′ = t1′+t2 = πM 3/2 / [2 （1 + ω）] + πM 1/2 / 2。當(dāng)ω = 1時(shí)，γc1 = 2 / M，且系統(tǒng)演化的時(shí)間為t1 = πM 3/2 / 4。但是我們?cè)黾应氐娜≈禃r(shí)，t1就可以減小。當(dāng)我們?nèi)? 時(shí)，就可以使 ，從而實(shí)現(xiàn)平方加速的效果[18]。
但是這樣的加速需要以降低系統(tǒng)演化成功的概率為代價(jià)。當(dāng)? 時(shí)，雖然系統(tǒng)演化的時(shí)間被縮短了，但是 | s〉 → | b〉 〉演化成功的概率從不加權(quán)時(shí)的接近100%降低到了30%左右。而其余70%左右的概率分別以40%左右的概率演化到了 | a〉 和30%左右的概率停留在了 | s〉。當(dāng)我們繼續(xù)增加ω到M時(shí)，取γc1 = 2 / 3M + 2 / M 2，系統(tǒng)經(jīng)時(shí)間t = πM / 1.83，以更高的概率演化到了 | a〉，而演化到 | b〉 的概率幾乎為0。如圖4所示，Pa表示系統(tǒng)演化到 | a〉 的概率，而Pb表示系統(tǒng)演化到 | b〉 的概率。此時(shí)，系統(tǒng)已經(jīng)從 | s〉 → | b〉 → | a〉 的兩步搜索合并成了 | s〉 → | a〉 的一步搜索，且時(shí)間 ，實(shí)現(xiàn)了平方加速的效果[12]。
圖4? 一階截?cái)鄦涡尉Ц裆舷到y(tǒng)演化的變化情況
3? 結(jié)? 論
連續(xù)時(shí)間量子行走算法是基于經(jīng)典馬爾可夫過程，對(duì)經(jīng)典游走的量子模擬算法。因其更適合解決圖表示的問題，所以相比較于Grover算法，更適合解決在結(jié)構(gòu)型數(shù)據(jù)庫上實(shí)現(xiàn)平方加速搜索的問題。
本文討論了通過對(duì)稱性分析對(duì)結(jié)構(gòu)型數(shù)據(jù)庫的結(jié)構(gòu)進(jìn)行分析，實(shí)現(xiàn)了系統(tǒng)演化所處希爾伯特空間的降維，并提供了確定臨界跳躍率γc的兩種方法，進(jìn)一步求得系統(tǒng)演化所需的時(shí)間，使系統(tǒng)能夠以較高概率演化到目標(biāo)狀態(tài)。最后我們討論了給圖上的邊增加權(quán)重對(duì)量子搜索的影響，并通過加權(quán)壓縮了系統(tǒng)演化的步驟，縮短了系統(tǒng)演化的時(shí)間，實(shí)現(xiàn)了平方加速。
雖然連續(xù)時(shí)間量子行走這一算法不是適用于所有搜索問題的通用解決方案，但它為解決一系列結(jié)構(gòu)型數(shù)據(jù)庫上的搜索問題提供了一種新的思路。至于進(jìn)一步探索其他確定臨界跳躍率γc的更簡便方法，以及連續(xù)時(shí)間量子行走算法在搜索問題上、或其他領(lǐng)域中的應(yīng)用等問題，對(duì)該算法的未來研究發(fā)展和進(jìn)一步拓展探究都具有重要作用。
參考文獻(xiàn)：
[1] GROVER K L. Quantum Mechanics Helps in Searching for a Needle in a Haystack [C]//Quantum Entanglement and Quantum Information--Proceedings of CCAST （World Laboratory） Workshop.Beijing：中國高等科學(xué)技術(shù)中心，1999：100-103.
[2] GROVER L K .Quantum Computers Can Search Arbitrarily Large Databases by a Single Query [J].Physical Review Letters，1997，79（23）：4709-4712.
[3] 薛鵬，王坤坤.量子行走 [J].光學(xué)學(xué)報(bào)，2024，44（2）：9-17.
[4] FARHI E，GUTMANN S .Quantum Computation and Decision Trees [J].Phys.rev.a，1997，58（2）：915-928.
[5] APERS S，CHAKRABORTY S，NOVO L，et al. Quadratic speedup for spatial search by continuous-time quantum walk [J/OL].Physical Review A，2021，95（3）：（2017-05-02）.https：//link.aps.org/doi/10.1103/PhysRevA.95.032301.
[6] DHAR D. Erratum：Lattices of effectively nonintegral dimensionality [J].J. Math. Phys.1977，18（12）：2520-2520.
[7] WONG T G，TARRATACA，LU?S TARRATACA，NAHIMOV N. Laplacian versus Adjacency Matrix in Quantum Walk Search [J]. Quantum Inf Process，2016，15：4029-4048.
[8] MOCHON C. Hamiltonian Oracles [J].Physical Review A，2007，75（4）：810-814.
[9] WANG Y，WU S. Role of symmetry in quantum search via continuous-time quantum walk [J/OL].SPIN，2021，11 （3）：2140002.https：//doi.org/10.1142/S2010324721400026.
[10] WONG，THOMAS G. Diagrammatic approach to quantum search [J].Quantum Information Processing，2015，14（6）：1767-1775.
[11] WANG Y，WU S，WANG W. Controlled quantum search on structured databases [J/OL].arXiv：2106.08398 [quant-ph].（2021-06-15）.https：//arxiv.org/abs/2106.08398.
[12] CHILDS A M. Optimal Quantum Adversary Lower Bounds for Ordered Search [C]//ICALP '08：Proceedings of the 35th international colloquium on Automata，Languages and Programming.Heidelberg：Springer-Verlag，2008：869–880.
[13] JANMARK J，MEYER D A，WONG T G .Global Symmetry is Unnecessary for Fast Quantum Search [J/OL].Physical Review Letters，2014，112（21）：210502（2014-05-28）.https：//link.aps.org/doi/10.1103/PhysRevLett.112.210502.
[14] MEYER D A，WONG T G. Connectivity is a poor indicator of fast quantum search [J/OL].Physical Review Letters，2015，114（11）：110503（2015-05-18）. https：//link.aps.org/doi/10.1103/PhysRevLett.114.110503
[15] CHAKRABORTY S，NOVO L，AMBAINIS A，et al. Spatial search by quantum walk is optimal for almost all graphs [J/OL].Physical Review Letters，2016，116（10）：100501 （2016-05-11）.https：//link.aps.org/doi/10.1103/PhysRevLett.116.100501.
[16] TANAKA H，SABRI M，PORTUGAL R. Spatial search on Johnson graphs by continuous-time quantum walk [J/OL].Quantum Information Processing，2022，21：74（2022-01-28）.https：//doi.org/10.1007/s11128-022-03417-9.
[17] APERS S，CHAKRABORTY S，NOVO L，et al. Quadratic speedup for spatial search by continuous-time quantum walk [J/OL].arXiv：2112.12746 [quant-ph].（2021-12-23）.https：//arxiv.org/abs/2112.12746.
[18] WONG，THOMAS G .Faster Quantum Walk Search on a Weighted Graph[J/OL].Physical Review A，2015，92（3）：032320 （2015-09-21）.https：//link.aps.org/doi/10.1103/PhysRevA.92.032320.
作者簡介：朱軒民（1983—）男，漢族，河南周口人，副教授，博士，研究方向：量子計(jì)算與量子信息；張德政（1998—），男，漢族，河北石家莊人，碩士在讀，研究方向：量子計(jì)算與量子信息。
- 現(xiàn)代信息科技的其它文章
- 基于深度神經(jīng)網(wǎng)絡(luò)的戰(zhàn)場(chǎng)信息網(wǎng)信息群發(fā)現(xiàn)技術(shù)
- 基于圖像重建的代謝腫瘤總體積分級(jí)模型
- 基于YOLOv7的礦工吸煙識(shí)別方法研究
- 基于區(qū)塊鏈的水下無線傳感器網(wǎng)絡(luò)惡意節(jié)點(diǎn)檢測(cè)機(jī)制
- 基于EWT和NeuralProphet-MLP的蜂窩網(wǎng)絡(luò)流量長期預(yù)測(cè)方法
- 中國通號(hào)FZL-300信號(hào)系統(tǒng)ATS分機(jī)設(shè)備原理及故障處理分析