変数配列と配列関数¶

Hi-QUBOは変数配列と配列演算をサポートしています.

変数配列の定義

2値変数の配列は qbpp::var() 関数を使って作成できます.

qbpp::var("name", size) は,指定した name を持つ size 個の変数の配列を返します.

以下のプログラムは,名前 x を持つ5個の変数の配列を定義します. x を std::cout で出力すると,5つの変数 x[0],x[1],x[2],x[3],x[4] が含まれていることを確認できます. 次に,qbpp::toExpr(0) を型推論とともに使用して,初期値が 0 の qbpp::Expr オブジェクト f を作成します. i = 0 から 4 までのforループで,各変数 x[i] が複合演算子 += を使って f に加算されます. 最後に,f が簡約化され,std::cout で出力されます.

vector-variables-and-functions-program1.cpp¶

#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x", 5);
  std::cout << x << std::endl;
  auto f = qbpp::toExpr(0);
  for (int i = 0; i < 5; ++i) {
    f += x[i];
  }
  std::cout << "f = " << f.simplify_as_binary() << std::endl;
}

このプログラムの出力は以下の通りです.

{x[0],x[1],x[2],x[3],x[4]}
f = x[0] +x[1] +x[2] +x[3] +x[4]

注意 qbpp::var(name, size) は qbpp::Var 型の size 個の要素を含む1次元の変数の配列を返します. 厳密な型は qbpp::Array<1, qbpp::Var> で,1 は次元数,qbpp::Var は要素の型を表します. auto を使えばコンパイラがこの型を推論してくれるので,明示的に書く必要があるのは,配列を非 static なクラスのメンバ変数として保持する場合だけです（C++ では非 static メンバに auto が使えないため）. 配列の型は,要素に対する要素ごとの演算をサポートするオーバーロードされた演算子を提供します.

注意 — インデックスの範囲 C++ では x[i] は範囲チェックを行いません（std::vector::operator[] と同じ規約）.範囲外や負のインデックスは未定義動作です.インデックスは [0, size) の範囲に収めてください.Python では範囲外インデックスに対して x[i] が IndexError を送出します. 配列の要素ごとの演算は同一の shape を要求します.異なる shape の配列を組み合わせるのはエラーです（C++ では致命的エラー,Python では例外送出）.

sum 関数

配列ユーティリティ関数 qbpp::sum() を使用すると,2値変数の配列の合計を取得できます. 以下のプログラムは qbpp::sum() を使用して,配列 x のすべての変数の合計を計算します.

vector-variables-and-functions-program2.cpp¶

#include <qbpp/qbpp.hpp>

int main() {
  auto x = qbpp::var("x", 5);
  std::cout << x << std::endl;
  auto f = qbpp::sum(x);
  std::cout << "f = " << f.simplify_as_binary() << std::endl;
}

このプログラムの出力は,前のプログラムとまったく同じです.

One-hot制約のQUBO

2値変数の配列が one-hot であるとは,ちょうど1つの要素が1に等しい,すなわち要素の合計が1に等しいことを意味します. \(X = (x_0, x_1, \ldots, x_{n-1})\) を \(n\) 個の2値変数の配列とします. 以下の式 \(f(X)\) は,\(X\) がone-hotである場合にのみ最小値0をとります.

\[ \begin{align} f(X) &= \left(1 - \sum_{i=0}^{n-1}x_i\right)^2 \end{align} \]

以下のプログラムは式 \(f\) を作成し,すべての最適解を見つけます.

vector-variables-and-functions-program3.cpp¶

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

int main() {
  auto x = qbpp::var("x", 5);
  auto f = qbpp::sqr(qbpp::sum(x) - 1);
  std::cout << "f = " << f.simplify_as_binary() << std::endl;
  auto solver = qbpp::ExhaustiveSolver(f);
  auto sol = solver.search({{"best_energy_sols", 0}});
  for (size_t k = 0; k < sol.size(); ++k) {
    std::cout << "(" << k << ") " << sol.sols[k] << std::endl;
  }
}

関数 qbpp::sum() は配列内のすべての変数の合計を計算します. 関数 qbpp::sqr() は引数の2乗を計算します. Exhaustive Solverはエネルギー値0のすべての最適解を見つけ,std::cout で以下のように出力されます.

