Polynomial¶

このセクションでは二値多変数多項式クラスとその周辺関数について説明します。

二値多変数多項式¶

\(n\) 次の二値多変数多項式 \(f_n\) は次のように表されます。

\[ \begin{align}\begin{aligned}f_n \left( x_1, x_2, \cdots, x_n \right) = \sum_{ \left\{ k_1, k_2, \cdots, k_n \right\} } { a_{k_1, k_2, \cdots, k_n} x_1^{k_1} x_2^{k_2} \cdots x_n^{k_n} }\\k_i \in \left\{ 0, 1 \right\}\end{aligned}\end{align} \]

ここで \(x_i\) は二値変数を表します。以後、変数がバイナリ変数 \(\left\{0, 1\right\}\) の場合には \(x\) の代わりに \(q\) を、イジング変数 \(\left\{-1, 1\right\}\) の場合には \(x\) の代わりに \(s\) を用いることにします。

Amplify ではこのような二値多変数多項式を表すクラスとして下記が提供されます。

BinaryPoly と IsingPoly はそれぞれ変数がバイナリ変数 \(\left\{0, 1\right\}\) とイジング変数 \(\left\{-1, 1\right\}\) の多変数多項式を表します。任意の次数を (例えば三次以上も) 表現する事が可能で定数項も含まれます。次数を \(2\) に固定した場合、それぞれ QUBO 模型、イジング模型に相当します。

Note

BinaryIntPoly と IsingIntPoly は係数を整数値に制限したい場合に使用します。計算途中においても整数に限定されるため意図しない結果になることがあります。そのため通常は実数値を扱える BinaryPoly と IsingPoly の使用を勧めます。

バイナリ変数及びイジング変数の性質

\[ \begin{align}\begin{aligned}q ^ 2 &= q \quad \left( q \in \left\{ 0, 1 \right\} \right)\\s ^ 2 &= 1 \quad \left( s \in \left\{ -1, + 1 \right\} \right)\end{aligned}\end{align} \]

により、二乗以上が現れることはありません。BinaryPoly や IsingPoly はこの代数法則を取り入れた数式処理が行われます。

多項式クラスの構築¶

二値多変数多項式クラスは次のようにデフォルト構築されます (以後 BinaryPoly を例にしていますがイジング含め他の多項式クラスでも同様です)。

from amplify import BinaryPoly

f = BinaryPoly()

>>> f
0

初期値を設定するには項の集合をコンストラクタの引数に与えます。次の形式のキーと値のペアを項として解釈します。

\(k x_i x_j \cdots x_m\) \(\to\) (i, j, ..., m): k

複数の項は辞書としてまとめられます。

\(k_2 x_i x_j + k_1 x_i + c\) \(\to\) {(i, j): k2, (i): k1, (): c}

例えば、 \(f = 2 q_0 q_1 + q_0 + q_1 - 1\) の構築は次のように書くことが出来ます。

from amplify import BinaryPoly

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

>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000

定数だけは特別に単なる数値が定数の単項として扱われます。

\(c\) \(\to\) c

また、コンストラクタの引数に上記の記法を複数与えることも出来ます。

先ほどの \(f = 2 q_0 q_1 + q_0 + q_1 - 1\) は次のように書いても同一です。

from amplify import BinaryPoly

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

>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000

コンストラクタ引数に同じ多項式クラスのオブジェクトを与えるとコピーされます。

from amplify import BinaryPoly

f = BinaryPoly({(0, 1): 2, (0): 1}, {(1): 1}, -1)
g = BinaryPoly(f)

>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> g
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000

多項式の演算子¶

多項式クラスには、多項式オブジェクト同士や項・定数との間に、等価・加法・減法・乗法・除法・べき乗が定義されます。べき乗と除法については、多項式(左辺)と数値(右辺)のみ対応しています。下記では省略していますが複合代入演算子にも対応しています。

from amplify import BinaryPoly

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

>>> f + f
4.000000 q_0 q_1 + 2.000000 q_0 + 2.000000 q_1 - 2.000000
>>> f + {(0, 1, 2): 1}
q_0 q_1 q_2 + 2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f + 1
2.000000 q_0 q_1 + q_0 + q_1

