Polynomial

このセクションでは、最適化問題の定式化に使用する多項式クラスとその周辺について説明します。

参考

このページを読む前に Tutorial にて Amplify SDK の基本的な使用方法について確認してください。

二値多変数多項式

Amplify SDK では二値 (バイナリまたはイジング) 変数の多変数多項式を使用して定式化することが出来ます。\(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\) は二値変数、\(a_{k_1, k_2, \cdots, k_n}\) は任意の実数を表します。以後、変数がバイナリ変数 \(\left\{0, 1\right\}\) の場合には \(x\) の代わりに \(q\) を、イジング変数 \(\left\{-1, 1\right\}\) の場合には \(x\) の代わりに \(s\) を用いることにします。ここで、バイナリ変数及びイジング変数の性質

\[ \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} \]

により、多項式では二乗以上が現れることはありません。

Amplify SDK ではバイナリ変数とイジング変数の代数法則に従う多項式を表すクラスとして下記が提供されます。

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

注釈

BinaryIntPoly と IsingIntPoly は係数を整数値に制限したい場合に使用します。計算途中においても整数に限定されるため意図しない結果になることがあります。そのため通常は実数値を扱える 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 q_0 q_1 + q_0 + q_1 - 1

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

\(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 q_0 q_1 + q_0 + q_1 - 1

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

from amplify import BinaryPoly

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

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> g
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 + f
4 q_0 q_1 + 2 q_0 + 2 q_1 - 2
>>> f + {(0, 1, 2): 1}
q_0 q_1 q_2 + 2 q_0 q_1 + q_0 + q_1 - 1
>>> f + 1
1 q_0 q_1 + q_0 + q_1

>>> f - f
0
>>> f - {(0, 1): 1}
q_0 q_1 + q_0 + q_1 - 1
>>> f - 2
2 q_0 q_1 + q_0 + q_1 - 3

>>> f * f
10 q_0 q_1 - q_0 - q_1 + 1
>>> f * {(2): 1}
2 q_0 q_1 q_2 + q_0 q_2 + q_1 q_2 - q_2
>>> 2 * f
4 q_0 q_1 + 2 q_0 + 2 q_1 - 2

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

>>> f ** 2
10 q_0 q_1 - q_0 - q_1 + 1

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

変数配列を用いた構築

上記の多項式の構築では、変数のインデックスを明示的に整数値で与える必要がありました。しかし、複雑な問題を定式化する際には、二次元以上のインデックスで変数を管理したり、複数の変数をまとめて取り扱いたい場合があります。

変数インデックスを便利に扱うために、Amplify SDK では多項式配列クラスが提供されます。多項式配列クラスは NumPy ndarray の多項式版のように振る舞います。多項式配列クラスを活用すると、高度な定式化を高速に処理することが可能です。

参考

多項式配列クラスの詳細については Polynomial Array を参照してください。

定式化に用いる変数配列を動的に発行するために SymbolGenerator() が用意されています。SymbolGenerator() で構築されるオブジェクトは、変数をインデックス0から順に発行し、任意の次元の形状に整形し多項式配列として返却する機能を持ちます。これを用いることで、多項式の変数インデックスを隠蔽し、プログラムコードにおいてユーザの使いやすい変数として名前を付けることが可能です。

次のようにして指定された長さの変数配列を生成します。

from amplify import BinaryPoly, SymbolGenerator

gen = SymbolGenerator(BinaryPoly)   # BinaryPoly の変数ジェネレータを宣言
q = gen.array(10) # 長さ 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, SymbolGenerator

gen = SymbolGenerator(BinaryPoly)
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1

任意の次元の変数配列を作成するには配列の形状を指定します。配列の形状を引数またはタプルで与えます。例えば、変数を \(4 \times 4\) の二次元インデックスで管理したい場合には、次のようにして変数配列を生成します。

from amplify import BinaryPoly, SymbolGenerator

# BinaryPoly の変数ジェネレータを定義
gen = SymbolGenerator(BinaryPoly)   # BinarySymbolGenerator を用いても同様
# 4 x 4 の変数配列を生成
q1 = gen.array(shape=(4, 4))  # gen.array(4, 4) としても同様

>>> q1
[[ q_0,  q_1,  q_2,  q_3],
 [ q_4,  q_5,  q_6,  q_7],
 [ q_8,  q_9, q_10, q_11],
 [q_12, q_13, q_14, q_15]]

変数配列 q の実体は q_0 から q_15 の16個の変数で構成されています。変数配列を用いることで、実体の変数インデックスに直接触れずに、配列インデックスを指定して、例えば q[2, 3] というアクセスが出来ます。

複数の配列を生成することも可能です。先ほどの変数ジェネレータ gen を用いて、何度でも array() メソッドを呼び出すことが出来ます。

from amplify import BinaryPoly, SymbolGenerator

# BinaryPoly の変数ジェネレータを定義
gen = SymbolGenerator(BinaryPoly)  # BinarySymbolGenerator を用いても同様
q1 = gen.array(4, 4)  # 4 x 4 の変数配列を生成
q2 = gen.array(shape=(2, 3)) # 2 x 3 の変数配列を生成

>>> q1
[[ q_0,  q_1,  q_2,  q_3],
 [ q_4,  q_5,  q_6,  q_7],
 [ q_8,  q_9, q_10, q_11],
 [q_12, q_13, q_14, q_15]]
>>> q2
[[q_16, q_17, q_18],
 [q_19, q_20, q_21]]

変数配列 q1 と q2 の実体は異なるインデックスであることに注意してください。変数配列を生成する度に、実体のインデックスは一つずつ増加していきます。つまり、異なる変数配列は異なる変数の集合として扱われます。

変数ジェネレータからスカラー変数を生成したい場合は、scalar() メソッドを用います。

from amplify import BinaryPoly, SymbolGenerator

# BinaryPoly の変数ジェネレータを定義
gen = SymbolGenerator(BinaryPoly)  # BinarySymbolGenerator を用いても同様
q = gen.array(shape=(4, 4))  # 4 x 4 の変数配列を生成
r = gen.scalar()

>>> r
q_16

変数のインデックスの開始番号を指定して変数ジェネレータを作成することが出来ます。この機能は互換性のために用意されているので、通常は使用する必要は無いでしょう。

from amplify import BinaryPoly, SymbolGenerator

# 開始インデックス4の BinaryPoly の変数ジェネレータを定義
gen = SymbolGenerator(BinaryPoly, 4)  # BinarySymbolGenerator を用いても同様
q = gen.array(shape=(2, 3)) # 2 x 3 の変数配列を生成

>>> q
[[q_4, q_5, q_6],
 [q_7, q_8, q_9]]

注釈

以前のバージョンとの互換性のために、gen_symbols() 関数が提供されています。これは次のような効果を持ちます。

gen_symbols(PolyType, *args):: SymbolGenerator(PolyType).array(*args)
gen_symbols(PolyType, start, shape):: SymbolGenerator(PolyType, start).array(shape)

複数の変数配列を生成する場合に gen_symbols() 関数を用いると、変数インデックスの開始番号 start をユーザ自身で計算して指定する必要があります。開始番号を誤ると多項式の構築が意図しない結果になるため、SymbolGenerator() を用いることを推奨します。

SymbolGenerator() は下記のクラスオブジェクトを生成する関数として設定されています。変数ジェネレータクラス、例えば BinarySymbolGenerator クラスを直接用いても良いでしょう。

変数ジェネレータクラス	エイリアス
`BinarySymbolGenerator`	`SymbolGenerator(BinaryPoly)`
`IsingSymbolGenerator`	`SymbolGenerator(IsingPoly)`
`BinaryIntSymbolGenerator`	`SymbolGenerator(BinaryIntPoly)`
`IsingIntSymbolGenerator`	`SymbolGenerator(IsingIntPoly)`

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)

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

