量子計算学習ノート - 回路モデルとチューリング機械モデル

---

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

---

以前、回路による計算モデルとチューリング機械による計算モデルは計算できる関数のクラスが同じという意味で等価であると述べた。ここではそれを示そう。

まず、回路族$${\{C_n\}}$$という集合を考えることにする。回路族とは特定の関数$${C: \mathbb{N} \to \mathbb{N}}$$を計算する回路$${C_n}$$を集めた集合である。ここで$${C_n}$$は$${n}$$ビット入力および有限個の補助ビットを用いて、有限ビット出力を行う回路だ。
入力$${x}$$に対して回路$${C_n}$$の出力は$${C_n(x)}$$と表現される。また回路族は矛盾がないことを要求する。つまり$${m \lt n}$$ビットを用いて入力値$${x}$$が表現可能な時、$${C_m(x) = C_n(x)}$$であることを要求する。

具体的に$${C(x) = x^2}$$を計算する回路族を考えよう。入力値$${x}$$が$${n}$$ビットによって表現が可能な時、$${n}$$ビットの入力を得てその二乗値を計算する回路を$${C_n}$$とする。この時$${C(x) = x^2}$$を計算する回路族とは$${\{C_n\}}$$となる。$${C_n}$$単体ではたとえ$${n}$$が十分大きくても、それよりも多くのビットを表現するのに利用する値の二乗値を計算できなくなってしまうので、あえて回路族を考える必要があることに注意する。

さて、回路族を考えれば回路モデルとチューリング機械モデルの等価性を述べるのに十分か？というとそうではない。実際、停止関数$${h(x)}$$に対してチューリング数$${x}$$が$${n}$$ビットで表現できたとすると、停止関数は$${n}$$ビット入力、$${1}$$ビット出力の関数である。このような関数を計算する回路$${C_n}$$が存在することは前回の証明で示されていて、回路族$${\{C_n\}}$$によって停止関数$${h(x)}$$が計算できることになってしまう。

しかしこれは、回路族$${\{C_n\}}$$を実際に構成できればの話である。回路族が存在することと、それが構成できるか、つまり任意の$${n}$$に対して$${C_n}$$を構成するアルゴリズムがあるか、という話は別の問題である。

このため、回路族の一様性という性質について議論する必要がある。回路族$${\{C_n\}}$$が一様な回路族であるとは、$${n}$$を入力すると回路の構成$${C_n}$$を出力するアルゴリズムが存在する、つまりチューリング機械上で回路構成の出力が行える時を言う。逆に、一様でない回路族は非一様な回路族と呼ばれる。

停止関数のアルゴリズムは存在しないのであるから、当然停止関数を計算できる回路族は一様な回路族ではなく、非一様な回路族である。この回路族の一様性によって、回路の計算モデルとチューリング機械の計算モデルの計算可能な関数のクラスは完全に一致する。つまり、チューリング機械で計算可能な関数のクラスは一様な回路族によって計算可能な関数のクラスと厳密に一致する。