トフォリ(CCX)ゲートを基本ゲートに分解する｜実機で動く形へ

トフォリ（CCX＝制御制御NOT）は「2つの制御がどちらも1のときだけ標的を反転」する便利なゲートですが、実機は3量子ビットゲートを直接は実行できません。1・2量子ビットの基本ゲートに分解する必要があります。この記事ではQiskitで分解し、それが正しいことを検証します。

なぜ分解が必要か

実機が持つのはアダマール・T・CNOTなどの限られた基本ゲートだけ。トフォリのような複雑なゲートは、これらの組み合わせにトランスパイルして初めて動きます（トランスパイルの話）。

準備

pip install qiskit

① トフォリを基本ゲートに分解

Qiskitに分解を任せ、どんな基本ゲートに化けるか見ます。

from qiskit import QuantumCircuit, transpile

qc = QuantumCircuit(3)
qc.ccx(0, 1, 2)              # トフォリ

basis = ["h", "t", "tdg", "cx"]
decomposed = transpile(qc, basis_gates=basis, optimization_level=0)
print("分解後のゲート:", dict(decomposed.count_ops()))
print("CNOTの数:", decomposed.count_ops().get("cx", 0))

出力例: {'h': 2, 't': 4, 'tdg': 3, 'cx': 6}。トフォリ1個が CNOT6個＋T系7個 に分解されます。「たった1ゲート」に見えても、実機では十数ステップに膨らむのです。

② 分解が正しいか検証

分解前後のユニタリ行列が一致すれば、同じ演算だと証明できます。

from qiskit.quantum_info import Operator
import numpy as np

u_orig = Operator(qc).data           # 分解前のトフォリ
u_deco = Operator(decomposed).data   # 分解後の回路

print("一致？:", np.allclose(u_orig, u_deco))

一致？: True。分解しても演算は完全に同じ。見た目は複雑になりますが、正しく等価です。

まとめ

• トフォリ(CCX)は実機では直接実行できず、基本ゲートに分解が必要
• Qiskitのtranspileでアダマール・T・CNOTに分解される（CNOT約6個）
• ユニタリ行列の一致で分解の正しさを検証できる
• CNOT数が実機コストの目安

もう少し詳しく（背景と理論）

トフォリ（CCX）ゲートは古典的には万能（AND/NOTを作れる可逆論理）ですが、量子でも標準的な普遍ゲート集合（例: クリフォード＋T）へ分解できます¹。よく使われる分解はアダマール・T・T†・CNOT からなり、CNOT を6個・T 系を7個必要とします²。ここで T ゲートの個数（T-count） が特に重要で、フォールトトレラント量子計算では T ゲートが最もコストの高い操作になるため、T-count の最小化が回路最適化の中心課題です³。多制御トフォリ（制御が3個以上）は補助量子ビットを使うとゲート数を線形に抑えられます⁴。

次の一歩 🌸

分解を担うのはトランスパイル、ゲートの基礎は量子ゲート入門、状態ベクトルの裏側はNumPyで作る量子シミュレータへどうぞ。

Footnotes

1. クリフォードゲート（H, S, CNOT）だけでは普遍量子計算にならず（Gottesman–Knill）、トフォリや T ゲートなど非クリフォード要素を加えて初めて普遍になる。 ↩

2. 標準的なトフォリ分解は CNOT 6個＋アダマール2個＋T/T† 7個。Operator の一致で等価性を検証できる（本文③）。 ↩

3. 誤り耐性計算では T ゲートは「マジック状態蒸留」を要し、クリフォードより桁違いに高コスト。T-count / T-depth の削減が回路コンパイラの主要な最適化目標になる。 ↩

4. n 制御トフォリは補助ビットを使えば O(n) 個の基本ゲートに、使わなくても O(n²) 程度に分解できる（Barenco et al., 1995）。 ↩