# パズル感覚で楽しむ量子回路

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

<br/>前回は茨城っぽい話ができたので、今回は自分の研究に関わることを紹介したいと思います。

こないだ(久々に)部屋の整理を行ったところ、懐かしい研究メモが出てきました。私は学部生から量子コンピュータに関連する研究をやっていますが、「あぁ、こんなのをやってた時期もあったなあ」と卒論締切ちょい前の自分が遠い日のように思い出されます。

量子コンピュータと一言で表しても、その中身は様々です。私が研究している分野では一般的なコンピュータと同じように「論理ゲート」みたいな「量子ゲート」なるものを回路上に置いて**量子回路を構成し、これを実際に動かしてみてどんな働きをするのかをシミュレートしてみる**、なんてことをやっていたりします。

プログラム上で量子ゲートを置くのが、まぁ大変で大変で。ちゃんと正しい場所に適切なゲートを置かなければ、当然うまいこと機能してくれません。場合によってはこの部分だけでもソースコードがめっちゃ長くなってしまい、どこが間違っているのか虱潰しに探す、なんてことに…。

今回発見したメモは、そんな量子回路の構成と格闘していた頃に書いていたもの。皆さんにもこの~~苦しみ~~楽しさをちょっとだけ味わってもらおうかな、ということで記事を書いてみました。
そんなに難しいことは書いていないつもり(てか説明できる自信がない)ですし、ちょっとした頭の体操として問題に挑戦してみてください。

</br>

## お題

これは「置換表」です。入力*X*に対して、ランダムな置換*P*が1対1で対応します。
「**置換結果を出力用の量子ビットに格納する**」という量子回路を考えるというのが、本記事のお題となります。

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

</br>入力値、出力値はともに4ビットです。そのため、量子ビットは計8つ用意することになります。各ビットは"0"か"1"の状態を取り、初期状態は"0"となっています(量子だと「重ね合わせ」なんてことも行えますが、今回はそこまで踏み込みません)。

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

</br>なので最初はこんな感じ。ここから、各ビットの線に量子ゲートとよばれるものを色々置いて弄っていくことになります。

</br>

## 使う道具を確認する

さて、肝心要の量子ゲートについて紹介しましょう。
論理ゲートの「AND」や「OR」などのように、量子回路でもゲートを置いて各ビットの状態を操作し、様々な機能を作ることができます。
全部を紹介するとキリがないので、今回は「**CNOTゲート**」と「**CCNOTゲート**」と「**Xゲート**」の3つだけ覚えていただければ大丈夫です。

### CNOTゲート

<img src="https://i.imgur.com/qFynWVF.png" width="200mm">

</br>**CNOTゲート**はXORゲートみたいなものです。
上の黒玉は「制御ビット」、下の十字は「標的ビット」とよびます。
制御ビットの状態が"0"か"1"のどちらを取っているかによって、標的ビットの操作内容が変わります。といっても至ってシンプルで、
* **制御ビットの状態が"1"なら標的ビットを反転する**
* **制御ビットが"0"なら何もしない**
* **どちらの場合も、ゲート通過後の制御ビットの状態は変わらない**

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

</br>要はこういうことです。制御ビットが"1"ですので、最初"0"の状態だった標的ビットが反転して、ゲート通過後の状態が"1"になりました。制御ビットは状態"1"のままですね。

そういう意味では、CNOTゲートは標的ビットにとってのXORゲートであると言えるわけです。CNOTゲートをうまく組み合わせることで、ビットの入れ替えなどの操作を行うこともできますよ。

</br>

### CCNOTゲート

<img src="https://i.imgur.com/HCxqQsO.png" width="200mm">

</br>**CCNOTゲート**は、基本的にはCNOTゲートとやっていることは変わりません。ただ、制御ビットが先ほどより1つ増えていますね。
つまり、「**2つの制御ビットがどちらも"1"なら標的ビットを反転する**」という操作を行います。こちらの場合も、それぞれの制御ビットの状態はゲート前後で変化しません。

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

</br>ちなみに、CNOTゲートでもそうですが常に標的ビットが一番下じゃないといけないということはありません。
こんな風にひっくり返ってもいいですし、標的ビットを制御ビットで挟むこともできます。

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

