本篇

Deutsche?Jozsa 算法原理

首先系統(tǒng)初始化為?|ψ? =?|0?,? 全部量子位通過H門制備均勻疊加態(tài)?

任何通過 Uf,? 使全部讓 f 為1的狀態(tài)的相位翻轉(zhuǎn),? 讓 f 為0的狀態(tài)則不進行任何操作?

再次讓全部量子位通過H門,? 產(chǎn)生干涉?.? 這里,? x · y是指在{0,1}^n空間里進行內(nèi)積,? 也就是?

這時候,? 測量系統(tǒng)得到 |0? 的概率為?

可以看到,? 當 f 為常數(shù)函數(shù)時,??測量系統(tǒng)得到?|0? 的概率為1;? f 為均衡函數(shù)時,? 累加項互相抵消變?yōu)?

量子黑盒

黑盒(Black Box)是指已知輸入和輸出范圍的未知操作,? 這里函數(shù) f 就是一個典型的黑盒

因為量子操作"不存在"輸出,? 所以黑盒只能在給出的量子位上進行操作.? 常見的黑盒為 相位(Phase)黑盒 和 標記(Marking)黑盒 兩種,? 下面分別介紹兩種黑盒的特性:? [設(shè)量子黑盒 Uf 有相應(yīng)的傳統(tǒng)黑盒 f, 并且 f 的輸出為0或1]

• 相位黑盒:? 翻轉(zhuǎn)特定狀態(tài)的相位.? 設(shè)|x?為某個特定的狀態(tài),? 如果f(x)=1,? 則翻轉(zhuǎn)|x?的狀態(tài),? 否則什么也不做,? 即?

• 標記黑盒:? 輸入數(shù)據(jù)位和結(jié)果位,? 結(jié)果位為1個量子位,? 調(diào)轉(zhuǎn)特定狀態(tài)時的結(jié)果位.? 設(shè)|x?為數(shù)據(jù)位,??|y?為結(jié)果位,? 如果f(x)=1,? 則把|0_y?和|1_y?互換,? 否則什么也不做,? 即?.? 標記黑盒也常寫作?

比較相位黑盒和標記黑盒,? 相位黑盒比標記黑盒節(jié)約了一個量子位,? 在繁瑣的黑盒調(diào)用時可以減少空間使用開銷.? 而標記黑盒不需要修改數(shù)據(jù)位,? 算法設(shè)計比較容易方便

DeutscheJozsa算法常用的黑盒

下面介紹幾種在DeutscheJozsa算法演示中常用的幾種黑盒,? 以演示相位黑盒的內(nèi)部邏輯

可以看到相位黑盒內(nèi)部邏輯比較特異化.? 如果函數(shù) f 的內(nèi)部邏輯不易"翻譯"為量子計算的話,? 使用相位黑盒將會非常困難.

相位反沖

相位反沖是一個把標記黑盒轉(zhuǎn)為相位黑盒的技巧,? 使得同時具有標記黑盒的算法易設(shè)計和相位黑盒的少量子位的特點.? 這個技巧需要一個臨時的額外量子位用于轉(zhuǎn)化,? 轉(zhuǎn)化完后這個量子位可以立即拋棄.

小例子:? 比較兩個量子位是否相同

設(shè)計標記黑盒,? 給出兩個數(shù)據(jù)量子位和一個結(jié)果位,? 如果兩個量子位相同則互換結(jié)果位的|0?和|1?:

試著運行一下:

可以看到 |000? 變?yōu)?|001?,??|110? 變?yōu)?|111?,? 也就是左邊兩位相同的狀態(tài)會把第3位的|0?變?yōu)閨1?,? 其他情況也可以自己測試

如果結(jié)果位原本的狀態(tài)是 |0?-|1?[忽略歸一化因子] ,? 并作用標記黑盒會怎么樣呢?? 因為如果 f(x) = 0時,? 標記黑盒和相位黑盒都不對量子位有影響,? 所以只考慮 f(x)=1時:??,? 可以看到這時候相當于結(jié)果位沒有改變卻在數(shù)據(jù)位上翻轉(zhuǎn)了相位.? 這就是相位反沖

繼續(xù)使用上面例子:? 加入一個包裝器把相位反沖應(yīng)用到標記黑盒上:

測試一下 IsEqualPhase:?

使用顏色表示相位,? 紅色為0,? 青色為π,? 可以看到|00?和|11?的相位都被翻轉(zhuǎn)了,? 則表明IsEqualPhase是一個相位黑盒