>>> f - f
0
>>> f - {(0, 1): 1}
q_0 q_1 + q_0 + q_1 - 1.000000
>>> f - 2
2.000000 q_0 q_1 + q_0 + q_1 - 3.000000

>>> f * f
10.000000 q_0 q_1 - q_0 - q_1 + 1.000000
>>> f * {(2): 1}
2.000000 q_0 q_1 q_2 + q_0 q_2 + q_1 q_2 - q_2
>>> 2 * f
4.000000 q_0 q_1 + 2.000000 q_0 + 2.000000 q_1 - 2.000000

>>> f / 2
q_0 q_1 + 0.500000 q_0 + 0.500000 q_1 - 0.500000

>>> f ** 2
10.000000 q_0 q_1 - q_0 - q_1 + 1.000000

>>> f + f == 2 * f
True

変数配列を用いた構築¶

変数のインデックスは通常 \(0\) 以上のスカラー値です。一方で、変数を二次元以上のインデックスで管理したり、必要な変数を事前に用意してグループごとに管理したい場合があります。そのような時に便利なのが gen_symbols() 関数です。この関数は、指定された多項式クラスに対し指定された形の変数配列を生成します。

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 10)

>>> q
[q_0, q_1, q_2, q_3, q_4, q_5, q_6, q_7, q_8, q_9]

項を用いた多項式の構築の代わりに、変数配列 q を用いて同様の式を構築してみます。

from amplify import BinaryPoly, gen_symbols

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

>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000

任意の次元の変数配列を作成するには、配列の形に対応したサイズを追加で指定します。

from amplify import BinaryPoly, gen_symbols

q = gen_symbols(BinaryPoly, 2, 2)

>>> q
[[q_0, q_1], [q_2, q_3]]

開始番号を指定することも可能ですが、配列の形 shape をタプルで与える必要があることに注意してください。

from amplify import BinaryPoly, gen_symbols

q_a = gen_symbols(BinaryPoly, 0, (2, 2))
q_b = gen_symbols(BinaryPoly, 4, (2, 2))

>>> q_a
[[q_0, q_1], [q_2, q_3]]
>>> q_b
[[q_4, q_5], [q_6, q_7]]

Note

変数配列を用いた方法は簡便かつ対応する数式に対して直感的です。さらに、生の変数インデックスを隠蔽しユーザにとって都合の良いインデックスで変数を扱うことが出来るため、通常はこの方法で構築することを推奨します。

変数配列への値の代入¶

gen_symbols() 関数によって生成した変数配列の一部に値を代入したい場合があります。そのような時には、変数配列の要素にアクセスし値を代入することが可能です。

下記は既に解となる変数の値がわかっている場合の例です。

from amplify import BinaryPoly, gen_symbols

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

>>> f
3.000000 q_1

ある要素に別の要素の値を代入すると、要素間で同じ変数値に制約する事が可能です。

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

>>> f
4.000000 q_0 - 1.000000

変数配列を用いた解の取得¶

前述の gen_symbols() 関数による変数配列と、ソルバークラス Solver の出力値を対応づけるのに便利なのが decode_solution() 関数です。gen_symbols() 関数によって隠蔽された変数のインデックスに対して、これをユーザが直接取り扱う必要なく、変数配列と全く同一の形状で置換し変数値を取得できます。

下記が decode_solution() 関数の使用例です。

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

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

client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000

solver = Solver(client)
result = solver.solve(f)
values = result[0].values
d = decode_solution(q, values)

>>> d[0][0]
1.000000
>>> d[0][1]
0
>>> d[1][0]
0
>>> d[1][1]
1.000000

ここで q は 2x2 の変数配列です。ソルバーの出力した values と変数配列 q を用いる事で decode_solution(q, values) にて q と同一形状の \(2 \times 2\) 配列として変数値配列 d を取得しています。これにより、 \(2 \times 2\) 配列 q の内部で割り当てられているインデックスを気にする必要無く、d[0][0] というように変数配列と同様のインデックスでアクセスが可能になっています。

念のため変数配列の内部インデックスやソルバーの出力値を見ておきましょう。

>>> q
[[q_0, q_1], [q_2, q_3]]
>>> values
{0: 1, 1: 0, 2: 0, 3: 1}
>>> d
[[1.000000, 0], [0, 1.000000]]