</br>CCNOTゲートは「Toffoliゲート」とよばれることもあります。どっちでも通じます。

</br>

### Xゲート
ここまでで「制御ビットが"1"じゃないと標的ビットを反転させられないの？」と疑問に思った方もいるでしょう。CNOTおよびCCNOTは先に示した条件でしか標的ビットを反転させることができません。
そこで**XゲートとよばれるものをCNOT・CCNOTゲートと組み合わせる**ことで、反転条件をカスタマイズできるのです。

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

</br>Xゲートは「ビットを反転させる」、要はNOTゲートみたいなものですね。
これをCNOT・CCNOTゲートの前に置いて、ムリヤリ反転条件に合致させちゃおうという寸法です。
例えば「1ビット目・2ビット目を制御ビット、3ビット目を標的ビット」として、「1ビット目が"1"、2ビット目が"0"の時に標的ビットを反転させたい」とするなら、このようにすればOK。

<center>
<img src="https://i.imgur.com/0m7rQcN.png" height="300mm">
</center>

</br>CCNOTゲートを適用させる前に、2ビット目にXゲートを置いています。こうすることで、2ビット目が0であればXゲートにより"1"に反転、するとCCNOTの条件を満たすので標的ビットが反転します。

以降、黒玉を"1"、白玉を"0"としてCNOT・CCNOTゲートを以下のように表すときがありますが、左と右で同じことを言っているのだ、と理解していただければ助かります。

<center>
<img src="https://i.imgur.com/0SfN4QN.png" width="500mm">
</center>

</br>ちなみにCNOT・CCNOTゲートをXゲートで挟むように表記していますが、2回以上連続して「あるビットが"0"の時に標的ビットを反転させる」操作を行いたいのであれば、連続するゲートの両端だけXゲートを置く、という様にすればXゲートの設置数を減らすことができます。

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

</br>最初に白玉を置くとき、または1つ前の玉から色が変わる時に、CNOT・CCNOTゲートの前にXゲートと覚えておきましょう。

</br>

## お題(再掲)とチュートリアル

では今回のお題に戻りましょう。

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

</br>一気に処理するのは大変なので、置換結果を1ビットずつ出力していくことを考えます。ここではチュートリアルとして、結果の1ビット目*p1*について量子回路を作ってみましょう。

直感的には入力の各パターンを1つずつ見ていって、置換結果と照らし合わせてゲートを置けば良いような気がしますよね。
入力4ビットを2つに分割して、それぞれについてCCNOTゲートとXゲートを使っていけばいいと。確かに、そのやり方でできないこともありません。

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

</br>しかし、それには計算のための**補助ビット**が必要となります。上図は解答例ですが、今回の場合ですと8ビット(*h1*から*h8*まで)追加となり、トータルでは**16ビット**用意しないと本機能を実現できないということになります。
量子コンピュータにおいては、ある状態をキープするのがとても大変。規模を大きくするとなると、より悩ましい問題となります。なので、可能な限り使うビット数は少なくしたい。

「入力4ビットを制御ビットとして扱えるゲートは無いのか」と焦れったくも感じるでしょうが、残念ながらそれは(公式では)用意されてません。
ところが今回のお題は、**実は補助ビットを使わず、なおかつCNOTとCCNOTゲートとXゲートだけで処理できる内容になっています**。

どういうことかというと、今回の場合ですと入力を4パターンまとめて処理しちゃうのです。
結果の1ビット目で"1"となっているのは8パターンですから、前半と後半に分けてそれぞれに対応するゲートを置くようにします。

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

</br>実際にはこんなゲートを置くわけではないのですが、ゲート操作による状態の変化を視覚化するために、前半の4パターンについて白玉("0")と黒玉("1")で表現します。
各入力パターンはタテに見ていって下さい。

で、こんなパズルを考えます。
「**ヨコに黒玉(または白玉)が4つ並ぶような行を、ゲート操作によって2つ作る**」

なんのこっちゃ。
図の一番上の行に注目すると、ここは全て白玉が並んでいますよね。

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

