課題をどのようにして組合せ最適化問題として解釈するのか、またどのようにして組合せ最適化問題をマシンが利用可能な形に変換するのかという問題は、アニーリングマシンにおけるプログラミングの本質部分です。
現在のマシンの多くは、イジング模型(または QUBO)を入力として持ちます。そのため、マシンに問題を注入する際には、
\[
H \left( \mathbf{\sigma} \right) = \sum_{ i \ne j}{J_{ij}\sigma_i \sigma_j} + \sum_i{h_i \sigma_i}
\]
という形に問題を変換しておく必要があります。
主要な方針としては、
- 課題をグラフの問題と解釈してグラフ上のイジング模型に変換する
- 課題を定式化してイジング模型に変数変換する
などが挙げられます。
前者については、イジング模型で表現できることが知られているグラフ問題を利用するという方法です。これが利用できる場合には直接的に課題をイジング模型に変換できます。後者については、エネルギー関数をイジング変数(またはQUBO変数)の多項式で表現するという方針です。どちらの場合でも重要な考え方は、好ましい組合せに対してエネルギーを下げる、好ましくない組合せに対してはエネルギーを上げる、という対応を行うことです。
このページでは後者の方針で具体的な変換例を考えてみたいと思います。
論理式からイジング模型への変換
#
なぜ、例として論理式を取り上げるのかというと、多くの計算量的に困難な決定問題が、論理式の決定問題に帰着するからです。これは充足可能性問題 (SAT)と呼ばれますが、最も有名なNP完全問題として知られています。イジング模型もNP完全問題の一つなので、互いに多項式時間還元が可能になっています。組合せ最適化問題においてもこの変換については同様なので、多くの最適化問題は充足可能性問題 (SAT)を経由することでイジング模型に変換することが可能です。
どのようにして論理式をイジングで表現するのか、例として AND OR NOT 演算子をイジング模型に変換してみたいと思います。
以降、論理式との相性からイジング変数
\(\sigma \in \left\{-1, +1 \right\}\)
ではなく、これを変数変換した
\(q\in \left\{0, +1 \right\}\)
とします。このように変数を変換したイジング模型をQUBOと呼びますが、変数変換
\[
q = \left(\sigma + 1 \right) / 2
\]
を行っているだけなので両者は等価です。
これから紹介する方法は変換方針の説明を目的としているため、必ずしも最も効率の良い変換ではありません。論理式の形式の仮定、対称性の考慮、解の制限を行うことで変数や結合の数を減らすことが可能です。
論理積 (AND)
#
論理積では変数が共に1の時に1が出力されます。つまり、両者とも1のときが好ましい、と解釈できます。これをエネルギー関数で実現すると、論理積という言葉の通り、
\[
A \& B \quad \rightarrow \quad - \left(A B \right)
\]
と2変数の積で表すと良さそうです。こうすると上の表のように両者が1のときのみエネルギーが下がり、それ以外のときはエネルギーが0で一定です。ただし、マイナス符号は最適化をエネルギー最小化としたためということに注意してください。論理積演算子としては掛け算が対応します。
論理和 (OR)
#
論理和では変数のうち少なくとも一つが1の時に1が出力されます。つまり、少なくとも片方が1のとき好ましい、と解釈できます。これをエネルギーで表すと下記のようにすると良さそうです。
\[
A | B \quad \rightarrow \quad - \left(A + B - A B \right)
\]
論理和、なので2変数の和で表されますが、注意点として両者とも1のときもエネルギー的に等価に扱わなくてはなりません。そのために
\(A B\)
を追加しています。こうすると上の表のように少なくとも一方が1のときに等しくエネルギーが下がり、両方共0の時にのみエネルギーが0になります。
論理肯定・否定 (NOT)
#
論理肯定と否定は1が好ましい、0が好ましいということなので、それぞれの場合にエネルギーが下がるようにすれば良いです。つまり単純に磁場の符号で表現することが出来ます。
\[
\begin{aligned}
&A& \quad \rightarrow \quad - A \\
\verb|~| &A& \quad \rightarrow \quad - \left(1 - A \right)
\end{aligned}
\]
論理否定では値を揃えるために定数1が追加されています。エネルギー関数の定数項であれば最小化の際には基準値にしか影響しないため、無視して良いことになります。しかし、AND や OR などの他の演算子の入力変数にかかる場合には
1 が効いてきますので、単純には無視できないことに注意してください。
具体例1
#
例として次の論理式を取り上げます。
\[
\left( A \& \left( \verb|~| \left(B | C \right) \right) \right)
\]
この式が 1(TRUE) を出力する
\(A,B,C\)
の組合わせを求めるという問題です。答えは
\(A=1, B=0, C=0\)
です。それ以外の組合わせでは 0(FALSE) になります。これをイジング模型のエネルギーで表現します。
以降、変換過程がわかりやすいように、QUBO 変数
\(q \in \left\{0, 1 \right\}\)
を用います。
まず、最もネストの深い
\(B | C\)
に着目します。これは先程の結果から、
\[
\left( A \& \left( \verb|~| \left(q_B + q_C - q_B q_C \right) \right) \right)
\]
となります。次に NOT を適用して、
\[
\rightarrow \quad \left( A \& \left( 1 - q_B - q_C + q_B q_C \right) \right)
\]
さらに AND を適用し積で置き換えます。
\[
\rightarrow \quad \left( q_A \left( 1 - q_B - q_C + q_B q_C \right) \right)
\]
これを整理して、最後に全体にマイナスの符号を付けます。
\[
\begin{aligned}
& \rightarrow & \quad - \left( q_A q_B q_C - q_A q_B - q_A q_C + q_A \right) \\
& = & - q_A q_B q_C + q_A q_B + q_A q_C - q_A
\end{aligned}
\]
マイナス符号は上で説明したように、「エネルギー最小化」で 1 が出力されるように与えます。
これで論理式を QUBO 変数の多項式で表すことが出来ました。
多項式の次数下げ
#
以上でイジング模型に変換できたわけですが、一つだけ問題があります。通常、マシンが扱うことの出来るイジング模型は相互作用の項が2体までになっています。そのため上の式で出てきた、
\(q_A q_B q_C\)
のような 3体以上の相互作用項はそのままでは扱うことが出来ません。
そこで、3体の相互作用を2体で表現できないかを考えてみます。まず、次のような変数変換で次数を下げることが出来ます。
\[
q_A q_B q_C = q_C q_D \qquad q_D = q_A q_B
\]
変数を1つ増やすことで2体に落としました。しかし、単純にこの置換だけでは不十分です。なぜなら、
\(q_D\)
は
\(q_A,q_B\)
と独立に自由に値を取ることが出来ないからです。そのため、
\(q_D = q_A q_B\)
に縛るようなペナルティを課す必要があります。
結論を先に書くと、
\[
H_p = q_A q_B - 2 q_A q_D -2 q_B q_D + 3 q_D
\]
を追加すると良いです。これは次の表から確認できます。
3体相互作用を変数変換し2体にするのに加えて、ペナルティ項を付加することで
\(q_D = q_A q_B\)
を満たさない場合にエネルギーが上昇します。こうすることで、最適値に関しては自動的に
\(q_D = q_A q_B\)
が満たされます。図で表すと下記のようなイメージです。4体以上の場合においても、この変数変換を繰り返すことで2次に落とすことが出来ます。
アニーリングマシンの出力は一般的に近似解なので、正しく
\(q_D = q_A q_B\)
を満たしているかはユーザがチェックする必要があります。
具体例2
#
(#具体例1)[具体例1]で取り上げた論理式について次数下げを行ってみます。
\[
\begin{aligned}
&& \left( A \& \left( \verb|~| \left(B | C \right) \right) \right) \\
& \rightarrow & - q_A q_B q_C + q_A q_B + q_A q_C - q_A \\
& = & - q_C q_D + q_A q_B + q_A q_C - q_A + H_p \\
& = & 2 q_A q_B + q_A q_C - 2 q_A q_D - 2 q_B q_D - q_C q_D - q_A + 3 q_D \qquad \left( q_D = q_A q_B \right)
\end{aligned}
\]
これの最適解を求めると、
\[
q_A = 1, \quad q_B = 0, \quad q_C = 0, \quad q_D = 0
\]
が得られます。この解は
\(q_D = q_A q_B\)
を満たすと同時に、元々の論理式に代入しても正しいことが確認できます。