変数配列への値の代入

変数配列の一部の要素に対して値を固定する場合や事前に解がわかっている場合には、配列要素にインデックスを指定して値を設定することが可能です。

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
q[0] = 1    # q[0] = 1 に固定する
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
3 q_1

ある要素に別の要素の値を代入すると、実体を同じ変数とすることが可能です。

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
q[1] = q[0] # q[1] = q[0] に固定する
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
4 q_0 - 1

上記の例では、配列要素に定数や単項を設定しましたが、任意の多項式オブジェクトを設定することが出来ます。

注釈

多項式配列に値を設定する場合は、多項式 (上記の例では f ) を構築する前に行ってください。多項式配列は参照ではなく実体を保持しているため、多項式を構築した後に配列要素に値を設定したとしても後から影響は与えられません。

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

多項式配列と、ソルバークラス Solver の出力を対応づけには、decode() メソッドを使用すると便利です。辞書形式で解を与えると、変数配列のそれぞれの要素に代入し同一の形状の数値型 numpy 配列を返却します。

下記が decode() メソッドの使用例です。

from amplify import BinarySymbolGenerator, Solver
from amplify.client import FixstarsClient

# 変数配列の生成
gen = BinarySymbolGenerator()
q = gen.array(shape=(2, 2))
print(f"q = {q}")

