檢視多他奇-喬薩演算法的原始碼

'''多他奇-喬薩算法'''（英語：Deutsch–Jozsa algorithm）是戴維持 ・ 多他奇和里查德 ・ 撨薩佇一九九二年提出的一種確定性量子算法。一九九八年，理察 ・ 克利夫、阿圖而 ・ 埃克特、基礎 ・ 馬基亞韋洛（Chiara Macchiavello）佮米凱萊 ・ 莫斯卡嘿其進行矣改進行。就算應該算法目前佇現實中基本無用途，但是會當證明伊比任何可能的確定性經典算法攏強欲指數級，是提早的有這个特別的量性算法之一。

==問題是咧講==

咧濟伊奇-喬薩問題當中，咱有一个予人號做是預言機的烏盒仔量子計算機，伊能實現某一函數 $ f \ colon \ { 零 , 一 \ } ^ { n } \ rightarrow \ { 零 , 一 \ } $。該函數以 n 比特值作為輸入，輸出結果則為零抑是一。問題承諾該函數愛遮是定函數（即對任何輸入攏輸出恆定值零抑是一）， 欲按怎是平衡（balanced）函數（即對一半的輸入返回一，另外一半回倒轉來）。 問題的任務是通過預言機確定 $ f $ 是常函數抑是平衡函數。

==問題背景==

多他奇-喬薩問題是專門為量仔計算設計的一个問題，該問題對量子算法來講是相對簡單，但是對任何確定性經典算法來講攏是十分困難的。其提出的動機是展示會當由量子計算機有效而且正確解決的一个烏盒仔問題，啊若同時確定性經典計算機著愛需要進行大量算才有法度解決這个問題。閣較準確來講，該問題表明矣複雜度類 EQP（即可以由量子計算機佇咧多項式時間內精確地解決）佮 P 之間的預言分離（oracle separation）。

因為這个問題佇咧概率經典計算機頂懸嘛真容易解決，伊袂產生佮複雜度類 BPP（即在概率經典計算機上以多項式時間解決而且精差有界）之間的預言分離。西蒙問題是一个證明 BQP 和 BPP 之間產生預言分離的例。

==經典算法==

對傳統的確定性算法來講，準講 _ n _ 是比特數，則佇上歹的狀況下需要 $ 二 ^ { n 影一 } + 一 $ 次對 $ f $ 的求值。為著證明 $ f $ 是常函數，著愛對超過一半的輸入來進行計算並且發現𪜶有仝款的輸出。上好是狀況 $ f $ 為平衡函數而且拄好選擇的前兩个輸入值對應無仝的輸出值。對傳統的隨機算法，$ k $ 次求值得很以產生高概率正確答案（著 $ k \ geq 一 $ 錯誤概率為 $ \ epsilon \ leq 二分之一 ^ { k } $）。 毋過，想欲保證得著正確的答案，猶原需要 $ k=二 ^ { n 影一 } + 一 $ 次求值。多他奇-喬薩量仔算法則干焦需要一擺對 $ f $ 求值得就會當準確的答案。

==歷史==

多他奇-喬薩問題是戴維 ・ 多他奇早上工作（一九八五年）的推廣。彼當陣伊提出的算法針對的是 $ n=一 $ 的簡單情形，即有一个輸入做一比特的布爾函數 $ f : \ { 零 , 一 \ } \ rightarrow \ { 零 , 一 \ } $，需要確定這个函數敢是定函數。

濟伊奇上早提出的算法實際上並毋是確定性的。一九九二年，濟伊奇佮喬薩共同提出一種確定性的算法，並且這个算法來推廣 $ n $ 比特的輸入值。佮濟伊奇的算法無仝，該算法需要兩擺互相函數求值。

後來克利夫等人閣對濟伊奇-喬薩算法進行矣改進，提出一種既具有確定性閣干焦需要一擺 $ f $ 求值的算法。毋過為著欲紀念濟伊奇佮喬薩兩个人開創性的貢獻，該算法猶原予人叫做是多伊奇-喬薩算法。

