【D-Wave 2000Q】 全結合相互作用を64ビットしか扱えない証明 Part1

キメラグラフで64量子ビット全結合までしか扱えない証明1QUANTUM

D-Wave 2000Qでは,量子プロセッサ上に2048量子ビットが配置されています.

しかし,D-Wave 2000Qで採用されているキメラグラフ構造は,全てのビットが相互に接続されているわけではありません.

そのため,全てのビットが相互作用を持つ全結合型の問題を扱おうとした場合,扱える問題サイズは非常に小さくなってしまいます.

今回は,D-Wave 2000Qのキメラグラフ構造において,全結合型の問題が64量子ビットまでしか扱えないことを証明したいと思います.

証明方法はいろいろありますが,数列漸化式で解いていきたいと思います.

 

スポンサーリンク

キメラグラフ

キメラグラフ

D-Wave 2000Qにおいては,上記のような8ノードのキメラグラフ上に量子ビットが配置されて,1ユニットを構成しています.

1ユニットは4量子ビット×4量子ビットの完全二部グラフとなっており,全てのビットが相互に接続されているわけではありません.

さらに,量子プロセッサ上には16×16のグリッドセルに,ユニットが配置されています.

全てのノードは,隣り合うユニット内の一つのノードと接続されているため,16×16×8=2048量子ビットが間接的に接続されていることになります.

 

キメラグラフとイジングモデル

そもそも,なぜキメラグラフを採用するのか.

それは,量子アニーリングがイジングモデルに着想を得たアルゴリズムとなっているからです.

イジングモデル

イジングモデルとは,上記のような再隣接の格子点のみと相互作用を及ぼすような,統計力学で用いられるモデルです.

ある格子点に着目すると,それぞれ上下左右で隣り合う最大4つの格子点と接続されています.

しかし,よく見ると端っこの格子点は,3つもしくは2つの格子点としか接続されていません.

キメラグラフにおいては,あるノードが少なくともユニット内の4ノードと接続されていました.

したがって,キメラグラフはイジングモデルのハミルトニアンで定式化された問題を解くことができるというわけです.

 

イジングモデルへの埋め込み

全てのノードが,上下左右の4ノードとしか接続されていない場合には,2048量子ビットがフルで使えます.

しかし,こんな都合の良い問題はなかなかありません.

実問題の多くは,ノード同士が多くの相互作用を必要とします.

このような問題を扱うために,グラフ問題の埋め込みが必要となります.

 

次回は,このグラフ問題の埋め込みの具体例を説明し,埋め込みの結果,全結合問題がD-Wave 2000Qでは64量子ビットまでしか扱えない事を証明します.

 

コメント

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