量子コンピュータでEternityIIパズルを解く【Qiskit初心者】

#はじめに
量子コンピューター Advent Calendar 2019の8日目です．

普段は，株式会社JijにてOpenJijの開発や量子アニーリング，機械学習の研究をさせていただいております．また東北大学の4年次に在籍中です．

先日，大学の研究室からQiskit Camp Asia 2019というハッカソンイベントに参加しました．そこで，Qiskitの量子コンピュータでEternity II というパズル問題に取り組んだので紹介します．

#Eternity II

https://en.wikipedia.org/wiki/Eternity_II_puzzle

2007年に発売され $2 million の懸賞金付きだったパズルです．誰も解けないまま期限の4年が経ち，いまだに誰も解けていません！

各ピースは3色または4色の柄がついており，全部で256ピースあります．これを一番外側がグレーかつ隣り合う色が同じになるように16×16でボードに配置していきます．

これについて，量子アニーリングに用いられるQUBOを使った解法を@Asa-Eagleさんが紹介しています．
https://qiita.com/AsaEagle/items/2cdb524cd762eae12992
Qiskit Camp Asia 2019では，@Asa-Eagleさんが立てたQiskitでこのパズルを解くプロジェクトに参加しました．

#問題設定
16×16のパズルを解くのは難しいので，ひとまず4×4のパズルを解くことを考えます．

#アプローチ
四隅のピースのうち1つはどれをどこに置いても，ボードを回転させれば同じになるので適当に1つ決めてしまいます．隣り合う色が同じになるように外側の組み合わせを考え，できたら1つ内側を考えます．これを最後までやれば，パズルが解けると考えました．

#ボードとピースの表現
https://qiita.com/AsaEagle/items/2cdb524cd762eae12992 にて紹介されている表現方法に従います．
可能な置き方を全て列挙し，あるピースをある置き方にする場合には1，しない場合には0として表現します．

• 0は左上がグレーになりさえすれば良いので適当に1つ決めます．これを置くか置かないかに1ビット要します．
• 3，12，15に3ピースどれかを置くので，3×3ビット
• 1，2，4，7，8，11，13，14も同様にして，8×8ビット
• 5．6．9．10に4ピースが4回転の置き方で，4×4×4ビット

合計が138ビットになります．IBM Q の32量子ビットシミュレータでこのサイズは扱えないので，4×4のパズルを解くのは難しそうです．

問題を簡単にして，2×2のパズルを解くことを考えます．

• はじめに0に1ピースで，1ビット
• 1，2，3に3ピースどれかを置くので，3×3ビット

これなら10ビットで表現可能なので，2×2のパズルを解いていきます．

10ビットそれぞれに，ピースのボードへの置き方を割り当てます．図の赤文字の位置にどの色を置くかを考えます．

ボードの0番について，0の位置にグレー，1の位置にグレー，2の位置にイエロー，3の位置にグリーンを置く場合は，[0，グレー，グレー，イエロー，グリーン]のような配列で表現します．

次にボードの1番について，図のような配置は，[1，イエロー，グレー，グレー，グリーン]となります．色の組み合わせが違う他のピースについても，右上がグレーになるような置き方が存在します．[1，グリーン，グレー，グレー，レッド][1，レッド，グレー，グレー，グリーン]です．

同様にして，全組合せを列挙すると以下のようになります．ただし，グレー：0，イエロー：1，グリーン：3，レッド：4です．

prb = [
       [[0,0,0,1,4]], #0
       [[1,1,0,0,4],  #1
        [1,3,0,0,4],  #2
        [1,4,0,0,3]], #3
       [[2,0,4,1,0],  #4
        [2,0,4,3,0],  #5
        [2,0,3,4,0]], #6
       [[3,4,1,0,0],  #7
        [3,4,3,0,0],  #8
        [3,3,4,0,0]]] #9

#量子ゲートの構築
各表現ビットどうしに量子ゲートをかけて，判定用のビットを操作します．最終的に任意の判定用ビットが全て1になるような表現ビットを出力することで，置き方が一意に定まります．実際に構築した量子ゲートが以下です．

表現ビットには，はじめにアダマールゲートをかけて0と1の重ね合わせ状態にしています．判定の例としてはじめの部分を見てみます．

先ほど示したq[0]は0番の2の位置がイエローになっています．となりの1番では0の位置がイエローなら条件を満たしますので，これが可能なq[4],q[5]にccxゲートをかけます．ccxゲートは入力ビットが全て1の時に，判定ビットを反転させます．

以下，同様にして判定を行っていき答えを求めました．

#まとめ
量子ゲート方式の量子コンピュータを初めて使ってみましたが，なかなか思うように問題を解くことができませんでした．最終的に解けたのは2×2のパズルでしたし，これを解くためにも表現に10ビット，判定に17ビット要しました．32ビットまででこのアプローチはこれが限界ですね！ピースの表現方法を変えたり，判定を効率よく行ってビットを節約したりするなど工夫が必要そうです．また，グローバーのアルゴリズムを使っても解けるそうなので，ぜひ試してみたいです．

以下が今回のプロジェクトページです．
https://github.com/qiskit-community/qiskit-camp-asia-19/issues/48