連續時間量子行走算法在截斷單形晶格上的搜索研究

朱軒民 張德政

收稿日期：2023-11-06

DOI：10.19850/j.cnki.2096-4706.2024.06.017

摘? 要：為證明連續時間量子行走算法在結構型數據庫上的搜索可以實現二次加速的效果，對結構型數據庫中的截斷單形晶格類型，進行了連續時間量子行走算法的應用研究。首先對截斷單形晶格進行對稱性分析，確定系統演化所處的希爾伯特空間，然后用哈密頓量本征態與基礎態的平方疊加、和簡并微擾理論兩種方法來求解系統演化需要的臨界跳躍率。最后通過對圖中的邊進行加權的方法，合并了量子搜索的步驟，縮短了系統演化的時間，從而實現了平方加速的效果，并表明了邊的權重對量子搜索過程的影響。

關鍵詞：量子計算；量子搜索；連續時間量子行走算法；結構型數據庫

中圖分類號：TP391? ? 文獻標識碼：A? 文章編號：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年提出量子計算的概念以來，量子游走算法一直被認為是實現量子計算的一個關鍵組成部分。特別是當Grover量子搜索算法在結構型數據庫中表現出的局限性，使其不能實現二次加速的最佳效果時，量子游走算法成為提高量子搜索效率的潛力算法[1，2]。

量子游走，又稱量子隨機行走算法，是經典隨機行走的量子版本。量子隨機行走算法分為離散時間量子行走和連續時間量子行走[3]。其中連續時間量子行走的思路來源于經典的連續型馬爾可夫過程，所以常借助于圖來進行描述，所以也更適合求解能夠表示成結構圖的問題，在量子領域中包括搜索、模擬、優化和圖論問題。在量子搜索的問題上，可以代替Grover算法在結構型數據庫中實現二次加速的搜索效果[4，5]。

本論文的目的是研究連續時間量子行走算法在截斷單行晶格中，解決量子搜索問題的應用。我們討論了階截斷單形晶格的結構特點，然后運用連續時間量子行走算法實現量子搜索.這一過程包括分析對晶格結構進行對稱性分析，并討論了尋找系統演化需要的臨界跳躍率的兩種方法。最后，我們通過對晶格上特定的邊進行加權對量子搜索的影響，并壓縮系統演化的時間，實現平方加速效果。

1? 連續時間量子行走算法在截斷單形晶格中的應用

截斷單形晶格因其具有有效的非整維數而得到了廣泛的關注[6]。一個零階截斷M維單形晶格是指一個由（M+1）個結點構成的完全圖，如圖1是一個零階6維單形晶格，其中用雙線圈圍成的點是目標態| a〉。單線圈圍成的點為演化相同的點，表示| b〉。當該完全圖上的各點均被一個M維完全圖取代時，就可以得到一個一階截斷M維單形晶格，如圖2是一個一階6維單形晶格。以此類推，一個r階截斷M維單形晶格是由一個（r-1）階晶格上的各點由M維完全圖取代得來。其中雙線圈圍成的點為標記點a，其余點，根據對稱性分析，演化情況相同的用相同的字母表示。

在量子系統中，信息用量子態表示。當結構型數據庫用圖表示時，圖中的結點表示系統的各量子態，即對應不同的信息。當數據庫用截斷單形晶格表示時，系統演化需要的哈密頓量可以用圖的拉普拉斯算子表示H = -γL，其中L = A - D。γ表示單位時間內，系統在鄰接點之間進行演化的概率振幅，被稱為跳躍率；A表示圖的鄰接矩陣；D表示以各點度數為對角元的對角矩陣。

因為截斷單形晶格是正則圖，即每個頂點都有相同的度數。在哈密頓量H的表達式中，D成為單位矩陣的整數倍。當省略D時，對搜索的效果并沒有影響。所以哈密頓量H中的拉普拉斯算符L可以用圖的鄰接矩陣A替代，即H = -γA。并且，在正則圖上使用連續時間量子行走算法時，用鄰接矩陣A或拉普拉斯算子L構造哈密頓量H，對實驗的結果并沒有影響[7]。

其次，為了表示我們需要搜索的目標態，我們將其在圖上對應的結點設置為標記點，如圖1中的點a。為了使系統演化到目標態，我們需要在哈密頓量H中引入一個oracle項，此時哈密頓量H可以表示為 [8]。

連續時間量子行走相較于離散時間量子行走，不需要硬幣空間，也不需要拋硬幣，但是需要找到一個合適的γ值，即臨界跳躍率γc，使系統可以從所處的初始狀態朝目標態的方向進行演化。接下來，我們將具體討論臨界跳躍率γc的求解過程。

1.1? 結構型數據庫的結構分析

對于如圖1所示的零階截斷N維單形晶格，即一個擁有（N+1）個結點的完全圖，我們可以將該系統對應的哈密頓量H表示為：

