今回の記事は2019年の1月に出た記事を加筆修正してお届けします。
D-Waveが5000量子ビット+量子ビットの新接続のマシンを2020年に投入するというニュースが2019年初頭に出ました。
"D-Wave Previews Next-Generation Quantum Computing Platform"
https://www.dwavesys.com/press-releases/d-wave-previews-next-generation-quantum-computing-platform
「D-Waveが量子アニーリングの次期仕様、5000量子ビットで2020年出荷」
https://tech.nikkeibp.co.jp/atcl/nxt/news/18/04292/
引用：https://www.dwavesys.com/press-releases/d-wave-previews-next-generation-quantum-computing-platform
使ってみる
意外とペガサスグラフを使っている人がいないので、少し使ってみます。
まずキメラグラフ
キメラグラフを書くのは簡単です。
import networkx as nx
import dwave_networkx as dnx
import matplotlib.pyplot as plt
G = dnx.chimera_graph(2, 2, 4)
dnx.draw_chimera(G)
plt.show()
こちらの形はD-Waveを使っていればみんなよくわかっています。よくある形なので覚えましょう。
つぎにペガサスグラフ
ペガサスグラフもD-Waveの提供しているdwave_networkxのツールを使うことによってトポロジーを簡単に確認できます。
import dwave_networkx as dnx
import matplotlib.pyplot as plt
P3 = dnx.pegasus_graph(3)
dnx.draw_pegasus(P3)
plt.show()
こちらが皆さん大好きペガサスグラフです。
量子アニーリングの性能に関してはあまり変わりがありません。同じようにアニーリングをするだけですが、使える量子ビットの結合が大きく変化するために、いままでのキメラグラフでの埋め込み方式を見直す必要があります。
QUBOで全結合から式を立ててペガサスへの埋め込みは少しコツがいりそうですが、あまりトポロジーが複雑ではないので、慣れれば簡単にできそうです。
上記dnxでペガサスグラフは簡単に作れますので、そのままD-Waveのシミュレータやblueqatなどでもシミュレーションができます。
P6 = dnx.pegasus_graph(6)
classical_sampler = neal.SimulatedAnnealingSampler()
sampler = dimod.StructureComposite(classical_sampler, P6.nodes, P6.edges)
こんな感じです。
ペガサストポロジーのおさらい
ペガサストポロジーはキメラグラフを拡張して作られていそうです。キメラグラフとペガサスグラフのトポロジーをおさらいしてみたいと思います。
キメラグラフは、先ほど出てきたように、
このような形状をしています。もともとは、ハードウェアとしては、4*4の量子ビットが井形に組まれていますので、１つの量子ビットが交差する４本の量子ビットと、他のユニット間で最大６の量子ビットと接続があります。８量子ビットで１つのユニットせるという呼び方をします。ノード・エッジ表記にするとこのような形になります。以前はもう少し違う形でも表現されていました。
ペガサスグラフはこれを拡張しているようです。トポロジーの接続方法からハードウェアの実装がみて取れます。新しいペガサスグラフは16接続ですが、既存のキメラグラフを拡張して接続数を増やしています。
引用：https://techcrunch.com/2019/02/27/d-wave-announces-its-next-gen-quantum-computing-platform/
既存D-Waveのキメラグラフはハードウェア構造として下記のように細長い量子ビットを活用して、4*4のユニットセルを縦横に16*16組んでいて、全部で2048量子ビットを実現しています。
一方ペガサスはこのキメラグラフの組み方を拡張して、
まずは、キメラグラフを右と上に腕を伸ばします。そして、それをずらして配置することで、最大12本と交差する形を作れます。また、他のユニットとの交差以外の接続は、両端が2接続あります。さらに今回は１ユニットセルの隣接量子ビット同士に新しい接続が1追加され（図で黒棒＋黒丸）全部で交差12+隣接ユニットセル2+隣接量子ビット新規接続1の合計15接続となりました。
これを頭に入れて解いてみましょう。。。シミュレータもこのトポロジーを考えれば作るのもそんなに大変ではなさそうなので、次世代D-Wave向けのアプリケーションも十分に余裕を持って開発ができるでしょう。
詳しい資料
詳しい資料はwhitepaperがでていますので、こちらから。
巡回セールスマン問題
次にペガサスグラフを使った際に、キメラグラフとどれくらいの量子ビット数の消費が異なるのかをみてみたいと思います。
４都市の巡回セールスマン問題
４都市を設定し、一筆書きで一番最短の経路が回れるような巡回セールスマン問題を考えます。
エネルギーコスト関数
量子アニーリングで言われるエネルギーコスト関数もしくはハミルトニアンと呼ばれる式のコストを最小にするように解かれます。式は、
\[ H = \sum_{v=1}^n\left( 1-\sum_{j=1}^N x_{v,j} \right)^2 + \sum_{j=1}^N\left(1-\sum_{v=1}^Nx_{v,j} \right)^2 + B\sum_{(u,v)\in E}W_{u,v}\sum_{j=1}^N x_{u,j} x_{v,j} \]
これを利用します。
QUBOmatrix
QUBOmatrixと呼ばれる基本の量子ビットの関係を表す行列は都市数4に対して、42∗42必要となります。
論理量子ビット数は下記のように4都市の巡回セールスマンでは16となります。
キメラグラフへ実装
キメラグラフは１つの量子ビットと最大で６の量子ビットが繋がっています。上記の理想的な論理ビットの16量子ビットでは、他の15量子ビットと繋がっていないと問題を解くことができません。そのため、最大接続数が6のキメラグラフでは２つ以上の量子ビットを強結合と呼ばれる強めの結合を間に設定することで複数の物理量子ビットを１つの論理量子ビットとして扱う手法が取られます。
そのため、論理量子ビットを構成するために大量の量子ビットが消費されますが、16の完全結合を作るためにざっくり80物理量子ビットくらいを使います。これはもっと減らせますが、
工夫して階段状に量子ビットをつなげることで10のユニットセルを使って簡易的に完全結合のグラフを表現します。
ペガサスグラフへの実装
今回新しく発表されたペガサスグラフは１つの量子ビットの最大接続が15です。交差する12と、両端の2、新しい隣接相互作用が1で合計15です。
エッジ・ノードの論理的な表現は下記のようになりますが、
単体のユニットセルの物理実装は下記のような細長い量子ビットの接続となると思われます。
ペガサスグラフでの完全結合は大幅に量子ビット数が減る
キメラグラフでは６論理量子ビットの完全結合を作るのに17物理量子ビット必要でした。
ペガサスグラフでは、それが大幅に減って6論理量子ビットの完全結合が8物理量子ビットで実現できるようになりました。
６の完全結合の比較
キメラグラフ：１７物理量子ビット
ペガサスグラフ：８物理量子ビット
かなり埋め込みが楽になりました。
16の完全結合
これができれば巡回セールス解けますが、だいたい従来キメラで単純に考えて80前後の物理量子ビットを消費しました。
ペガサスではだいたい50前後で実現できるため、大幅な量子ビットの節約となりました。
まだ出てないトポロジーなので、勉強と節約のしがいがありそうです。以上です。