2
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

最小値を取る関数minをQUBOに変換する

Posted at

はじめに

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

2
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?