相應的，系統演化所處的希爾伯特空間是N+1維。

但是當系統較為復雜，N的數目較大時，處理N維矩陣就顯得較為困難。為此，我們需要對希爾伯特空間進行降維。設我們的目標態為| a〉，如圖1中的點a為我們目標態對應的標記點。此時圖1中的對稱性將被打破：標記點對應的態為| a〉；而其他非標記點因其對稱性相同，且晶格的對稱性和系統的演化情況之間具有一致性，所以它們的演化情況都相同，可以用同一個基礎態來表示：。由此，我們就可以用| a〉 和| b〉 來構成我們的希爾伯特空間。對應的哈密頓量就可以表示為：

希爾伯特空間就從原來的N+1維降為了2維[9]。

圖1? 零階6維單形晶格

類似的，我們可以用這種對稱性分析的方法處理更復雜的圖，如圖2的一階截斷6維單形晶格。該圖共有42個點。但是當我們引入標記點a，然后根據對稱性分析，我們可以將系統演化的希爾伯特空間降至7維，由{ | a〉 ，| b〉 ，| c〉 ，| d 〉 ，| e〉 ，| f 〉 ，| g〉 }組成。且分析證明，即使該一階截斷單形晶格的維數M增大時，這個7維不變子空間仍然適用。且這種對稱性分析的方法適用于其他正則圖結構如超立方體圖，和非正則圖結構如樹[10，11]。

圖2? 一階截斷6維單形晶格

1.2? 算法應用

當在結構型數據庫中進行搜索時，因為不知道和目標態有關的信息，所以我們選擇一個初態，使系統的概率是平均分配到圖上的每個點，即每個點或每個狀態都有可能是我們的目標。該初態也是物理實驗中較常采用和較易制備的，可以表示為 。如圖1的完全圖中，標記點用a表示，非標記點用b表示。系統哈密頓量可以表示為H = -γA - | a〉 〈a |。當結點數目很多時候，b點的數目N - 1≈N，所以初態| s〉 ≈| b〉。

我們解跳躍率γ取不同值時，哈密頓量H的本征值和本征態，并求本征態與基礎態的平方疊加，H = 100維的完全圖上如圖3所示。從圖中我們可以看出，當Nγ = 1，亦即γ = 1 / N時，H的本征態為 ，且兩本征態之間的能量差值最小為 。這里，γc = 1 / N即完成搜索需要的臨界跳躍率。此時，初態和系統的狀態可以表示為? 和

，系統狀態

會隨著時間的推移而在? 和? 之間進行周期性振動，

對應概率可以表示為 和 ，其中?E10 = E1 - E0。令

|〈a | Ψ （t）〉 | 2 = 1，得t = π / ?E10。所以，當γ = 1 / N時，經t = π / ?E10后，系統可以從| s〉? 演化到| a〉，搜索完成[5]。

圖3? 哈密頓量H的本征態和基礎態之間的平方疊加

除了上述取多個γ值，然后求哈密頓量本征態和基礎態之間平方疊加的方法外，我們還可以將簡并微擾理論應用到連續時間量子行走算法中，來求解臨界跳躍率γc和系統演化的時間t [10]。仍以圖1的完全圖為例，我們根據簡并微擾理論，將哈密頓量H拆分為H = H （0） + H （1）。其中? 是領先項， 是微擾項。領先項H （0）的本征態即| a〉 和| b〉 ，對應的本征值，即對應的能量為-1和-γN。當使兩本征態對應能量相等時，γ = γc = 1 / N，再引入微擾項H （1），系統的本征態可以用αa | a〉 + αb | b〉 表示。以{ | a〉，| b〉 }為計算基，將哈密頓量H重新展開，得本征態和本征值為? 和 。同樣的，取時間 ，系統可以從| b〉 演化到| a〉。因為當完全圖的點足夠多時，| s〉 ≈| b〉 。所以當γ = 1 / N時，經 ，系統可從初態| s〉 演化到目標態| a〉 。

當晶格階數增加，從零階增至一階時，系統的搜索需要兩步來完成。并且每一步需要的臨界跳躍率γc將有所不同。在使用簡并微擾理論進行求解時，也將需要對哈密頓量進行不同的拆分，且每一步選擇的領先項也將有所不同。特別是階數升至二階甚至更高階時，領先項的選擇將需要明顯參照系統演化發生的局部結構。總結規律得，設截斷單型晶格的階數為r，則搜索需要的步驟為步，對應的臨界跳躍率分別為γc1 = （r + 1） / M，γc2 = r / M，…，1 / M，所需時間為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為截斷單形晶格的維數，N是晶格所有結點的數量N = （M + 1） M r。當階數增加時，系統演化需要的時間也將增加，不能實現平方加速。我們可以通過增加圖中邊的權重，來縮短時間，我們在下一節中進行討論[11，12]。

