🗺

D-Wave Leap の Discrete Quadratic Model を使って地図の塗り分け問題を解いてみる

2022/02/22に公開

はじめに

AIREV株式会社の上里です。
D-Wave社の量子アニーリングクラウドサービスLeapで提供されている、問題の制約を直接的に表現することができる問題定式化モデルであるConstrained Quadratic Model（CQM）に関する記事を以前に書きました。今回はその続編としまして、離散変数を直感的に扱えるという特徴をもつDiscrete Quadratic Model（DQM）を利用した問題定式化を試してみようと思います。この記事では地図の塗り分け問題をDQMで定式化し、Leapのハイブリッドソルバで解いてみます。

Discrete Quadratic Model（DQM）

DQMは離散変数を直感的に扱えるという特徴をもつ定式化モデルです。DQMの変数は {0, 1, 2, 3} や {red, green, blue, yellow} のような離散的な値をとることができます。 DQM の目的関数は $N$ 個の変数 $\{d_i\}_{i=1,...,N}$ と実数値関数 $a_i (d_i)$ 及び $b_{i,j} (d_i, d_j)$ と定数 $c$ を用いて下記のように表されます。

\begin{aligned} \sum_{i} a_i (d_i) + \sum_{i,j} b_{i,j}(d_i, d_j) + c \end{aligned}

この目的関数を最小化するような変数の値の組み合わせが問題の解となります。したがって、より目的に近い変数の値の組み合わせに対して関数 $a_i (d_i)$ 及び $b_{i,j} (d_i, d_j)$ がより小さい値を返すように目的関数を設計していくことが定式化のポイントになります。記事の後半で実際に問題の定式化を行う際に理解の助けとなりますので、この点だけ覚えておいてください。

他の定式化モデルとの比較

量子アニーリングではQUBOの形で定式化された問題を解くことができます。D-Wave LeapではQUBOと同等な定式化モデルBinary Quadratic Model（BQM）に加えて、より柔軟な定式化を行えるよう、CQM及びDQMが提供されています。DQMがBQMやCQMと比較してどのような特徴を持っているのか見てみましょう。

BQMではQUBOと同様に扱える変数が2値をとるもの（バイナリ変数）に制限されています。したがって、3つ以上の値から1つを選ぶような問題を表現する場合には、少々回りくどい方法での定式化が必要になります。具体的には、値の選択肢の数と同数の変数を用意し、選択されている値に対応する変数の値を 1 とし、他の値に対応する変数の値を 0 とするような One-hot encoding の形が典型的かと思います。（数独をBQMで定式化している記事が参考になるかと思います。）これに対してDQMの変数は3値以上の離散値をとることができるため、多くの値の選択肢を持つ変数でも簡潔に表現することができます。

また以前に紹介したCQMには問題の制約を直接表現することができるという特徴がありました。DQMではBQMと同様に目的関数内に制約としての働きをする項（ペナルティ項）を設ける形で制約を表現します。

それぞれのモデルの特徴を下の表にまとめます。

定式化モデル	利用できる変数の種別	制約の表現方法	ドキュメント	関連記事
BQM	バイナリ	目的関数のペナルティ項	リンク	リンク
CQM	バイナリ、整数値	直接設定	リンク	リンク
DQM	任意の離散値	目的関数のペナルティ項	リンク	この記事

DQMの定式化を試してみる

それでは、ここからは実際の問題をDQMでどのように定式化できるのか見ていきましょう。

実行環境

LeapやOcean SDKの初期設定についてはこの記事の対象外となりますので、必要に応じて公式ドキュメントや解説記事等を参照してください。
DQMはOcean SDKのバージョン3.0.0以降でサポートされています。この記事のコードはPython 3.9.1、Ocean SDK 4.2.0での動作を確認済みです。

例題：カナダの13州の地図塗り分け問題

今回はカナダの州を題材として地図の塗り分け問題を解いてみます。カナダの全13の州（準州を含む）に、地図上で隣り合っている州に同じ色を塗らないように4つの色を割り当てる方法を量子アニーリングを利用して探し出します。

13の州のリストを provinces 、隣り合っている州のペアのリストを borders 、4つの色のリストを colors とします。

provinces = [
  "AB", "BC", "ON", "MB", "NB", "NL", "NS",
  "NT", "NU", "PE", "QC", "SK", "YT"
]
borders = [
  ("BC", "AB"), ("BC", "NT"), ("BC", "YT"), ("AB", "SK"), ("AB", "NT"),
  ("SK", "MB"), ("SK", "NT"), ("MB", "ON"), ("MB", "NU"), ("ON", "QC"),
  ("QC", "NB"), ("QC", "NL"), ("NB", "NS"), ("YT", "NT"), ("NT", "NU")
]
colors = [0, 1, 2, 3]

変数の設定

DQMのインスタンスを生成し、変数を追加します。それぞれの州に対してどの色が割り当てられたかを示すように変数を作成していきます。具体的には、 colors の {0, 1, 2, 3} の色の値をとることができる変数をそれぞれの州ごとに作成します。

