IBM Quantum Challenge 2020 参加記
はじめに
2020/11/8 から3週間開催された IBM Quantum Challenge に参加しました．せっかくなので記事に残しておきます．今後参加する人も増えそうなので，参考になればと思います．
各問題についてのコメント
第1週 問題a
基本的な量子ゲートの説明から入り，加算器を実装するのが問題 a の課題です．去年も同じような導入でした．
この問題に関しては資料を読めばつまる所もないと思うのでノーコメント．
第1週 問題b
グローバー探索のちょうどよいイテレーション回数を求める問題です．去年はもうちょっとブラックボックス感があったきがする（よく覚えてない）のですが，今回のような設定にしたほうが教育的で良いと思いました．
グローバー探索は資料にもあるとおり，候補の空間を欲しい答えが張る部分空間とそれと直交する部分空間の2次元で表現した上で，探索対象のベクトルに関する各種操作を自分で図示すると理解が進むと思います．
第2週 問題a
グローバー探索で 3x3 のライツアウト問題を解け，という問題です．
オラクルとしては，解の候補（どのボタンを押すかの 9 個の量子ビット）の各ビットをみて，そこを押したら反転する入力のセル（ビット）を対象に cx ゲートを適用するだけです．
解となる要素は入力データ部分が全部 0 になってるわけですから，X ゲートで反転して全部の and を取ればよいわけですね．
探索空間は 2^9 なので大体 17 回やればほとんどアタリだけ引くことができるようになります．
最適化も含めて考えれば去年の本番の問題よりちょっと簡単目ぐらいの難易度に感じました．
第2週 問題b
qRAM を用いて複数の入力データを重ね合わせることで，4つのライツアウト盤面から高々3回のボタンを押してクリアできるものを見つける，という問題．
入力が複数個になっていること，単にそれぞれのライツアウトを解くだけでなく高々3回で解けるものだけを見つける必要があることなど，考えることが増えて少しむずかしいです．
オラクルの中で問題 2a のグローバー探索をするというのが去年には無い方法だったので，かなり勉強になりました．僕はこれにしばらく気が付かず，半日ほど時間を溶かしました．
内側のグローバー探索の直後では探索空間が大体4個*1になるため，diffusion 回路をアドレス部分に関してやれば十分ということです．そのため（外側の）グローバー探索のイテレーション回数は1で済みます．
外側のオラクルは 9 個の 1bit データを全部足すカウンタを使います．可逆にしないといけないという点では古典と異なりますが，ほとんど HW の回路を組むのと一緒です．
和を記録しておくのに愚直にやれば4ビット必要ですが，これ全部を補助ビットから賄うともったいないので，下位1ビットは和を取りたいビットの1つ目を直接入れておくようにすると補助ビットを1つ節約できます．補助ビットが余っていればいるだけ uncomputation がサボれるため，量子ビット数がギリギリな設定ではこういう工夫が効いてきます．
https://github.com/Suikaba/ibm-quantum-challenge-2020/blob/master/ex2b.py
いやしかし難しいなあ．*2
第3週（最終問題）
いよいよ本番です．この週は予定がありまくりで時間を無理やり捻出しました*3．
問題は競プロ勢にはおなじみの以下のような問題．
4x4 のグリッドが16個与えられる．それぞれのグリッドにはちょうど6個の惑星があり，4x4のセルのうちのどこかに配置されている．
あなたはレーザーを持っていて，3発まで打てる．このレーザーは行 or 列の一直線上にある惑星を同時に破壊できる．
16個のグリッドのうち，クリアできないグリッドをグローバーのアルゴリズムによって特定せよ．ただし，
あなたはレーザーを持っていて，3発まで打てる．このレーザーは行 or 列の一直線上にある惑星を同時に破壊できる．
16個のグリッドのうち，クリアできないグリッドをグローバーのアルゴリズムによって特定せよ．ただし，
これが2部グラフの最大マッチングに対応するのはもはや常識ですが，今回はこれを量子回路で解く必要があります．
去年の感じだとルールをかなり忖度しないと本テストで簡単に reject されてしまうので，こういうのを想定してるんだろうなーという方向で最適化する解答を先に載せます．
自分の解法（ルール準拠）
この解法ではいかなる古典的な知識も用いず，また問題の解の存在条件の言い換えなども行いません．
量子ビットの用途は以下のとおり．
- アドレス(4bit)
- 惑星データ (6bit)
- レーザーデータ (8bit)
- オラクル用補助ビット (1bit)
- 補助ビット (9bit)
惑星データは入力を見て座標に対応する2つのレーザーに対応するビットの or をとったものになります．
次はアルゴリズムの流れについて．自分はグローバー探索を3段組にしました．
1. 一番内側のグローバー探索ではちょうど3発レーザーを打っているものを探索（入力データに依存しない）
2. 2段目のグローバー探索では上の条件に加え，盤面をクリアできるものを探索（入力データに依存）
3. 一番外側では上で見つけた解答の部分だけ符号反転．具体的にはちょうど3発打っているものだけ反転すればいい感じになる．
Slack チャンネルを見ている限り，3段目の部分で詰まっている人が多いのかなという印象を受けました．
僕の理解が正しければ，グローバー探索はアタリを引くアルゴリズムですが，逆にハズレよりアタリのほうが遥かに多い場合にはハズレを引くアルゴリズムということもできます．今回はハズレが1個でアタリが15個あるので，アタリ部分だけ狙い撃ちして反転できれば目的を達成できます．
また，1段目と2段めを分けたのは惑星データのストアの回数を若干少なくするためです．
このストア部分は入力データ 16 x 6 回のループを回す必要があり，そこそこ cx ゲートを使うのでできるだけ少ないほうが嬉しいです．でもよく考えたらあんまり変わってないかもしれません．悲しいね．
一番良いのは問題 2b のようにストアする部分がイテレーションの外側に出ていることなのですが，今回はそれができなかったのでこのような形になりました．
僕の実装では最適化を頑張っても 244k 程度のコストになりました*4．個人的には opt_is_count3 あたりの実装が気に入っています．その他も ancilla ビットを使い切ってできるだけ uncomputation が発生しないように努めているつもりです．
うーんしかし惑星データのストア部分を外に出せないと 100k 切るのは夢物語ですね．でもみんな 100k 当たり前のように切ってるんだよなあ．なにがいけないのかなあ．
別解その1（多分ルール非準拠，未提出）
unsolvable な盤面を直接求めに行く方針です．*5
結論を言えば，8-queen's problem ならぬ 4-queen's problem のようなものに言い換えられます．
すなわち解き方としては
- 0~3 の長さ4の順列を生成する．i 番目の数 p[i] が (i, p[i]) のセルに対応する．
- 盤面のうち順列に対応する位置すべてに惑星があるかチェックする．これは順列との or をとってカウントが4かどうかで判定可能
という流れで解けます．この解き方の問題点は outermost の探索空間が 2^2 * 24 通りあるために1回のイテレーションでは十分な確率で解を得るのが難しいことです．せめて3回ぐらいまわせればそれっぽくなるんですけどね．
実装したところ，回路の最適化なしでも1回イテレーションするだけなら 40k 程度のコストになりました．
別解その2（ルール非準拠）
別解1をより進めます．盤面には高々 6 個の惑星しか無いので，4つの行のうち少なくとも2つの行には惑星が1つしかありません．
したがって，前処理で盤面の行・列をいい感じに swap すれば，盤面で考えるべきは以下の x の部分だけになります．
xooo
oxoo
ooxx
ooxx
左上2箇所は決め打ちできるので，右下2パターンについてだけ探索すればよく，探索空間が小さくなるためイテレーション1回でも相当高確率で解が得られます．
また回路規模も（特に最適化なしで）16k ぐらいになります．
これ結構気に入っていたのですが，禁止されちゃって悲しかった．
ちなみにコンテスト中の1位の記録が 10k を切っていたのですが，こういうズルなしでやってるんだとしたら本当にすごいです．全く思いつかないよ．
その他のこと
まとめ
全然だめだったけど今年も楽しかった～．運営の皆様お疲れさまです．
競プロ勢とも相性いいと思うので，参加したことのない人は来年は出てみてはいかがでしょう．初心者でも楽しめるはず．
ただルールが結構ガバガバだったり，システムが不安定*7だったりするので，そういうのが嫌な人は見送ったほうが良いかもしれません．システムはそのうち洗練されていくものですし，今後も続いていけば良いなあと思います．来年も楽しみにしています．
