QUBO++入門：QUBO++とは（HUBO対応2025年10月版）

QUBO++

QUBO++は，組合せ最適化問題を解くためのC++ベースのDSL（Domain-Specific Language）／ライブラリです．記号処理により，解きたい問題を等価なQUBO（Quadratic Unconstrained Binary Optimization）またはHUBO（High-order Unconstrained Binary Optimization）へ自動変換し，その解を求めることができます．

主な特徴は次のとおりです．

• 簡潔なC++17ベースの設計
  基本クラスは変数（qbpp::Var），式（qbpp::Expr），解（qbpp::Sol）の3つ．これらを理解するだけで，QUBO/HUBO問題を扱うC++コードを容易に記述できます．

• HUBO対応
  2次に限定されるQUBOだけでなく高次のHUBOも扱えます．記号処理部は次数の制限がなく，付属のHUBOソルバーは最大16次までの式に対応します．

• 桁数制限のない整数
  多倍長整数をサポートし，定数項や係数に桁数制限のない値を使用できます．

• 整数変数のサポート
  整数変数を扱えるため，整数計画問題をQUBO形式で簡潔に定式化できます．

• 多彩な演算子と関数
  ベクトル演算を含む複雑な式を表現・操作するための演算子と関数を豊富に用意しています．

• 組み込みソルバー
  ヒューリスティックソルバー（Easy Solver），全探索ソルバー（Exhaustive Solver），GPUソルバー（ABS3）を提供します．

• 並列処理による高速化
  Intel® Threading Building Blocks（TBB）によるマルチスレッド化で，高速な記号処理と変換を実現します．

• 外部ソルバー連携
  商用MIPソルバー（Gurobi Optimizer）をQUBOソルバーとして呼び出すAPIを備えています．

QUBO/HUBO問題とは

HUBO問題とは，0または1の値を取る2値変数を用いた多項式の中で，その式の値（エネルギー値とも呼ばれます）を最小化する変数の割り当てを求める問題です．このエネルギー値という概念は物理現象に由来しています．多項式の最大次数が2であるHUBO問題のことをQUBO問題と呼びます．

具体的には，次のような3変数を含む関数$f(a,b,c)$は3次の多項式となります．

$$\begin{aligned} f(a,b,c) &= (a+b+c)(a+2b+3c-3)^2 \\ &= 4a +b -5ab -2ac +7bc +22abc \end{aligned}$$

式を展開し整理するときに，2値変数の二乗は一乗と等しい，例えば，$a^2=a$が成り立つことを用いています．この関数$f(a,b,c)$は，その定義から次のいずれかの条件を満たすときに最小エネルギー値0をとります：

• $a+b+c=0$
• $a+2b+3c=0$
  したがって，最適解は，$(a,b,c)=(0,0,0),(1,1,0),(0,0,1)$で，これらはいずれも最小値$f(a,b,c)=0$を与えます．

QUBO++のプログラム

このQUBO問題を解くQUBO++プログラムは，次のように記述することができます．

#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"

int main() {
  auto a = qbpp::var("a");
  auto b = qbpp::var("b");
  auto c = qbpp::var("c");
  auto f = (a + b + c) * qbpp::sqr(a + 2 * b + 3 * c - 3);
  std::cout << "f = " << f.simplify_as_binary() << std::endl;
  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sols = solver.search_optimal_solutions();
  std::cout << sols << std::endl;
}

QUBO++を使用する場合，ヘッダファイルqbpp.hppをインクルードします．今回は，QUBOソルバーであるExhaustive Solverを用いるため，qbpp_exhaustive_solver.hppもインクルードします．Exhaustive Solverは，全解探索を行うQUBOソルバーです．

まず，3つの変数 a,b,cを関数qbpp::varで定義します．この関数の引数は文字列で，変数を表示するときの名前に対応します．各変数の定義によって，QUBO++内部では変数に対応するクラスqbpp::Varのインスタンスが作成されます．