# 多項式の構築
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]
)
print(f"f = {f}")

# イジングマシンクライアントの設定
client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000

# マシンの実行
solver = Solver(client)
result = solver.solve(f)
values = result[0].values

# 解のデコード
print(f"solution = {q.decode(values)}")

q = [[q_0, q_1], [q_2, q_3]]
f = q_0 q_1 + q_0 q_2 - q_0 q_3 + q_1 q_3 + q_2 q_3
solution = [[1. 0.], [0. 1.]]

変数配列 q にソルバーの出力した values を適用することで、q の要素それぞれに対し解の代入が行われ q と同一形状の \(2 \times 2\) 配列として返却されます。

念のため変数配列の中身とソルバーの出力値を見てきましょう。

>>> q
[[q_0, q_1], [q_2, q_3]]
>>> values
{0: 1, 1: 0, 2: 0, 3: 1}
>>> q.decode(values)
array([[1., 0.],
       [0., 1.]])

配列要素それぞれに対して正しく置換されていることを確認できました。

上記では全ての変数配列の要素が置換されました。しかし、定式化において変数配列の一部の要素のみが使用された場合を考えてみましょう。

from amplify import BinarySymbolGenerator, Solver
from amplify.client import FixstarsClient

gen = BinarySymbolGenerator()
q = gen.array(shape=(4, 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]
)

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

変更箇所として q が \(4 \times 2\) に拡張されています。多項式そのものは変更が無いため解は先ほどの結果と同様です。

>>> f
q_0 q_1 + q_0 q_3 - q_0 q_4 + q_1 q_4 + q_3 q_4
>>> values
{0: 1, 1: 0, 2: 0, 3: 1}

このような場合、使用されなかった変数 q_4, q_5, q_6, q_7 に対する解は不定、つまり二値どちらの値でも良いことになります。途中計算において一部の変数が消去されてしまった場合も同様のことが起こりえます。decode() メソッドは、このような場合にデフォルト値 1 で変数を置換します。

>>> q.decode(values)
array([[1., 0.],
       [0., 1.],
       [1., 1.],
       [1., 1.]])

明示的にデフォルト値を別の値に指定することも可能です。decode() メソッドの最後の引数にデフォルト値を指定します。

>>> q.decode(values, default=0)
array([[1., 0.],
       [0., 1.],
       [0., 0.],
       [0., 0.]])

ただし、デフォルト値に None を指定した場合は特別な動作を行います。この時、変数の置換は行われず不定の変数が残されます。

