目的

可逆論理回路勉強ノートです。間違っていたら指摘お願いします。

可逆ゲート

以下のゲートについて、古典論理回路に対応する可逆回路を示します。

NOT
XOR
バッファ
AND
OR
デコーダ

NOT

論理反転です。

$a$	$\bar{a}$
0	1
1	0

反転操作は可逆なので普通に反転するだけでも OK です。量子ゲートではパウリ X ゲートを使用します。

XOR

$a$	$b$	$ a \oplus b $
0	0	0
0	1	1
1	0	1
1	1	0

制御付きノットゲートは XOR としても解釈できます。
可逆性を保つためにどちらか一方の入力の情報は保存していなければなりません。

バッファ

制御付きノットゲートの入力を 0 に固定するとバッファとして使えます。
これがなぜ重要なのかについては後で説明します。

AND

$a$	$b$	$ a \land b $
0	0	0
0	1	0
1	0	0
1	1	1

トフォリゲートは入力を 0 に固定すると AND として使えます。
可逆性を保つために入力の情報は保存していなければなりません。

入力が多い場合も多入力のトフォリゲートを用いて同様に書けます。

OR

AND の入出力を反転してやれば OR が得られます。

デコーダ

トフォリゲートが AND として使える、ということから古典回路のデコーダをほぼそのまま可逆計算回路に焼き直すことができます。

$a$	$b$	$ n=3 $	$ n=2 $	$ n=1 $	$ n=0 $
0	0	0	0	0	1
0	1	0	0	1	0
1	0	0	1	0	0
1	1	1	0	0	0

ゴミの消去

可逆操作の組み合わせで計算しようとすると、多くの場合、情報の捨て場としてゴミが発生します。$∣0⟩$ を入力に使って AND を実現したりしていますが、なにか最終的な結果を得るために途中結果として用いたがもう不要である、もう一度 $∣0⟩$ に戻せるなら再利用もできるだろうに、というような場合です。あるいは入力ビットを破壊してしまうこともありえます。

可逆操作を組み合わせて作った計算回路を $U$ と書くことにします。

$U$ で行った可逆操作を逆順にした操作を考えることもできて、これを $U^\dagger$ と書くことにします。

おもしろいことに、$U$ の結果にそのまま $U^\dagger$ を作用させるとゴミを含めてすべての操作を元に戻すことができます。

これでゴミはきれいな状態に戻ります。しかし、これだけだとせっかく計算した内容まで元に戻ってしまってなにも行わなかったのと代わりがありません。そこで、制御ノットゲートを用いて計算結果を取り出してやります。

まとめ

代表的な古典論理回路について、それに対応する可逆論理回路を並べてみました。また、計算の途中で発生するゴミを消去する方法についても記述しました。
量子計算も可逆計算の範囲ならなんとか数式を使わずに理解できそうです。