ドイッチュ・ジョサのアルゴリズム
ドイッチュ・ジョサの問題では、オラクルと呼ばれるある関数 f : { 0 , 1 } n → { 0 , 1 } {\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}} が実装されたブラックボックス量子コンピュータが与えられている。 わかりやすく言えば、オラクルはn桁の2進数値を入力として受け取り、0または1を出力する。
ここで、関数 f {\displaystyle f} は定値 (すべての量子ビットが0 またはすべての量子ビットが1)であるか、均等 (量子ビットの丁度半数が1で、残りの半数が0)であることが保証されている。
問題は、オラクルを用いて関数が定値か均等かを決定することである。