はじめに
量子アニーリングマシンを利用して最適化を行うには,問題をQUBO (Quadratic Unconstrained Binary Optimization) の形で表現する必要があります.
ここでは,最小値を取る関数minをQUBOに変換してみます.
問題設定
バイナリ変数 $x\in \{0,1\}^n$ の関数 $f_i(x), i=1,2,...,m$ があるとします.その最小値$F$を最小化したい,としましょう.
\text{minimize}\quad F
F=\min_i f_i(x)
もちろん, $f_i(x)$ ごとに $m$ 回最適化を行って,一番小さな値を取る $f_i(x)$ を見つければ解は求まります.が,それではつまらないので,ここでは1回の最適化計算で解を求めることを考えます.
変換方法
$f_i(x)$ に新たなバイナリ変数 $y_i$ を乗じたものを新たに $F'$ と置き,これを最小化することを考えます.
F'=\sum_{i=1}^m y_if_i(x)
ここで,「最小の $f_i(x)$ に対応する $y_i$ だけが1で,残りは0」であれば, $F=F'$ が満たされます.
そこで,$y_i$ には,どれか1つだけが1で,残りが0になるようなペナルティ $P$ を置きます.
P=\left(\sum_{i=1}^m y_i-1\right)^2
ここで,$F'$ と $P$ を同時に小さくすることを考えた場合,それを解決するには「最小の $f_i(x)$ に対応する $y_i$ だけが1で,残りは0となる」しかありません.よって,$F'$ と $P$ を(正の係数を用いて)線形結合させてQUBOで表現し,最適化問題を解けば,$f_i(x)$ の最小値を得る $x$ が解として求まるはずです.
なお,$F'$ については,$f_i(x)$ に $y_i$ を乗じていることで次数が上がってしまいます.必要なら次数を下げましょう.次数下げの方法は,イジング模型への変換 – 量子コンピューティング情報サイトに載っています.
数値例とpythonコード
\text{minimize}\quad \min\left( f_1(x), f_2(x) \right)
f_1(x)=x_1+2x_2
f_2(x)=3x_1-x_2
を前述の方法に従って変換すると,次のようになります.(当然ながら解は $x_1=0, x_2=1$ で,最小値は $f_2(x)=-1$ です.)
F'=y_1f_1(x)+y_2f_2(x)=x_1y_1+2x_2y_1+3x_1y_2-x_2y_2
P=\left(y_1+y_2-1\right)^2=-y_1-y_2+2y_1y_2+1\quad \because y_i^2=y_i
$F'$ と $P$ を足したものを最小化すれば,きっと解が求まるはず.
この問題を,DWave社のqbsolvを使って解いてみましょう. (自分の環境ではDWaveマシンは呼び出せないので,qbsolv内のタブーサーチソルバで解を求めています.)
qbsolvに与えるために,問題を次のように変形します.
\text{minimize}\quad F'+P = x^{\text{T}}Qx + 1, \quad x^{\text{T}} = [x_1, x_2, y_1, y_2]
上三角係数行列 $Q$ を,qbsolvに次のように与えます.定数の1は最小化には影響しないのでqbsolvには与えません.
from dwave_qbsolv import QBSolv
Q = {(0, 2): 1,
(1, 2): 2,
(0, 3): 3,
(1, 3):-1,
(2, 2):-1,
(3, 3):-1,
(2, 3): 2}
response = QBSolv().sample_qubo(Q)
計算結果を見てみると,
list(response.samples())
[{0: 0, 1: 1, 2: 0, 3: 1}]が得られます.
すなわち $x_1=0$, $x_2=1$, $y_1=0$, $y_2=1$ という解が求まりました.
また,
list(response.data_vectors['energy'])
で最小値を見ると,-2.0となっています.Pから出てきた定数の $1$ を足せば $-1$ となり,$F'$ の最小値が得られていることがわかります.
環境
Python 3.6.3
dwave-qbsolv 0.2.7
おわりに
$F'$ と $P$ を線形結合するときのパラメータを調整してもうまくいかない($P$がゼロにならない)ときは,素直に $m$ 回最適化計算しましょう.