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

---

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

---

前回、有限数ビットから有限数ビットを出力するあらゆる関数に対して、その関数を計算する回路が存在することを示した。この記事ではそのようなあらゆる回路は実はNANDゲートだけあれば構成できることを示す。

前回構成した回路の構成要素には次の4つがある。

1. 配線

2. 補助ビット

3. FANOUT

4. AND、XOR、NOTゲート

このうち、実は4の要素は幾分冗長であり、実はNANDゲートだけあれば、任意の関数を計算する回路を構成できる。言い換えればAND、XOR、NOTゲートは1、2、3の利用が許されるときNANDゲートを使って構成できる。

まず、NOTをNANDで構成することを考えよう。補助ビット$${1}$$と入力$${x}$$に対してNANDを適用すると、これはNOTゲートと等価になる。

$$
NAND(1,x) = NOT(AND(1,x)) = NOT(x)
$$

ANDゲートはNOTゲートが構成されたので、次のように構成可能だ。

$$
NOT(NAND(x,y)) = NOT(NOT(AND(x,y))) = AND(x,y)
$$

最後にXORゲートを構成する。

$$
\begin{array}{l}
XOR(x,y) \\
= OR(AND(x,NOT(y)), AND(NOT(x),y))\\
= OR(NOT(NOT(AND(x,NOT(y)))), NOT(NOT(AND(NOT(x),y))))\\
= OR(NOT(NAND(x,NOT(y))), NOT(NAND(NOT(x),y)))\\
= NOT(NOT(OR(NOT(NAND(x,NOT(y))), NOT(NAND(NOT(x),y)))))\\
= NOT(AND(NAND(x,NOT(y)), NAND(NOT(x),y)))\\
= NAND(NAND(x,NOT(y)), NAND(NOT(x),y))
\end{array}
$$

以上より、AND、XOR、NOTをNANDを用いて表現することができたので、任意の関数はNANDゲートだけで構成できることが分かった。