import dimod

dqm = dimod.DiscreteQuadraticModel()
for p in provinces:
  dqm.add_variable(len(colors), label=p)

CQMのときと同様、DQMのインスタンスは dimod モジュールから生成します。 add_variable メソッドは、第一引数で指定された数の離散値をとる変数をDQMに追加します。また求めた解のそれぞれの変数の値を確認する際に便利なように label 引数を利用してそれぞれの変数に州の記号のラベルをつけます。

目的関数のペナルティの設計

目的関数の式を再掲します。

\begin{aligned} \sum_{i} a_i (d_i) + \sum_{i,j} b_{i,j}(d_i, d_j) + c \end{aligned}

記事前半のDQMの目的関数の解説部分で述べたように、より目的に近い変数の値の組み合わせに対して関数 $a_i (d_i)$ 及び $b_{i,j} (d_i, d_j)$ がより小さい値を返すように目的関数を設計していくことが定式化のポイントになります。それぞれの関数の意味を考えると、関数 $a_i (d_i)$ は与えられた変数の値に対するペナルティを返す関数と考えられます。同様に関数 $b_{i,j} (d_i, d_j)$ は与えられた2つの変数の値の組み合わせに対してのペナルティを返す関数です。
今回は地図上で隣り合っている2つの州が同じ色を割り当てられてしまうケースに対して $b_{i,j} (d_i, d_j)$ が大きな値を返すように設計します。

for p0, p1 in borders:
  dqm.set_quadratic(p0, p1, {(color, color): 1 for color in colors})

set_quadratic メソッドで $b_{i,j} (d_i, d_j)$ を設定しています。第一引数と第二引数で対象の変数のペアを指定します。そして第三引数にキーが値のペア（タプル）、バリューが対応する返り値（ペナルティ）となるような dict を渡します。第三引数でキーとして指定されていない値のペアに対してはデフォルトで 0 が返るようになっています。

今回の問題ではそれぞれの変数単体の値に対してはペナルティを設定する必要がないのですが、 $a_i (d_i)$ の動作も確認してみましょう。アルバータ州 "AB" には必ず 0 の色が割り当てられるように、 1, 2, 3 の色にはペナルティ 1 を返すように設計してみます。 $a_i (d_i)$ は set_linear メソッドで設定することができます。

dqm.set_linear("AB", [0, 1, 1, 1])

ハイブリッドソルバで解いてみる

DQMで定式化した問題を実際にLeapのハイブリッドソルバで解いてみましょう。ハイブリッドソルバは古典コンピュータと量子アニーリングを組み合わせて問題を解くため、利用できる量子ビット数の制限が厳しい純粋な量子アニーリングのソルバに比べ、幅広い問題を解くことができます。

from dwave.system import LeapHybridDQMSampler

sampler = LeapHybridDQMSampler()
sampleset = sampler.sample_dqm(dqm, label='DQM example')

print(sampleset.first.energy)  # 0.0
print(sampleset.first.sample)
# {'AB': 0, 'BC': 3, 'MB': 1, 'NB': 3, 'NL': 3,
#  'NS': 2, 'NT': 1, 'NU': 0, 'ON': 3, 'PE': 1,
#  'QC': 1, 'SK': 2, 'YT': 2}

dwave.system モジュールの LeapHybridDQMSampler は、Leapのハイブリッドソルバから得られた解のパターンを取得してくれます。解のパターンは目的関数の値が小さいものから順にならんでいるため、 sampleset の first プロパティで目的関数が最小となった解を取得できます。解の目的関数の値は energy プロパティから、変数の値は sample プロパティから取得できます。
上記の結果では、アルバータ州 "AB" に 0 の色を割り当て、どの隣り合った州のペアも同じ色を割り当てられていない解が求められました。
塗り分け結果は次のようになっています。

（0 → 青、1 → 緑、2 → 赤、3 → 黄）

ローカル環境で動かしてみる

Leapのマシンを利用せずにローカル環境のCPUで試しに動かしてみたい、という方は sampler を dimod モジュールで提供されている ExactDQMSolver に差し替えると手元のCPUで動作させることができます。ただしこちらはテスト用のソルバであり、非常に低速な点に注意してください。（公式ドキュメントでもそのように言及されています。）

sampler = dimod.ExactDQMSolver()
sampleset = sampler.sample_dqm(dqm)

まとめ

今回は3つ以上の値をとる離散変数を扱える定式化モデルであるDQMを紹介し、地図の塗り分け問題を例題として実際にDQMで定式化した問題の解をLeapのハイブリッドソルバで求めてみました。
Leapで提供されているBQM、CQM、DQMはそれぞれ特徴が異なり、問題の性質によって定式化しやすいモデルを選択することができます。
Leapの使い方や定式化の方法などについても少しずつ知見が得られてきましたので、今後はより実践的な問題に対しての量子アニーリングの適用に挑戦してみたいと考えております。

参考

（2022年1月18日アクセス）