変数と式の定義

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

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

変数と式の定義

変数は qbpp::var("name") を auto 型推論とともに使用して定義できます。指定した name は、変数を std::cout で出力する際に使用されます。

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

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

#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 -ldl

実行すると、展開された式が出力されます。

./test
f = 1 +a*b +b*b +a*c +b*c -a -b -b -c

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

WARNING 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） をとると仮定すると、恒等式 $b^2=b$ を使って式をさらに簡約化できます。この目的には、代わりに simplify_as_binary() を使用します。

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

出力は以下のようになります。

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

簡約化関数は、各項内の変数と式内の項を並べ替え、低次の項が先に表示されるようにし、同じ次数の項は変数の辞書順でソートします。変数自体は定義された順序で並べられます。

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

変数が スピン値 $-1$/$+1$ をとると仮定する場合、恒等式 $b^2 = 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 を変更せずに簡約化された式を返します。

NOTE QUBO++では、ほとんどの メンバ関数 はオブジェクトをその場で更新しますが、グローバル関数 は元のオブジェクトを変更せずに新しい値を返します。

否定リテラル

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

#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)\cdots(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）は否定リテラルをネイティブに処理するため、求解前に展開する必要はありません。