>>> q.decode(values, default=None)
[[  1,   0],
 [  0,   1],
 [q_4, q_5],
 [q_6, q_7]]

注釈

デフォルト値に None を指定した場合、decode() メソッドの返却するオブジェクトは NumPy array ではなく Python list 型であることに注意してください

注釈

以前のバージョンとの互換性のために、decode_solution() 関数が提供されています。これは次のような効果を持ちます。

decode_solution(poly_array, *args):: poly_array.decode(*args)

論理式の構築

バイナリ変数 \(\left\{0, 1\right\}\) の \(0\) を False、\(1\) を True と見なした論理演算を行う事が出来ます。例えば、ブール変数 \(x_0, x_1\) に対する論理和 \(x_0 \lor x_1\) を表すバイナリ変数多項式は次のようにして得られます。

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
x = gen.array(2)

>>> x[0] | x[1]
- q_0 q_1 + q_0 + q_1

この多項式 - q_0 q_1 + q_0 + q_1 と下記の真理値表を見比べると、全ての取り得る状態について多項式が真理値表と同じ値になることが確認できます。

\(x_0\)	\(x_1\)	\(x_0 \lor x_1\)	\(-x_0 x_1 + x_0 + x_1\)
0	0	0	0
0	1	1	1
1	0	1	1
1	1	1	1

バイナリ変数多項式では論理演算子として、論理積 &, 論理和 |, 排他的論理和 ^ 及びそれぞれの複合代入演算子 &=, |=, ^= と論理否定 ~ が提供されます。これらの演算子を用いると、論理式で表される組合せ最適化問題、あるいは充足可能性問題をバイナリ変数多項式で定式化することが出来ます。

それぞれの演算子の効果は次の通りです。ここで、多項式 \(f_0\) と \(f_1\) は変数の取り得る全ての場合について \(0\) または \(1\) を満たすものとします。それ以外の値を取り得る場合の動作は未定義です。

論理演算	出力
\(f_0 \lor f_1\)	\(-f_0 f_1 + f_0 + f_1\)
\(f_0 \land f_1\)	\(f_0 f_1\)
\(f_0 \oplus f_1\)	\(-2 f_0 f_1 + f_0 + f_1\)
\(\lnot f_0\)	\(- f_0 + 1\)

定式化の一例として、最大SAT問題をバイナリ変数多項式で表します。最大SAT問題は与えられた論理式を充足する節 (括弧) の数を最大にするようなブール変数の組合わせを求める問題です。例えば次のような論理式が与えられたとして、

\[\left( \lnot x_0 \lor x_1 \right) \land \left(\lnot x_0 \lor x_2 \right) \land \left(x_1 \lor x_2 \right) \land \left(x_0 \lor \lnot x_2 \right)\]

ブール変数 \(x_0, x_1, x_2\) の全ての取り得る値について True となる節の数を最大化します。この場合4となれば全ての節が充足し論理式全体として True になります。

この問題は次のようにしてバイナリ変数多項式の最小化問題で表されます。

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
x = gen.array(3)
f = - (~x[0] | x[1]) - (~x[0] | x[2]) - (x[1] | x[2]) - (x[0] | ~x[2])

全ての節についてバイナリ変数多項式として表し和を取っています。マイナスの符号がついているのは充足数の最大化問題を最小化問題に変換しているためです。次のようにして、目的関数がどのように表されるのかを確認できます。

>>> f
- q_0 q_1 - 2 q_0 q_2 + q_1 q_2 + 2 q_0 - q_1 - 3

これをバイナリ変数の組合せ最適化問題として解くことで解が得られます。

from amplify import Solver
from amplify.client import FixstarsClient

# イジングマシンクライアントの設定
client = FixstarsClient()
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 1000

# マシンの実行
solver = Solver(client)
result = solver.solve(f)

