Tutorial

はじめに

Amplify はイジングマシンを手軽に扱うためのミドルウェアライブラリです。イジングマシンとは、イジング模型 あるいは QUBO模型 と呼ばれる、二次二値多変数多項式の最小化問題に対する専用のハードウェアです。下記はQUBOによる表現例になります。

\[f = \sum_{i < j}{Q_{i,j} q_i q_j} + \sum_{i}{Q_{i,i} q_i} \quad \left(q_i \in \left\{ 0, 1\right\} \right)\]

通常、イジングマシンを実行するためには「対象となる最適化問題」を「実行マシンへ入力可能な形式」に変換する必要があります。 なぜなら多くのイジングマシンは、バイナリ変数 \(\left\{0, 1\right\}\) または イジング変数 \(\left\{-1, 1\right\}\) の二次多項式のみを入力可能形式とし (論理模型) 、マシンによっては任意の二次二値多項式を扱えるわけではなく、ハードウェア仕様に起源する変数間のグラフ構造に従った形式 (物理模型) で表現する必要があるためです。

ユーザの対象とする最適化問題 (入力模型) をイジングマシンで実行する場合、入力模型から論理模型に変換し、さらに論理模型をマシン固有の物理模型に変換するという手順を踏みます。一方、マシンの出力値を解釈するためにこの手順の逆変換を各々のステップに施します。この変換・逆変換処理では、変換に伴う制約条件等の「前処理」や出力値の逆変換に伴う制約条件の充足検査等の「後処理」もまた重要になります。

Amplify は最適化問題をイジングマシンで実行するための統合インターフェースを提供し、入力模型やマシンの仕様に依存した変換・逆変換や前処理・後処理を隠蔽します。また、入力模型の作成や結果の解釈を行うための支援機能を提供します。Amplify のアーキテクチャについてはリファレンス 1 を参照してください。次の図は Amplify によるイジングマシンへの入力から実行及び結果の解釈までのフローを表します。

_images/architecture.png
1

松田佳希 “イジングマシンにおける共通ソフトウェア基盤開発” 2020年電子情報通信学会総合大会

各フローと Amplify が提供するクラスの対応関係は次の通りです。

入力レイヤ

ユーザがイジングマシンへの「入力模型」として直接操作を行います。下記の数式を取り扱うことが出来ます。

多項式

BinaryPoly, IsingPoly, BinaryIntPoly, IsingIntPoly

行列

BinaryMatrix, IsingMatrix BinaryIntMatrix, IsingIntMatrix

論理式

LogicalPoly

制約式

BinaryConstraint, IsingConstraint, BinaryIntConstraint, IsingIntConstraint

論理レイヤ

構築した入力模型をイジングマシンが取り扱うことが可能な「論理模型」として抽象化します。

二次多項式模型

BinaryQuadraticModel, IsingQuadraticModel, BinaryIntQuadraticModel, IsingIntQuadraticModel

物理マシンレイヤ

最適化ソルバによって各ハードウェア仕様に基づき論理模型を「物理模型」に変換します。ユーザが直接変換コードを記述する必要はなく、各マシンの実行パラメータの操作のみを行います。

最適化ソルバ

Solver

マシンクライアント
Fixstars

FixstarsClient

D-Wave

DWaveClient, DWaveSamplerClient, LeapHybridSamplerClient

Fujitsu

FujitsuDASolverClient, FujitsuDAPTSolverClient, FujitsuDAMixedModeSolverClient, FujitsuDA2SolverClient, FujitsuDA2PTSolverClient, FujitsuDA2MixedModeSolverClient

Toshiba

ToshibaClient

Amplify を使用したイジングマシン使用の流れは次の通りです。

  1. 対象となる最適化問題を定式化し入力模型を作成する (入力レイヤ)

  2. 入力模型を二次二値多項式模型に変換する (論理レイヤ)

  3. 使用するマシンを宣言しパラメータ設定を行う (マシンレイヤ)

  4. 最適化ソルバに論理模型を与えて入力レイヤに逆変換された実行結果を得る

ここからは上記に従い各レイヤでの Amplify の実際の使用手順について説明します。

問題の作成

まずは上述の「入力模型」の取り扱いについて説明します。最も単純な例題として、下記のバイナリ変数 \(\left\{0, 1\right\}\) についての関数 (バイナリ多項式) の最小化問題を取り上げます。

\[f\left( q_0, q_1 \right) = 1 - q_0 q_1\]

\(q_0, q_1 \in \left\{ 0, 1 \right\}\) なので自明に \(f \left( q_0 = 1, q_1 = 1 \right) = 0\) が最適解となります。ここから実際にこの問題をマシンに入力し、適切な解が出力されるかを確認していきます。

バイナリ多項式をプログラムコード上で表現するために BinaryPoly クラスが提供されています。

from amplify import BinaryPoly

f = BinaryPoly(1, {(0, 1): -1})
print(f"f = {f}")

これは次のように出力されます。

f = - q_0 q_1 + 1.000000

BinaryPoly のコンストラクタで与えている 1, {(0, 1): -1}\(1 - q_0 q_1\) と解釈されます。コンストラクタに与える多項式の各項は、変数インデックスのタプルをキーとし値を係数とする辞書で表されます。定数項については空のタプルか、または定数そのものを与えてください。

