第6章可逆計算 — 古典計算を包含する
この章の目標
- 「量子ゲートはすべて可逆、古典ゲートは大半が不可逆」という非対称を理解する
- Toffoliゲートを使って AND/OR/NOT/ファンアウト を可逆に構成できるようになる
- 「量子コンピュータは古典計算をすべて実行できる」ことの構成的証明を手にする
- ゴミビットとアンコンピュート（計算の巻き戻し）のパターンを理解する
6.1 古典ゲートは情報を捨てる
古典のANDゲートは入力2ビット→出力1ビット。出力 0 からは入力が $(0,0), (0,1), (1,0)$ のどれだったか復元できません。情報を捨てる＝不可逆です。ところが量子回路のゲートはすべてユニタリで、ステップ1演習3-7で見た通り可逆でなければならない。とすると素朴な疑問が生じます：
「ANDすら実装できない量子コンピュータは、古典コンピュータより弱いのでは？」
この章の答えは「弱くない。どんな古典計算も、可逆な形に書き直して量子回路に乗せられる」です。CSの背景がある人にとって、このステップで一番面白い章になるはずです。
6.2 Toffoliゲート（CCNOT）
3ビットゲート。制御2本が両方 $|1\rangle$ のときだけ標的を反転する： $$|a\rangle|b\rangle|c\rangle \mapsto |a\rangle|b\rangle|c \oplus (a \wedge b)\rangle$$
q0: ──●──
│
q1: ──●──
│
q2: ──⊕──$8 \times 8$ の置換行列（$|110\rangle \leftrightarrow |111\rangle$ だけ入れ替え）で、明らかにユニタリ。2回掛けると元に戻る（自己逆）。
Toffoliの標的への作用 $c \oplus (a \wedge b)$ を見てください。ANDの結果をXORで書き込む形になっています。入力 $a, b$ は出力にそのまま残っているので、いつでも巻き戻せる＝可逆。「情報を捨てずに、答えを追記する」のが可逆計算の基本発想です。
6.3 Toffoli一つで古典論理が全部組める
補助ビット（アンシラ）を定数で用意すると、Toffoliから古典の基本ゲートがすべて出てきます：
| 作りたいもの | 構成 | 確認 |
|---|---|---|
| AND | Toffoli の標的に $c = 0$ を入れる | $|a, b, 0\rangle \mapsto |a, b, a \wedge b\rangle$ |
| NAND | Toffoli の標的に $c = 1$ を入れる | $|a, b, 1\rangle \mapsto |a, b, 1 \oplus (a \wedge b)\rangle = |a, b, \overline{a \wedge b}\rangle$ |
| NOT | $X$ ゲートそのもの | もともと可逆 |
| XOR | CNOT の標的 | $|a, b\rangle \mapsto |a, a \oplus b\rangle$ |
| ファンアウト（コピー） | CNOT の標的に $0$ | $|a, 0\rangle \mapsto |a, a\rangle$ — 基底状態なのでno-cloningに抵触しない（第5章5.2節） |
| OR | De Morgan: $a \vee b = \overline{\bar{a} \wedge \bar{b}}$ → $X$ 3枚 + Toffoli（演習6-3） |
NANDとファンアウトが揃えば古典回路は何でも組めます（NANDは古典の万能ゲート）。よって：
任意の古典論理回路は、Toffoli・CNOT・X と定数アンシラだけで、同じ計算をする可逆回路（＝量子回路）に機械的に変換できる。ゲート数の増加は定数倍。量子計算は古典計算を包含する。
この結論により、量子コンピュータの計算能力は古典コンピュータの真の上位互換です（能力の意味で。速度・コストの意味では現状オーバーヘッドが巨大です）。だからニュースで見るべき論点は「量子で計算できるか」ではなく「古典より速いか」だけです。そして高速化の源泉はこの章の古典部分ではなく、重ね合わせ＋干渉（ステップ3）にあります。この切り分けができると、量子計算の主張の評価が一気に正確になります。
6.4 ゴミビットとアンコンピュート
可逆化の代償として、回路には中間結果（ゴミビット）が残ります。例えば $f(a,b,c) = (a \wedge b) \wedge c$ を計算するには、まず $t = a \wedge b$ をアンシラに作り、次に $t \wedge c$ を計算します。この $t$ が出力に残り続けます。
古典なら無視すればよいゴミが、量子では実害になります：ゴミビットが主レジスタとエンタングルしていると、第4章の問4-7の「目撃者」となって以降の干渉を壊すのです。対策がアンコンピュート：
- 計算する（ゴミ $t$ が発生）
- 結果をCNOTで出力用レジスタに書き出す（基底状態のコピーなので合法）
- 手順1の逆回路を実行してゴミをアンシラの初期値 $|0\rangle$ に戻す（ユニタリは常に巻き戻せる——第5章問5-7）
結果: $|x\rangle|0\rangle_{\text{ancilla}}|0\rangle_{\text{out}} \mapsto |x\rangle|0\rangle_{\text{ancilla}}|f(x)\rangle_{\text{out}}$ — アンシラは綺麗に返却され、エンタングルも残らない。
「計算 → コピー → 巻き戻し」。この3拍子はステップ3で関数をオラクル $U_f: |x\rangle|y\rangle \mapsto |x\rangle|y \oplus f(x)\rangle$ として使うときの標準実装です。
from qiskit import QuantumCircuit
from qiskit.quantum_info import Operator
import numpy as np
qc = QuantumCircuit(3)
qc.ccx(0, 1, 2) # Toffoli (CCNOT)
U = Operator(qc).data.real.astype(int)
print(U) # |110⟩⇄|111⟩ だけ入れ替える置換行列
# AND として使う: q2 を |0⟩ にして a=1, b=1 を入れる
qc2 = QuantumCircuit(3, 1)
qc2.x(0); qc2.x(1) # a=1, b=1
qc2.ccx(0, 1, 2)
qc2.measure(2, 0) # 結果は必ず 1 (= 1 AND 1)演習6
Toffoliゲートの8行の真理値表を書き、(a) 出力から入力が一意に決まる（可逆）こと、(b) 2回適用すると恒等になることを確認せよ。
解答を見る
$000{\to}000$, $001{\to}001$, $010{\to}010$, $011{\to}011$, $100{\to}100$, $101{\to}101$, $110{\to}\mathbf{111}$, $111{\to}\mathbf{110}$。(a) 右側に重複がない（置換）ので可逆 ✓。(b) 入れ替わるのは最後の2行だけで、2回で元に戻る ✓。「可逆な古典ゲート＝真理値表が置換」という見方は、そのまま「置換行列＝ユニタリの特別な場合」につながります。
古典の基本ゲート AND, OR, XOR, NOT のうち、そのままで可逆なものはどれか。不可逆なものについて、出力から入力が復元できない実例を挙げよ。
解答を見る
可逆は NOT のみ（1対1）。XORも2入力1出力の形では不可逆です（$0 \oplus 0 = 1 \oplus 1 = 0$）——CNOTのように入力の片方を出力に残す形にして初めて可逆になります。AND: 出力0の原因は3通り。OR: 出力1の原因は3通り。「入力本数＞出力本数のゲートは必ず不可逆」（鳩の巣原理）にも注目。可逆化の一般手法が「入力を出力に残して、結果は追記する」である理由です。
De Morgan則 $a \vee b = \overline{\bar{a} \wedge \bar{b}}$ を使い、X と Toffoli で OR を構成する回路を書け（アンシラ $c = 0$ を使ってよい）。$a, b$ の4通りすべてで検算せよ。入力ワイヤの $a, b$ は最後に元の値に戻しておくこと。
解答を見る
q0(a): ──[X]──●──[X]──
│
q1(b): ──[X]──●──[X]──
│
q2(0): ───────⊕──[X]──手順：$a, b$ を反転 → Toffoliで $\bar{a} \wedge \bar{b}$ を書き込み → 標的を反転して $\overline{\bar{a} \wedge \bar{b}} = a \vee b$ → 入力側の $X$ を掛け直して $a, b$ を復元。検算：$(0,0)$: Toffoli制御は $(1,1)$ で標的1、反転して0 ✓。$(0,1)$: 制御 $(1,0)$ で標的0、反転して1 ✓。$(1,0)$, $(1,1)$ も同様に1 ✓。「反転して・ANDして・反転する」——古典の恒等式が回路の等価変形としてそのまま使えます。
3入力AND $a \wedge b \wedge c$ を、Toffoli 2個とアンシラ2本（初期値0）で構成せよ。さらにアンコンピュートを追加して、中間結果のアンシラを $|0\rangle$ に返却する完全版を書け。
解答を見る
q0(a): ──●───────●── Toffoli① : t = a∧b を anc1 に
│ │
q1(b): ──●───────●── Toffoli② : t∧c を anc2 に（これが答え）
│ │
q2(c): ──┼──●────┼── Toffoli③（=①と同じ）: anc1 を巻き戻す
│ │ │
anc1: ──⊕──●────⊕──
│
anc2: ─────⊕───────①で $t = a \wedge b$、②で $t \wedge c$ を出力用 anc2 に書き込み、③（①の再適用。Toffoliは自己逆）で anc1 を $0$ に戻す。最終結果：$|a,b,c\rangle|0\rangle|a \wedge b \wedge c\rangle$。「計算→書き出し→巻き戻し」の3拍子の最小例です。$n$ 入力ANDも同じパターンで、アンシラを積みながら計算し、逆順に巻き戻せば構成できます。
Toffoliに重ね合わせを入れる：入力 $|+\rangle|1\rangle|0\rangle$（$a$ が重ね合わせ、$b = 1$, $c = 0$）に対する出力を計算せよ。出力はエンタングルしているか。
解答を見る
線形性で分解：$\frac{1}{\sqrt2}(|010\rangle + |110\rangle)$ の各項にToffoliを適用。$|010\rangle$: 制御 $(0,1)$ → 不発 → $|010\rangle$。$|110\rangle$: 制御 $(1,1)$ → 標的反転 → $|111\rangle$。出力 $\frac{|010\rangle + |111\rangle}{\sqrt2}$。q0とq2だけ見ると $\frac{|0\rangle|0\rangle + |1\rangle|1\rangle}{\sqrt2}$ の形でエンタングルしています。古典回路として設計したToffoliが、重ね合わせを入れると自動的に「全分岐並列のAND計算機」になる——古典回路の可逆化がそのまま量子アルゴリズムの部品（オラクル）になる理由です。ANDの答えが $a$ の値と相関して書き込まれていることを確認してください。
アンコンピュートを省略するとどうなるか。問6-4の回路で③（巻き戻し）を省き、その後 q0 に $H$ を掛けて干渉を起こそうとした場合に何が起きるか、第4章の問4-7を踏まえて定性的に説明せよ。
解答を見る
anc1 には $a \wedge b$ が残っており、入力が重ね合わせなら anc1 は主レジスタとエンタングルしたままです。すると anc1 が「どの分岐だったか」の目撃者になり（問4-7と同じ構図）、q0 上の分岐同士は直交する相手と絡んでいるため干渉できません。$H$ を掛けても期待した打ち消し合いは起きず、アルゴリズムは壊れます。アンコンピュートは美観ではなく干渉の生死を分ける必須工程——「量子計算では、ゴミ掃除をサボると答えが消える」。メモリリークどころではない、量子ならではの規律です。
「Toffoliで古典計算を全部含めるなら、量子コンピュータのプログラムも普通のプログラミング言語のコンパイラで書けばよいのでは？」——この発想はどこまで正しく、どこから間違うか。この章と第4・5章の内容で答えよ。
解答を見る
正しい部分：算術・比較・ビット演算などの「古典的な部品」は実際にコンパイラ的に可逆回路へ機械変換され、量子アルゴリズム内のサブルーチン（オラクル、モジュラー演算など）として使われます。Shorのアルゴリズムの大部分は実はこの種の古典演算回路です。
間違う部分：(1) 機械変換した回路は古典と同じ速度でしか動かない——高速化は $H$ や位相・干渉という非古典部品の設計から来るので、そこは自動化できない。(2) 古典プログラムの前提（コピー、ログ、分岐での破壊的代入）は可逆化・no-cloning・測定制約に合わせて書き直しが要る。(3) ゴミ管理（アンコンピュート）がアルゴリズムの正しさ自体に食い込む。まとめ：「古典部分は機械的、量子的な旨味は手作り」。この境界線が見えていれば、量子ソフトウェアの現状（回路コンパイラ、Qiskitのtranspiler）の立ち位置も正確に理解できます。