>>> print(f"number of satisfied clauses: {int(-result[0].energy)}")
number of clauses: 4
>>> print(f"x = {x.decode(result[0].values).astype(bool)}")
x = [ True  True  True]

これにより、4つ全ての節を充足する変数 \(x_0, x_1, x_2\) の解を求めることが出来ました。

定式化補助関数

多項式クラスの数式処理を支援する関数が提供されます。

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

バイナリ変数多項式では次の論理式に関する支援を行う関数も提供されます。

全ての論理積 \(\land_i\) に相当する intersection() 関数
全ての論理和 \(\lor_i\) に相当する union() 関数
全ての排他的論理和 \(\oplus_i\) に相当する symmetric_difference() 関数

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

リストに対する演算

リスト 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 BinarySymbolGenerator, sum_poly, pair_sum, product

gen = BinarySymbolGenerator()
q = gen.array(3)

>>> q
[q_0, q_1, q_2]
>>> 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

注釈

多項式配列に対する和の演算は、実行速度の面から組み込み関数 sum() より sum_poly() 関数を使用することを推奨します。

多次元の多項式配列に対する sum_poly() 関数を適用した結果は、軸を指定しない sum() メソッドと同一の結果となります。任意の軸に対する和を計算する場合には、sum() メソッドを使用してください。

from amplify import BinarySymbolGenerator, sum_poly, pair_sum, product

gen = BinarySymbolGenerator()
q = gen.array(3, 3)

>>> q
[[q_0, q_1, q_2],
 [q_3, q_4, q_5],
 [q_6, q_7, q_8]]
>>> sum_poly(q)
q_0 + q_1 + q_2 + q_3 + q_4 + q_5 + q_6 + q_7 + q_8
>>> q.sum()
q_0 + q_1 + q_2 + q_3 + q_4 + q_5 + q_6 + q_7 + q_8
>>> q.sum(axis=0)
[q_0 + q_3 + q_6, q_1 + q_4 + q_7, q_2 + q_5 + q_8]

バイナリ変数多項式では次の論理演算が可能です。

\[ \begin{align}\begin{aligned}l &= \bigwedge_{i = 0}^{n - 1} x_\left[ i \right]\\l &= \bigvee_{i = 0}^{n - 1} x_\left[ i \right]\\l &= \bigoplus_{i = 0}^{n - 1} x_\left[ i \right]\end{aligned}\end{align} \]

from amplify import BinarySymbolGenerator, intersection, union, symmetric_difference

gen = BinarySymbolGenerator()
x = gen.array(3)

>>> intersection(x)
q_0 q_1 q_2
>>> union(x)
q_0 q_1 q_2 - q_0 q_1 - q_0 q_2 - q_1 q_2 + q_0 + q_1 + q_2
>>> symmetric_difference(x)
4 q_0 q_1 q_2 - 2 q_0 q_1 - 2 q_0 q_2 - 2 q_1 q_2 + q_0 + q_1 + q_2

関数に対する演算

関数 \(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}\]

第一引数に数値範囲を与えるか、第一引数から第三引数に組み込み関数 range と同一の引数を与えて数値範囲を指定し、最後の引数に適用する関数を与えます。すなわち、sum_poly(start[, stop, step], func) は sum_poly(range(start[, stop, step]), func) に相当します。

pair_sum() 関数には引数を二つ持つ関数を与えることも可能です。

例: 式に対する演算

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

from amplify import BinarySymbolGenerator, sum_poly, pair_sum, product

gen = BinarySymbolGenerator()
q = gen.array(3)

>>> q
[q_0, q_1, q_2]
>>> product(3, lambda i: 2 * q[i] - 1)
8 q_0 q_1 q_2 - 4 q_0 q_1 - 4 q_0 q_2 - 4 q_1 q_2 + 2 q_0 + 2 q_1 + 2 q_2 - 1

例: ネストした演算

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

