はじめに

量子アニーリングマシンを利用して最適化を行うには，問題を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$ 回最適化計算しましょう．