SWAP パズル

いつもならとっくに寝ているはずの時間ですが、アリスは自宅ガレージで量子フーリエ変換回路の調整にいそしんでいます。 明日は小学校の量子コンピュータクラブの発表会で、自慢の量子プログラムをみんなの前でお披露目するからです。

「そっちはどんな調子?」

同じクラブのボブから、チャットが飛び込みました。 返信しようとした瞬間、アリスは飲んでいた牛乳をカスタムキーボードの上にこぼしてしまいました。 これは自作量子コンピュータを操作するための特製キーボードで、 量子ゲートを入力するための CNOT や SWAP といった特別なキーが並んでいます。

「あっ、SWAP キーが動かなくなっちゃった!」

SWAP キーが動かなければ、明日のデモはできません。 幸いなことに、CNOT キーはまだ生きています。

問題: CNOT から SWAP を作るには?

CNOT を何度か組合わせて SWAP と同じ働きをする量子回路を作ってください。 完成したら MEASUREMENT 命令を使って、確かにビットが入れ替わっていることを確認してください。