from amplify import BinarySymbolGenerator, sum_poly, pair_sum, product

gen = BinarySymbolGenerator()
q = gen.array(3, 3)

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

バイナリ変数多項式では次の論理演算が可能です。

\[ \begin{align}\begin{aligned}l &= \bigwedge_{i = 0}^{n - 1} g\left( i \right)\\l &= \bigvee_{i = 0}^{n - 1} g\left( i \right)\\l &= \bigoplus_{i = 0}^{n - 1} g\left( i \right)\end{aligned}\end{align} \]

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

変数 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

バイナリ変数多項式では次の論理演算が可能です。

\[ \begin{align}\begin{aligned}l &= \bigwedge_{i = 0}^{n - 1} x_i\\l &= \bigvee_{i = 0}^{n - 1} x_i\\l &= \bigoplus_{i = 0}^{n - 1} x_i\end{aligned}\end{align} \]

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

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

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

アインシュタインの縮約記法

複数の多項式配列に対してアインシュタイン縮約記法を表す添え字文字列に従い和を演算します。 einsum() 関数のエイリアスです。機能の詳細は多項式配列による定式化を参照してください。

参考

多項式配列に対する numpy.einsum() として機能します。引数の記法や機能について numpy.einsum() も参考にしてください。

下記の二次元配列 \(q\) に対するアインシュタインの縮約記法の計算例は次の通りです。

from amplify import BinarySymbolGenerator, sum_poly, pair_sum, product

gen = BinarySymbolGenerator()
q = gen.array(3, 3)

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

二次元配列の要素和 \(s\) を計算します。

\[s = \sum_i \sum_j {q_{ij}}\]

>>> sum_poly("ij->", q)
q_0 + q_1 + q_2 + q_3 + q_4 + q_5 + q_6 + q_7 + q_8

行方向の和から計算される一次元配列 \(p\) を返却します。

\[p_i = \sum_j {q_{ij}}\]

>>> sum_poly("ij->i", q)
[q_0 + q_1 + q_2, q_3 + q_4 + q_5, q_6 + q_7 + q_8]

各行と各列の内積から計算される二次元配列 \(p\) を返却します。

\[p_{ik} = \sum_j {q_{ij} q_{jk}}\]

>>> sum_poly("ij,jk->ik", q, q)
[[q_1 q_3 + q_2 q_6 + q_0, q_0 q_1 + q_1 q_4 + q_2 q_7, q_0 q_2 + q_1 q_5 + q_2 q_8],
 [q_0 q_3 + q_3 q_4 + q_5 q_6, q_1 q_3 + q_5 q_7 + q_4, q_2 q_3 + q_4 q_5 + q_5 q_8],
 [q_0 q_6 + q_3 q_7 + q_6 q_8, q_1 q_6 + q_4 q_7 + q_7 q_8, q_2 q_6 + q_5 q_7 + q_8]]

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

変数変換

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

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

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

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

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

>>> f.change_variables([3, 4])
2 q_3 q_4 + q_3 + q_4 - 1

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

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

項の数

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

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.count()
4

定数項の取得

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

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.constant()
-1.0

定数値への変換可能性

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

from amplify import BinarySymbolGenerator
import math

gen = BinarySymbolGenerator()
q = gen.array(10)
f = q[0] + 1
g = f - q[0]

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

次数

多項式オブジェクトの次数を返します。多項式オブジェクトが \(0\) と等価な場合、\(-1\) を返します。

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.degree()
2

一次以下であるか

多項式オブジェクトが一次以下の多項式であるかどうかを返します。

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.is_linear()
False

二次以下であるか

多項式オブジェクトが二次以下の多項式であるかどうかを返します。

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.is_quadratic()
True

インデックスの最大値

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

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.max_index()
1

多項式への代入と値の評価

多項式オブジェクトの変数に値を代入するには decode() メソッドを使用します。

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

