Deutsch-Jozsa アルゴリズムの回路を見る前におさらいをしたい。
ここだけの記号として $S_n = \{0, 1\}^n$ と置く。
今回 $f: S_n \to \{0, 1\}$ なる、定数あるいはバランス関数を考えるのであった。こういうコンテキストでは $f$ は “オラクル” と呼ばれるらしい。$x \in \Z_{\geq 0}$ に対し、$x=x_1x_2\cdots x_n$ という 2 進展開を考えることで、$x_1x_2\cdots x_n \mapsto \{x_1, x_2, \cdots, x_n\}$ を同一視して $x \in S_n$ と考えることができる。
この $f$ はとりあえず未知なのだが、$f$ の情報を持つようなユニタリゲート $U_f$ として $U_f: \ket{x}\ket{y} \mapsto \ket{x}\ket{y \otimes f(x)}$ なるものと考える。ニールセン&チャンでは $U_f: \ket{x,y} \mapsto \ket{x,y \otimes f(x)}$ と書いているが同じことである。
このゲート $U_f$ を使った回路上で測定を行うと $f$ の性質が分かるということだが、$U_f$ を $f$ に依存せずに用意できないので、誰が与えてくれるのだろう？という疑問はある。ニールセン&チャンを読むと
3.2.5 項で $f$ を計算する古典回路が与えられれば量子コンピュータ上で変換 $U_f$ を同程度の効率で計算する量子回路が存在することを示す。我々の目的には $U_f$ はブラックボックスと考えて良い。
とある。よって、定数あるいはバランス関数 $f$ をとった時、$U_f: \ket{x}\ket{y} \mapsto \ket{x}\ket{y \otimes f(x)}$ を満たす $U_f$ がとれるので、これを測定者に与える。“この条件のもとで、測定者は古典アルゴリズムより少ない計算量で $f$ の性質を特定できるか？” ということが課題だと思う。
まとめると、
- $\ket{0}^{\otimes n} \ket{1}$ を入力として用意する。
- 与えられたゲート $U_f$ を使って組んだ回路に上記を入力し、出力を測定する。
- $\ket{y} = \ket{0}^{\otimes n}$ を観測する確率は $ \mathrm{Prob}(\ket{0}) = \left| \frac{1}{2^n} \sum_{x=0}^{2^n-1} (-1)^{f(x)}\right|^2$ であるという理論から $f$ の性質を判定する。
という量子アルゴリズムによって、計算量 $\mathcal{O}(1)$ で $f$ を判断できますというのがこの Deutsch-Jozsa アルゴリズムということだろう。