==算法==

多他奇-撨薩算法成立的前提一是由 $ x $ 計算 $ f ( x ) $ 的預言機著愛是一个袂共 $ x $ 退相干的量仔預言機。此外，伊嘛袂當佇算法結束了後留任何 $ x $ 的副本。

準講咱有 $ n + 一 $ 比特量子態 $ | 零 \ rangle ^ { \ otimes n } | 一 \ rangle $，即前 n 比特分別佮 $ | 零 \ rangle $ 抑若上尾一比特則是講 $ | 一 \ rangle $。對每一个比特應用阿達馬變換會用得著


: $ { \ frac { 一 } { \ sqrt { 二 ^ { n + 一 } } } } \ sum _ { x=零 } ^ { 二 ^ { n } 影一 } | x \ rangle ( | 零 \ rangle-| 一 \ rangle ) $ .

$ f $ 是由量仔來預言機實現的函數。預言機會量子態 $ | x \ rangle | y \ rangle $ 炤著 $ | x \ rangle | y \ oplus f ( x ) \ rangle $，其中 $ \ oplus $ 是模二加法（由受著控制非門實現，會當看做是量仔版異抑是門）。 所以這个量子來講機會當共述量子態轉換做


: $ { \ frac { 一 } { \ sqrt { 二 ^ { n + 一 } } } } \ sum _ { x=零 } ^ { 二 ^ { n } 影一 } | x \ rangle ( | f ( x ) \ rangle-| 一 \ oplus f ( x ) \ rangle ) $ .

對著每一个 $ x , f ( x ) $ 的結果替零抑是一。為著檢驗這兩種可能性，咱注意著頂懸的量態等價數佇咧


: $ { \ frac { 一 } { \ sqrt { 二 ^ { n + 一 } } } } \ sum _ { x=零 } ^ { 二 ^ { n } 影一 } ( 影一 ) ^ { f ( x ) } | x \ rangle ( | 零 \ rangle-| 一 \ rangle ) $ .

現此時會使失覺察最後一个量比特 $ { \ frac { | 零 \ rangle-| 一 \ rangle } { \ sqrt { 二 } } } $，後壁的部份為著：


: $ { \ frac { 一 } { \ sqrt { 二 ^ { n } } } } \ sum _ { x=零 } ^ { 二 ^ { n } 影一 } ( 影一 ) ^ { f ( x ) } | x \ rangle $ .

閣對每一量比特進行阿達馬變換，得著


: $ { \ frac { 一 } { \ sqrt { 二 ^ { n } } } } \ sum _ { x=零 } ^ { 二 ^ { n } 影一 } ( 影一 ) ^ { f ( x ) } \ left [{ \ frac { 一 } { \ sqrt { 二 ^ { n } } } } \ sum _ { y=零 } ^ { 二 ^ { n } 影一 } ( 影一 ) ^ { x \ cdot y } | y \ rangle \ right]={ \ frac { 一 } { 二 ^ { n } } } \ sum _ { y=零 } ^ { 二 ^ { n } 影一 } \ left [\ sum _ { x=零 } ^ { 二 ^ { n } 影一 } ( 影一 ) ^ { f ( x ) } ( 影一 ) ^ { x \ cdot y } \ right] | y \ rangle $

其中 $ x \ cdot y=x _ { 零 } y _ { 零 } \ oplus x _ { 一 } y _ { 一 } \ oplus \ cdots \ oplus x _ { n 影一 } y _ { n 影一 } $ 是每一比特相應乘積之和。

最後咧，咱會使檢驗測量得著 $ | 零 \ rangle ^ { \ otimes n } $ 的概率


