【実践】量子コンピュータでEternity II パズルを解く【IBM Qiskit】

Qiskit Eternity IIQUANTUM

前回は,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になるような表現ビットを出力することで,置き方が一意に定まります.

実際に構築した量子ゲートがこちらです.

スクリーンショット 2019-12-07 16.19.22.png

 

表現ビットには,はじめにアダマールゲートをかけて0と1の重ね合わせ状態にしています.

判定の例としてはじめの部分を見てみます.

先ほど示したq[0]は0番の2の位置がイエローになっています.

となりの1番では0の位置がイエローなら条件を満たしますので,これが可能なq[4],q[5]にccxゲートをかけます.

ccxゲートは入力ビットが全て1の時に,判定ビットを反転させます.

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

スクリーンショット 2019-12-07 16.38.45.png

まとめ

現状,量子ゲート方式の量子コンピュータでは扱える問題サイズが非常に小さいですね.

今回も2×2のパズルを解くのに,27ビット要しました.

ビットを節約するために,ピースの表現方法を変えたり,判定を効率良く行ったり,工夫が必要そうです.

コメント

タイトルとURLをコピーしました