Quantum Walk in Graph

來自專欄 Cosmos4 人贊了文章

大約2015年4月結束了一個實驗，後面被boss指派去探索引力退相干的坑，半年沒有進展之後，我考慮在原實驗的裝置上是否可以來做做其他實驗。又經過半年的調研和模擬，自己覺得是可以做一些東西，可惜隨著衛星項目面臨發射，以及後續實驗計劃，組裡並沒有心思來仔細討論該方案。今天在翻資料的時候，又看到下面這一份報告，有些感慨，未料我的畢業方向也將是完全與此無關，只是當時覺得，到此該了結一個階段了。

報告放出來，做個告別。

Quantum Walk Review

• Quantum walk 基本要素:

1. Initial state ：對最終的QW分布有很大影響
2. Coin C：每一次對quantum state 進行一次幺正變換
3. Shift S :根據quantum state 經行一次walk，在walk空間也可以用幺正矩陣表示，walk 的位置分布態為X，整個過程寫成矩陣形式：

整體量子態：

變換矩陣：

一次Quantum Walk 則為：

走了n步後：

• Quantum Walk 的優勢與應用

1. 相比經典Random walk 有明顯的speedup，例如在一維兩者walk速度的對比為： ;
2. 用來構建搜索演算法，例如Grover Search Algorithm.其主要思想是：構建一個Oracle, f(x), 對輸入x的輸出為（1，0），目標點f(x)=1,其他點為零。即用來尋找某一個目標點。該演算法在trapped ion, NRM, cold atom 等系統裡面都已實現：

1998 Experimental Implementation of Fast Quantum Searching

2003 Experimental Implementation of Quantum Random Walk Algorithm

2005 Implementation of Grovers Quantum Search Algorithm in a Scalable System

他們實現都是通過兩bit量子態（4種）之間的walk，標記其中一種，附加一個不同的相位例如-1，使得經過一次或幾次變換後，在目標點概率達到最高。實際上是對一個均勻的輸入態經行設計好的U變換，使其在目標點出現。

基於graph的空間搜索演算法：在graph中標記一個特殊的點，或者子圖，對於常規點應用coin C, 特殊點應用coin C 最終行過walk之後找到該標記點或子圖。目前有一些理論以及方案文章，但還沒有看到實驗：

2004 Spatial search by quantum walk

2009 Searching via walking: How to find a marked subgraph of a graph using quantum walks

2009 Quantum searches on highly symmetric graphs

2008 Quantum walk based search algorithms

2016 Spatial search by quantum walk is optimal for almost all graphs

2016 Quantum algorithms: an overview

• 三個關鍵點：

1. 基於Graph的Quantum walk 實驗目前就2中的圓環型graph, complete graph等更複雜的還沒有。
2. 基於Graph可以做搜索演算法，理論成熟
3. 基於time bin 可以做complete graph，直接做quantum walk 很簡單，但是想要做搜索演算法，例如標記特殊點，需要可變Coin，目前想到的是可用PM來加高速的phase標記，但是會有一些損耗，可行性需要分析

K5 Simulation

K5光路圖

K5 Graph

or

Note: The first state for marked point search; The second state for k5 Quantum walk

每次walk的變換矩陣U：

• k5 Quantum walk

Python simulation:

5個位置點的概率分布

• K5 marked point search

Initial state 為均勻的位置疊加態(即上面第一個態），mark 點0，即所有走到0點時附加一個相位

Python 模擬數據

Point 0 的位置分布隨步數及Phase變化圖：

在加Pi phase時，3步之後，有0.8的概率走到0點，並且有一定的周期性。其他位置點概率比較小，說明具有搜索能力

數學模型：

參見：

2009 Searching via walking: How to find a marked subgraph of a graph using quantum walks

2009 Quantum searches on highly symmetric graphs

對於K5, marked point 0 的U矩陣可以寫出：

三個基矢：

初始態:

w2 態的概率即為在0點的概率，該模型與python模擬吻合。

• K5,K17, K65, K257 marked point 0 模擬（注意目前time bin 方案只有偶數個門與理論符合）

也可以實現Mark多個點，例如K257,marked 0,1：

實驗實現的技術要點

初態的製備：需要一個時間點上均勻的疊加態可以採用一串單偏振脈衝，作為時間上均勻的一個疊加態

Marked phase 如何加在一個時間點上：用PM？根據模擬，由於對稱性，在marked point 上態總是單一偏振態，與輸入初始態偏振一致，因此可以直接用PM來見Phase調製。注意：這種對稱性也是目前方案只能有偶數個門的原因，奇數個門會破壞這種對稱性，如何加phase才能正確模擬目前還需探索清楚。

損耗估計： 實現不同門的K圖走完一個周期的步數不同，2，4，6，8個門分別對應約4，10，22，44步左右如果走一步損耗3~6db，最大估計能走10步左右，可以設計4個門。但是如果只需要達到探測到標記點的概率接近1，則所需步數在：Sqrt(N)步左右，例如K65則需要8步左右

光路相位穩定：本質上需要相干疊加，如果4個門，17個點，以1ns一個點，走一圈17ns，10步總共需要170ns，預計問題不大，但是需保證每一個路徑的相對相位保持一致，因此每個門需要主動實時相位穩定，不需要高頻，但需要自動補償

延時必須精確：需要時間點上干涉，假設脈衝寬度300ps，如果4個門，走十步最多經過40次延遲，則需要每一步延時誤差範圍在150ps/40=3.75ps左右，1ps對應300um

附錄：Mathematica simulation

THE END

推薦閱讀：