已知有一個函數(shù)?a,? 求使得?f 輸出1的輸入總數(shù).

求解這個問題的算法叫做量子計數(shù)(Quantum Counting).? 實際上這個算法是Grover算法和相位估計的結(jié)合應用.? 所以這里也不詳細敘述了.

在Grover算法的附章里,? 詳細討論了在n個量子位系統(tǒng)里,? 單次迭代過程對態(tài)的變換為 ,? 其中為Grover擴散算子,? 為量子相位黑盒版的未知函數(shù)f,? 為均勻疊加態(tài)在空間與的夾角,? 為全部使未知函數(shù)f輸出為1的態(tài)的疊加,? 為全部使未知函數(shù)f輸出為0的態(tài)的疊加,? 為全部的數(shù)量,? 為全部態(tài)的數(shù)量.

不難知道,? 單次迭代的特征態(tài)與特征值為? ,?;? , .? 使用相位估計可以求出θ,? 進而求出M,? 即使未知函數(shù) f 輸出為1的輸入數(shù)量.

因為特征態(tài)乘上一個非零系數(shù)也是特征態(tài),? 所以和也分別是單次迭代的特征態(tài).? 這兩個態(tài)的疊加態(tài)為 = ,? 也就是說特征態(tài)的疊加剛好為容易制備的均勻疊加態(tài).

使用相位估計對Grover算法里的單次迭代分析,? 測量結(jié)果得到 和 ,? 即,? 又因為,? 得,? 最后求得.

由相位估計的誤差分析不難知道,? 最佳測量值與實際值之間存在誤差 ,? 其中m是用于相位估計的量子位數(shù)量.? 求解誤差為?= = ,? 因為?和 * ,? 所以,? 即.??

因為測量計算后的結(jié)果很可能為小數(shù),? 所以需要進行四舍五入.? 為了得到準確的M,? 自然有條件,? 即? ?????? .? 一般情況下,? 有.? 特別地,? 使用,??在時誤差取極大值,? 即.

* 對于|ΔM/N|=|sin(π(φ+Δφ))+sin(πφ)||sin(π(φ+Δφ))-sin(πφ)|,? 確實有|sin(π(φ+Δφ))-sin(πφ)|<=π|Δφ|,? 但|sin(π(φ+Δφ))+sin(πφ)|<=|2sin(πφ)+πΔφ|在Δφ<0時不一定成立.? 實際上這步不是很嚴謹,? 但是教材都這樣寫,? 而且對后續(xù)推導沒有太大影響,? 就這樣子吧.

下面以之前用作Grover算法的例子 -- 圖形著色問題實際操作一下,? 因為大部分代碼都在之前演示過,? 這里只給出關鍵代碼.

需要注意的是,? 上面討論的Grover擴散算子定義為,? 但實際上比較常用的版本為,? 可以看到兩個版本相差了一個相位π,? 測量后計算M需要注意一下這個差異.

需要注意的是,? 盡管運行精度已經(jīng)足夠測量出準確結(jié)果,? 但是相位估計算法依然有可能給出偏差比較大的結(jié)果從而造成很大的誤差.? 上述代碼里的圖為4個頂點,? 并且4個頂點之間全部連接,? 只有4個頂點都為不同顏色才是正確的著色方案,? 即總共正確答案數(shù)量為 4! = 24 個.

在實際使用中,? 量子計數(shù)常搭配Grover算法一起使用,? 而Grover算法并不需要準確的M,? 并且如果M遠遠小于N時,? 相位估計精度m=n+2實在是overkill.? 所以m=n+2總共還是拿來玩玩就好,? 計算速度實在是硬傷.

你以為我又要推銷瑟圖群和垃圾庫了?? 我這次就不推了? (

一晚上趕出來的專欄,? 困shi了.? 封面隨便在瑟圖庫里找了一張圖,? 用latex做封面其實也很花時間好吧.