decode_solution() 関数によって q が values で正しく置換されていることを確認できました。

上記では全ての変数配列の要素が置換されました。しかし次のような場合を考えてみましょう。

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

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

変更点として q を \(3 \times 3\) に拡張しました。先ほどと同様に、多項式をソルバーに入力し解を decode_solution() 関数で取得します。

solver = Solver(client)
result = solver.solve(f)
values = result[0].values
d = decode_solution(q, values)

>>> d
[[1.000000, 0, q_2], [0, 1.000000, q_5], [q_6, q_7, q_8]]

以前とは異なり、一部の要素について変数 q_x が残ってしまいました。多項式 f に全ての q の配列要素が登場しなかったためです。

もし、一部の変数が値に置換されず残ってしまうことが好ましくない場合には注意が必要です。これはちょうど良いサイズの変数配列を生成すれば必ずしも回避出来るわけではなく、意図せず発生してしまう事があります。例えば、数式を構築している最中に一部の変数が足し引きされて消去されてしまうことがあり得るからです。

そのような場合に備えて、decode_solution() 関数の第三引数には、置換されなかった変数に対するデフォルト値を設定できます。

solver = Solver(client)
result = solver.solve(f)
values = result[0].values
d = decode_solution(q, values, 1)

>>> d
[[1.0, 0.0, 1.0], [0.0, 1.0, 1.0], [1.0, 1.0, 1.0]]

これにより全ての変数を置き換えることに成功しました。

対象の問題設定において、もし変数のデフォルト値が定義できるのならば第三引数を与えることを推奨します。出力値の解釈時に意図しない結果を防ぐ事が可能になるためです。

Note

decode_solution() 関数に与えられる変数値は、上述の辞書型だけでなく、リスト型やより柔軟な関数オブジェクトにも対応しています。詳細は Reference を参照してください。

定式化補助関数¶

多項式クラスのための定式化補助関数として

全ての和 \(\sum_i\) に相当する sum_poly() 関数
全ての組合せの和 \(\sum_{i \ne j}\) に相当する pair_sum() 関数
全ての積 \(\prod_i\) に相当する product() 関数

が提供されています。

これらの関数には下記の三つの機能があります。

リストに対する演算¶

リスト q に対して次の演算を行います。

\[\begin{split}f &= \sum_{i = 0}^{n - 1} q_\left[ i \right] \\ f &= \sum_{i \ne j} q_\left[ i \right] q_\left[ j \right] \\ f &= \prod_{i = 0}^{n - 1} q_\left[ i \right]\end{split}\]

from amplify import BinaryPoly, sum_poly, pair_sum, product

q = gen_symbols(BinaryPoly, 3)

>>> sum_poly(q)
q_0 + q_1 + q_2

>>> pair_sum(q)
q_0 q_1 + q_0 q_2 + q_1 q_2

>>> product(q)
q_0 q_1 q_2

インデックスに対する演算¶

変数 q_i に対して次の演算を行います。

\[\begin{split}f &= \sum_{i = 0}^{n - 1} q_i \\ f &= \sum_{i \ne j} q_i q_j \\ f &= \prod_{i = 0}^{n - 1} q_i\end{split}\]

第一引数から第三引数には組み込みクラス range と同一の引数を与えるか、第一引数に列挙型を与えることも可能です。ただし最終引数には多項式クラスの型を与えてください。

from amplify import BinaryPoly, sum_poly, pair_sum, product

>>> sum_poly(3, BinaryPoly)
q_0 + q_1 + q_2
>>> sum_poly(1, 4, BinaryPoly)
q_1 + q_2 + q_3
>>> sum_poly(1, 6, 2, BinaryPoly)
q_1 + q_3 + q_5
>>> sum_poly(range(2, 7, 2), BinaryPoly)
q_2 + q_4 + q_6

>>> pair_sum(3, BinaryPoly)
q_0 q_1 + q_0 q_2 + q_1 q_2
>>> pair_sum(1, 4, BinaryPoly)
q_1 q_2 + q_1 q_3 + q_2 q_3
>>> pair_sum(1, 6, 2, BinaryPoly)
q_1 q_3 + q_1 q_5 + q_3 q_5
>>> pair_sum(range(2, 7, 2), BinaryPoly)
q_2 q_4 + q_2 q_6 + q_4 q_6

