変数の定義と式の作成¶

ヘッダーファイルと名前空間

QUBO++ を使用するには、ヘッダーファイル qbpp.hpp をインクルードし、qbpp 名前空間を使用する必要があります。

変数と式の定義

変数は qbpp::var("name") を使用して定義できます。auto 型推論が使えます。指定した名前は、std::cout で変数を表示する際に使用されます。

式は、+、-、* などの標準的な算術演算子を使用して構築されます。

次のサンプルプログラムでは、変数 a、b、c と式 f を定義し、std::cout で出力しています。

variables-and-expressions-program1.cpp¶

#include <qbpp/qbpp.hpp>

int main() {
  auto a = qbpp::var("a");
  auto b = qbpp::var("b");
  auto c = qbpp::var("c");
  auto f = (a + b - 1) * (b + c - 1);
  std::cout << "f = " << f << std::endl;
}

式 \((a + b - 1)(b + c - 1)\) は自動的に展開され、f に格納されます。

この QUBO++ プログラムでは、変数 a、b、c は qbpp::Var クラスのオブジェクトであり、式 f は qbpp::Expr クラスのオブジェクトです。

ヘッダーファイルおよびライブラリのパスが正しく設定されていれば、このプログラム（test.cpp として保存）を g++ で次のようにコンパイルできます。

g++ test.cpp -o test -std=c++17 -lqbpp -ltbb

実行可能ファイルを./testで実行すると、展開された式が出力されます。

f = 1 +a*b +b*b +a*c +b*c -a -b -b -c

注意: qbpp::var() の変数名は省略可能です。省略した場合、{0}、{1} … のようなデフォルト名が自動的に割り当てられます。

警告: qbpp::Expr などの多くの QUBO++ クラスのインスタンスは、std::cout を使用してテキストとして表示できます。しかし、このテキスト出力は将来的にフォーマットが変更される可能性があるため、後続の計算の入力として使用することは推奨されません。また、QUBO++ ドキュメントに示されている出力は古いバージョンで生成された可能性があり、最新バージョンでの出力は異なる場合があります。

式の簡略化

qbpp::Expr オブジェクトに格納された式は、simplify() メンバ関数を呼び出すことで簡略化できます:

std::cout << "f = " << f.simplify() << std::endl;

この変更を加えると、プログラムの出力は次のようになります:

f.simplify() = 1 -a -2*b -c +a*b +a*c +b*b +b*c

メンバ関数呼び出し f.simplify() は、式 f を簡略化し、その結果の値を返します。この値は std::cout によって出力されます。

すべての変数が2値（0 または 1）を取ると仮定すると、恒等式を用いて式をさらに簡略化できます。その目的のために、代わりに simplify_as_binary() を使用します:

std::cout << "f = " << f.simplify_as_binary() << std::endl;

すると、出力は次のようになります:

f = 1 -a -b -c +a*b +a*c +b*c

simplify 関数は、各項内の変数や式内の項の順序を並べ替えます。低次の項が先に現れるようにし、同じ次数の項は変数の辞書順に並べられます。変数自体の順序は、定義された順序に従います。

スピン変数による式の簡略化

変数がスピン値 -1 / +1 を取ると仮定すると、恒等式を用いて式をさらに簡略化できます。この場合、simplify_as_spin() メンバ関数を使用して式を簡略化できます:

std::cout << "f = " << f.simplify_as_spin() << std::endl;

すると、出力は次のようになります:

f = 2 -a -2*b -c +a*b +a*c +b*c

式簡略化のためのグローバル関数

メンバ関数は、f に格納された式を更新します。f を変更せずに簡略化したい場合は、代わりにグローバル関数 qbpp::simplify(f)、qbpp::simplify_as_binary(f)、および qbpp::simplify_as_spin(f) を使用できます。これらは f を変更せずに簡略化された式を返します。

注意: QUBO++ では、多くのメンバ関数は可能な限りオブジェクトをインプレースで更新しますが、グローバル関数は元のオブジェクトを変更せずに新しい値を返します。

否定リテラル

Hi-QUBOは ~ 演算子を使った否定リテラルをネイティブにサポートしています。 2値変数 x に対して、式 ~x は \(1-x\) を表します。

variables-and-expressions-program2.cpp¶

#include <qbpp/qbpp.hpp>

int main() {
  auto a = qbpp::var("a");
  auto b = qbpp::var("b");
  auto c = qbpp::var("c");
  auto d = qbpp::var("d");
  auto f = ~a * ~b * ~c * ~d + a * b;
  std::cout << "f = " << f << std::endl;
  std::cout << "f = " << qbpp::simplify_as_binary(f) << std::endl;
}

出力:

f = ~a*~b*~c*~d +a*b
f = a*b +~a*~b*~c*~d

