はじめに
テトロミノ敷き詰め問題を量子コンピュータ（シミュレータ）で解いてみます。前回３つの正方形でできたピースの問題を解いてみましたが、今回は４つです。ちなみに、３つのはトロミノと言うそうです。
「ペントミノ「のような」タイル敷き詰め問題を量子コンピュータで解いてみる」
https://qiita.com/drafts/5ddb63f74193babf9b7e/edit
問題
テトロミノとは、４つの正方形を組み合わせた形状のことで、下図の５つのピースがあります。テトリスと同じです。ピースは、回転したり、裏返したりすることができます。
このピース２つずつを、下図のようにボートに敷き詰めていきます。
考え方
3つの時と同じように、まずは、ピースp0の盤面への置き方を考えてみます。下図のように41通りあるようです。この置き方を、それぞれ「q0, q1, q2, q3, q4, q5・・・」とします。
他のピースについても置き方をすべて考えて、それぞれq41, q42・・・と割り当てます。ピースによっては下図のように回転・反転で８通りありますので、８通り×それぞれの置き方を考えます。
今回は３つ（トロミノ）の時と違って、人力ですべて書き出すことはできないので、この書き出しもPythonでやります。例えば、私はそれぞれのピースを以下のような行列で定義して、numpyの回転と反転と掛け算を使って作りました。
p = [[[1,1,1,1]],
[[1,1],[1,1]],
[[1,1,1],[1,0,0]],
[[1,1,1],[0,1,0]],
[[1,1,0],[0,1,1]]]
本当は、対称性や置いちゃダメな置き方（端が1つだけ空いてしまうなど）もあるのですが、とりあえず全部列挙してしまいます。すべてのピースのすべての置き方を列挙すると429個ありました。
立式
立式も3つの時とほぼ同じです。イジングモデルやQAOAで解けるように立式してみます。
量子ビットが表すものを決める
ピースp0は、q0～q40のどれかの置き方になるはずですので、置き方q0になるときに、q0=1 、q0にならない時 q0=0 とします。同様にして、q1になるとき、q1=1, ならないときq1=0・・・、ピースp1についても、置き方q41になるときq41=1, ならないときq41=0・・・とします。
各ピースについて、置き方の中から２つだけ選ばれるようにする・・・①
まずは、p0の置き方は「q0, q1, q2, ・・・, q40」の41個がありますが、その中から同じ形のピース２つ分が選ばれるようにします。
41個の量子ビットの中から２つだけが選ばれる、という条件を最小値問題の式にしてみます。以下のようになります。
\{2-(q0+q2+q3....+q40)\}^2
これで、q0～q41の中で、２個だけ１のとき最小値の０、それ以外は１以上の値になります。
同様にして、ピースp1, p2・・・についても立式していきます。
盤面の各位置（1, 2, 3・・・）に置くピースが重ならないようにする・・・②
次に、盤面に注目します。
盤面の「1」の位置に置かれる可能性のあるピースは１つだけ選ばれるようにします。ピースは重なってもだめだし、どれか１つは配置されていないとダメなので、盤面の「1」上に来る可能性のあるピースの中から、１つだけを選ぶ必要があります。先ほどと同様に立式すると、
\{1-(q0+q25+q41+q69+...)\}^2
とすれば、盤面の位置1に置かれるピースの配置が１つのみに絞られます。q0, q25はピースp0の置き方の中に含まれています。q41, q69・・・はp1, p2・・・の置き方です。
盤面の他の位置2, 3, 4, 5・・・についても同様に立式します。
QUBO作成
イジングモデルやQAOAで解けるようにQUBOの形にします。
式が長くて展開に時間がかかるので、今回はQUBOに直接値を入れて作成しました。条件①のQUBOは以下のような感じです。
[[-3. 2. 2. ... 0. 0. 0.]
[ 0. -3. 2. ... 0. 0. 0.]
[ 0. 0. -3. ... 0. 0. 0.]
...
[ 0. 0. 0. ... -3. 2. 2.]
[ 0. 0. 0. ... 0. -3. 2.]
[ 0. 0. 0. ... 0. 0. -3.]]
条件②の方のQUBOは以下のような感じです。
[[-4. 6. 4. ... 0. 0. 0.]
[ 0. -4. 6. ... 0. 0. 0.]
[ 0. 0. -4. ... 0. 0. 0.]
...
[ 0. 0. 0. ... -4. 2. 0.]
[ 0. 0. 0. ... 0. -4. 2.]
[ 0. 0. 0. ... 0. 0. -4.]]
さらに、条件①と条件②のバランスを考えて足し合わせたものを、QUBOにします。量子ビット数は、配置の総数と同じで429個ですので、QUBOマトリクスのサイズは429×429でした。
シミュレータで解いてみる
今回はオープンソースのシミュレータblueqatと、D-waveのqbsolvで解いてみました。
３個のタイルの時と違って、一発では良い解が得られないので、何回もループして良い解を探します。
良い解では、例として以下のような結果が得られました！
[13, 33, 66, 68, 144, 223, 251, 298, 339, 352]
いくつか解はあるようです。
下図のような外れの解も結構でてきます。赤い部分は重なってしまったところです。
まとめ
テトロミノは何とか解けました。次はペントミノ（５つの正方形）に挑戦してみたいと思います！
実はペントミノもコードは書いてみたのですが、量子ビット数が多くて、工夫しないと解けないようです。解は得られますが、３か所位重なってしまう解がほとんどで、最良でも1か所間違いまでしか得られていません。対称性や、ダメな置き方を省いたりして量子ビット削減しても1870になってしまい、難しいです。他の方法を含め、考えてみます！