次に，多項式fを数式の形で定義しています．このfは，QUBO++内部ではクラスqbpp::Exprのインスタンスです．このfを2値変数として展開・整理するため，メンバ関数simplify_as_binary()を呼び出します．同時に，その結果をstd::coutで出力し，内容を確認することができます．

このfを引数としてExhaustive Solverのオブジェクトを作成します．続いて，すべての最適解を出力するために，メンバ関数search_optimal_solutions()を呼び出し，その結果をsolに格納します．最後に，このsolをstd::coutに出力します．

このプログラムをコンパイルし実行すると，次のように正しい出力が得られます．

f = 4*a +b -5*a*b -2*a*c +7*b*c +22*a*b*c
(0) 0:{{a,0},{b,0},{c,0}}
(1) 0:{{a,0},{b,0},{c,1}}
(2) 0:{{a,1},{b,1},{c,0}}

すべての解を表示したい場合，search_optimal_solutions()をsearch_all_solutions()に変更します．これにより，8通りのすべての解が値の小さい順に表示されます．出力は以下の通りです．

f = 4*a +b -5*a*b -2*a*c +7*b*c +22*a*b*c
(0) 0:{{a,0},{b,0},{c,0}}
(1) 0:{{a,0},{b,0},{c,1}}
(2) 0:{{a,1},{b,1},{c,0}}
(3) 1:{{a,0},{b,1},{c,0}}
(4) 2:{{a,1},{b,0},{c,1}}
(5) 4:{{a,1},{b,0},{c,0}}
(6) 8:{{a,0},{b,1},{c,1}}
(7) 27:{{a,1},{b,1},{c,1}}

一方，最適解を1つだけ得たい場合は，search_optimal_solutions()をsearch()に変更します．このメンバ関数は，最適解の中から任意に1つを選択して出力します．以下はその出力例です．

f = 4*a +b -5*a*b -2*a*c +7*b*c +22*a*b*c
0:{{a,0},{b,0},{c,0}}

Exhaustive Solver

QUBO++にバンドルされているExhaustive Solverは，$n$変数を持つQUBO式に対して，全$2^n$通りの解を網羅的に探索し，それぞれのエネルギー値を計算します．そのため，$n$が大きくなると計算時間が急激に増加し，現実的な時間内で処理を終えるためには，変数の個数$n$は30～40程度が上限となります．

Exhaustive Solverは，作成したHUBO式が意図したエネルギー値を持つかどうかを確認するデバッグ用途として使用されることを想定しています．内部では，Intel® Threading Building Blocks (TBB) を活用したマルチスレッド処理により，高速化を実現しています．

まとめ

• 変数の作成：qbpp::var関数を使用して次のように変数を作成します．これにより，変数を表すqbpp::Varオブジェクトaが生成されます．

auto a = qbpp::var("a");

• 多項式の記述：変数を用いて多項式を次のように記述します．これにより，式を表すqbpp::Exprオブジェクトfが生成されます．

  auto f = (a + b + c) * qbpp::sqr(a + 2 * b + 3 * c - 3);

• 多項式の整理：多項式を二値変数とみなして整理するには，qbpp::Exprクラスのsimplify_as_binary()メンバ関数を使用します．この関数を呼び出すと，整理されたQUBO式が得られます．

  f.simplify_as_binary();

• 式の表示式：式を表示するには，std::coutを使用します．

  std::cout << "f = " << f << std::endl;

• QUBO式の最適解の求解：整理されたQUBO式を引数としてExhaustiveSolverインスタンスを作成します．

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);

• 全ての最適解の探索：全ての最適解を求めるには，search_optimal_solutions()メンバ関数を呼び出します．

   auto sol = solver.search_optimal_solutions();

• 得られた解の表示：得られた解を表示するには，std::coutを使用します．

std::cout << sol << std::endl;