否定リテラル ~x は、1 - x として展開されるのではなく、否定フラグを持つ単一の変数として内部的に格納されます。これはパフォーマンスにとって重要です。~x を単純に展開すると、~x1 * ~x2 * ... * ~xk のような \(k\) 個の否定リテラルの積は、\((1-x_1)(1-x_2)...(1-x_k)\) を展開した後に最大 \(2^k\) 個の項を生成します。例えば、上記の項 ~a*~b*~c*~d は単一の4次項として格納されますが、展開形 \((1-a)(1-b)(1-c)(1-d)\) は16個の項を生成します。

1 -a -b -c -d +a*b +a*c +a*d +b*c +b*d +c*d -a*b*c -a*b*d -a*c*d -b*c*d +a*b*c*d

QUBO++に同梱されているすべてのソルバー（EasySolver、ExhaustiveSolver、ABS3 GPU Solver）は否定リテラルをネイティブに処理するため、求解前に展開する必要はありません。

変数と式の定義

変数は var("name") を使用して定義できます。指定した名前は、変数を表示する際に使用されます。

式は、+、-、* などの標準的な算術演算子を使用して構築されます。

次のサンプルプログラムでは、変数 a、b、c と式 f を定義し、表示します。

variables-and-expressions-program1.py¶

import pyqbpp as qbpp

a = qbpp.var("a")
b = qbpp.var("b")
c = qbpp.var("c")
f = (a + b - 1) * (b + c - 1)
print("f =", f)

式 \((a + b - 1)(b + c - 1)\) は自動的に展開され、f に格納されます。

このプログラムでは、変数a、b、cはクラスVarのオブジェクトであり、式fはクラスExprのオブジェクトです。実行可能ファイルを実行すると、展開された式が出力されます。

f = 1 +a*b +b*b +a*c +b*c -a -b -b -c

注意: qbpp.var() の変数名は省略可能です。省略した場合、{0}、{1} … のようなデフォルト名が自動的に割り当てられます。

警告: 式をはじめとするPyQBPPのほとんどのオブジェクトは、print()を使ってテキストとして出力できます。ただし、このテキスト出力は安定性が保証されておらず、今後のリリースで形式が変更される可能性があるため、後続の計算への入力として使用しないでください。また、PyQBPPドキュメントに示されている出力は古いバージョンで生成された可能性があり、最新バージョンでの出力は異なる場合があります。

式の簡略化

Expr オブジェクトに格納された式は、simplify() メンバ関数を呼び出すことで簡略化できます:

print("f =", f.simplify())

この変更を加えると、プログラムの出力は次のようになります:

f.simplify() = 1 -a -2*b -c +a*b +a*c +b*b +b*c

メンバ関数呼び出し f.simplify() は、式 f を簡略化し、その結果の値を返します。

print("f =", f.simplify_as_binary())

すると、出力は次のようになります:

f = 1 -a -b -c +a*b +a*c +b*c

スピン変数による式の簡略化

変数がスピン値 -1 / +1 を取ると仮定すると、恒等式 \(b^2=1\) を用いて式をさらに簡略化できます。この場合、simplify_as_spin() メンバ関数を使用して式を簡略化できます:

print("f =", f.simplify_as_spin())

すると、出力は次のようになります:

f = 2 -a -2*b -c +a*b +a*c +b*c

式簡略化のためのグローバル関数

メンバ関数は、f に格納された式を更新します。f を変更せずに簡略化したい場合は、代わりにグローバル関数 simplify(f)、simplify_as_binary(f)、および simplify_as_spin(f) を使用できます。これらは f を変更せずに簡略化された式を返します。

import pyqbpp as qbpp
g = qbpp.simplify_as_binary(f)  # fは変更されず、gは新しい簡約化された式

注意: PyQBPP では、多くのメンバ関数は可能な限りオブジェクトをインプレースで更新しますが、グローバル関数は元のオブジェクトを変更せずに新しい値を返します。

否定リテラル

PyQBPPは ~ 演算子を使った否定リテラルをネイティブにサポートしています。 2値変数 x に対して、式 ~x は \(1-x\) を表します。

variables-and-expressions-program2.py¶

import pyqbpp as qbpp

a = qbpp.var("a")
b = qbpp.var("b")
c = qbpp.var("c")
d = qbpp.var("d")
f = ~a * ~b * ~c * ~d + a * b
print("f =", f)
print("f =", qbpp.simplify_as_binary(f))

出力:

f = ~a*~b*~c*~d +a*b
f = a*b +~a*~b*~c*~d

1 -a -b -c -d +a*b +a*c +a*d +b*c +b*d +c*d -a*b*c -a*b*d -a*c*d -b*c*d +a*b*c*d