日本

D-Waveのサンプリング機能を使って「最大クリーク問題」の 最適解群を求める

D-Waveシステムは量子アニーリングを使用して、エネルギー関数の最小値を求めることで問題を解きます。複数の量子アニーリングが異なる解を返す可能性があるため、問題を「サンプリング」し、返された結果の最低エネルギーの解を調べることができます。

ここでは、最大クリーク(Maximum Clique)問題を例にとって、D-Waveシステムのサンプリング機能をご紹介します。

最大クリーク問題は、グラフ中のクリーク(どの任意の二頂点間にも辺がある頂点集合)の中で最大のものを見つける問題です。この問題は、補グラフに対する最大独立集合問題と等価です。最適解をD-Waveシステムを使って求めます。

D-WaveのOcean SDKを使用して、この問題例を解くプログラムを作成し、D-Waveシステムでアニーリングします。 Ocean SDKは、D-Wave量子コンピューターをプログラミングするためのオープンソースのPythonツールのセットです。

Ocean SDKについては、以下のリンクをご参照ください。

頂点が7つある以下のグラフについて、最大クリーク(Maximum Clique)を求めます。

以下の頂点の組み合わせ3つのどれもが最大のクリークとなりそうです。(複数の最適解があります。)

  • 1,2,3
  • 3,4,5
  • 4,5,6

それでは、実際に、D-Waveシステムでこのグラフについて最大クリーク(Maximum Clique)を求めます。

D-Waveシステムへは1回の問題投入で複数のアニーリングを要求できるため、D-Waveシステムから一度に複数の解を得ることができます。

以下のように各自のPC上にD-WaveのSDKを使ってプログラムを作成し実行し、この問題を解きます。

「result=sampler.sample_qubo(Q,num_reads=1000)」の箇所でPCからD-Waveシステムへデータが転送され、量子アニーリングを設定数回分(この例では1000回)実施し、結果をPCへ戻します。

【プログラム】
import networkx as nx
from dwave_networkx.algorithms.independent_set import maximum_weighted_independent_set_qubo
from dwave.system.samplers import DWaveSampler
from dwave.system.composites import EmbeddingComposite
G = nx.Graph()
G.add_edges_from([(1,2),(1,3),(2,3),(3,4),(3,5),(4,5),(4,6),(5,6),(6,7)]) ←各辺を定義してグラフ(G)生成
compl_G= nx.complement(G) ←グラフ(G)の補グラフ(compl_G)を生成。
Q=maximum_weighted_independent_set_qubo(compl_G)
    ←補グラフ(compl_G)の最大独立集合を求めるためのQUBO(Q)をグラフ(G)から作成
print(Q)  ←Qの内容をプリント
sampler=EmbeddingComposite(DWaveSampler())  ←サンプラーを設定(D-Waveの構造にマップします)
result=sampler.sample_qubo(Q,num_reads=1000)  ←Qをマップし、D-Waveで1000回アニーリング実施
for s,e,n in result.data(['sample', 'energy', 'num_occurrences']):
    print(s, e, n)   ←1000回のアニーリングの集計結果(頂点組み合わせと、そのエネルギー値及び出現数)をプリント

【プリント出力】配列Qの内容
{(1, 1): -1.0, (2, 2): -1.0, (3, 3): -1.0, (4, 4): -1.0, (5, 5): -1.0, (6, 6): -1.0, (7, 7): -1.0, (1, 4): 2.0, (1, 5): 2.0, (1, 6): 2.0, (1, 7): 2.0, (2, 4): 2.0, (2, 5): 2.0, (2, 6): 2.0, (2, 7): 2.0, (3, 6): 2.0, (3, 7): 2.0, (4, 7): 2.0, (5, 7): 2.0}

【プリント出力】頂点組み合わせパターンと、そのエネルギー値及び出現数
{1: 1, 2: 1, 3: 1, 4: 0, 5: 0, 6: 0, 7: 0} -3.0 183
    ←「1:1」=「頂点1:選択する」、「2:1」=「頂点2:選択する」、「3:1」=「頂点3:選択する」、、、
    ←頂点1,2,3の組み合わせのエネルギー値は「-3.0」で、1000回のうち183回出現。以下同様。
{1: 0, 2: 0, 3: 0, 4: 1, 5: 1, 6: 1, 7: 0} -3.0 551
{1: 0, 2: 0, 3: 1, 4: 1, 5: 1, 6: 0, 7: 0} -3.0 263
{1: 0, 2: 0, 3: 0, 4: 1, 5: 0, 6: 1, 7: 0} -2.0 1
{1: 0, 2: 0, 3: 1, 4: 0, 5: 1, 6: 0, 7: 0} -2.0 1
{1: 0, 2: 0, 3: 0, 4: 1, 5: 1, 6: 1, 7: 1} 0.0 1

この結果から、以下の頂点の組み合わせのどれもが一番低いエネルギー値「-3.0」となりますので、最大クリークとなる頂点の組み合わせはこの3つのパターンとなります。

  • 1,2,3
  • 4,5,6
  • 3,4,5