Matrix

このセクションでは行列形式による定式化について説明します。行列形式ではバイナリ変数とイジング変数の二次多項式相当する行列クラスが提供されます。

注釈

行列形式は多項式で扱うには非効率なほど項の数が多い密結合の問題を扱う場合に使用されます。大まかに Amplify SDK の使い方を知る場合には、このセクションは飛ばしても構いません。

二次多項式の行列表現

二次多項式の行列表現を次のように上三角行列で定義します。

バイナリ変数の二次多項式

\[f = \sum_{i < j}{Q_{i,j} q_i q_j} + \sum_{i}{Q_{i,i} q_i} \quad \left(q_i \in \left\{ 0, 1\right\} \right)\]

一次の項を対角項に、二次の項を非対角項に配置して、行列 \(Q\) を定義します。

\[\begin{split}Q = \left(\begin{array}{ccccc} Q_{0,0} \\ & \ddots & & \LARGE Q_{i,j} \\ & & Q_{i,i} \\ & \huge 0 & & \ddots \\ & & & & \end{array}\right)\end{split}\]

多項式と行列 \(Q\) の関係は次のように表されます。

\[f = q^{\mathrm{T}} Q q\]

ここで、変数はベクトル \(q^{\mathrm{T}} = \left(q_0, q_1, \cdots \right)\) を用いて表しました。

イジング変数の二次多項式

\[f = \sum_{i < j}{J_{i,j} s_i s_j} + \sum_{i}{h_i s_i} \quad \left(s_i \in \left\{ -1, +1\right\} \right)\]

バイナリ変数の場合と同様に、一次の項を対角項に、二次の項を非対角項に配置して、行列 \(J\) を定義します。

\[\begin{split}J = \left(\begin{array}{ccccc} h_{0} \\ & \ddots & & \LARGE J_{i,j} \\ & & h_{i} \\ & \huge 0 & & \ddots \\ & & & & \end{array}\right)\end{split}\]

多項式と行列 \(J\) の関係は次のように表されます。

\[f = s^{\mathrm{T}} J s - \mathrm{Tr}\ J + s^{\mathrm{T}} \cdot \operatorname{diag} J\]

ここで、変数はベクトル \(s^{\mathrm{T}} = \left(s_0, s_1, \cdots \right)\) を用いて表しました。

上記 \(Q\) と \(J\) を表す行列クラスとして下記が提供されています。

• BinaryMatrix

• IsingMatrix

• BinaryIntMatrix

• IsingIntMatrix

BinaryMatrix と IsingMatrix はそれぞれ変数がバイナリ変数 \(\left\{0, 1\right\}\) の行列 \(Q\) とイジング変数 \(\left\{-1, 1\right\}\) の行列 \(J\) を表します。

注釈

BinaryIntMatrix と IsingIntMatrix は行列要素を整数値に制限したい場合に使用します。計算途中においても整数に限定されるため意図しない結果になることがあります。そのため通常は実数値を扱える BinaryMatrix と IsingMatrix を使うことを推奨します。

行列クラスの構築

行列クラスは次のように size を指定すると、size \(\times\) size の零行列として構築されます (以後 BinaryMatrix を例にしていますがイジング含め他の行列クラスでも同様です)。

from amplify import BinaryMatrix

m = BinaryMatrix(3)

>>> m
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

対角項と非対角項は、それぞれ二次多項式の一次式の係数と二次式の係数に対応します。

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

from amplify import BinaryMatrix

m1 = BinaryMatrix(3)
m2 = BinaryMatrix(m1)

>>> m2
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

リストを初期値として行列クラスを構築することも出来ます。行列要素は、上三角部分か全要素を row major で与えます。

一次元リストの場合は行列サイズを指定する必要があります。

from amplify import BinaryMatrix
import numpy as np

m1 = BinaryMatrix(3, [1.0, 2.0, 3.0, 4.0, 5.0, 6.0])
m2 = BinaryMatrix(3, [1.0, 2.0, 3.0, 0.0, 4.0, 5.0, 0.0, 0.0, 6.0])

>>> m1
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]
>>> m2
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]

二次元リストを与える場合は行列サイズが自動的に決定されます。

from amplify import BinaryMatrix
import numpy as np

m1 = BinaryMatrix([[1.0, 2.0, 3.0], [4.0, 5.0], [6.0]])
m2 = BinaryMatrix([[1.0, 2.0, 3.0], [0.0, 4.0, 5.0], [0.0, 0.0, 6.0]])

>>> m1
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]
>>> m2
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]

行列の演算子

行列オブジェクトに対する操作で最も重要なのが要素アクセスです。次のように二次多項式に対応する行列を作成します。

\[f = q_0 q_1 - q_1 q_2 - 2 q_0 + q_2\]

from amplify import BinaryMatrix

m = BinaryMatrix(3)
m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1

>>> m
[[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]]

m[i, j] 要素の値が \(q_i q_j\) の係数に対応しています。上三角行列なので \(i \le j\) となることに注意してください。行列の下三角部分にはアクセスできません。

行列オブジェクト同士の等価・加法・減法、行列オブジェクトと定数との間で乗法・除法 に対応する演算子が定義されています。それぞれの複合代入演算も可能です。

from amplify import BinaryMatrix

m1 = BinaryMatrix(3)