>>> product(3, BinaryPoly)
q_0 q_1 q_2
>>> product(1, 4, BinaryPoly)
q_1 q_2 q_3
>>> product(1, 6, 2, BinaryPoly)
q_1 q_3 q_5
>>> product(range(2, 7, 2), BinaryPoly)
q_2 q_4 q_6

関数に対する演算¶

関数 \(g(i)\) に対して次の演算を行います。

\[\begin{split}f &= \sum_{i = 0}^{n - 1} g\left(i\right) \\ f &= \sum_{i \ne j} g\left(i\right) g\left(j\right) \\ f &= \sum_{i \ne j} g\left(i, j\right) \quad \left(i < j \right)\\ f &= \prod_{i = 0}^{n - 1} g\left(i\right)\end{split}\]

式に対する演算¶

\[f = \prod_{i = 0}^{n - 1} { \left( 2 x_i - 1 \right) }\]

from amplify import BinaryPoly, sum_poly, pair_sum, product

q = gen_symbols(BinaryPoly, 3)

>>> product(3, lambda i: 2 * q[i] - 1)
8.000000 q_0 q_1 q_2 - 4.000000 q_0 q_1 - 4.000000 q_0 q_2 - 4.000000 q_1 q_2 + 2.000000 q_0 + 2.000000 q_1 + 2.000000 q_2 - 1.000000

ネストした演算¶

\[f = \sum_{i = 0}^{n - 1} { \left( \sum_{j = 0}^{n - 1}{ q_{i,j} - 1} \right)^2 }\]

from amplify import BinaryPoly, sum_poly, pair_sum, product

q = gen_symbols(BinaryPoly, 3, 3)

>>> sum_poly(3, lambda i: (sum_poly(3, lambda j: q[i][j]) - 1) ** 2)
2.000000 q_0 q_1 + 2.000000 q_0 q_2 + 2.000000 q_1 q_2 + 2.000000 q_3 q_4 + 2.000000 q_3 q_5 + 2.000000 q_4 q_5 + 2.000000 q_6 q_7 + 2.000000 q_6 q_8 + 2.000000 q_7 q_8 - q_0 - q_1 - q_2 - q_3 - q_4 - q_5 - q_6 - q_7 - q_8 + 3.000000

多項式クラスのメソッド¶

変数変換¶

多項式オブジェクトに含まれるインデックスを別のインデックスに変換します。

from amplify import BinaryPoly, gen_symbols

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

辞書を与えて変数 q_0 を q_3 に置換します。

>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.change_variables({0: 3})
2.000000 q_1 q_3 + q_1 + q_3 - 1.000000

リストで与える場合は、変換元のインデックスをリストのインデックスとし、変換先のインデックスをその要素の値にします。ここでは q_0 を q_3 に、q_1 を q_4 に変換します。

>>> f.change_variables([3, 4])
2.000000 q_3 q_4 + q_3 + q_4 - 1.000000

関数を与えると任意のインデックス変換が可能です。

>>> f.change_variables(lambda i: 2 * i + 2)
2.000000 q_2 q_4 + q_2 + q_4 - 1.000000

項の数¶

多項式オブジェクトにいくつの項が含まれているかを返します。

from amplify import BinaryPoly, gen_symbols

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

>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.count()
4

定数項の取得¶

多項式オブジェクトから定数項を取得します。

from amplify import BinaryPoly, gen_symbols

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

>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.constant()
-1.0

定数値への変換可能性¶

多項式オブジェクトが定数のみで構成されているかを返します。これが True の場合、数値への暗黙変換が可能です。

from amplify import BinaryPoly, gen_symbols
import math

q = gen_symbols(BinaryPoly, 10)
f = q[0] + 1
g = f - q[0]

>>> f
q_0 + 1.000000
>>> g
1.000000
>>> f.is_number()
False
>>> g.is_number()
True
>>> math.exp(g)
2.718281828459045

インデックスの最大値¶

多項式オブジェクトの項に現れる最大のインデックスを返します。