: $ { \ bigg | } { \ frac { 一 } { 二 ^ { n } } } \ sum _ { x=零 } ^ { 二 ^ { n } 影一 } ( 影一 ) ^ { f ( x ) } { \ bigg | } ^ { 二 } $

當 $ f ( x ) $ 是常函數（相長干涉）時此概率為一，當 $ f ( x ) $ 是平衡函數（相消干涉）就按呢概率為零。嘛會使講，若是 $ f ( x ) $ 是常函數就按呢測量結果為 $ | 零 \ rangle ^ { \ otimes n } $（即所有量仔比特全為零）， 其他結果愛表明講 $ f ( x ) $ 是平衡函數。

==多他奇算法==

多他奇算法是一般多他奇-撨薩算法的特例。現此時咱需要檢查 $ f ( 零 )=f ( 一 ) $ 敢若成立是。這佮檢查相當的 $ f ( 零 ) \ oplus f ( 一 ) $，做結果共零時仔表明 $ f $ 是常函數，若無毋是常函數。

咱對兩个比特量子態 $ | 零 \ rangle | 一 \ rangle $ 開始，對每一量比特應用阿達馬變換，結果為著


: $ { \ frac { 一 } { 二 } } ( | 零 \ rangle + | 一 \ rangle ) ( | 零 \ rangle-| 一 \ rangle ) . $

函數 $ f $ 會當將 $ | x \ rangle | y \ rangle $ 炤做 $ | x \ rangle | f ( x ) \ oplus y \ rangle $，將此函數應用佇咧當前的量子態，會用得著


: $ { \ frac { 一 } { 二 } } ( | 零 \ rangle ( | f ( 零 ) \ oplus 零 \ rangle-| f ( 零 ) \ oplus 一 \ rangle ) + | 一 \ rangle ( | f ( 一 ) \ oplus 零 \ rangle-| f ( 一 ) \ oplus 一 \ rangle ) ) $


: $={ \ frac { 一 } { 二 } } ( ( 影一 ) ^ { f ( 零 ) } | 零 \ rangle ( | 零 \ rangle-| 一 \ rangle ) + ( 影一 ) ^ { f ( 一 ) } | 一 \ rangle ( | 零 \ rangle-| 一 \ rangle ) ) $


: $=( 影一 ) ^ { f ( 零 ) } { \ frac { 一 } { 二 } } \ left ( | 零 \ rangle + ( 影一 ) ^ { f ( 零 ) \ oplus f ( 一 ) } | 一 \ rangle \ right ) ( | 零 \ rangle-| 一 \ rangle ) . $

忽略上尾一个比特佮全局相位因為，會用得得著量的子態


: $ { \ frac { 一 } { \ sqrt { 二 } } } ( | 零 \ rangle + ( 影一 ) ^ { f ( 零 ) \ oplus f ( 一 ) } | 一 \ rangle ) . $

閣再應用阿達馬變換，得著


: $ { \ frac { 一 } { 二 } } ( | 零 \ rangle + | 一 \ rangle + ( 影一 ) ^ { f ( 零 ) \ oplus f ( 一 ) } | 零 \ rangle-( 影一 ) ^ { f ( 零 ) \ oplus f ( 一 ) } | 一 \ rangle ) $


: $={ \ frac { 一 } { 二 } } ( ( 一 + ( 影一 ) ^ { f ( 零 ) \ oplus f ( 一 ) } ) | 零 \ rangle + ( 一-( 影一 ) ^ { f ( 零 ) \ oplus f ( 一 ) } ) | 一 \ rangle ) . $

若是唯若欲測量結果 $ | 零 \ rangle $ 時有 $ f ( 零 ) \ oplus f ( 一 )=零 $。反之，若是唯若欲測量結果 $ | 一 \ rangle $ 時有 $ f ( 零 ) \ oplus f ( 一 )=一 $。所以阮會使肯定知影講 $ f ( x ) $ 敢是常函數。

==參考文獻==

[[分類: 待校正]]