変数のインデックスと値を辞書形式で与えて変数 q_0 に \(1\) を代入します。変数インデックスが辞書のキーに見つからない場合は、デフォルト値として 1 で置換されます。

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.decode({0: 1})    # q_0 = 1, q_1 は暗黙的に1で代入
3.0

明示的にデフォルト値を別の値に指定するには、引数 default で指定します。

>>> f.decode({0: 1}, default=0)    # q_0 = 1, q_1 は暗黙的に0で代入
0.0

デフォルト値に None を指定した場合は、値が与えられていない変数の置換は行われず変数として残ります。

>>> f.decode({0: 1}, default=None)    # q_0 = 1, q_1 は残す
3 q_1

変数の値をリストで与えることも出来ます。変数のインデックスと代入する値をリストのインデックスとその要素に設定します。

>>> f.decode([1, 0])   # q_0 = 1, q_1 = 0 を代入する
0.0

インデックスを受け取り値を返す関数を与えることも出来ます。

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

注釈

以前のバージョンとの互換性のために、replace() メソッドと replace_all() メソッドが提供されています。これらは decode() メソッドと同様に変数の置換を行いますが、下記の差異があります。

poly.replace(dict):: poly.decode(`dict`, default=None) と同一だが replace は返値の型は定数であっても多項式型
poly.replace_all(list, default):: poly.decode(`list`, `default`) と同一だが replace_all は default に None は指定できない
poly.replace_all(dict, default):: poly.decode(`dict`, `default`) と同一だが replace_all は default に None は指定できない

変数記号の変更

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

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f.symbol
q
>>> f
2 q_0 q_1 + q_0 + q_1 - 1

f.symbol = "x"

>>> f
2 x_0 x_1 + x_0 + x_1 - 1

辞書形式への変換

多項式を 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 q_0 q_1 + q_1 q_2 + q_0 + q_2 - 2
>>> 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 IsingSymbolGenerator

gen = IsingSymbolGenerator()
s = gen.array(10)
f = -1 * s[0] * s[1] + s[0] + s[1] + 1

>>> f
- s_0 s_1 + s_0 + s_1 + 1
>>> f.to_Binary()
- 4 q_0 q_1 + 4 q_0 + 4 q_1 - 2

デフォルトの変数変換ではバイナリ変数 \(0, 1\) はそれぞれイジング変数 \(-1, 1\) に対応しますが、キーワード引数 ascending に False を与えることで変数の対応関係を逆にすることができます。この場合、関係式 \(s = -2 q + 1\) に基づいて変数変換が行われます。

>>> f
- s_0 s_1 + s_0 + s_1 + 1
>>> f.to_Binary(ascending=False)
- 4 q_0 q_1 + 2

イジング変数の多項式への変換

バイナリ変数の多項式からイジング変数の多項式へ変換します。デフォルトでは、バイナリ変数 \(q\) とイジング変数 \(s\) との対応関係 \(q = \left(s + 1\right) / 2\) に基づいて変数変換が行われます。また、キーワード引数 ascending に False を与えると、関係式 \(q = \left(-s + 1\right) / 2\) に基づいて変数変換が行われます。

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

>>> f
2 q_0 q_1 + q_0 + q_1 - 1
>>> f.to_Ising()
0.5 s_0 s_1 + s_0 + s_1 + 0.5
>>> f.to_Binary(ascending=False)
0.5 s_0 s_1 - s_0 - s_1 + 0.5

行列形式への変換

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

変換後には行列クラスと定数項のタプルが返却されます。

参考

行列クラスについては Matrix を参照してください。

from amplify import BinarySymbolGenerator

gen = BinarySymbolGenerator()
q = gen.array(10)
f = 2 * q[0] * q[1] + q[0] + q[1] - 1

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

from amplify import IsingSymbolGenerator

gen = IsingSymbolGenerator()
s = gen.array(10)
f = -1 * s[0] * s[1] + s[0] + s[1] + 1

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

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

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