散文網(wǎng) » 科技 »學(xué)習(xí) » 量子計(jì)算 [3] -- DeutscheJozsa算法

量子計(jì)算 [3] -- DeutscheJozsa算法

2021-04-06 12:27 作者:nyasyamorina 0人讀過(guò) | 我要投稿

算法簡(jiǎn)介

DeutscheJozsa算法是用于求解一個(gè)問(wèn)題:

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

傳統(tǒng)算法

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

給定一個(gè)范圍D,? 對(duì) f 進(jìn)行歷遍,? 當(dāng)存在兩種不一致的輸出時(shí),? 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),? 對(duì) f 進(jìn)行歷遍,? 如果存在不相同的輸出,? 則 f 為均衡函數(shù),? 否則 f 為常數(shù)函數(shù)

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

量子算法

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

之前說(shuō)過(guò),? 一個(gè)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時(shí)翻轉(zhuǎn), 沒(méi)有大問(wèn)題].? 有了 Uf,? 調(diào)用一次 Uf 就獲得全部結(jié)果成為可能

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

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

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