低自己相関二進数列（LABS）問題
低自己相関二値列（LABS）問題は、自己相関を最小化するスピン列$S=(s_i)$ ($s_i=\pm, 0\leq i\leq n-1$) を見つけることを目的とする。 $S$の自己相関（アラインメント$d$）は以下のように定義される
\[\left(\sum_{i=0}^{n-d-1}s_is_{i+d}\right)^2\]LABSの目的関数は、全アラインメントにおけるこれらの自己相関の和である：
\[\begin{aligned} \text{LABS}(S) &= \sum_{d=1}^{n-1}\left(\sum_{i=0}^{n-d-1}s_is_{i+d}\right)^2 \end{aligned}\]LABS問題は、$\text{LABS}(S)$を最小化する配列$S$を見つけることである。
スピンからバイナリへの変換
QUBO++にバンドルされているソルバーはスピン変数を直接サポートしていないため、 以下の変換を用いてスピン変数を2進変数に変換する：
\[\begin{aligned} s_i &\leftarrow 2s_i - 1 \end{aligned}\]この変換後、各 $s_i$ はバイナリ変数として扱えるため、 バイナリ変数用の HUBO ソルバーを用いて $\text{LABS}(S)$ の解を求めることができる。
QUBO++はこの変換をspin_to_binary()関数を通じて提供します。
LABS問題のためのQUBO++プログラム
以下のQUBO++プログラムはLABS問題を定式化し解く：
#include "qbpp.hpp"
#include "qbpp_easy_solver.hpp"
int main() {
const int n = 30;
auto s = qbpp::var("s", n);
auto labs = qbpp::expr();
for (size_t d = 1; d < n; ++d) {
auto temp = qbpp::expr();
for (size_t i = 0; i < n - d; ++i) {
temp += s[i] * s[i + d];
}
labs += qbpp::sqr(temp);
}
labs.spin_to_binary();
labs.simplify_as_binary();
auto solver = qbpp::easy_solver::EasySolver(labs);
solver.time_limit(10.0);
solver.enable_best_energy_sols();
auto sols = solver.search();
size_t i = 0;
for (const auto& sol : sols.best_sols()) {
std::cout << i++ << ": LABS = ";
std::cout << sol.energy() << " : ";
for (size_t j = 0; j < n; ++j) {
std::cout << (sol(s[j]) ? "+" : "-");
}
std::cout << std::endl;
}
}
このプログラムでは、 s は変数のベクトルを格納する n 変数のベクトルを格納します。
変数 qbpp::Expr オブジェクト labs は、LABS目的関数の数学的定義に直接従い、
ネストされたループを用いて構築される。
その後、 labs は spin_to_binary() 関数を用いて二値変数上の式に変換され、
simplify_as_binary().
その後、イージーソルバーが10秒の時間制限で実行される。 enable_best_energy_sols() が有効化されているため、
最小エネルギーを達成する全解がsolsに格納される。
範囲ベースの for ループを用いて、すべての最良エネルギー解を出力する。 このプログラムの典型的な出力は次の通りである:
0: LABS = 59 : -----+++++-++-++-+-+-+++--+++-
1: LABS = 59 : -+-++-+-+---+++-------+--++-++
2: LABS = 59 : -+-+--+-+---+++-------+--++-++
3: LABS = 59 : +-+-++-+-+++---+++++++-++--+--
4: LABS = 59 : --+--++-+++++++---+++-+-++-+-+
5: LABS = 59 : ----++++++-++-++-+-+-+++--+++-
6: LABS = 59 : +-+--+-+-+++---+++++++-++--+--
7: LABS = 59 : ++-++--+-------+++---+-+-++-+-
8: LABS = 59 : -+++--+++-+-+-++-++-++++++----
9: LABS = 59 : +---++---+-+-+--+--+-----+++++
この実行では、同一の最小LABS値を達成する複数の解が得られた。