# パズル感覚で楽しむ量子回路(解答編)

※この記事は[茨大 Advent Calender 2020](https://adventar.org/calendars/5043) 16日目の記事です。
<br/>

<br/>**皆様、お待たせいたしました！**
全世界待望の「パズル感覚で楽しむ量子回路」の答え合わせのお時間がやって参りました。
なにその記事、まだ読んでないよって方は[こちらのリンク](https://hackmd.io/@man-in-pajamas-of-prisoner/Bk5TKfyhD)からどうぞ。

<br/>

<br/>…んん？そちらの方は？

何？

<span style="font-size: 150%;"><strong>「読んだけど解くの面倒だから答えだけ教えろ」</strong></span>

…ですって？？

<br/>

<br/>……うん。だよね。
まぁ、ここに書く解答例で実際に機能するかどうか、もしよろしければ後で確認してみてくださいませ。

</br>

## お題のおさらい

<center>
<img src="https://i.imgur.com/JE8ZeKv.png" height="500mm">
</center>

</br>この置換表に従って、入力X(4ビット)に対応する出力P(4ビット)を、出力用のビットに格納する量子回路を作れというのがお題でした。

使う道具は「CNOTゲート」と「CCNOTゲート」と「Xゲート」の3つ。
ゲートの役割をよく理解し、入力の状態を操作するテクニックを用いることで、

<center>
<img src="https://i.imgur.com/4gLG2Pa.png" width="800mm">
</center>

</br>使用するビット数を抑えつつ、回路(の一部)を構成できるということを書きました。前回は*p1*の回路を作りましたので、この回答編では*p2*～*p4*のそれぞれの場合について考えてみましょう。

</br>

## 解答例

* ***p2*の場合**

<center>
<img src="https://i.imgur.com/CvsxIpv.png" width="800mm">
</center></br>

* ***p3*の場合**
<center>
<img src="https://i.imgur.com/H1hWrXr.png" width="800mm">

</center></br>

* ***p4*の場合**
<center>
<img src="https://i.imgur.com/SzzqH0l.png" width="800mm"></center></br>

</br>**多分これらが一番楽だと思います。**
CCNOTゲートとXゲートだけで作れました。それでも回路図がカツカツだぁ…。
使うゲートの数で言うと、多分…上に挙げた回路で最適化できているんじゃないかと。

正解は1つだけではないので、CNOTゲートと組み合わせた方もいると思います。ひとまず通したいものだけがきちんと通っていれば大丈夫です。

え、解答例よりもっと楽な方法が見つかったって？
……そんな方はコッソリ教えていただけると助かります。

</br>

## よくわかる解説

### *p2*の前半

<center>
<img src="https://i.imgur.com/bltXr9B.png" width="800mm"></center>

</br>考えるのは**入力{"0000","0001","0100","0111"}の4パターン**。
既に白玉の行が1つできていますから、もう1行作れそうなところを見ますと、"0111"の*x3*が白玉になればよさそうだと分かります。
なので、青枠で囲ったCCNOTゲートを置いて3行目を白玉の行にした後、*x1*と*x3*を制御ビットとするCCNOTゲートで*p2*を反転させればOKとなります。

</br>

### *p2*の後半

<center>
<img src="https://i.imgur.com/cboP7K9.png" width="800mm">
</center>

</br>考えるのは**入力{"1000","1001","1100","1110"}の4パターン**。
状態を変化させて黒玉、または白玉の行を作れそうな候補は3行目と4行目ですが、"1110"の*x3*を白玉にしようとCCNOTゲートを置いても、"1001"の*x4*をやはり白玉にしようとCCNOTゲートを置いても、他のパターンが邪魔をしてしまいます。

そんな時でも大丈夫。考え方としては、「**CCNOTゲートを2個使って、1個目のゲートで対象を絞り込んでから2個目のゲートで白玉の行を作る**」というものです。

<center>
<img src="https://i.imgur.com/iCaprM6.png" width="800mm">
</center>

</br>まず、青枠で囲ったCCNOTゲートを置きます。すると、この条件に合致するパターンは"1001"のみなので、"1001"の*x3*が反転します。

<center>
<img src="https://i.imgur.com/vDc5wlV.png" width="800mm">
</center>

</br>上図は反転後のイメージです。さて、これで**各パターンの*x2*と*x3*の組がバラバラになった**ことに気がつきましたか？これが「対象の絞り込み」です。
後は、下図の緑枠で囲ったCCNOTゲートを置けば…

<center>
<img src="https://i.imgur.com/2GxOl9b.png" width="800mm">
</center>

</br>これで4行目がすべて白玉になったので、*x1*と*x4*を制御ビットとするCCNOTゲートで*p2*を反転させましょう。
後は、前半と後半(**各パートの処理後に入力を元に戻すゲートを付けるのを忘れずに**)を合体させれば、*p2*の回路が完成となります。

</br>

### *p3*の前半

<center>
<img src="https://i.imgur.com/jInfzlL.png" width="800mm">
</center>

</br>考えるのは**入力{"0000","0101","0111","1001"}の4パターン**。
一番考えることが多いパートですが、*p2*でやったことをそのまま適用できるので問題ありません。
見た感じだと1行目と3行目を白玉の行にできそうなので、どんなゲートを置けばいいのか考えてみます。
<center>
<img src="https://i.imgur.com/WW1ezhF.png" width="800mm">
</center>

</br>まずは分かりやすいところから、1行目を白玉の行にしましょう。
青枠で囲ったCCNOTゲートを置いて、"1001"の*x1*を白玉に反転させます。

<center>
<img src="https://i.imgur.com/453CNtr.png" width="800mm">
</center>

</br>続いて緑枠のCCNOTゲート。これを置くと、"0101"の*x4*だけが白玉に反転します。そうすると**各パターンの*x2*と*x4*の組がバラバラになる**ので、下準備はこれでOK。

<center>
<img src="https://i.imgur.com/UCQwrHu.png" width="800mm">
</center>

</br>赤枠で囲ったCCNOTゲートを置いた後に、*x1*と*x3*を制御ビットとするCCNOTゲートで*p3*を反転させれば、前半の処理は完了です。

</br>

### *p3*の後半

</br>実のところ、***p3*の前半まで終われば後はウイニングランみたいなもの**です。
追加で解説しないといけない要素はないし、ゲートもそんなに置かずにクリアできるし。

<center>
<img src="https://i.imgur.com/DhCCbWB.png" width="800mm">
</center>

</br>考えるのは**入力{"1010","1100","1101","1111"}の4パターン**。
既に1行目に黒玉が並んでいて、*x3*と*x4*の組がバラバラになっているので、ここまで来た皆さんであればどんなCCNOTゲートを置けばよいかもすぐに分かるはずです。

図の通りにすれば後半の処理もお終い、あとは合体させるだけ。

</br>

### *p4*の前半

<center>
<img src="https://i.imgur.com/DvP2RBJ.png" width="800mm">
</center>

</br>考えるのは**入力{"0001","0100","0110","0111"}の4パターン**。
いや、もう解説することはありませんね。まんま。学部生の頃の私は*p2*や*p3*のような「下準備」が必要なパターンでてこずっていた記憶があります。
その時だけちょっと頭を使わないといけませんが、それ以外であれば楽です、楽。

</br>

### *p4*の後半

<center>
<img src="https://i.imgur.com/a7DTzbo.png" width="800mm">
</center>

</br>考えるのは**入力{"1010","1011","1100","1111"}の4パターン**。
考えることは*p4*の前半と一緒、回路を作ったら前半と後半を合体させれば*p4*の回路が完成です！
あとは*p1*から*p4*の回路をひとつに繋げばいいのですが…そこまで図は作りません！**面倒くさい！**

</br>

## おわりに

うまく回路は作れましたか？
置換表(出力)の中身を変えることで、今回のお題とは違った回路を組むことができます。
興味のある方は色んなパターンを試してみてください。

こういうパズル、ゲーム化してみると意外と面白いかもしれませんね。
どなたか作ってみません(他力本願)？

私が研究している「**量子情報科学**」(量子力学や量子コンピュータについて、数学的アプローチで研究するということ…分かりそうで分からない)の分野において、量子回路を組むことはメインではないのですが、「こういったのをかたわらでやっているのだ」ということを何となーく理解していただけたなら幸いです。