剰余問題¶

以下の問題はHi-QUBOを用いて解くことができます. 次の条件を満たす最小の非負整数 \(x\) を求めます:

\(x\) を3で割った余りが2
\(x\) を5で割った余りが3
\(x\) を7で割った余りが5

3,5,7は互いに素であるため,1周期内で \(x\) を探索すれば十分です:

\[ 0\leq x \leq 3\times 5\times 7 -1 \]

非負整数 \(d_3\),\(d_5\),\(d_7\)（商）を導入し,剰余条件を線形等式として書き直します:

\[\begin{split} \begin{aligned} x - 3d_3 &= 2 \\ x - 5d_5 &=3 \\ x - 7d_7 &= 5 \end{aligned} \end{split}\]

これらの制約の下で \(x\) を最小化したいです. 上記の \(x\) の範囲から,商の変数は以下のように制限できます:

\[\begin{split} \begin{aligned} 0&\leq d_3 \leq 5\times 7-1 \\ 0&\leq d_5 \leq 3\times 7-1 \\ 0&\leq d_7 \leq 3\times 5-1 \end{aligned} \end{split}\]

Hi-QUBO プログラム

以下のプログラムは,この剰余問題の解 \(x\) を求めます:

modular-arithmetic-program1.cpp¶

#include <qbpp/qbpp.hpp>
#include <qbpp/easy_solver.hpp>

int main() {
  auto x = 0 <= qbpp::var_int("x") <= 3 * 5 * 7 - 1;
  auto d3 = 0 <= qbpp::var_int("d3") <= 5 * 7 - 1;
  auto d5 = 0 <= qbpp::var_int("d5") <= 3 * 7 - 1;
  auto d7 = 0 <= qbpp::var_int("d7") <= 3 * 5 - 1;
  auto c3 = x - 3 * d3 == 2;
  auto c5 = x - 5 * d5 == 3;
  auto c7 = x - 7 * d7 == 5;
  auto f = x + 1000 * (c3 + c5 + c7);
  f.simplify_as_binary();

  auto solver = qbpp::EasySolver(f);
  auto sol = solver.search({{"time_limit", 1.0}});

  std::cout << "x = " << sol(x) << std::endl;
  std::cout << sol(x) << " - 3 * " << sol(d3) << " = " << c3.body(sol) << std::endl;
  std::cout << sol(x) << " - 5 * " << sol(d5) << " = " << c5.body(sol) << std::endl;
  std::cout << sol(x) << " - 7 * " << sol(d7) << " = " << c7.body(sol) << std::endl;
}

3つの制約は c3,c5,c7 として表現されています. それぞれは,対応する等式が成り立つときに0になるQUBOペナルティ項に変換されます.

次に,制約の充足を \(x\) の削減よりも優先するために,大きなペナルティ重み（1000）を用いて x を最小化します.

最後に,Easy Solverが制限時間（1.0秒）内で f の低エネルギー解を探索し,得られた値は以下のように出力されます:

したがって,

\[ \begin{aligned} x &\equiv 68 & (\bmod 105) \end{aligned} \]

最小の解は \(x=68\) です.

以下の問題は PyQBPP を使って解くことができます. 次の条件を満たす最小の非負整数 \(x\) を求めます:

\(x\) を 3 で割った余りが 2,
\(x\) を 5 で割った余りが 3,
\(x\) を 7 で割った余りが 5.

3,5,7 は互いに素であるため,1周期内で \(x\) を探索すれば十分です:

\[ 0\leq x \leq 3\times 5\times 7 -1 \]

非負整数 \(d_3\),\(d_5\),\(d_7\)（商）を導入し,余りの条件を線形等式として書き直します:

\[\begin{split} \begin{aligned} x - 3d_3 &= 2 \\ x - 5d_5 &=3 \\ x - 7d_7 &= 5 \end{aligned} \end{split}\]

これらの制約の下で \(x\) を最小化したいです. 上記の \(x\) の範囲から,商の変数を以下のように制限できます:

\[\begin{split} \begin{aligned} 0&\leq d_3 \leq 5\times 7-1 \\ 0&\leq d_5 \leq 3\times 7-1 \\ 0&\leq d_7 \leq 3\times 5-1 \end{aligned} \end{split}\]

PyQBPP プログラム

以下のプログラムは,この余り問題の解 \(x\) を求めます:

modular-arithmetic-program1.py¶

import pyqbpp as qbpp

x = qbpp.var("x", between=(0, 3 * 5 * 7 - 1))
d3 = qbpp.var("d3", between=(0, 5 * 7 - 1))
d5 = qbpp.var("d5", between=(0, 3 * 7 - 1))
d7 = qbpp.var("d7", between=(0, 3 * 5 - 1))
c3 = (x - 3 * d3 == 2)
c5 = (x - 5 * d5 == 3)
c7 = (x - 7 * d7 == 5)
f = x + 1000 * (c3 + c5 + c7)
f.simplify_as_binary()

solver = qbpp.EasySolver(f)
sol = solver.search(time_limit=1.0)

print(f"x = {sol(x)}")
print(f"{sol(x)} - 3 * {sol(d3)} = {sol(c3.body)}")
print(f"{sol(x)} - 5 * {sol(d5)} = {sol(c5.body)}")
print(f"{sol(x)} - 7 * {sol(d7)} = {sol(c7.body)}")

3つの制約は c3,c5,c7 として表現されています. それぞれは,対応する等式が成り立つときに 0 となる QUBO ペナルティ項に変換されます.

大きなペナルティ重み（1000）を使って x を最小化することで,x の削減よりも制約の充足が優先されます.

最後に,Easy Solver がキーワード引数で指定された制限時間（1.0秒）内で f の低エネルギー解を探索し,得られた値は以下のように出力されます:

x = 68
- 3 * 22 = 2
- 5 * 13 = 3
- 7 * 9 = 5

したがって,

\[ \begin{aligned} x &\equiv 68 & (\bmod 105) \end{aligned} \]

最小の解は \(x=68\) です.