D-Waveのサンプリング機能を使って最適解群を求める

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

ここでは、最大独立集合（MIS：Maximum Independent Set）問題を例にとって、D-Waveシステムのサンプリング機能をご紹介します。 MISは、与えられたグラフの頂点同士を結ぶ辺を持たない頂点の集合です。この例では、D-Waveシステムを使用して、頂点の数を最大にする組み合わせを見つけます。

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

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

• GitHub上のOcean SDK：https://github.com/dwavesystems/dwave-ocean-sdk
• ドキュメント：https://docs.ocean.dwavesys.com/en/latest/

 

以下に示されている結果では、その一部に最適には及ばないものがあることがわかります。 D-Waveシステムは確率的であるため、通常、返された結果の間で回答の分布が見られ、その一部は最適ではない場合があります。このため、ほとんどの場合、D-Waveシステムに問題を投入する際に複数のアニーリングを要求する必要があります。

量子アニーリングを使用すると、大きな問題でもサンプル群が非常に高速に生成されます。また、後で説明するように、追加のアニールは、問題を解く必要な時間にわずかな影響を及ぼします。

例1

頂点が7つある以下のグラフについて、最大独立集合(Maximum-Independent-Set)を求めます。

 

※　このグラフの場合、頂点1を選択すると、頂点2，3は選択できません。

頂点3を選択すると、頂点1，2，4，5は選択できません。

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

• 1，4，7
• 1，5，7
• 2，4，7
• 2，5，7

それでは、実際に、D-Waveシステムでこのグラフについて最大独立集合(Maximum-Independent-Set)を求めます。

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）生成

Q=maximum_weighted_independent_set_qubo(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, 2): 2.0, (1, 3): 2.0, (2, 3): 2.0, (3, 4): 2.0, (3, 5): 2.0, (4, 5): 2.0, (4, 6): 2.0, (5, 6): 2.0, (6, 7): 2.0}

【プリント出力】頂点組み合わせパターンと、そのエネルギー値及び出現数

{1: 0, 2: 1, 3: 0, 4: 0, 5: 1, 6: 0, 7: 1} -3.0 189

←「1：0」＝「頂点1：選択しない」、「2：1」＝「頂点2：選択する」、「3：0」＝「頂点3：選択しない」、、、

←頂点2，5，7の組み合わせのエネルギー値は「-3.0」で、1000回のうち189回出現。以下同様。

{1: 1, 2: 0, 3: 0, 4: 1, 5: 0, 6: 0, 7: 1} -3.0 252

{1: 0, 2: 1, 3: 0, 4: 1, 5: 0, 6: 0, 7: 1} -3.0 316

{1: 1, 2: 0, 3: 0, 4: 0, 5: 1, 6: 0, 7: 1} -3.0 236

{1: 0, 2: 0, 3: 1, 4: 0, 5: 0, 6: 1, 7: 0} -2.0 2

{1: 1, 2: 0, 3: 0, 4: 0, 5: 0, 6: 1, 7: 0} -2.0 1

{1: 0, 2: 0, 3: 1, 4: 0, 5: 0, 6: 0, 7: 1} -2.0 3

{1: 0, 2: 1, 3: 0, 4: 1, 5: 1, 6: 0, 7: 1} -2.0 1

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

• 2，5，7
• 1，4，7
• 2，4，7
• 1，5，7

※　D-Waveシステムで、この量子アニーリングに要したQPU時間は238606 µs（約0.2秒）でした。

＜QPU時間　：　QPU（quantum processing unit）を使用した時間＞

例2

次は、以下のグラフについて、最大独立集合(Maximum-Independent-Set)を求めます。

例1のプログラムの辺の定義のみを書き換えて、実行します。

【プログラム】

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),(2,3),(3,4),(4,5),(5,1),(6,8),(8,10),(10,7),(7,9),(9,6),(1,6),(2,7),(3,8),(4,9),(5,10)])

Q=maximum_weighted_independent_set_qubo(G)

print(Q)

sampler=EmbeddingComposite(DWaveSampler())

result=sampler.sample_qubo(Q,num_reads=1000)

for s,e,n in result.data([‘sample’, ‘energy’, ‘num_occurrences’]):

print(s, e, n)

【結果】

{(1, 1): -1.0, (2, 2): -1.0, (3, 3): -1.0, (4, 4): -1.0, (5, 5): -1.0, (6, 6): -1.0, (8, 8): -1.0, (10, 10): -1.0, (7, 7): -1.0, (9, 9): -1.0, (1, 2): 2.0, (1, 5): 2.0, (1, 6): 2.0, (2, 3): 2.0, (2, 7): 2.0, (3, 4): 2.0, (3, 8): 2.0, (4, 5): 2.0, (4, 9): 2.0, (5, 10): 2.0, (6, 8): 2.0, (6, 9): 2.0, (8, 10): 2.0, (10, 7): 2.0, (7, 9): 2.0}

{1: 0, 2: 1, 3: 0, 4: 1, 5: 0, 6: 1, 7: 0, 8: 0, 9: 0, 10: 1} -4.0 287

{1: 1, 2: 0, 3: 1, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 1, 10: 1} -4.0 144

{1: 0, 2: 1, 3: 0, 4: 0, 5: 1, 6: 0, 7: 0, 8: 1, 9: 1, 10: 0} -4.0 107

{1: 1, 2: 0, 3: 0, 4: 1, 5: 0, 6: 0, 7: 1, 8: 1, 9: 0, 10: 0} -4.0 197

{1: 0, 2: 0, 3: 1, 4: 0, 5: 1, 6: 1, 7: 1, 8: 0, 9: 0, 10: 0} -4.0 243

