QUBO++入門：reduce関数（素因数分解）

reduce関数

QUBO（Quadratic Unconstrained Binary Optimization）は，二値変数を用いた二次式で表されます．しかし，三次以上の項を含む多項式の場合，その最小値を求める問題は HUBO（High-order Unconstrained Binary Optimization）と呼ばれます．HUBO式は，等価なQUBO式に変換することが可能です．QUBO++では，qbpp::reduce 関数を用いることで，この変換を簡単に行えます．

次の多項式 $f(a,b,c,d)$ を例にして説明します．
$$
\begin{align*}
f(a,b,c,d) &=-(1-a)b(1-c)d = -bd+abd+bcd-abcd
\end{align*}
$$
この多項式において，$f(0,1,0,1) = -1$ が最小値となります．しかし，Exhaustive Solver や Easy Solver といったQUBOソルバーは三次以上の項を扱うことができません．そのため，この多項式を補助変数を用いて一次と二次の項だけを持つ等価なQUBO式に変換します．

プログラム例

先に示したHUBO式 $f(a,b,c,d)$ を等価なQUBO式に変換し，Exhaustive Solverで最適解を求めます．以下はそのプログラムの例です．

#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 d = qbpp::var("d");

  auto f = -(1 - a) * b * (1 - c) * d;
  f.simplify_as_binary();
  std::cout << "f = " << f << std::endl;

  auto g = qbpp::reduce(f);
  g.simplify_as_binary();
  std::cout << "g = " << g << std::endl;

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(g);
  auto sols = solver.search_optimal_solutions();
  std::cout << sols << std::endl;
}

• f に $f(a,b,c,d)$ を計算する式を生成し，整理した結果を表示しています．
• qbpp::reduce 関数を適用した結果を g として生成し，整理後に表示しています．
• Exhaustive Solver を用いて全ての最適解を探索し，その結果を表示しています．

このプログラムを実行すると，次のような出力が得られます．

f = -b*d +a*b*d +b*c*d -a*b*c*d
g = {0} +{1} +3*{2} +a*b +a*d -a*{0} -a*{2} +b*c +b*d -b*{0} -b*{1} -b*{2} +c*d -c*{1} -c*{2} -d*{0} -d*{1} -d*{2}
0:-1:{{a,0},{b,1},{c,0},{d,1},{{0},1},{{1},1},{{2},0}}

ここで，g に表示されている {0}, {1}, {2} は，等価変換において導入された補助変数です．また，$f(0,1,0,1) = -1$ の最適解が正しく得られていることが確認できます．

素因数分解

reduce 関数を使用したプログラム例として，素因数分解を取り上げます．ここでは，2つの素数 $p$ と $q$ の積 $m$ が与えられたとき，$p$ と $q$ を求める素因数分解をQUBO++を用いて求めます．次の多項式 $f(p,q)$ において，最小値 $f(p,q) = 0$ となるとき，$pq = m$ が成り立ちます．そのような $p$ と $q$ が $m$ の素因数分解です．

$$\begin{align*} f(p,q) &= (pq-m)^2 \end{align*}$$

QUBO++では，この式を次のように等式を用いて記述できます．
$$
\begin{align*}
f(p,q) &= pq == m
\end{align}
$$
$f(p,q)$ は四次項を持つため，reduce関数を使用して等価なQUBO式に変換した後，Easy Solver を用いて $f(p,q)$ の解を求めます．以下は $m = 35$ の場合の例です．

#include "qbpp.hpp"
#include "qbpp_easy_solver.hpp"

int main() {
  auto p = 2 <= qbpp::var_int("p") <= 8;
  auto q = 2 <= qbpp::var_int("q") <= 8;
  auto f = p * q == 35;
  f.reduce().simplify_as_binary();

  auto solver = qbpp::easy_solver::EasySolver(f);
  solver.set_target_energy(0);
  solver.enable_default_callback();
  auto sol = solver.search();
  std::cout << "p = " << sol.get(p) << std::endl;
  std::cout << "q = " << sol.get(q) << std::endl;
}

• p と q は，それぞれ$[2,8]$の範囲の整数変数として生成しています．
• これらの積が 35 に一致する条件を表す多項式をfとしています．
• この f を reduce 関数と simplify_as_binary 関数を用いて，QUBO式に変換し整理しています．
• 最適解がエネルギー値 0 であることがわかっているため，set_target_energy 関数を使用してエネルギー値が 0 になった時点で探索を終了する設定にしています．
• enable_default_callback 関数で，デフォルトのコールバック関数を有効化し，経過時間やエネルギー値を表示します．
  このプログラムを実行すると，以下の出力が得られます．

TTS = 0.000s Energy = 841
TTS = 0.001s Energy = 822
TTS = 0.001s Energy = 820
TTS = 0.001s Energy = 815
TTS = 0.002s Energy = 400
TTS = 0.004s Energy = 397
TTS = 0.004s Energy = 25
TTS = 0.008s Energy = 7
TTS = 0.008s Energy = 5
TTS = 0.008s Energy = 0
p = 5
q = 7

0.008秒でエネルギー値 0 の最適解 $p = 5$，$q = 7$ が得られていることが確認できます．

#　まとめ

• reduce 関数を使用することで，三次以上の多項式を二次以下のQUBO式に等価変換することができます．
• Easy Solver では，set_target_energy 関数を利用して目標エネルギー値を設定できます．この設定により，目標エネルギー値に達した時点で探索を終了させることが可能です．
• enable_default_callback 関数を使用すると，デフォルトのコールバック関数が有効化され，経過時間やエネルギー値を簡単に確認できます．

QUBO++情報

• QUBO＋＋ツールとABS2 QUBO Solverの詳細情報：QUBO++に関する公式サイトです．ツールの特徴や使用方法，ABS2 QUBO Solverとの連携について詳しく説明されています．
• 【研究成果】組合せ最適化問題を解くためのプログラミング用ツールQUBO＋＋を無償公開します：広島大学からの公式リリース情報です．QUBO++の開発背景や研究成果について記載されています．
• 利用条件：QUBO++は非商用利用や評価研究目的に限り無償で利用可能です．商用利用や定常的な業務での使用を希望する場合は，ライセンス契約が必要となります．