f = 1 -x[0] -x[1] -x[2] -x[3] -x[4] +2*x[0]*x[1] +2*x[0]*x[2] +2*x[0]*x[3] +2*x[0]*x[4] +2*x[1]*x[2] +2*x[1]*x[3] +2*x[1]*x[4] +2*x[2]*x[3] +2*x[2]*x[4] +2*x[3]*x[4]
(0) 0:{{x[0],1},{x[1],0},{x[2],0},{x[3],0},{x[4],0}}
(1) 0:{{x[0],0},{x[1],1},{x[2],0},{x[3],0},{x[4],0}}
(2) 0:{{x[0],0},{x[1],0},{x[2],1},{x[3],0},{x[4],0}}
(3) 0:{{x[0],0},{x[1],0},{x[2],0},{x[3],1},{x[4],0}}
(4) 0:{{x[0],0},{x[1],0},{x[2],0},{x[3],0},{x[4],1}}

5つの最適解がすべて表示されます.

PyQBPPは変数の配列と配列演算をサポートしています.

変数配列の定義

バイナリ変数の配列は var() 関数を使って作成できます.

var("name", shape=size) は,指定された name を持つ size 個の変数からなる配列を返します.

以下のプログラムは,x という名前の5個の変数からなる配列を定義します. x を表示すると,5つの変数 x[0],x[1],x[2],x[3],x[4] が含まれていることが確認できます. 次に,f = 0 から始め,i = 0 から 4 までの for ループで,各変数 x[i] を複合演算子 += で f に加えます. 最後に,f を簡約化して表示します.

vector-variables-and-functions-program1.py¶

import pyqbpp as qbpp

x = qbpp.var("x", shape=5)
print(x)
f = 0
for i in range(5):
    f += x[i]
print("f =", f.simplify_as_binary())

このプログラムの出力は以下の通りです.

{x[0],x[1],x[2],x[3],x[4]}
f = x[0] +x[1] +x[2] +x[3] +x[4]

注意 — x[i] は範囲外インデックスに対して IndexError を送出します.配列の要素ごとの演算は同一の shape を要求し,異なる shape の配列を組み合わせると例外を送出します.

Sum 関数

ユーティリティ関数 sum() を使って,バイナリ変数配列の合計を取得できます. 以下のプログラムは sum() を使って配列 x のすべての変数の合計を計算します.

vector-variables-and-functions-program2.py¶

import pyqbpp as qbpp

x = qbpp.var("x", shape=5)
print(x)
f = qbpp.sum(x)
print("f =", f.simplify_as_binary())

このプログラムの出力は,前のプログラムとまったく同じです.

One-hot 制約の QUBO

バイナリ変数の配列が one-hot であるとは,ちょうど1つの要素が1に等しいこと,すなわち要素の合計が1に等しいことを意味します. \(X = (x_0, x_1, \ldots, x_{n-1})\) を \(n\) 個のバイナリ変数の配列とします. 以下の式 \(f(X)\) は,\(X\) が one-hot であるとき,かつそのときに限り最小値 0 をとります.

\[ \begin{align} f(X) &= \left(1 - \sum_{i=0}^{n-1}x_i\right)^2 \end{align} \]

以下のプログラムは式 \(f\) を作成し,すべての最適解を求めます.

vector-variables-and-functions-program3.py¶

import pyqbpp as qbpp

x = qbpp.var("x", shape=5)
f = qbpp.sqr(qbpp.sum(x) - 1)
print("f =", f.simplify_as_binary())

solver = qbpp.ExhaustiveSolver(f)
result = solver.search(best_energy_sols=0)
for i, sol in enumerate(result.sols):
    print(f"({i}) {sol}")

関数 sum() は配列内のすべての変数の合計を計算します. 関数 sqr() は引数の二乗を計算します. Exhaustive Solver は,エネルギー値 0 のすべての最適解を以下のように求めます.

f = 1 -x[0] -x[1] -x[2] -x[3] -x[4] +2*x[0]*x[1] +2*x[0]*x[2] +2*x[0]*x[3] +2*x[0]*x[4] +2*x[1]*x[2] +2*x[1]*x[3] +2*x[1]*x[4] +2*x[2]*x[3] +2*x[2]*x[4] +2*x[3]*x[4]
(0) Sol(energy=0, {x[0]: 0, x[1]: 0, x[2]: 0, x[3]: 0, x[4]: 1})
(1) Sol(energy=0, {x[0]: 0, x[1]: 0, x[2]: 0, x[3]: 1, x[4]: 0})
(2) Sol(energy=0, {x[0]: 0, x[1]: 0, x[2]: 1, x[3]: 0, x[4]: 0})
(3) Sol(energy=0, {x[0]: 0, x[1]: 1, x[2]: 0, x[3]: 0, x[4]: 0})
(4) Sol(energy=0, {x[0]: 1, x[1]: 0, x[2]: 0, x[3]: 0, x[4]: 0})

5つの最適解がすべて表示されます.