日本システム開発株式会社からAIに関するコラムをお届けします。

推論システム開発に2017年から携わっている実績に基づき、様々な情報を発信しています。

日本システム開発の技術、
覗いてみませんか。

AIコラム第14回「クラウドプラットフォームFixstars Amplify上でイジングマシンを動かしてみる」

2022.12.06

今回は、Fixstars Amplify社が提供するイジングマシンFixstars Amplify Annealing Engineのデモ環境を試してみます。

題材として、二次割当問題と呼ばれるタスクをイジングマシンを用いて解いてみました。

イジングマシンとは

量子コンピュータの一種です。

量子コンピュータの方式「量子ゲート方式」「量子アニーリング方式」「イジングマシン」のうち、イジングマシンに属するものです。

量子ゲート方式	量子アニーリング方式	イジングマシン
Google IBM ION Q Microsoft Rigetti Computing XANADU	D-Wave Systems	NTT 東芝 Fixstars

* 量子ゲート方式：量子回路に基づいた計算を実行でき応用先が多いが、ハードウェアの製造が研究段階
* 量子アニーリング方式：組み合わせ最適化に特化したマシン
* イジングマシン：FPGAやGPU等を利用して、量子アニーリング方式と同様の組み合わせ最適化計算を行う

Fixstars Amplify Annealing Engineは「イジングマシン」に相当し、組み合わせ最適化計算を行います。

解きたい問題を後述するQUBO形式またはイジング形式で定式化することで、イジングマシンにより解を計算することができます。

QUBO形式による定式化

QUBO形式とイジング形式による定式化は相互に変換可能なので、ここではQUBO形式による定式化について説明します。

QUBO形式による定式化では、バイナリ変数 b_i∈{ 0, 1 } を用いて以下のような目的関数を定義します。

※ f(b) = \sum_{i,j=1}^N Q_{i,j} b_i b_j

上記のような定式化ができれば、目的関数を最小化するような q_0, …, q_N の値をイジングマシンで計算できます。

例えば

※f(b) = 2 b_0 b_1 – b_1 + b_2

を最小化すると q_0 = 0, q_1 = 1, b_2 = 0 のような解が得られます。

さらに、 b_1+b_2 = 1 のような制約条件を与えることができます。

制約条件は、(係数) * (b_1 + b_2 – 1)^2 のような項をf(b)に加えることで実現できます。

オンライン実行環境

Fixstars Amplify上でユーザー登録しログインすると、オンラインデモが実行できます。

また「サンプルコード」をクリックすることで、Jupyter Notebook 環境を利用できます。

二次割当問題（Quadratic Assignment Problem）を解く

今回は以下のような、二次割当問題に該当する問題をイジングマシンを使って解きます。

施設 0…4 を場所 0…4 にそれぞれ割り当てたい。

施設iと施設j間の移動人数 Pij、場所iと場所j 間の移動距離 Tij がある場合に、「移動人数 x 移動距離」の合計を最小化する。

Pの値

facilities = [

　　[0, 15, 12, 8, 7],

　　[15, 0, 14, 2, 4],

　　[12, 14, 0, 6, 6],

　　[8, 2, 6, 0, 11],

　　[7, 4, 6, 11, 0]

]

Tの値

facilities = [

　　[0, 4, 7, 6, 10],

　　[4, 0, 2, 5, 4],

　　[7, 2, 0, 8, 7],

　　[6, 5, 8, 0, 12],

　　[10, 4, 7, 12, 0]

]

まずQUBO変数 q_ij を定義します。

q_ij = 1 の場合に、施設 i を場所 j に割り当てることを考えると、以下のように目的関数を定式化できます。

※ $$ f(b) = \sum_{i,j,k!=i,l!=j} p_{i,k} t_{j,l} q_{i,j} q_{k,l} $$

これは以下のように実装できます。

In [13]:

from amplify import (

　　gen_symbols,

　　BinaryPoly,

)

N = 5

facilities = [

　　[0, 15, 12, 8, 7],

　　[15, 0, 14, 2, 4],

　　[12, 14, 0, 6, 6],

　　[8, 2, 6, 0, 11],

　　[7, 4, 6, 11, 0]

]

