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

---

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

---

これまでは計算モデルとしてチューリング機械を扱ってきたが、チューリング機械は少し理想化されたモデルだった。というのもテープの長さは片方に無制限であり、実際のコンピュータは記憶領域は有限であることに反している。そこで回路による計算モデルを導入しよう。

回路による計算モデルは後に示すが計算能力としてチューリング機械と等価であり、多くの応用に対してより便利かつ現実的だ。実際量子コンピュータの準備のために回路モデルは重要である。

回路モデルは論理ゲートから構成される。論理ゲートはある定数$${k}$$個の入力から$${l}$$個の出力を行う関数$${f: \{0,1\}^k \to \{0, 1\}^l}$$を計算する。いくつかの論理ゲートを紹介しよう。

まずはNOTゲートだ。これは次のような関数を計算する。

$$
NOT: \{0,1\}\to \{0,1\},\ NOT(x) = 1 \oplus x
$$

これにより入力ビットをその内容によらず、もう片方の内容に反転することができる。

なお、計算の回路モデルにおいては不安定性を避けるため、回路内の出力の一部を再び回路の入力とするような「ループ」を許容しないこととする。このような回路の性質を非巡回的（acyclic）という。

別の論理ゲートについても見てみよう。次はAND, OR, XORだ。これらは2入力、1出力の論理ゲートである。

$$
AND: \{0,1\}^2 \to \{0,1\},\ AND(x,y) = x \land y\\
OR: \{0,1\}^2 \to \{0,1\},\ OR(x,y) = x \lor y\\
XOR: \{0,1\}^2 \to \{0,1\},\ XOR(x,y) = x \oplus y
$$

次にNAND, NORである。

$$
NAND: \{0,1\}^2 \to \{0,1\},\ NAND(x,y) = \neg (x \land y)\\
NOR: \{0,1\}^2 \to \{0,1\},\ NOR(x,y) = \neg (x \lor y)
$$

さらに、FANOUT、CROSSOVER(FO, CO)といったゲートも許容される。これらによって補助ビットや作業ビットを準備して、計算途中で別の作業領域を作成することができる。

$$
FO: \{0,1\} \to \{0,1\}^2,\ FO(x) = (x,x)\\
CO: \{0,1\}^2 \to \{0,1\}^2,\ CO(x,y) = (y,x)
$$

さて、これらの簡単な回路要素を組み合わせることで数えきれないほどの種類の計算をすることができる。まずは半加算器HA(half-adder)だ。これは$${x,y}$$のXORと、繰り上がりの情報を出力する。

$$
\begin{array}{l}
HA: \{0,1\}^2 \to \{0,1\}^2\\
HA(x,y)\\
= (AND(\pi_1(CO(x)), \pi_1(CO(y))),XOR(\pi_2(CO(x)), \pi_2(CO(y)))) \\
= (x \land y, x \oplus y)
\end{array}
$$

ここで$${\pi_n}$$は順序対のn番目の射影（n番目の要素を取り出したもの）である。

半加算器を構成できると全加算器FA(full-addr)を構成できる。全加算器は3つのビットをとり、2つのビットの加算と前の計算からの繰り上がりをさらに足し合わせる。結果として1ビットとさらなる繰り上がり1ビットを出力する。

$$
\begin{array}{l}
FA: \{0,1\}^3 \to \{0,1\}^2\\
FA(x,y,z)\\
= (OR((\pi_1(HA(x,y)), \pi_1(HA(\pi_2(HA(x,y)),z))), \pi_2(HA(\pi_2(HA(x,y)),z))) \\
= (c, x \oplus y \oplus z)
\end{array}
$$

ここで、 cはx,y,zのうち2つ以上1なら1、そうでなければ0である。

半加算器と全加算器の組み合わせで任意のビット数同士の自然数の和を実現できる。

さて、少数の決まったゲートだけを用いて任意の関数を計算できるのだが、これについては次の記事で述べよう。