計資中心電子報C&INC E-paper

作者：張晏瑞 / 中原大學智慧運算與大數據碩士學位學程助理教授

---

量子行走（Quantum Walk）是古典隨機行走的量子類比，在量子計算領域中是設計量子演算法的重要工具​。與傳統的隨機漫步不同，量子行走利用量子疊加和干涉來實現全新的動態行為。本文將回顧量子行走的基本概念，介紹其在量子計算中的應用（例如搜尋演算法、圖論問題、路徑優化等），並說明一個具體的量子行走搜尋演算法。

 

量子行走在量子計算中的應用

由於量子行走能夠比傳統隨機行走更快速地探索狀態空間​並利用干涉濃縮成功機率，它在各種量子演算法中扮演了重要角色​。以下列舉量子行走在幾個典型領域的應用：

1.搜尋演算法中的量子行走

資料搜索是量子行走最突出的應用之一。著名的Grover 演算法其實可以被視為一種特殊的量子行走，其在無結構資料庫中搜尋標記項的過程可通過量子行走的框架來理解​。一般而言，基於量子行走的搜尋演算法通常能夠實現與Grover演算法相當的平方級加速：相對於古典$O(N)$的線性複雜度，量子行走搜尋可在約$Ｏ(\sqrt{N})$的步驟內找到目標。

具體來說，量子行走可用於在圖或資料結構中尋找特殊節點或元素。例如，量子行走搜尋演算法（Quantum Walk Search）透過在狀態空間構造一個對應的圖，將目標元素對應為圖中的「標記」頂點，然後讓量子行走者在圖上演化來擴大標記頂點的振幅​。當演化進行一段時間後，行者的位置在標記節點的機率大幅上升，測量即可發現目標。這類演算法廣泛適用於無結構資料庫搜尋、滿足特定性質解的尋找等。Neil Shenvi、Julia Kempe 和 K. Birgitta Whaley 在2003年的工作中率先提出了利用量子隨機行走進行資料庫搜尋的演算法[1]，證明了量子行走方法確實能夠找到標記項並實現與Grover相同量級的加速​。總體而言，基於量子行走的搜尋演算法已成為量子計算中搜尋問題的一種關鍵方案，在理論上提供了比古典搜尋更快的運算效率。

 

2.圖論與網路問題中的應用

 

Figure 1 全連結有向圖：量子行走在圖論與網路問題中的應用示意圖

 

圖論領域提供了量子行走大展身手的自然舞台。因為量子行走本質上就是在圖上進行的遍歷，其可用來解決許多圖相關的計算問題。例如，在圖中尋找特殊結構（如發現是否存在三角形迴路）的問題上，基於量子行走的演算法可比傳統演算法取得多項式級別的加速​。又例如，著名的元素區別問題（element distinctness，判斷一列表中是否有重複元素）就可以轉化為圖上的遍歷問題，通過量子行走技術實現比最優古典演算法更快的解法​。

在網路分析方面，量子行走也被視為一種有前景的工具​。例如，量子PageRank演算法即是利用量子行走來評估網路中節點的重要性，其構想是將Google PageRank使用的隨機遊走模型替換為量子行走，以期望更快地收斂或得到不同的網路排名結果。同樣地，量子行走的命中時間（hitting time，首次到達特定頂點的所需步數）可用於衡量網路中的連通性或中心節點。值得一提的是，在某些特殊構造的圖上，連續時間的量子行走甚至能夠展現出指數級的速度優勢——例如Childs等人的研究展示了量子行走可以在一種特殊設計的「焊接樹」圖上實現對古典演算法指數級別的超越​[2]。雖然這類指數加速通常局限於人工設計的問題，卻凸顯了量子行走潛在的強大威力。

 

3.路徑優化與其他優化問題

由於量子行走能同時探索多條路徑並通過干涉強化優良解的機率，它也被嘗試應用於各種組合優化和路徑優化問題中。例如，在尋找最短路徑或旅行推銷員問題這類路徑優化難題中，量子行走理論上可以將搜索空間並行探索，搭配適當的振幅放大機制來提升找到最優解的機率。雖然對於NP困難問題目前並無已知的量子多項式時間解法，但量子行走提供了一種可能的啟發式途徑，使得搜索過程較古典演算法更有效率。更一般地，量子行走已被應用於量子優化演算法的設計，包括將古典馬可夫鏈蒙地卡羅方法量子化（由Szegedy提出的方法）以實現加速[3]。這種方法將古典隨機過程轉換為對應的量子行走演化，能在求解滿意度問題、圖著色等優化挑戰中取得平方級的加速​。

除了上述領域，量子行走在機器學習和密碼學等新興領域也開始展現應用潛力​[4]。例如，量子行走可用於構造量子強化學習的環境模型，或設計抗量子隨機遊走難題的加密原語。不論是在何種應用中，量子行走的核心優勢在於其能利用量子平行性與干涉，以不同於古典隨機過程的方式高效地探索狀態空間，從而為各類計算問題提供潛在的加速。

結語

量子行走將量子力學的疊加與干涉原理引入了隨機行走模型，提供了一種全新的計算範式。在量子計算與演算法領域，量子行走已被成功應用於搜尋、圖論、優化等多種問題，展現出相對古典演算法的加速優勢​。我們從解析量子行走的基本概念，了解到硬幣位元和受控移動是其核心組成，並透過分析量子隨機行走搜尋演算法，加深了對其工作機制的理解。下篇文章中，我們將提供一個簡單的 Python/Qiskit 程式實作示範，模擬量子行走的過程並解析程式碼運作方式。

對於有志於量子計算的讀者而言，量子行走是值得深入研究的主題。一方面，它具有優美的理論性質，將古典隨機過程與量子演化緊密聯繫；另一方面，它在實際演算法設計中已證明能帶來速度提升。隨著量子硬體的不斷進步，越來越多基於量子行走的演算法有望在實驗中得到驗證，為我們解決複雜計算問題帶來新的可能性。希望本文的介紹能夠幫助讀者建立對量子行走的清晰認識，為進一步學習量子演算法奠定基礎。祝各位在量子世界的探索旅程中「漫步」愉快！