</br>ゲートを使って入力を弄り、このような行を2つ作れということです。
2行とも同じ色である必要はありません。黒玉の行と白玉の行が1つずつでもOK。

説明しようとするとなかなか難しい…。
実際にゲートを置いて、どうすればいいのかを見てみます。

さっきも見たように、最初の状態で白玉の行が1つ完成しているので、もう1行白玉か黒玉の行を作ればいいということになります。1行目はそのままにしておいて、他の行で作れそうなところを探しましょう。

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

</br>2行目に注目しますと、1つだけ黒玉になっています。
この黒玉をどうにかすれば、白玉の行をもう1つ作れそうですね。
そこで2行目を標的ビットとするCNOTかCCNOTゲートを置くことを考えます。そうなるとどのビットを制御ビットとするかが問題です。

3,4行目に注目しますと、2行目が唯一黒玉だった列"0111"ではどちらも黒玉になっています。
他の列はそうなっていませんから、ということは…

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

</br>このようなCCNOTゲートを置いてみます。
3行目と4行目の制御ビットが黒玉の時だけ、2行目の標的ビットが反転するので、

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

</br>2行4列目の黒玉だけが反転し、白玉の行が2つ完成しました。
ここまで来たら、ほぼ解けたも同然。
この白玉の2行を制御ビット(白玉になります)、出力用ビットを標的ビットとするCCNOTゲートを置けばOK。
各ゲートの白玉をXゲートに置き換えて、必要な部分のみを抜き出すと…

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

</br>これで**入力{"0000","0001","0010","0111"}のときだけ*p1*が"1"になる量子回路**の完成です。実際に入力してみると、通す4パターンが入力の場合は*p1*が"1"になって、それ以外のパターンでは*p1*が"0"のままになることを確認できます。

## 後半戦

なんとなく動きは理解しましたか？
後半もやってみましょう。

その前にゲート操作で入力を色々と弄ってしまったので、一旦元に戻しましょう。
図の続きに、青枠で囲った部分を追加します。

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

</br>出力用ビットを操作したゲート(赤枠で囲った部分)を軸に、対称になるようにゲートを置いてやることで、元に戻せます。

では後半。やることは大して変わりません。

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

</br>今回も既に、1行目に黒玉の行ができていますね。で、2行4列目だけ黒玉になっているので、ここを反転させれば黒玉の行と白玉の行が1つずつある、ということになります。
ゲートを置くのに都合の良い行を探して…

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

</br>ここにこのようなゲートを置けば、

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

</br>黒玉が反転して、白玉の行ができました。
前半と同じように必要な部分を抜き出すと…

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

</br>**入力{"1000","1010","1011","1101"}のときだけ出力用ビットが"1"になる量子回路**の完成です。
あとは入力を元に戻す操作を追加して、前半と後半の量子回路を合体させれば、

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

</br>できあがり。
出力用ビットの1ビット目*p1*の処理はこれで完了です。**多分これが一番楽だと思います。**
ちゃんとCCNOTゲートとXゲートで回路を組めましたね。

2ビット～4ビット目についても同じようにゲート処理を行っていくことになりますが、それは皆さんの宿題としましょう。
場合によっては2つ以上のCCNOTゲートを置いて入力を弄る必要があるかもしれません。

</br>

## おわりに

学部生の時はこのようなパズルをせっせと解いて、それをプログラムに打ち込んで…とやっていたのですが、**実はプログラムで新しくゲートを定義すりゃあ済む話**だということに気付いて、それっきり全然やらなくなりました。
人間便利さに一度気付いてしまうと戻れなくなるものです。恐ろしいね。

あ、宿題と称して残りの部分の解説を投げ出しているわけではありません。
ちゃんと解答編も用意してありますって。

<span style="font-size: 150%;"><strong>**明日公開**です。</strong></span>…早すぎる？

ではでは！

</br>

## 参考資料
* 小野田 将人, 山下 茂, 櫛田 耕平</br>「複数複数出力を考慮した量子回路設計手法」</br>(括弧内の論文名をコピってググるとPDFファイルを閲覧できます)