前回は,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.
コメント