平方根

この例は、$c=2$ の平方根を、 qbpp::cpp_int。 $s = 10 ^{10}$ を固定整数とする。 QUBO++ は実数を直接扱えないため、$\sqrt{c}$ ではなく $\sqrt{cs^2}$ を計算する。 以下の関係式から、

より、小数点以下10桁の精度で $\sqrt{c}$ の近似値を得ることができる。

平方根計算のHUBO定式化

整数変数 $x$ を定義し、その値域を $[s, 2s]$ とする。 次に、以下の式を用いて問題を定式化する：

QUBO++では、この等式制約は次のHUBO式に変換される：

この式を最小化する $x$ の値を求めることで、 $c$ の平方根を小数点以下10桁の精度で近似できる。 $x$ は内部的に二進変数の線形式で表現されるため、この目的関数はそれらの二進変数に対する4次式となる。

QUBO++プログラム

以下のQUBO++プログラムは上記の考えに基づきHUBO式を構築し、Easy Solverを用いて解く：

#define COEFF_TYPE qbpp::cpp_int
#define ENERGY_TYPE qbpp::cpp_int

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

int main() {
  const int c = 2;
  auto s = qbpp::cpp_int("10000000000");
  auto x = s <= qbpp::var_int("x") <= c * s;
  auto f = x * x == c * s * s;
  f.simplify_as_binary();
  auto solver = qbpp::easy_solver::EasySolver(f);
  solver.time_limit(1.0);
  auto sol = solver.search();
  std::cout << "Energy = " << sol.energy() << std::endl;
  std::cout << "x = " << x << "\n = " << sol(x) << std::endl;
}

非常に大きな係数が使用されるため、2つのマクロを定義する COEFF_TYPE および ENERGY_TYPE を qbpp::cpp_int, 任意に大きな整数を表現できる。 定数 s, 整数変数 x、および HUBO 式 f は、上記の定式化に従って定義される。 イージーソルバーは1.0秒の時間制限で実行される。

このプログラムは以下の出力を生成する:

Energy = 57910111919782629376
x = 10000000000 +x[0] +2*x[1] +4*x[2] +8*x[3] +16*x[4] +32*x[5] +64*x[6] +128*x[7] +256*x[8] +512*x[9] +1024*x[10] +2048*x[11] +4096*x[12] +8192*x[13] +16384*x[14] +32768*x[15] +65536*x[16] +131072*x[17] +262144*x[18] +524288*x[19] +1048576*x[20] +2097152*x[21] +4194304*x[22] +8388608*x[23] +16777216*x[24] +33554432*x[25] +67108864*x[26] +134217728*x[27] +268435456*x[28] +536870912*x[29] +1073741824*x[30] +2147483648*x[31] +4294967296*x[32] +1410065409*x[33]
 = 14142135624

イージーソルバーが正しい近似値を出力していることを確認できます：

報告されたエネルギー値がゼロではなく、等式制約が厳密に満たされていない点に注意してください。 これは単に、等式に対する厳密な整数解が存在しないためです。 代わりにソルバーは、等式制約の誤差を最小化する解を見つけます。 出力に示されるエネルギー値は、この誤差の二乗に対応します。 誤差が最小化されているため、結果として得られる $x$ の値は平方根の近似値を表します。