前回は，4×4 Eternity II パズルを解こうとしましたが，問題サイズが大きくなってしまい，断念しました．
今回は，現実的に解ける問題サイズまで落とし込んで，実際にパズルを解いてみます．
前回はこちら↓
問題の簡略化
問題を簡単にして，2×2のパズルを解くことを考えます．
- 先ほどの考え方に倣って，番地0には2隅がグレーの1枚を割り当てます．これに，1ビット要します．
- 番地1，2，3には，2隅がグレーの3枚を割り当てます．3カ所に置くので，3×3ビット要します．
これなら10ビットで表現可能なので，2×2のパズルを解いていきます．
10ビットそれぞれに，ピースのボードへの置き方を割り当てます．図の赤文字の位置にどの色を置くかを考えます．
ボードへのピースの置き方
10ビットそれぞれに，ピースのボードへの置き方を割り当てます．図の赤文字の位置にどの色を置くかを考えます．
ボードの0番について，0の位置にグレー，1の位置にグレー，2の位置にイエロー，3の位置にグリーンを置く場合は，[0，グレー，グレー，イエロー，グリーン]のような配列で表現します．
次にボードの1番について，図のような配置は，[1，イエロー，グレー，グレー，グリーン]となります．
色の組み合わせが違う他のピースについても，右上がグレーになるような置き方が存在します．
[1，グリーン，グレー，グレー，レッド][1，レッド，グレー，グレー，グリーン]です．
同様にして，全組合せを列挙すると以下のようになります．
ただし，グレー：0，イエロー：1，グリーン：3，レッド：4です．
1 2 3 4 5 6 7 8 9 10 11 | 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のパズルを解くのに，27ビット要しました．
ビットを節約するために，ピースの表現方法を変えたり，判定を効率良く行ったり，工夫が必要そうです．
My favorite food is Sushi and Yakiniku.
コメント