QAP.05：制約条件を仕込む１【量子コンピュータ/アニーリング@Python/Fixstars Amplify】
【はじめに】
※再掲
繰り返しになるが、量子アニーリングによるプログラムの挙動をざっくりいうと、
与えられた「数式（＋制約条件）」の中で、その「答えをできるだけ小さくする変数の組み合わせ」を見つける。
というものであった。
今回は「制約条件をもたせた目的関数（数式）」の量子アニーリングプログラミングについてざっくりとまとめていく。
【制約条件を仕込むには】
結論から言うと、制約条件を仕込むには
「目的関数」の後ろに「ペナルティ関数（※）」をつける。
※「制約条件」を破ると「目的関数」の値が「小さくなるのを邪魔する関数」のこと。
さらに「ペナルティ関数」に対しても、その「影響度を調整するための重み」を設定する。
■イメージ図
以下で具体例をあげつつ、プログラムをしてみる。
【例題】x + 2y - 3zに制約条件ある場合
次の「目的関数」の値をできるだけ小さくする「(x, y, z)の組み合わせ」を求めよう。(※x, y, zは「0または1」のどちらかの値をとる)
・目的関数：x + 2y - 3z
・制約条件：x + y + z = 2 （※３つのうち２つの変数が１になる）
※「第一回目の記事の例題」に「制約条件」を付与したもの。その時は、制約条件がなかったので(x,y,z)=(0,0,1)が正解であった。
【説明】
量子アニーリングで計算させるには、「制約条件をペナルティ関数として表現する」必要がある。
制約条件には
・「等式制約」
・「不等式制約」
・「論理式制約（OR制約、NAND制約など）」
・…
等、様々な種類がある。
ある程度こんな感じに数式で表現したらいい、というものはある。
（詳細は専門家や数学が好きな人・得意な人などに任せるとして、、、）例えば今回の場合、次のような「ペナルティ関数を含んだ数式」をつくって量子アニーリング計算をすればいい。
以上を踏まえて、プログラムを作っていく。
今回の実行環境は「Fixstars Amplify」＋「Google Colab」。
【１】ライブラリのインストール
! pip install amplify
! pip install --upgrade amplify【２】クライアントオブジェクトの作成
from amplify.client import FixstarsClient
client = FixstarsClient()
client.parameters.timeout = 1000 # タイムアウトは1000ミリ秒（1秒）
client.parameters.outputs.duplicate = True # みつかった解が複数あってもOK
client.parameters.outputs.num_outputs = 0 # 0: 見つかった解を全て出力
# トークン設定
client.token = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" # 無料登録して取得したトークンを指定する※トークンは掲載上「XXX... ...XXX」としているが、実際は「Fixstars Amplify」に無料登録して取得したトークンを設定する。
【３】変数を用意する（イジング変数/QUBO変数）
※再掲
「Fixstars Amplify」では組み合わせを見つけるための変数として「イジング変数」と「QUBO変数」を用意している。
・イジング変数：「-1」 または「1」をとる
・QUBO変数：「0」または「1」をとる
今回は「QUBO変数」を使用する。
from amplify import BinaryPoly
from amplify import SymbolGenerator
# 数式：x + 2y - 3zの係数部分相当
coef = [1, 2, -3]
gen = SymbolGenerator(BinaryPoly) # BinaryPolyを生成させる
q = gen.array(len(coef)) # BinaryPolyを指定の数だけ生成
print(q)【ここまでの実行結果】
[q_0, q_1, q_2]
▲ q_0, q_1, q_2の３つのQUBO変数を生成した。
【４】目的関数ｆを作る
「目的関数（組み合わせを探す数式）：x + 2y - 3z」を作る。
※今回は変数は「(x, y, z) ＝ (q_0, q_1, q_2)」と対応させている。
f = coef[0]*q[0] + coef[1]* q[1] + coef[2]*q[2]
# forループでまとめて作る場合
#f = sum(coef[i]*q[i] for i in range(len(coef)))
# アインシュタイン縮約表記の場合
#from amplify import einsum
#f = einsum("i,i",q,coef)
print(f)【ここまでの実行結果】
q_0 + 2 q_1 - 3 q_2
【５】ペナルティ関数ｇを作る
「制約条件：x+y+z=2」に対する「ペナルティ関数ｇ」を作成する。
今回はそのまま数式の表記通りにプログラミングする。
（※「Fixstars Amplify」が提供する「penalty()」や「equal_to()」等の「ヘルパー関数」を使ったやり方は次回説明予定）
g = (q[0]+q[1]+q[2]-2)**2
print(g)【ここまでの実行結果】
2 q_0 q_1 + 2 q_0 q_2 + 2 q_1 q_2 - 3 q_0 - 3 q_1 - 3 q_2 + 4
【６】重みを決めて数式（エネルギー式）を完成させる
最後に「ペナルティ関数ｇ」に対する「重み」を決めて、「最終的な数式（エネルギー式）」を完成させる。
今回は「重み：10」を設定し、「エネルギー式：h(q_0, q_1, q_2)」としてまとめてみる。
# 最終的な数式（エネルギー式）
# ペナルティ関数に対し「重み：10」を設定
h = f + 10*gあとは、Solverオブジェクト経由で量子アニーリング計算をさせればよい
【７】Solverオブジェクトを生成して量子アニーリング計算をする
※再掲
「Fixstars Amplify」では「Solverオブジェクト(Client設定仕込み済み)」経由で「目的関数」を解かせる。
# Solverオブジェクト生成
from amplify import Solver
solver = Solver(client)
# エネルギー式を与えて問題を解かせる
result = solver.solve(h)【８】計算結果を確認する
# 計算結果があるかを確認
if len(result) == 0:
print("no answer")▲今回は答えが求められるので何も表示されない想定。
ここも繰り返しの説明になるが、
問題によっては「複数の答え（条件に合う変数の組み合わせ）」がでることもある。そのため、計算結果はイテレータで順次取り出していく。
from amplify import decode_solution
for sol in result:
energy = sol.energy
values = sol.values
res = decode_solution(q, values)
print(f"energy = {energy}, {values} Result is {q} = {res}")【実行結果】
energy = -2.0, {2: 1, 1: 0, 0: 1} Result is [q_0, q_1, q_2] = [1. 0. 1.]
▲(q_0, q_1, q_2)=(1, 0, 1)で値 -2.0が答えとして返ってきた（正解）
【９】全体コード
最後に全体コードを示しておく。
【例題】
・x + 2y - 3zを最小にするx, y, zを探す。
ただし「x + y + z = 2（制約条件）」を満たすこと。
【実行環境】
・Fixstars Amplify ＋ Google Colab
■事前準備：ライブラリのインストール
! pip install amplify
! pip install --upgrade amplify■ここからが全体コード
from amplify import BinaryPoly
from amplify import SymbolGenerator
from amplify import Solver
from amplify import decode_solution
from amplify.client import FixstarsClient
client = FixstarsClient()
client.parameters.timeout = 1000 # タイムアウトは1000ミリ秒（1秒）
client.parameters.outputs.duplicate = True # みつかった解が複数あってもOK
client.parameters.outputs.num_outputs = 0 # 0: 見つかった解を全て出力
# トークン設定
client.token = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" # 無料登録して取得したトークンを指定する
# 係数
coef = [1, 2, -3]
# QUBO変数を3つ用意
gen = SymbolGenerator(BinaryPoly)
q = gen.array(len(coef))
print(q) # [q_0, q_1, q_2]
# 目的関数ｆ
f = coef[0]*q[0] + coef[1]* q[1] + coef[2]*q[2]
# forループでまとめて作る場合
#f = sum(coef[i]*q[i] for i in range(len(coef)))
# アインシュタイン縮約表記の場合
#from amplify import einsum
#f = einsum("i,i",q,coef)
print(f) # q_0 + 2 q_1 - 3 q_2
# ペナルティ関数ｇ
g = (q[0]+q[1]+q[2]-2)**2
print(g) # 2 q_0 q_1 + 2 q_0 q_2 + 2 q_1 q_2 - 3 q_0 - 3 q_1 - 3 q_2 + 4
# 最終的な数式（エネルギー式ｈ）
# ペナルティ関数に対し「重み：10」を設定
h = f + 10*g
# Solverオブジェクト生成
solver = Solver(client)
# エネルギー式を与えて問題を解かせる
result = solver.solve(h)
# 結果の確認(回答有無チェック)
if len(result) == 0:
print("no answer")
# 答えを出力
for sol in result:
energy = sol.energy
values = sol.values
res=decode_solution(q, values)
print(f"energy = {energy}, {values} Result is {q} = {res}") 【実行結果】
energy = -2.0, {2: 1, 1: 0, 0: 1} Result is [q_0, q_1, q_2] = [1. 0. 1.]
▲（x, y, z）= (q_0, q_1, q_2) = (1, 0, 1)の時に、値：-2.0という結果が返ってきた。
【おまけ】重みの値について
今回は適当に「重み：１０」としたが、設定する値にはある程度注意が必要である。
例えば、今回の例題で「重み：1」としてみると次のような結果が得られる。
from amplify import BinaryPoly
from amplify import SymbolGenerator
from amplify import Solver
from amplify import decode_solution
from amplify import einsum
from amplify.client import FixstarsClient
client = FixstarsClient()
client.parameters.timeout = 1000 # タイムアウトは1000ミリ秒（1秒）
client.parameters.outputs.duplicate = True # みつかった解が複数あってもOK
client.parameters.outputs.num_outputs = 0 # 0: 見つかった解を全て出力
# トークン設定
client.token = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" # 無料登録して取得したトークンを指定する
# 係数
coef = [1, 2, -3]
# QUBO変数を3つ用意
gen = SymbolGenerator(BinaryPoly)
q = gen.array(len(coef))
print(q) # [q_0, q_1, q_2]
# 目的関数ｆ
# アインシュタイン縮約表記
f = einsum("i,i",q,coef)
# ペナルティ関数ｇ
g = (q[0]+q[1]+q[2]-2)**2
# 最終的な数式（エネルギー式ｈ）
# ペナルティ関数に対し「重み：10」を設定
h = f + 1.0*g
# Solverオブジェクト生成
solver = Solver(client)
# エネルギー式を与えて問題を解かせる
result = solver.solve(h)
# 結果の確認(回答有無チェック)
if len(result) == 0:
print("no answer")
# 答えを出力
for sol in result:
energy = sol.energy
values = sol.values
res=decode_solution(q, values)
print(f"energy = {energy}, {values} Result is {q} = {res}") 【実行結果】
energy = -2.0, {2: 1, 1: 0, 0: 0} Result is [q_0, q_1, q_2] = [0. 0. 1.]
energy = -2.0, {2: 1, 1: 0, 0: 1} Result is [q_0, q_1, q_2] = [1. 0. 1.]
▲（x, y, z）= (q_0, q_1, q_2) = (0, 0, 1)の時に値：-2.0というパターンがでてきてしまう。
これは設定した「重みの値」がよくなかったことが原因である。
設定する「重みの値」次第では、
「ペナルティ関数」があまり影響を与えないようになり、量子アニーリングとしては正しい挙動だが、求めたい答えにたどり着いていない（制約条件を満たしていない等）』ということがありえる。
「重み」はある程度大きくしておく必要がある。
ただし、大きすぎると大雑把な解しか出なくなり、最適解にたどり着かないこともあるので、適当に調整しつつ「いい感じになりそうな重み」を設定していく。
いいなと思ったら応援しよう！
