ドイッチュ・ジョサのアルゴリズム

〇 関数の推測問題を解くアルゴリズム

〇 関数の推測問題は、次である。

● 入力が、nビット、出力が、1ビットの関数 f(x) が

・定数型
　すべてのxに対して、f(x) = 0 あるいは、f(x) =1

・分散型
　半分のxで、f(x) = 0 のこり半分で、f(x) = 1

のどちらであるかを判定する。

〇 古典コンピュータでは、2のn乗のオーダー、

量子コンピュータでは、n+1個のオーダーとなる。