量子コンピュータでパズルを解く方法を解説します．
この記事は，以前Qiitaに投稿した記事を再構成したものです．
Colabでも実行できます．実行にはIBM Qiskitのライセンスを取得して，API Tokenを入力する必要があります．
Eternity II
Eternity IIは，2007年に発売され $2 million の懸賞金付きだったパズルです．当時，誰も解けないまま期限の4年が経ち，いまだに誰も解けていません．
各ピースは3色または4色の柄がついており，全部で256ピースあります．これを一番外側がグレーかつ隣り合う色が同じになるように16×16でボードに配置していきます．
量子アニーリングによる解法が既に存在しますが，今回はゲート方式の量子コンピュータによる解法を紹介します．
アプローチ
四隅のピースのうち1つはどれをどこに置いても，ボードを回転させれば同じになるので適当に1つ決めてしまいます．隣り合う色が同じになるように外側の組み合わせを考え，できたら1つ内側を考えます．これを最後までやれば，パズルが解けると考えました．
ボードとピースの表現
あるピースをある置き方にする場合には1，しない場合には0として表現します．
具体的には，上図のようにピースの番地を定義しておきます．
- 番地0は左上がグレーになりさえすれば良いです．回転すればどのピースを置いても同じことになるので，適当に1つ決めます．このために，1ビット要します．
- 番地3，12，15には，2隅がグレーの3ピースどれかを置きます．3カ所のどこに置くかを考慮して，3×3ビット要します．
- 番地1，2，4，7，8，11，13，14には，1隅がグレーの8ピースを置きます．8カ所のどこに置くかを考慮して，8×8ビット要します．
- 番地5，6，9，10には，どの隅もグレーでない4ピースを置けます．また，回転して4通りの置き方があるので，4×4×4ビット要します．
合計が138ビットになります．IBM Q の32量子ビットシミュレータでこのサイズは扱えないので，4×4のパズルを解くのは難しそうです．
残念ですが，問題サイズを小さくして解くことを考えましょう．
続きはこちら↓
My favorite food is Sushi and Yakiniku.
コメント