m1[0, 1] = 1
m1[1, 2] = -1
m1[0, 0] = -2
m1[2, 2] = 1

m2 = BinaryMatrix(m1)

>>> m1 == m2
True
>>> m1 == [[-2, 1, 0], [0, 0, -1], [0, 0, 1]]
True

>>> m1 + m2
[[-4, 2, 0],
 [0, 0, -2],
 [0, 0, 2]]

>>> m1 - m2
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

>>> m1 * 2
[[-4, 2, 0],
 [0, 0, -2],
 [0, 0, 2]]

>>> m1 / 2
[[-1, 0.5, 0],
 [0, 0, -0.5],
 [0, 0, 0.5]]

行列クラスのメソッド

行列の評価

行列オブジェクトと変数ベクトルを用いて下記の式に従い評価します。

バイナリ変数の二次多項式

\[f = q^{\mathrm{T}} Q q\]

イジング変数の二次多項式

\[f = s^{\mathrm{T}} J s - \mathrm{Tr}J + s^{\mathrm{T}} \cdot \operatorname{diag} J\]

リストや numpy.ndarray をベクトルとして扱えます。

from amplify import BinaryMatrix
import numpy

m = BinaryMatrix(3)

m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1

>>> m
[[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]]
>>> m.evaluate([1, 0, 1])
-1.0

サイズの変更

行列オブジェクトのサイズの拡大縮小を行います。拡大時には拡大要素が \(0\) 要素で埋められ、縮小時には切り捨てられます。

from amplify import BinaryMatrix

m = BinaryMatrix(3)

m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1

>>> m
[[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]]

m.resize(6)

>>> m
[[-2, 1, 0, 0, 0, 0],
 [0, 0, -1, 0, 0, 0],
 [0, 0, 1, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0]]

注釈

このメソッドは破壊的です

行列のサイズ

行列オブジェクトのサイズを取得します。

from amplify import BinaryMatrix

m = BinaryMatrix(3)

m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1

>>> m.size()
3

バイナリ行列への変換

イジング行列からバイナリ行列へ変換します。変換後のバイナリ行列と定数項のタプルで返却されます。

from amplify import IsingMatrix

m = IsingMatrix(3)

m[0, 0] = -0.75
m[0, 1] = 0.25
m[1, 2] = -0.25
m[2, 2] = 0.25

>>> m.to_BinaryMatrix()
([[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]], 0.5)

デフォルトの変数変換ではバイナリ変数 \(0, 1\) はそれぞれイジング変数 \(-1, 1\) に対応しますが、 キーワード引数 ascending に False を与えることで変数の対応関係を逆にすることができます。

>>> m.to_BinaryMatrix(ascending=False)
([[1, 1, 0],
 [0, 0, -1],
 [0, 0, 0]], -0.5)

イジング行列への変換

バイナリ行列からイジング行列へ変換します。変換後のイジング行列と定数項のタプルで返却されます。

from amplify import BinaryMatrix

m = BinaryMatrix(3)

m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1

>>> m.to_IsingMatrix()
([[-0.75, 0.25, 0],
 [0, 0, -0.25],
 [0, 0, 0.25]], -0.5)

デフォルトの変数変換ではバイナリ変数 \(0, 1\) はそれぞれイジング変数 \(-1, 1\) に対応しますが、 キーワード引数 ascending に False を与えることで変数の対応関係を逆にすることができます。

>>> m.to_IsingMatrix(ascending=False)
([[0.75, 0.25, 0],
 [0, 0, -0.25],
 [0, 0, -0.25]], -0.5)

二次多項式への変換

行列オブジェクトから対応する多項式クラスへ変換します。

from amplify import BinaryMatrix

m = BinaryMatrix(3)

m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1

>>> m.to_Poly()
q_0 q_1 - q_1 q_2 - 2.000000 q_0 + q_2

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

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

NumPy 連携

行列クラスは NumPy 行列と相互変換を行うことが可能です。多項式形式に対する多項式配列のように、行列クラスは NumPy ndarray の強力な配列演算を用いて構築することを推奨します。

numpy.ndarray から行列クラスを構築します。

from amplify import BinaryMatrix
import numpy as np

a1 = np.array([1.0, 2.0, 3.0, 4.0, 5.0, 6.0])
m1 = BinaryMatrix(3, a1)
a2 = np.array([1.0, 2.0, 3.0, 0.0, 4.0, 5.0, 0.0, 0.0, 6.0])
m2 = BinaryMatrix(3, a2)
a3 = np.array([[1.0, 2.0, 3.0], [0.0, 4.0, 5.0], [0.0, 0.0, 6.0]])
m3 = BinaryMatrix(a3)

>>> m1
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]
>>> m2
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]
>>> m3
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]

>>> m1 == a3
True
>>> m2 == a3
True
>>> m3 == a3
True

行列クラスから numpy.ndarray に変換します。

from amplify import BinaryMatrix
import numpy as np

a1 = np.array([[1.0, 2.0, 3.0], [0.0, 4.0, 5.0], [0.0, 0.0, 6.0]])
m1 = BinaryMatrix(a)
a2 = m1.to_numpy()

>>> a2
[[1. 2. 3.]
 [0. 4. 5.]
 [0. 0. 6.]]
>>> type(a2).__name__
ndarray