整数変数と連立方程式の求解

整数変数

PyQBPPは整数変数をサポートしており、内部的には複数のバイナリ変数を使って実装されています。整数値の表現には従来のバイナリエンコーディングが使用されます。

以下のプログラムは整数変数の定義方法を示しています。

import pyqbpp as qbpp

x = qbpp.between(qbpp.var_int("x"), 1, 8)
y = qbpp.between(qbpp.var_int("y"), -10, 10)
print(f"x = {x} uses {x.var_count()} variables.")
print(f"y = {y} uses {y.var_count()} variables.")

整数変数は between() 関数を使って定義し、変数がとりうる整数範囲を指定します。関数 var_int("name") は指定された name を持つ VarIntCore オブジェクトを作成し、between(var_int("name"), min, max) はバイナリ変数でエンコードされた線形式を表す VarInt オブジェクトを作成します。プログラムの出力は以下の通りです。

x = 1 +x[0] +2*x[1] +4*x[2] uses 3 variables.
y = -10 +y[0] +2*y[1] +4*y[2] +8*y[3] +5*y[4] uses 5 variables.

WARNING 整数変数に必要なバイナリ変数の数は、その範囲に対して対数的に増加します。 max - min が大きい場合、QUBOのサイズが増大するため、広い整数範囲はできる限り避けるべきです。

連立方程式を解くためのQUBO定式化

PyQBPPは変数を整数変数として表現することで、連立方程式を解くことができます。例として、解が $x=4$、$y=6$ である以下の連立方程式のQUBO定式化を構築します。

\[\begin{aligned} x + y = 10\\ 2x+4y = 28 \end{aligned}\]

PyQBPP プログラム

以下のプログラムはQUBO式を構築し、それを解いて $x$ と $y$ の値を復号します。

import pyqbpp as qbpp

x = qbpp.between(qbpp.var_int("x"), 0, 10)
y = qbpp.between(qbpp.var_int("y"), 0, 10)

f = (x + y) == 10
g = (2 * x + 4 * y) == 28
h = f + g
h.simplify_as_binary()

solver = qbpp.EasySolver(h)
sol = solver.search({"target_energy": 0})

print("sol =", sol)
print("x =", x, "=", sol(x))
print("y =", y, "=", sol(y))
print("f =", sol(f))
print("g =", sol(g))
print("x + y =", sol(f.body))
print("2x + 4y =", sol(g.body))

まず、VarInt オブジェクト x と y を範囲 $[0,10]$ で定義します。 Expr オブジェクト f は制約 (x + y) == 10 を表すために作成されます。内部的には、これはQUBO式 sqr(x + y - 10) と等価です。同様に、g は制約 (2 * x + 4 * y) == 28 を表します。結合式 h = f + g は両方の方程式をエンコードします。 Easy Solver のインスタンスを h で作成し、最適解がすべての制約を満たすため、search() に {"target_energy": 0} を渡します。 search() を呼び出すと、すべてのバイナリ変数の最適な割り当てを格納した Sol オブジェクト sol が返されます。

ここで、

f: x + y = 10 を強制するペナルティ式。方程式が満たされるとき、かつそのときに限り sol(f) = 0 となります。
f.body: 線形式 x + y。sol(f.body) は x + y の実際の評価値を返します。

g と g.body についても同様です。

プログラムの出力は以下の通りです。

sol = Sol(energy=0, x[0]=0, x[1]=1, x[2]=1, x[3]=0, y[0]=0, y[1]=0, y[2]=1, y[3]=0)
x = x[0] +2*x[1] +4*x[2] +3*x[3] = 6
y = y[0] +2*y[1] +4*y[2] +3*y[3] = 4
f = 0
g = 0
x + y = 10
2x + 4y = 28

このように、x、y の値と制約式が解と一致していることが確認できます。

WARNING PyQBPPの == 演算子は、左辺が式で右辺が整数の場合のみサポートされています。 整数 == 式 や 式 == 式 の形式の比較はサポートされていません。