Tutorial¶

はじめに¶

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

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

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

入力レイヤ¶

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

多項式: BinaryPoly, IsingPoly, BinaryIntPoly, IsingIntPoly
行列: BinaryMatrix, IsingMatrix BinaryIntMatrix, IsingIntMatrix
論理式: LogicalPoly
制約式: BinaryConstraint, IsingConstraint, BinaryIntConstraint, IsingIntConstraint

論理レイヤ¶

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

二次多項式模型: BinaryQuadraticModel, IsingQuadraticModel, BinaryIntQuadraticModel, IsingIntQuadraticModel

物理マシンレイヤ¶

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

最適化ソルバ

Solver

マシンクライアント

Fixstars: FixstarsClient
D-Wave: DWaveClient (will be deprecated), DWaveSamplerClient, LeapHybridSamplerClient
Fujitsu: FujitsuDASolverClient, FujitsuDAPTSolverClient, FujitsuDAMixedModeSolverClient, FujitsuDA2SolverClient, FujitsuDA2PTSolverClient, FujitsuDA2MixedModeSolverClient
Toshiba: ToshibaClient

Amplify SDK によるプログラミングフロー¶

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

対象となる最適化問題を定式化し入力模型を作成する (入力レイヤ)
入力模型を二次二値多項式模型に変換する (論理レイヤ)
使用するマシンを宣言しパラメータ設定を行う (マシンレイヤ)
最適化ソルバに論理模型を与えて入力レイヤに逆変換された実行結果を得る

ここからは上記に従い各レイヤでの 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 クラスが提供されています。

BinaryPoly の構築はいくつか方法がありますが、必要な変数を配列 \(\mathbf{q} = \left\{q_0, q_1, ... \right\}\) として変数の集合を用意してから多項式を構築する方法が簡単です。

まず、変数の配列は gen_symbols() 関数により生成することが出来ます。

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 2)

>>> q
[q_0, q_1]

gen_symbols(BinaryPoly, 2) では、バイナリ変数 (BinaryPoly) として、変数インデックス \(0\) から長さ \(2\) の一次元配列を作成しました。これを用いて次のように多項式を組み立てます。

from amplify import BinaryPoly, BinaryQuadraticModel, gen_symbols

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

>>> f
f = - q_0 q_1 + 1.000000

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

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 を参照してください。

実行するマシンの設定¶

使用するマシンを宣言しマシンパラメータを設定します。ここでは Amplify Annealing Engine (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.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000    # タイムアウト1秒

Note

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx には Amplify Annealing Engine のアクセストークンを入力して下さい。無料ユーザ登録を行うことでアクセストークンが発行されます。

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.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000    # タイムアウト1秒

solver = Solver(client)
result = solver.solve(model)
for solution in result
    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.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000    # タイムアウト1秒

solver = Solver(client)
result = solver.solve(model)
values = result[0].values
print(f"q = {decode_solution(q, values)}")

q = [1.000000, 1.000000]

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

Note

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

次のステップ¶

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