本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #810
- 日期：2026-03-18
摘要
最近，研究表明，一維量子遊走可以比經典隨機遊走更快地混合，這表明量子蒙特卡羅演算法可以優於經典演算法。我們研究了 n 維超立方體上的兩種量子行走，一種在離散時間，一種在連續時間。在這兩種情況下，我們都表明量子行走以 $(\pi/4)n$ 步混合，比經典行走所需的 $O(n log n)$ 步更快。在連續時間的情況下，此時的機率分佈是完全均勻的。更重要的是，這些行走揭示了量子行走混合時間定義中的幾個微妙之處。儘管連續時間遊走具有精確均勻的 $O(n)$ 瞬時混合時間，但當像 [AharonovAKV2001] 中那樣隨機選擇停止時間時，它永遠不會接近均勻分佈。我們的分析比循環行走所必需的更仔細地處理不同階段項之間的干擾；先前的一般邊界預測超立方體的指數混合時間，而不是線性混合時間。