当社はCookieを使用して、お客様が当社のWebサイトでより良い体験を得られるようにしています。引き続き閲覧する場合は、当社グループのプライバシーポリシー 
に同意したことになります。
Jupyter Notebookで実行する
チュートリアルFixstars Amplify チュートリアルへようこそ。
Amplify は、量子アニーリングマシン・イジングマシンを手軽かつ効率的に利用するためのプラットフォームです。
Amplify を使うと、組合せ最適化問題の最適化アプリケーションを素早く作成することができます。
また、多様なイジングマシンへ対応しており、その変更コストも小さいため、様々なイジングマシンへの移植の手間が大幅に削減されます。
このチュートリアルでは、Amplifyを使って容易かつ高速に組合せ最適化問題を解く方法を学びます。 このチュートリアルは以下の内容を含みます。
このチュートリアルでは、オンライン環境でAmplifyを使用しながら使い方を学んでいきます。 Amplifyをお手元のコンピュータ上で動作させたい場合は、Quick Startに従ってインストールを行ってください。
量子アニーリングマシン・イジングマシンは、イジング模型または QUBO 模型で表現された最適化問題を解くシステムです。 イジング模型や QUBO 模型を使って組合せ最適化問題を定式化することができれば、量子アニーリングマシンやイジングマシンを用いて 組合せ最適化問題の解を得ることができます。
組合せ最適化問題とは、整数・順列のような離散的な値で表現される変数を決定するための基準を表現したものです。
組合せ最適化問題の多くは、以下に示す 決定変数、目的関数、制約条件 の3つを使って表現します。
例えば、最適化問題の例として以下のようなものがあります。
巡回セールスマン問題は、セールスマンが複数の都市を出来るだけ移動距離が短くなるように1度ずつ訪問するための移動順序を定める問題です。 この組合せ最適化問題の表現は
となります。
グラフ彩色問題は、隣り合う領域と色が等しくならないように、領域を塗り分ける問題です。 この組合せ最適化問題の表現は
となります。
イジング模型や QUBO 模型は、量子アニーリングマシン・イジングマシンが扱うことのできる問題の種類です。 様々な組合せ最適化問題を量子アニーリングマシン・イジングマシンで解くために、組合せ最適化問題をイジング模型・QUBO 模型へ変換する必要があります。
QUBO 模型は、下記のような式で表されます。
$ \displaystyle H = \sum_{i<j} J_{ij} q_i q_j + \sum_i h_i q_i \quad q_i\in\{0, +1 \} $
また、イジング模型は、下記のような式で表されます。
$ \displaystyle H = \sum_{i<j} J_{ij} s_i s_j + \sum_i h_i s_i \quad s_i\in\{+1, -1 \} $
イジング模型と QUBO 模型の違いは扱う変数の値のみです。両者は適切な式変形により相互に問題を変換できます。
このようにイジング模型や QUBO 模型を通じて組合せ最適化問題を解く上で、 Amplify が担う大きな役割は以下の2つです。
例えば、一般の組合せ最適化問題では制約条件の種類として、等式制約や不等式制約が登場します。しかし、イジング模型・QUBO 模型ではこのような制約を直接的に記述することはできず、 ユーザーが工夫する必要があります。また、イジング模型や QUBO 模型で最適化した結果が元の問題で制約条件を満たしているか確認したり、一部の変数を 定数として扱ったりする場合等に柔軟な対応を行うのは大変です。
Amplify では、出来るだけ直感的にイジング模型・ QUBO 模型で問題を定式化するための多数の機能を備えています。
現在、様々な量子アニーリングマシンやイジングマシンの研究開発が行われており、マシンのアップデートやそれに伴う性能向上も盛んに行われています。 そのような、アップデートを重ねるマシンへの追従を行ったり、仕様の異なる様々なマシンを利用するためのコストが高い状況です。
各マシンの仕様が異なる例として、各マシンで直接実行できる問題形式への変換があります。 各量子アニーリングマシン・イジングマシンでは必ずしもイジング模型や QUBO 模型を直接解けるとは限りません。 マシンによっては、それぞれのマシンが直接扱うことのできる模型へと更に変換を施したうえで問題を解く必要がある場合があるため、変換が必要なマシンに対しては個別の変換処理を行う必要があります。 また、各マシンに解くべき問題を送信するためのリクエストはマシン毎に異なるため、各マシンの仕様に合わせて実装する必要があります。
Amplify では、そのようなマシンの仕様差を吸収し、ごく少量のコード変更で自由に異なるマシンを試すことができます。
それでは、次の節から Amplify を使って組合せ最適化問題を解く方法を学んでいきましょう。
アニーリングマシンの入力形式である「二値変数二次多項式」の一種である「イジング模型」について説明します。
イジング模型は以下のような形のイジング変数の多項式関数で表されます。
$ \displaystyle H = \sum_{i<j} J_{ij} s_i s_j + \sum_i h_i s_i \quad s_i\in\{+1, -1 \} $
例題として、下記のイジング変数 {+1,-1} についての関数 (二値変数二次多項式) の最小化問題を取り上げます。
$ \displaystyle f(s_0, s_1) = 1 - s_0 s_1 $
$s_0,s_1 \in \{+1, -1\}$ なので $f(s_0=1,s_1=1)=0 $ が最適解の一つとなります。
これをAmplifyを用いて表現してみます。
AmplifyではIsingPolyクラスを用いて、イジング模型の多項式を表現することができます。イジング変数の定義には
IsingSymbolGenerator
を用います。
from amplify import IsingPoly, IsingSymbolGenerator
# イジング変数s_0, s_1を定義
gen = IsingSymbolGenerator()
s = gen.array(2)
# 目的関数 f = 1 - s_0 * s_1 を定義
f = 1 - s[0] * s[1]
print(f"f = {f}")
こうして作成した二値変数二次多項式の最小化問題をアニーリングマシンで実行して、解を得られるか確認してみましょう。
from amplify import Solver
from amplify.client import FixstarsClient
# クライアントの設定
client = FixstarsClient() # Fixstars Amplify AE
client.parameters.timeout = 1000 # タイムアウト1秒
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # ローカル環境で使用する場合は、Amplify AEのアクセストークンを入力してください
# ソルバーの構築
solver = Solver(client) # ソルバーに使用するクライアントを設定
# 問題を入力してマシンを実行
result = solver.solve(f) # 問題を入力してマシンを実行
上記の例で、solver.solve にてマシンを実行し、得られた結果 result は下記の属性を持つオブジェクトになっています。
solutions: 実行結果のリスト。各要素は以下の属性を持ちます。energy: エネルギー値（入力模型の評価値）values: 上記の energy に対応した入力変数の辞書（キーは変数のインデックス、値はその変数の値）frequency: 同一の解の個数例えば、実行結果のリストの先頭にある解は result.solutions[0].values で取得できます。
同じことが、result[0].valuesでも実現できます。
これは、resultへの要素アクセスが透過的にresult.solutionsの要素へのアクセスとなるためです。
変数配列の各要素に対して解の値を取得したい場合は decode メソッドを使用します。
for sol in result: # 複数の解をイテレート
# sol.values: 決定変数の値（キーをインデックス、値を変数値とする辞書）
# sol.energy: 目的関数の値（目的関数に決定変数を代入した値）
solution = s.decode(sol.values) # 変数配列sをsol.valuesでデコード
print(f"result: {s} = {solution} (f = {sol.energy})")
最適解として、$s_0=1,s_1=1$ が得られました。
アニーリングマシンのもう一つの入力形式である「QUBO模型」について説明します。
QUBOとはQuadratic Unconstrained Binary Optimizationの略で、制約条件なし0-1整数二次計画問題のことです。
QUBO模型は以下のような形のバイナリ変数の多項式関数で表されます。
$ \displaystyle H = \sum_{i<j} J_{ij} q_i q_j + \sum_i h_i q_i \quad q_i\in\{0, +1 \} $
QUBO模型における2変数の問題の例を見てみます。
$ \displaystyle f(q_0, q_1) = 1 - q_0 q_1 $
$f(q_0=1,q_1=1)=0 $ が最適解となります。
これをAmplifyを用いて表現してみます。
まずは、目的関数を定義します。
from amplify import BinaryPoly, BinarySymbolGenerator
# イジング変数q_0, q_1を定義
gen = BinarySymbolGenerator()
q = gen.array(2)
# 目的関数 1 - q_0 * q_1 を定義
f = 1 - q[0] * q[1]
print(f"f = {f}")
先ほどと同様に、この目的関数の最適解を求めます。
from amplify import decode_solution, Solver
from amplify.client import FixstarsClient
# クライアントの設定
client = FixstarsClient() # Fixstars Optigan
client.parameters.timeout = 1000 # タイムアウト1秒
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # ローカル環境で使用する場合は、Amplify AEのアクセストークンを入力してください
# ソルバーの構築
solver = Solver(client) # ソルバーに使用するクライアントを設定
# 問題を入力してマシンを実行
result = solver.solve(f) # 問題を入力してマシンを実行
for sol in result: # 複数の解をイテレート
# sol.values: 決定変数の値（キーをインデックス、値を変数値とする辞書）
# sol.energy: 目的関数の値（目的関数に決定変数を代入した値）
solution = q.decode(sol.values) # 変数配列qをsol.valuesでデコード
print(f"result: {q} = {solution} (f = {sol.energy})")
最適解として、$q_0=1,q_1=1$ が得られました。
