QUBO・制約条件の扱い方

2. QUBOと制約条件の扱い方

2.1 QUBOとは

前章で、量子アニーリングで最適化問題を解く準備として

変数は 0/1 の2値とする
目的関数を数式で表す
制約条件を数式で表すまで行いました。

では、これらを 量子アニーリングにどう渡す のでしょうか？
量子アニーリングが扱うことができるのは、実は以下のようなとても限られた形です。

E(x) = \sum_{i=1}^N Q_{ii} x_i + \sum_{i=1}^N \sum_{j=i+1}^N Q_{ij} x_i x_j

ここで、 $Q*{ii}, Q*{ij}$ は解くべき問題を表す係数です。 $x$ は $[x_1, x_2, \ldots, x_N]$ で表される $N$ 次元のベクトルです。
つまり、目的関数と制約条件を 「二値変数かつ二次の式」 に落とし込むところまでしっかり定式化しなければ、量子アニーリングは問題を理解できません。
上のような “量子アニーリングが理解できる形式” を、一般に QUBO （Quadratic Unconstrained Binary Optimization）と呼びます。

QUBOは、最適化問題を二値変数と二次形式で表現するための統一的な枠組みであり、量子アニーリングを含む多くのソルバーが前提とする標準形式です。問題をQUBOに変換できれば、そのまま量子アニーリングマシンやイジングマシンなどの専用ハードウェアに入力して解を求めることが可能になります。 QUBO形式の問題を解く専用のマシンについては別ページにて一部紹介してるので、ぜひご覧ください。

ナップサック問題を振り返ると、目的関数そのものは QUBO 形式で記述できそうだということがわかります。しかし、QUBO は制約を直接扱うことができない形式であるため、実際の問題に含まれる制約は目的関数の中に組み込む必要があります。次章では、この制約を目的関数に埋め込む具体的な方法について詳しく説明します。

2.2 ペナルティ法

QUBOは「制約なし」の形式で定義されているため、実際の最適化問題に含まれる制約をそのまま扱うことはできません。そこで重要となるのが、制約を目的関数の中に組み込むための仕組みです。その中で代表的な手法が ペナルティ法 です。量子アニーリングは、膨大な解候補の中からエネルギーの低い解を探索します。ペナルティ法では、制約を満たさない解に対して大きなペナルティを加える（エネルギーをが高くする）ことで、そうした解が選ばれにくくなるように仕組みます。まとめると次のようになります：

制約を満たす解 → ペナルティが 0 または十分小さく、選ばれやすい
制約を破る解 → 大きなペナルティが加わり、避けられやすい

以下で、具体例を用いて説明します。

2.3 等式制約の扱い方

等式制約は、最適化問題で最も基本的な制約の一つで、ペナルティ法を用いて、目的関数に容易に組み込むことができます。
最適化問題が次のように表されているとします：

\begin{aligned} \min_{x} \; f(x) \quad \text{s.t.} \quad g(x) = 0 \end{aligned}

これは制約 $g(x)=0$ を満たす解の中から、 $f(x)$ が最も小さくなるものを求めるという意味です。
このとき、目的関数に次のペナルティ項を追加します：

\min_{x} \left( f(x) + \lambda\, g(x)^2 \right)

ここで、 $\lambda$ はペナルティ係数と呼ばれるパラメータです。制約を破った場合（ $g(x) \neq 0$ ）、追加項が正となりエネルギーが高くなる一方、制約を満たす場合には $g(x)=0$ となりペナルティ項は $0$ になります。
したがって、この目的関数では制約を満たしている解ほど低いエネルギーとなり、選ばれやすくなります。

ここでは等式制約の中でも代表的なone-hot 制約の埋め込みについて紹介します。 one-hot 制約は、複数の選択肢のうち「1のみ選ぶ」という条件を表すもので、最適化問題は以下のようになります：

\min_{x} f(x) \quad \text{s.t.} \quad \sum_{i=1}^N x_i = 1

ペナルティ法に従い、この制約式を $g(x)=0$ の形にします。すると先ほどの制約は次のように表すことができます：

\sum_{i=1}^N x_i - 1 = 0

この式を2乗してにペナルティ係数 $\lambda$ を掛けた次の項がペナルティ項となります。
よって、one-hot 制約を目的関数に埋め込んだ最適化問題は次のように書けます：

\min_{x} \left\{ f(x) + \lambda \left( \sum_{i=1}^N x_i - 1 \right)^2 \right\}

このように、one-hot 制約をはじめとする等式制約は、ペナルティ法により目的関数に埋め込むことができます。

2.4 不等式制約とスラック変数

もしかすると、等式ではなく不等式制約を扱いたい場合もあるかもしれません。ナップサック問題を例に考えてみましょう。
例えば、「選べる品物の数は $K$ 個以下」という制約を考えると、次のような不等式で書くことができます：

\sum_{i=1}^N x_i \le K

不等式制約つきの最適化問題は一般的に記述すると次にようになります：

\begin{aligned} \min_{x} \; f(x) \quad \text{s.t.} \quad h(x) \le 0 \end{aligned}

しかし、この不等式制約をそのままペナルティ法で扱おうとすると問題が生じます。等式制約と同様に、目的関数にペナルティ項 $\lambda\, h(x)^2$ を加えるだけでは、制約を満たしている解でも $h(x)=0$ でない限り必ず正の値が生じてしまい、不要なペナルティを与えてしまうからです。
そのため、不等式制約では等式制約のときと同じ方法を直接適用することができません。そこでよく使われるのが、不等式をいったん等式へと変換し、等式制約として扱う方法です。この変換のために導入される補助変数が、スラック変数（slack variable）です。

例えば、先ほどの不等式制約を新しい変数 $s$ を用いて次のように書き直します。

\sum_{i=1}^N x_i + s = K, \quad s \ge 0

この変数 $s$ がスラック変数であり、もとの制約の「余裕」の大きさを表しています。ここで $s$ に上限値と表現精度を決め、二値変数で表現します。
具体的には、 $s$ を 0 以上の整数として扱い、それを0/1の二値変数で表すには2進数表現を用います：

s = \sum_{k=0}^{m-1} 2^{k} y_k, \qquad y_k \in \{0,1\}

ここで、 $m$ は $s$ が取りうる値の範囲によって決まります。スラック変数は $0 \le s \le K$ を満たす必要があるため、2進数で $K$ までの値を表現できる最小のビット数 $m$ を決めます：

2^m-1 \ge K

このようにして、スラック変数を新しい二値変数の集合 $\{y_1, y_2, \ldots, y_{m-1}\}$ へ置き換えることができます。

このとき、元の不等式制約は、拡張された変数 $(x,y)$ に対する次の等式制約として書き直すことができます：

\sum_{i=1}^N x_i + \sum_{k=0}^{m-1} 2^{k} y_k - K = 0

ここまで変形できれば、あとは等式制約の場合と同様に、この式が0となるようにペナルティ項を目的関数に追加します。
最終的に不等式制約を目的関数に埋め込んだ最適化問題は次のようにかけます：

\min_{x} \; \left\{ f(x)+ \lambda \left( \sum_{i=1}^N x_i + \sum_{k=0}^{m-1} 2^{k} y_k - K \right)^2 \right\}

このように、不等式制約は直接ペナルティをかけるのではなく、スラック変数を導入して等式制約に変換し、そのうえで等式制約としてペナルティ法を適用するのが基本的な考え方です。スラック変数の取り方や表現に応じて導入される二値変数の数や QUBO のサイズは変化しますが、発想そのものは単純であり、多くの QUBO 定式化で標準的に用いられている手法です。