Hi-QUBO

立方方程式

整数上の三次方程式は QUBO++ を使用して解くことができます。例えば、次の式を考えてみましょう

\[\begin{aligned} x^3 -147x +286 &=0. \end{aligned}\]

この方程式には3つの整数解があります：$x = -13, 2, 11$。

三次方程式を解くQUBO++プログラム

以下のQUBO++プログラムでは、整数変数xを$[-100, 100]$の範囲で定義し、全探索ソルバーを用いて全ての最適解を列挙する：

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

int main() {
  auto x = -100 <= qbpp::var_int("x") <= 100;
  auto f = x * x * x - 147 * x + 286 == 0;
  f.simplify_as_binary();
  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sols = solver.search_optimal_solutions();
  for (const auto& sol : sols) {
    std::cout << "x= " << x(sol) << " sol = " << sol << std::endl;
  }
}

式 f は次の目的関数に対応する：

\[\begin{aligned} f & = (x^3 -147x +286)^2 \end{aligned}\]

整数変数 x は二進変数の線形表現として実装されるため、 f となるため、6次多項式となる。 このプログラムは以下の出力を生成する:

x = -100 +x[0] +2*x[1] +4*x[2] +8*x[3] +16*x[4] +32*x[5] +64*x[6] +73*x[7]
x = 11 sol = 0:{{x[0],0},{x[1],1},{x[2],1},{x[3],0},{x[4],0},{x[5],1},{x[6],0},{x[7],1}}
x = 2 sol = 0:{{x[0],0},{x[1],1},{x[2],1},{x[3],0},{x[4],0},{x[5],1},{x[6],1},{x[7],0}}
x = -13 sol = 0:{{x[0],0},{x[1],1},{x[2],1},{x[3],1},{x[4],0},{x[5],0},{x[6],0},{x[7],1}}
x = 2 sol = 0:{{x[0],1},{x[1],0},{x[2],1},{x[3],1},{x[4],1},{x[5],0},{x[6],0},{x[7],1}}
x = -13 sol = 0:{{x[0],1},{x[1],1},{x[2],1},{x[3],0},{x[4],1},{x[5],0},{x[6],1},{x[7],0}}
x = 11 sol = 0:{{x[0],1},{x[1],1},{x[2],1},{x[3],1},{x[4],0},{x[5],1},{x[6],1},{x[7],0}}

最初の行は、整数変数 x が8個の二進変数で符号化されていることを示している。 また、元の3次方程式には整数解が3つしかないにもかかわらず、プログラムは6つの最適解を出力する。 これは係数 73 の係数が x[7] が2の冪乗ではないため、同じ整数値が複数の異なる二進変数割り当てによって表現される可能性があるためである。 x.

最終更新日: 2026.01.12