デフォルトコンストラクタでは値 \(0\) の多項式が生成されます。これに項を後から追加することも出来ます。

f = BinaryPoly()
f += {(0, 1): -1, (): 1}
print(f"f = {f}")a
f = - q_0 q_1 + 1.000000

この記法の代わりに、先に変数集合 \(\mathbf{q} = \left\{q_0, q_1, ... \right\}\) を用意してから多項式を構築する事も可能です。変数配列は gen_symbols() 関数により得ることが出来ます。

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 2)
f = 1 - q[0] * q[1]
print(f"f = {f}")
f = - q_0 q_1 + 1.000000

gen_symbols(BinaryPoly, 2) では、バイナリ変数 (BinaryPoly) として、変数インデックス \(0\) から長さ \(2\) の一次元配列を作成しています。この方法では、プログラムコード上でよりシステマティックに多項式を構築することが可能です。二次元以上の配列や、指定の値からインデックスを開始することも出来ます。詳細は 変数配列を用いた構築 を参照してください。

Exercise

多項式の次数や項を変更し意図通り構築されることを確認してください (三次以上も可能です)。

論理模型への変換

次に入力模型から論理模型を構築します。今回は BinaryPoly を入力として持つので、論理模型として BinaryQuadraticModel に変換します。この変換は、後述する最適化ソルバクラス Solver にて暗黙的に行う事も出来ますが、ここでは下記の様に model 変数で明示化します。

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols

q = gen_symbols(BinaryPoly, 2)
f = 1 - q[0] * q[1]
model = BinaryQuadraticModel(f)

この論理模型の構築には、多項式の他に行列や制約式を与えたり、または多項式と制約式、行列と制約式、といった組合せで与えることも可能です。また、論理模型の内部表現や内部状態についてはいくつかのメソッドで取得が可能ですが、このチュートリアルでは割愛します。

Note

多項式や行列と制約式の組合せについては 論理模型オブジェクトの構築 を参照してください。

Note

制約式を入力模型とした実行例は EXAMPLES を参照してください。

クライアントの設定

使用するマシンを宣言しマシンパラメータを設定します。ここでは FixstarsClient を例として設定を行います。

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols
from amplify.client import FixstarsClient

q = gen_symbols(BinaryPoly, 2)
f = 1 - q[0] * q[1]
model = BinaryQuadraticModel(f)

client = FixstarsClient()
client.url = "http://xxx.xxx.xxx.xxx"
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000    # タイムアウト1秒

Note

client.parameters.urlclient.parameters.token はそれぞれ指定された URL と API トークンを入力してください。

Note

他のクライアントを使用する場合のパラメータは Client 内のそれぞれのクライアントリファレンスを参照してください。

最適化ソルバの実行

以上で準備は完了です。最適化ソルバ Solver にクライアントを設定し、solve() メソッドを呼ぶことでマシンが実行されます。マシンからは複数の解が出力されることがあるので、次のようにして先頭から取り出します。今回はシンプルなバイナリ多項式のみを入力模型としましたが、制約式を与えた場合には制約を満たす解だけがフィルタされて出力されます。

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols, Solver
from amplify.client import FixstarsClient

q = gen_symbols(BinaryPoly, 2)
f = 1 - q[0] * q[1]
model = BinaryQuadraticModel(f)

client = FixstarsClient()
client.url = "http://xxx.xxx.xxx.xxx"
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000    # タイムアウト1秒

solver = Solver(client)
result = solver.solve(model)
for solution in result.solutions:
    print(f"energy = {solution.energy}\nvalues = {solution.values}")
energy = 0.0
values = {0: 1, 1: 1}

表示された値のうち energy は入力模型の \(f\) の値を、values は入力インデックスと変数の値を表す辞書を表します。つまり今回表示されている解は \(f\left( q_0 = 1, q_1 = 1 \right) = 0\) を意味します。これは最初に想定した最適解と一致します。

入力変数と出力変数を関係づけるために、decode_solution() 関数を使用すると便利です。この関数は入力模型の構築時に使用した変数配列をデコードし出力値の配列に変換します。

from amplify import (
    BinaryPoly,
    BinaryQuadraticModel,
    gen_symbols,
    Solver,
    decode_solution,
)
from amplify.client import FixstarsClient

q = gen_symbols(BinaryPoly, 2)
f = 1 - q[0] * q[1]
model = BinaryQuadraticModel(f)

client = FixstarsClient()
client.url = "http://xxx.xxx.xxx.xxx"
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000    # タイムアウト1秒

solver = Solver(client)
result = solver.solve(model)
values = result.solutions[0].values
print(decode_solution(q, values))
[1.000000, 1.000000]

decode_solution(q, values) は変数配列 q に対して入力インデックスと変数の値を表す辞書 values を適用させます。これにより入力模型の構築時と同様に解の解釈を効率的に行う事が可能になります。

Note

変数配列のインデックスに対して変数値が存在しない場合には値の適用が行われません。decode_solution() の第三引数にデフォルト値を設定すると、そのような場合にデフォルト値を適用します。詳細は 変数配列を用いた解の取得 を参照してください。

次のステップ

以上が Amplify を用いたイジングマシンの基本的流れになります。 より高度な使用方法については次セクション以降に、具体的な問題に対する実行例については EXAMPLES、クラスや関数のリファレンスは Reference を確認してください。