除了截斷單形晶格以外，其他圖如超立方體圖、樹、d維拉丁圖和Johnson圖等也實現了用連續時間行走算法完成量子搜索[5，13-17]。連續時間量子行走算法的使用中，解哈密頓量H本征態和基礎態平方疊加的方法尋找臨界跳躍率γc應用較為廣泛，而簡并微擾理論目前只在截斷單形晶格和超立方體圖上得以成功運用[10]。

2? 實現平方加速

在截斷單形晶格上使用連續時間量子行走算法時，若晶格階數超過0時，系統演化將不能實現時間上的平方加速效果。如圖2的一階截斷6維晶格上，系統從初態? 演化到目標態| a〉，需要兩個步驟| s〉 → | b〉 → | a〉。兩個步驟對應的臨界跳躍率為γc1 = 2 / M和γc2 = 1 / M，對應的時間為t1 =

πM 3/2 / 4和t2 = πM 1/2 / 2。整個搜索過程系統演化需要的時間為t = t1 + t2 = πM 3/2 / 4 + πM 1/2 / 2 = Θ （M 3/2） = Θ（N3/4）。可見，此時的量子搜索不能達到平方加速的效果。

為了縮短量子搜索的時間，我們首先將一階截斷M維單形晶格看成是M + 1個“零階截斷單形晶格”彼此連接構成。我們稱這M + 1個“零階截斷單形晶格”為“零階完全子圖”。一階截斷單形晶格上的兩步演化中，第一步演化需要的時間較長，并且是造成量子搜索不能達到平方加速效果的原因。而第一步從| s〉 ≈| g〉 演化到 | b〉 的過程，可以看成是兩個零階完全子圖之間的演化。然后我們選擇在零階完全子圖之間的邊上增加權值，即在圖2所示的虛線上增加權重ω。

用簡并微擾理論求解系統演化第一步的臨界跳躍率為γc1 = （1 + 1 / ω） / M，此時演化所需的時間為t1 = πM 3/2 / [2 （1 + ω）]。而第二步的演化是 | b〉 → | a〉，在圖2中是同一個零階完全子圖中不同點之間的演化，所以不受權值為ω邊的影響，所以系統演化的總時間為t′ = t1′+t2 = πM 3/2 / [2 （1 + ω）] + πM 1/2 / 2。當ω = 1時，γc1 = 2 / M，且系統演化的時間為t1 = πM 3/2 / 4。但是我們增加ω的取值時，t1就可以減小。當我們取? 時，就可以使 ，從而實現平方加速的效果[18]。

但是這樣的加速需要以降低系統演化成功的概率為代價。當? 時，雖然系統演化的時間被縮短了，但是 | s〉 → | b〉 〉演化成功的概率從不加權時的接近100%降低到了30%左右。而其余70%左右的概率分別以40%左右的概率演化到了 | a〉 和30%左右的概率停留在了 | s〉。當我們繼續增加ω到M時，取γc1 = 2 / 3M + 2 / M 2，系統經時間t = πM / 1.83，以更高的概率演化到了 | a〉，而演化到 | b〉 的概率幾乎為0。如圖4所示，Pa表示系統演化到 | a〉 的概率，而Pb表示系統演化到 | b〉 的概率。此時，系統已經從 | s〉 → | b〉 → | a〉 的兩步搜索合并成了 | s〉 → | a〉 的一步搜索，且時間 ，實現了平方加速的效果[12]。

圖4? 一階截斷單形晶格上系統演化的變化情況

3? 結? 論

連續時間量子行走算法是基于經典馬爾可夫過程，對經典游走的量子模擬算法。因其更適合解決圖表示的問題，所以相比較于Grover算法，更適合解決在結構型數據庫上實現平方加速搜索的問題。

本文討論了通過對稱性分析對結構型數據庫的結構進行分析，實現了系統演化所處希爾伯特空間的降維，并提供了確定臨界跳躍率γc的兩種方法，進一步求得系統演化所需的時間，使系統能夠以較高概率演化到目標狀態。最后我們討論了給圖上的邊增加權重對量子搜索的影響，并通過加權壓縮了系統演化的步驟，縮短了系統演化的時間，實現了平方加速。

雖然連續時間量子行走這一算法不是適用于所有搜索問題的通用解決方案，但它為解決一系列結構型數據庫上的搜索問題提供了一種新的思路。至于進一步探索其他確定臨界跳躍率γc的更簡便方法，以及連續時間量子行走算法在搜索問題上、或其他領域中的應用等問題，對該算法的未來研究發展和進一步拓展探究都具有重要作用。

參考文獻：

[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：中國高等科學技術中心，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].光學學報，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—）男，漢族，河南周口人，副教授，博士，研究方向：量子計算與量子信息；張德政（1998—），男，漢族，河北石家莊人，碩士在讀，研究方向：量子計算與量子信息。