平方根

この例では、大きな整数を用いて $c=2$ の平方根を計算する方法を示します。 $s = 10^{10}$ を固定整数とします。 PyQBPP は実数を直接扱えないため、$\sqrt{c}$ の代わりに $\sqrt{cs^2}$ を計算します。 以下の関係式から、

\[\begin{aligned} \sqrt{c} &= \sqrt{cs^2}/s \end{aligned}\]

10桁の10進精度で $\sqrt{c}$ の近似値を得ることができます。

平方根計算の HUBO 定式化

範囲 $[s, 2s]$ の値を取る整数変数 $x$ を定義します。 次に、以下の等式を用いて問題を定式化します:

\[\begin{aligned} x ^ 2 &= cs ^ 2 \end{aligned}\]

PyQBPP では、この等式制約は以下の HUBO 式に変換されます:

\[(x ^ 2 -cs^2)^2\]

この式を最小化する $x$ の値を見つけることで、10桁の10進精度で $c$ の平方根の近似値を得ます。 $x$ は内部的にバイナリ変数の線形式として表現されるため、この目的関数はバイナリ変数に関して4次式になります。

PyQBPP プログラム

以下の PyQBPP プログラムは、上記の考え方に基づいて HUBO 式を構築し、Easy Solver を用いて解きます:

import pyqbpp as qbpp

c = 2
s = 10**10
x = qbpp.between(qbpp.var_int("x"), s, c * s)
f = x * x == c * s * s
f.simplify_as_binary()
solver = qbpp.EasySolver(f)
sol = solver.search({"time_limit": 1.0})
print(f"Energy = {sol.energy}")
print(f"x = {sol(x)}")

Python の整数は任意精度であるため、特別な整数型を指定する必要はありません（C++版では INTEGER_TYPE_CPP_INT が必要です）。 定数 s、整数変数 x、HUBO 式 f は上述の定式化に従って定義されています。 Easy Solver は制限時間1.0秒で実行されます。パラメータは search() の引数として渡します。

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

Energy = 57910111919782629376
x = 14142135624

Easy Solver が正しい近似値を出力していることが確認できます:

\[\sqrt{2\times 10^{20}}\approx 14142135624\]

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