量子計算学習ノート - 回路2

---

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。

---

前回は回路を構成するいくつかのゲートと、それを用いて自然数の和を求める回路を構成した。今回は和だけではなく、任意の関数を計算する回路がここまで使ってきたゲートで構成できることを示そう。

まず、簡単のために$${n}$$入力、$${1}$$出力の場合を示す。つまり任意の$${f: \{0,1\}^n \to \{0,1\}}$$なる関数を計算する回路が構成できることを示そう。このような関数はBool関数、回路はBool回路と呼ばれている。

数学的帰納法によって示そう。まず$${n = 1}$$の時、このような関数のパターンは次に示す$${f_1, f_2, f_3, f_4}$$の4つある。

$$
\begin{array}{c|cccc}
x & f_1(x) & f_2(x) & f_3(x) & f_4(x) \\ \hline
0 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1
\end{array}
$$

$${f_2}$$と$${f_3}$$は簡単だ。$${f_2}$$は入力を何も変えないので一本の配線に流した入力をそのまま出力すればよい(恒等関数)。$${f_3}$$は入力を反転しているので、NOTゲートを適用するだけでよい。
$${f_1, f_4}$$は補助入力の力が必要になる。$${f_1}$$は補助入力に$${0}$$を与え、入力とのANDゲートを取ることで出力を強制的に$${0}$$にすればよい。$${f_4}$$は補助入力に$${1}$$を与え、入力とのORゲートを取ることで出力を強制的に$${1}$$にすればよい。

さて、$${n = 1}$$の時は真であることがわかったので、$${n = k}$$の時、これが正しいことを仮定し、$${n = k+1}$$において正しいことを示す。今、適当な$${k + 1}$$個の入力から$${1}$$つの出力を得る関数を$${f(x_0, x_1, \cdots, x_k)}$$とおく。このとき$${k}$$個の入力から$${1}$$つの出力を得る関数$${f_0, f_1}$$をそれぞれ

$$
f_0(x_1, \cdots, x_k) \equiv f(0, x_1, \cdots, x_k) \\
f_1(x_1, \cdots, x_k) \equiv f(1, x_1, \cdots, x_k)
$$

によって定義する。仮定から$${f_0, f_1}$$を構成する回路は存在するため、以下のように回路を構成すると、これは$${f(x_0, x_1, \cdots, x_k)}$$を計算する回路となる。

f(x_0, x_1, … , x_k)を計算する回路

これで$${n}$$入力、$${1}$$出力の場合は証明された。では出力が$${m}$$個になった場合はどうだろうか。これも数学的帰納法で示そう。

$${1}$$の場合は証明済みだから、$${m = k}$$において回路が存在すると仮定して、$${m = k+1}$$について示すことにする。まず適当な関数$${f: \{0,1\}^n \to \{0, 1\}^{k+1}}$$を次のようにおくことにする。

$$
f(x_1, \cdots, x_n) = (y_0, y_1, \cdots, y_k)
$$

$${m = k}$$および$${m = 1}$$出力における回路は既に存在するから、次の関数$${f_1, f_k}$$に対する回路は存在することになる。

$$
f_1(x_1, \cdots, x_n) = y_0\\
f_k(x_1,\cdots, x_n) = (y_1, \cdots, y_k)
$$

したがって$${f}$$の回路は$${f_1, f_k}$$の回路の出力を結合することで得られるから、証明できたことになる。