{1: 0, 2: 0, 3: 1, 4: 0, 5: 1, 6: 0, 7: 1, 8: 0, 9: 0, 10: 0} -3.0 1

{1: 0, 2: 1, 3: 0, 4: 0, 5: 1, 6: 1, 7: 0, 8: 0, 9: 0, 10: 0} -3.0 2

{1: 0, 2: 1, 3: 0, 4: 0, 5: 1, 6: 0, 7: 0, 8: 1, 9: 0, 10: 0} -3.0 1

{1: 0, 2: 0, 3: 1, 4: 0, 5: 1, 6: 1, 7: 0, 8: 0, 9: 0, 10: 0} -3.0 1

{1: 0, 2: 1, 3: 0, 4: 1, 5: 0, 6: 1, 7: 0, 8: 0, 9: 0, 10: 0} -3.0 2

{1: 0, 2: 0, 3: 0, 4: 1, 5: 0, 6: 1, 7: 1, 8: 0, 9: 0, 10: 0} -3.0 4

{1: 1, 2: 0, 3: 0, 4: 1, 5: 0, 6: 0, 7: 0, 8: 1, 9: 0, 10: 0} -3.0 2

{1: 0, 2: 0, 3: 1, 4: 0, 5: 1, 6: 0, 7: 0, 8: 0, 9: 1, 10: 0} -3.0 1

{1: 0, 2: 1, 3: 0, 4: 0, 5: 1, 6: 0, 7: 0, 8: 0, 9: 1, 10: 0} -3.0 1

{1: 0, 2: 0, 3: 1, 4: 0, 5: 0, 6: 1, 7: 0, 8: 0, 9: 0, 10: 1} -3.0 2

{1: 1, 2: 0, 3: 1, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0, 10: 1} -3.0 1

{1: 0, 2: 1, 3: 0, 4: 1, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0, 10: 1} -3.0 1

{1: 1, 2: 0, 3: 1, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 1, 10: 0} -3.0 2

{1: 1, 2: 0, 3: 0, 4: 1, 5: 0, 6: 0, 7: 1, 8: 0, 9: 0, 10: 1} -2.0 1

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

• 2，4，6，10
• 1，3，9，10
• 2，5，8，9
• 1，4，7，8
• 3，5，6，7

※　D-Waveシステムで、量子アニーリングに要したQPU時間は238622 µs（約0.2秒）でした。

例1のグラフより頂点の数、辺の数が多くなっていますが、QPU時間はほとんど変わりません。

例3

次は、例2のグラフに頂点、辺を追加し、最大独立集合(Maximum-Independent-Set)を求めます。

 

例2のプログラムの辺の定義のみを以下のように書き換えて、実行します。

G.add_edges_from([(1,2),(2,3),(3,4),(4,5),(5,1),(6,8),(8,10),(10,7),(7,9),(9,6),(1,6),(2,7),(3,8),(4,9),(5,10),(1,11),(2,12),(3,13),(4,14),(5,15),(11,12),(12,13),(13,14),(14,15),(15,11)])

エネルギーが最小（-6.0）の組み合わせ（最適解）として、以下の10パターンが得られます。最大頂点数は6です。

{1: 0, 2: 1, 3: 0, 4: 1, 5: 0, 6: 1, 7: 0, 8: 0, 9: 0, 10: 1, 11: 1, 12: 0, 13: 1, 14: 0, 15: 0} -6.0 96

{1: 0, 2: 1, 3: 0, 4: 1, 5: 0, 6: 1, 7: 0, 8: 0, 9: 0, 10: 1, 11: 0, 12: 0, 13: 1, 14: 0, 15: 1} -6.0 68

{1: 1, 2: 0, 3: 0, 4: 1, 5: 0, 6: 0, 7: 1, 8: 1, 9: 0, 10: 0, 11: 0, 12: 1, 13: 0, 14: 0, 15: 1} -6.0 20

{1: 1, 2: 0, 3: 1, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 1, 10: 1, 11: 0, 12: 1, 13: 0, 14: 1, 15: 0} -6.0 284

{1: 1, 2: 0, 3: 0, 4: 1, 5: 0, 6: 0, 7: 1, 8: 1, 9: 0, 10: 0, 11: 0, 12: 0, 13: 1, 14: 0, 15: 1} -6.0 25

{1: 0, 2: 0, 3: 1, 4: 0, 5: 1, 6: 1, 7: 1, 8: 0, 9: 0, 10: 0, 11: 0, 12: 1, 13: 0, 14: 1, 15: 0} -6.0 88

{1: 0, 2: 0, 3: 1, 4: 0, 5: 1, 6: 1, 7: 1, 8: 0, 9: 0, 10: 0, 11: 1, 12: 0, 13: 0, 14: 1, 15: 0} -6.0 100

{1: 0, 2: 1, 3: 0, 4: 0, 5: 1, 6: 0, 7: 0, 8: 1, 9: 1, 10: 0, 11: 1, 12: 0, 13: 0, 14: 1, 15: 0} -6.0 82

{1: 1, 2: 0, 3: 1, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 1, 10: 1, 11: 0, 12: 1, 13: 0, 14: 0, 15: 1} -6.0 146

{1: 0, 2: 1, 3: 0, 4: 0, 5: 1, 6: 0, 7: 0, 8: 1, 9: 1, 10: 0, 11: 1, 12: 0, 13: 1, 14: 0, 15: 0} -6.0 65

※　D-Waveシステムで、この量子アニーリングに要したQPU時間は238640µs（0.238640秒）でした。

例1、2のグラフより頂点の数、辺の数が多くなっていますが、QPU時間はほとんど変わりません。

【参照】　ホワイトペーパー「14-1038A-A_Finding_Multiple_Optimal_Solutions_Using_Sampling_Functionality_D-Wave」