作者：張晏瑞 / 中原大學智慧運算與大數據碩士學位學程助理教授
隨著量子計算的快速發展，量子行走（Quantum Walk）成為了一個備受關注的研究領域。它作為傳統隨機行走的量子版本，利用量子疊加、量子干涉等特性，展現出超越經典計算方法的潛力。本文將介紹量子行走的基本概念、主要類型及其應用前景。
量子行走的發展
量子行走的概念最早由物理學家Aharonov等人於1993年提出，目的是在量子計算中模擬隨機行走。此後，隨著量子計算研究的深入，量子行走逐漸成為量子算法的重要基礎之一。經過多年的理論研究與實驗探討，量子行走已被廣泛應用於量子搜尋、量子模擬及量子計算複雜度分析等領域，其發展前景不容小覷
量子行走的基本概念
量子行走是一種量子計算框架，用於模擬複雜系統的動態行為。與古典的隨機行走不同，量子行走利用了量子力學中的疊加與干涉特性，使得量子行走的步伐具有更大的靈活性與可控性。古典隨機行走依賴於隨機的二元結果（例如擲硬幣決定前進方向），而量子行走則基於量子位元的量子態，使得行走者可以同時處於多個路徑的疊加狀態，從而提升計算能力。
在古典隨機行走中，行走者的移動由一個古典硬幣決定，每次擲硬幣的結果確定行走者的方向，例如「1」表示向右移動，「0」表示向左移動。經過多次擲硬幣後，行走者的位置形成了一個二項分佈的最終結果。
相對而言，量子行走利用了量子態的疊加和相位特性。行走者可以同時沿多條路徑移動，每條路徑的狀態都是以疊加的形式存在。由於量子干涉的影響，這些路徑相互干涉，最終形成一個不同於古典隨機行走的機率分佈，這種分佈在計算效率和靈活性上展現出顯著優勢。
Figure 1. 古典和量子行走示意圖從而提升計算能力。
量子行走的主要類型
量子行走主要分為離散時間量子行走（Discrete-Time Quantum Walk, DTQW）和連續時間量子行走（Continuous-Time Quantum Walk, CTQW）。在DTQW中，行走者的移動是通過一個量子幣操作運算來決定的，該操作運算類似於古典行走中的擲硬幣過程。然而，量子幣的設置可以根據參數進行調整，使得量子行走可以適應不同的計算需求。而CTQW則是通過哈密頓量來控制行走者的動態，其運行過程是連續。
離散時間量子行走的運行機制
在離散時間量子行走（DTQW）中，量子行走的運行依賴於兩個主要的運算符：硬幣運算符 $\mathcal{C}$ 和移動運算符 $\mathcal{S}$。硬幣運算符 $\mathcal{C}$ 負責改變量子幣的狀態，而移動操作符 $\mathcal{S}$ 則決定行走者的位置。量子行走的整體運行可以用一個演化運算符 $\mathcal{W}=\mathcal{S}\cdot\mathcal{C}$ 來表示，其中$\mathcal{W}$是行走的演化運算符。在具體操作上，硬幣運算符$\mathcal{C}$作用於行走者的量子幣態，改變其量子態。移動運算符$\mathcal{S}$則根據量子幣的態來決定行走者的移動方向。這兩個運算符的結合使得行走者可以同時探索多條路徑，形成量子疊加態。與古典典隨機行走相比，這種量子行走的分佈通常顯示出更為複雜的干涉圖樣，行走者可以在量子態空間中探索多條路徑，並最終形成一個量子行走的分佈，從而展現出量子行走的計算優勢。
以下以$\mathcal{H}$閘來代表硬幣運算符$\mathcal{C}$的量子行走演化示範：
假設初始狀態為 $|0\rangle_p \otimes |0\rangle_c$，其中第一個量子態表示位置，第二個量子態表示量子幣的態。演化操作符 $\mathcal{W}=\mathcal{S}\cdot\mathcal{H}$ 的作用過程如下：
第一步
- 應用 H 閘（硬幣運算符）在量子幣上： \[H|0\rangle_c = \frac{1}{\sqrt{2}}(|0\rangle_c + |1\rangle_c)\] 這意味著量子幣現在處於疊加態，50%機率處於狀態 $|0\rangle_c$ 50%機率處於狀態 $|1\rangle_c$。
- 移動操作符 $\mathcal{S}$ 根據幣態進行移動：
- 若幣態為 $|0\rangle_c$，行走者向左移動。
- 若幣態為 $|1\rangle_c$，行走者向右移動。
因此 $\mathcal{S}$ 運算後，整個系統的量子態變為：
\[|\psi\rangle = \frac{1}{\sqrt{2}}(|-1\rangle_p \otimes |0\rangle_c + |1\rangle_p \otimes |1\rangle_c)\]
第二步
再次 H 閘運算在量子幣上，系統的量子態成為：
\[|\psi\rangle = \frac{1}{2}(|-1\rangle_p \otimes (|0\rangle_c + |1\rangle_c) + |1\rangle_p \otimes (|0\rangle_c - |1\rangle_c))\]
再次應用移動運算符 $\mathcal{S}$，根據硬幣量子態移動行走者，量子態：
\[|\psi\rangle = \frac{1}{2}(|-2\rangle_p \otimes |0\rangle_c + |0\rangle_p \otimes |1\rangle_c + |0\rangle_p \otimes |0\rangle_c - |2\rangle_p \otimes |1\rangle_c)\]
結語
量子行走作為量子計算中的一個關鍵工具，展現了其在模擬複雜系統和提高計算效率方面的巨大潛力。透過離散時間量子行走的演化示範，我們可以清楚地看到量子行走利用量子疊加與干涉特性，形成複雜的干涉圖樣，這不僅提升了計算能力，還開闢了新的計算方法和應用領域的廣闊前景。隨著量子計算技術的快速進展，量子行走的應用將不再僅限於理論探討，而是逐漸走向實際應用，對量子搜尋、量子模擬及其他量子技術領域產生深遠的影響。
在未來的量子技術發展中，量子行走將扮演越來越重要的角色，成為解決複雜問題的關鍵技術之一。這一技術的進步不僅推動了量子計算的發展，也為我們打開了探索新型量子算法的視野，為未來的量子技術奠定了堅實的基礎。
下篇文章中，我們將介紹「如何利用Qiskit模擬量子行走」，進一步探索其應用潛力。
參考資料
- Chang, YJ., Wang, WT., Chen, HY. et al. A novel approach for quantum financial simulation and quantum state preparation. Quantum Mach. Intell. 6, 24 (2024). https://doi.org/10.1007/s42484-024-00160-5