locations = [

　　[0, 4, 7, 6, 10],

　　[4, 0, 2, 5, 4],

　　[7, 2, 0, 8, 7],

　　[6, 5, 8, 0, 12],

　　[10, 4, 7, 12, 0]

]

# QUBO変数を生成

q = gen_symbols(BinaryPoly, N, N)

# モデル化

ij_arr = []

for i in range(N):

　　for j in range(N):

　　　　ij_arr.append((i, j))

cost = 0

for i, j in ij_arr:

　　neighbours = [var for var in ij_arr if var[0] != i and var[1] != j]

　　for i2, j2 in neighbours:

　　　　c = facilities[i][i2] * locations[j][j2] / 2.0

　　　　cost += c * q[i][j] * q[i2][j2]

print(“目的関数 f = “, cost)

１つの施設を１つの場所に割り当てるので、以下のような制約条件を定義します。

※ $$ \sum_{i} q_{i,j} = 1 \quad \text{for all j} $$

※ $$ \sum_{j} q_{i,j} = 1 \quad \text{for all i} $$

これは以下のように実装できます。

In [14]:

from amplify import sum_poly, BinaryQuadraticModel

from amplify.constraint import equal_to

const_1 = sum (

　　[equal_to (sum_poly (N, lambda j: q[i][j]), 1) for i in range(N)]

)

const_2 = sum (

　　[equal_to (sum_poly (N, lambda i: q[i][j]), 1) for j in range(N)]

)

constraints = const_1 + const_2

目的関数と制約条件を足すことで、最終的な二値多項式模型が得られます。

In [15]:

constraints *= 1000　# 強さを設定

# 目的関数と制約条件を結合する

model = cost + constraints

最後にイジングマシンを用意し、二値多項式模型を渡して実行します。

In [16]:

from amplify import Solver

from amplify.client import FixstarsClient

client = FixstartsClient()

client.parameters.timeout = 1000　# タイムアウト1秒

solver = Solver(client)

# 問題を解く

result = solver.solve(model)

結果を確認することで、施設 0,1,2,3,4 を場所 1,4,2,3,0 に割り当てた場合に、最小のコスト 470 となることがわかりました。

In [17]:

from amplify import decode_solution

import numpy as np

# result が空の場合は制約条件が満たされず、解が求まらない

if len(result) == 0:

　　raise RuntimeError (“Given constraint conditions are not satisfied”)

for sol in result:

　　values = sol.values

　　energy = sol.energy

　　print (f”energy = {energy}“)

　　print (f”q = {decode_solution (q, values)}“)

solution = np.array(decode_solution(q, result[0].values))

print ()

for i, j in ij_arr:

　　if solution[i][j] == 1:

　　　　print (f”Facility {i} assigned to Location {j}“)

energy = 470.0

q = [[0. 1. 0. 0. 0]

　[0. 0. 0. 0. 1.]

　[0. 0. 1. 0. 0.]

　[0. 0. 0. 1. 0.]

　[1. 0. 0. 0. 0.]]

Facility 0 assigned to Location 1

Facility 1 assigned to Location 4

Facility 2 assigned to Location 2

Facility 3 assigned to Location 3

Facility 4 assigned to Location 1

まとめ

イジングマシンであるFixstars Amplify Annealing Engineを用いて、二次割当問題の解を求めました。

オンラインデモのページではチュートリアルが充実しているので、興味がある方はぜひ試してみてください。

量子コンピューティングの応用先や現在の立ち位置については、以下サイトが参考になります。

二次割当問題の定式化やパラメータは以下サイトを参考にしました。

最後までお読みいただき、ありがとうございました。

AIコラム 第14回「クラウドプラットフォームFixstars Amplify上でイジングマシンを動かしてみる」

イジングマシンとは

QUBO形式による定式化

オンライン実行環境

二次割当問題（Quadratic Assignment Problem）を解く

まとめ

■関連サービス

AIコラム第14回「クラウドプラットフォームFixstars Amplify上でイジングマシンを動かしてみる」