量子計算QuantumComputingCalvinTang

179209347@Deutsch問題

Deutsch

的問題就是：

如果有一個符合以上條件的未知函數(shù)，那么如何嘗試最少且足夠的次數(shù)，來確定它是常數(shù)函數(shù)還是平衡函數(shù)。量子計算算法-單量子比特4種可能操作

平衡函數(shù)：常數(shù)函數(shù)：現(xiàn)在問題是：假設(shè)有一個函數(shù)操作，我們只知道它是四種操作里的一種，但我們可以用輸入輸出進(jìn)行測試，那么，要確定屬于平衡函數(shù)還是常數(shù)函數(shù)，我們最少做幾次測試？Oracle

Oracle

注：古希臘時期，Oracle是Delphi的阿波羅神廟女祭司，她們有時會對詢問的問題給出yes或no的回復(fù)。而在量子計算里：Oracle代表的功能是輸入數(shù)據(jù)，輸出1（yes）

或0(no)。

量子計算里，Oralce可以表示為：Oracle-量子計算算法

Oracle

000011101110Deutsch（多伊奇）算法推導(dǎo)-2個量子比特HHH|0?

|1?

輸入兩個量子比特，一個|0?

一個|1?

，所以：

Deutsch（多伊奇）算法推導(dǎo)-2個量子比特

HHH|0?

|1?

Deutsch（多伊奇）算法推導(dǎo)-2個量子比特

HHH|0?

|1?

Deutsch（多伊奇）算法推導(dǎo)-2個量子比特

HHH|0?

|1?

Deutsch（多伊奇）算法推導(dǎo)-2個量子比特

測量0結(jié)果都為1，即說明是常數(shù)函數(shù)。

HHH|0?

|1?

Deutsch（多伊奇）算法推導(dǎo)-2個量子比特

HHH|0?

|1?

Deutsch（多伊奇）算法推導(dǎo)-2個量子比特

測量0結(jié)果都為0，即說明是平衡函數(shù)。HHH|0?

|1?

Deutsch-Jozsa算法–推廣到n個量子比特

Deutsch-Jozsa算法–推廣到n個量子比特HHH

|1?

Deutsch-Jozsa算法–推廣到n個量子比特

所以有：

HHH

|1?

Deutsch-Jozsa算法–推廣到n個量子比特

所以有：HHH|1?

Deutsch-Jozsa算法–推廣到n個量子比特

HHH|1?

Deutsch-Jozsa算法–推廣到n個量子比特

由于：Deutsch-Jozsa算法–推廣到n個量子比特

Deutsch-Jozsa算法–推廣到n個量子比特HHH|1?

|

0?

|

1?

|

2?

|

3?

Deutsch-Jozsa算法–推廣到n個量子比特HHH|1?

|

0?

|

1?

|

2?

|

3?

Deutsch-Jozsa算法–推廣到n個量子比特HHH|1?

|

0?

|

1?

|

2?

|

3?

這里，我們只關(guān)注如下取值情形：

所以有：

Deutsch-Jozsa算法–推廣到n個量子比特

所以有：同樣，我們只關(guān)注如下取值情形：

Deutsch-Jozsa算法–2個量子比特線路設(shè)計（1/3）

|0?

|1?

InputAInputBOutputAOutputB輔助輸入冗余輸出X

常數(shù)函數(shù)：Deutsch-Jozsa算法–2個量子比特線路設(shè)計（2/3）f(x)=x平衡函數(shù)：|0?

|1?

InputAInputBOutputAOutputB輔助輸入冗余輸出+Oracle

Deutsch-Jozsa算法