算法簡介

DeutscheJozsa算法是用于求解一個問題:

有一個未知的函數(shù)? f: {0,1}^n → {0,1}?[這個函數(shù)是接收n個0或1, 輸出1個0或1],? 已知這個 f 要么是常數(shù)函數(shù)(Constant function),? 要么是均衡函數(shù)(Balance function)[均衡函數(shù)的意思是說 f 對于所有可能的輸入, 有一半輸出0, 另外一半輸出1].? 設(shè)計算法檢測 f 是常數(shù)函數(shù)還是均衡函數(shù)

傳統(tǒng)算法

因為函數(shù)輸入是n個0或1,? 把輸入看作一個二進(jìn)制數(shù),? 那么? f: x → {0,1}; x ∈ Z∩[0, 2^n)

給定一個范圍D,? 對 f 進(jìn)行歷遍,? 當(dāng)存在兩種不一致的輸出時,? f 不是常數(shù)函數(shù),? 那么 f 即是均衡函數(shù).? 如果 f 是均衡函數(shù),? 那么在

范圍Z∩[0, 2^n)里有一半輸入到 f 后輸出為同樣的結(jié)果,? 那么為了確定 f 是否為常數(shù)函數(shù),? 范圍D的大小至少為 2^(n-1)+1

于是傳統(tǒng)算法為:? 在大小為?2^(n-1)+1 的范圍D內(nèi),? 對 f 進(jìn)行歷遍,? 如果存在不相同的輸出,? 則 f 為均衡函數(shù),? 否則 f 為常數(shù)函數(shù)

不難看出,? 如果 f 為常數(shù)函數(shù),? 則需要調(diào)用函數(shù)?2^(n-1)+1 次,? 或者在第?2^(n-1)+1 次時才有不相同的結(jié)果,? 運氣好的話第2次就可以得到與第1次不一樣的結(jié)果

量子算法

因為量子位門屬于可逆邏輯門,? 所以所有量子計算都在已有的量子位上進(jìn)行,? 而不會輸出任何結(jié)果.? 為此,? 需要把函數(shù) f 進(jìn)行"可逆化"

之前說過,? 一個n量子位系統(tǒng)的狀態(tài)可以表示為? |ψ? = c_0|0? + ... + c_{2^n-1}|2^n-1?.? 不妨把"可逆化"的 f 記為 Uf.? Uf 把所有 f 輸出為1的狀態(tài)的相位進(jìn)行翻轉(zhuǎn)?[當(dāng)然也可以設(shè)為 f 為0時翻轉(zhuǎn), 沒有大問題].? 有了 Uf,? 調(diào)用一次 Uf 就獲得全部結(jié)果成為可能

所有量子位都以?|0? 初始化,? 為了制備均勻疊加的量子態(tài),? 可以對所有量子位通過H門, 用3量子位做示例:

把擁有均勻疊加的量子位系統(tǒng)通過 Uf 后,? f 的所有輸出已經(jīng)蘊(yùn)含在量子位的相位里.? 但因為測量量子位會使量子位坍縮到測量結(jié)果里而失去其他狀態(tài)的信息,? 并且不存在有效測量相位的途徑,? 所以還不能得到需要的結(jié)果

這時候把量子位狀態(tài)互相干涉,? 即通過H門.? 之后,? 測量所有量子位.? 如果 f 為常數(shù)函數(shù),? 則干涉會在|0?增長,? 而在其他狀態(tài)消減為0,? 如果 f 為均衡函數(shù),? 則在|0?消減為0.? 所以如果測量結(jié)果全為0,? 表明 f 為常數(shù)函數(shù),? 否則為均衡函數(shù)

可以看到量子算法里只對未知函數(shù)調(diào)用了1次,? 相較于傳統(tǒng)算法最少2次, 最多2^(n-1)+1次,? 加速效果是非常明顯的

數(shù)學(xué)細(xì)節(jié)可以期待一下未來的附章

DeutscheJozsa算法盡管沒有實機(jī)用途,? 但是作為量子計算入門是一個非常好的實例了

算法演示:? [github.com/nyasyamorina/nyasQuantumCalculate/blob/main/examples/2-DeutschJozsaAlgorithm.py]

日常推自制庫和瑟圖群: [https://github.com/nyasyamorina/nyasQuantumCalculate]? [274767696]