from amplify import BinaryPoly, gen_symbols

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

>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.max_index()
1

多項式への値の代入¶

多項式オブジェクトの変数に対し値を代入します。

from amplify import BinaryPoly, gen_symbols

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

辞書を与えて変数 q_0 に \(1\) を代入します。代入されない変数は置換されずに残ります。

>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.replace({0: 1})
3.000000 q_1

多項式の値の評価¶

多項式オブジェクトの全ての変数に対し値を代入します。

from amplify import BinaryPoly, gen_symbols

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

辞書を与えて変数 q_0 に \(1\)、q_1 に \(-1\) を代入します。全ての変数について対応関係を持たせる必要があるので注意してください。

>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.replace_all({0: 1, 1: -1})
-3.0

リストで与える場合は、対象のインデックスをリストのインデックスとし、代入する値をその要素に設定します。

>>> f.replace_all([1, -1])
-3.0

関数を与える場合は、インデックスを受けとって対応する値を出力するようにします。

>>> f.replace_all(lambda i: 2 * i + 1)
9.0

変数記号の変更¶

print() 関数などで文字列として多項式オブジェクトを出力したときの、変数を表す文字の取得と変更を行うプロパティです。初期値はバイナリ多項式では \(q\)、イジング多項式では \(s\) です。

from amplify import BinaryPoly, gen_symbols

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

>>> f.symbol
q
>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000

f.symbol = "x"

>>> f
2.000000 x_0 x_1 + x_0 + x_1 - 1.000000

辞書形式への変換¶

多項式を Python 辞書型に変換します。

from amplify import BinaryPoly

f = BinaryPoly(
    {(1, 2, 3): -1, (0, 1): 2, (1, 2): 1, (0): 1, 2: 1, (): -2}
)

>>> f
- q_1 q_2 q_3 + 2.000000 q_0 q_1 + q_1 q_2 + q_0 + q_2 - 2.000000
>>> f.asdict()
{(1, 2, 3): -1.0, (0, 1): 2.0, (1, 2): 1.0, (0,): 1.0, (2,): 1.0, (): -2.0}

バイナリ多項式への変換¶

イジング多項式からバイナリ多項式へ変換します。バイナリ変数 \(q\) とイジング変数 \(s\) との対応関係 \(s = 2 q - 1\) に基づいて変数変換を行います。

from amplify import IsingPoly, gen_symbols

s = gen_symbols(IsingPoly, 10)
f = -1 * s[0] * s[1] + s[0] + s[1] + 1

>>> f
- s_0 s_1 + s_0 + s_1 + 1.000000
>>> f.to_Binary()
- 4.000000 q_0 q_1 + 4.000000 q_0 + 4.000000 q_1 - 2.000000

イジング多項式への変換¶

バイナリ多項式からイジング多項式へ変換します。バイナリ変数 \(q\) とイジング変数 \(s\) との対応関係 \(q = \left(s + 1\right) / 2\) に基づいて変数変換を行います。

from amplify import BinaryPoly, gen_symbols

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

>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.to_Ising()
0.500000 s_0 s_1 + s_0 + s_1 + 0.500000

行列形式への変換¶

行列形式に変換します。ただし多項式の次数は \(2\) 以下である必要があります。

変換後には行列クラスと定数項のタプルが返却されます。行列クラスについては Matrix を参照してください。

from amplify import BinaryPoly, gen_symbols

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

>>> f
2.000000 q_0 q_1 + q_0 + q_1 - 1.000000
>>> f.to_Matrix()
([[1, 2],
 [0, 1]], -1.0)

from amplify import IsingPoly, gen_symbols

s = gen_symbols(IsingPoly, 10)
f = -1 * s[0] * s[1] + s[0] + s[1] + 1

>>> f
- s_0 s_1 + s_0 + s_1 + 1.000000
>>> f.to_Matrix()
([[1, -1],
 [0, 1]], 1.0)

変換元の多項式クラスと変換先の行列クラスの対応関係は次の通りです。

多項式クラス	行列クラス
`BinaryPoly`	`BinaryMatrix`
`IsingPoly`	`IsingMatrix`
`BinaryIntPoly`	`BinaryIntMatrix`
`IsingIntPoly`	`IsingIntPoly`