@yuichirominato 2018.08.01更新

NP問題のイジング

NP イジング 量子アニーリング 量子ゲート

はじめに

量子アニーリングなどの組合せ最適化問題が流行っていますが、
なかなか実際の解法などを詳細に解説しているところがありません。
下記の論文にはたくさんの例題が載っていて公開されていますので、
片っ端から解いていこうと思います。

初見なので違っているところがあれば指摘してください。

“Ising formulations of many NP problems”
Andrew Lucas

Department of Physics, Harvard University, Cambridge, MA, USA 02138
We provide Ising formulations for many NP-complete and NP-hard problems, including
all of Karp’s 21 NP-complete problems. This collects and extends mappings to the Ising model from partitioning, covering and satisfiability. In each case, the required number of spins is at most cubic in the size of the problem. This work may be useful in designing adiabatic quantum optimization algorithms.

lucas@fas.harvard.edu January 27, 2014

https://arxiv.org/pdf/1302.5843.pdf

必要なこと

イジングという物理モデルの上でハミルトニアンと呼ばれる数式が必要です。解きたい問題をハミルトニアンと呼ばれる形におとしこみ、そこから実際の量子ビットにパラメータを生成します。今回は実際に手元でシミュレーションを通じて実行した例題の結果もなるべく併記しておきます。

1.分割問題 / Partitioning Problems

1.1自然数分割問題 / Number Partitioning

ある自然数の集合を2つのグループに分割し、それぞれのグループ内の自然数の和が同じになるような分割方法を探します。下記のハミルトニアンでは、N個の自然数の$i$番目を$n_i$として、グループAに属する時には$s_i=-1$、グループBに属する時には$s_i=1$と分類することで、2つのグループ内のそれぞれの和が等しい時に最小値問題で$H=0$となります。

$H = (\sum_{i=1}^N n_i s_i)^2$

(例題)$n_i=[1,1,1,1]$

$s_i=[1,-1,-1,1]$となりました。$1\times1+1\times-1+1\times-1+1\times1 = 0$ですので{1,1}と{1,1}にわかれました。

(例題)$n_i=[1,2,3,4,5,6,7,8,10]$

$s_i=[-1,1,1,-1,1,1,1,-1,-1]$となりました。
{1,4,8,10}と{2,3,5,6,7}にわかれました。
それぞれ足すと23になるのであっているようです。

$s_i=[1,-1,1,1,1,-1,-1,-1,1]$も答えと出ました、
この場合には、{1,3,4,5,10}と{2,6,7,8}とやはり23ずつになりました。
基底状態となる解は多数あるようです。

(例題)$n_i=[3,2,6,9,2,5,7,3,3,6,7,3,5,3,2,2,2,6,8,4,6,3,3,6,4,3,3,2,2,5,8,9]$

長くしてみましたが問題なく解けました。
$s_i=[-1,-1,1,1,-1,-1,-1,1,-1,-1,-1,1,1,1,1,-1,-1,1,1,-1,-1,-1,1,1,1,-1,1,1,-1,-1,1,-1]$

問題が簡単なので苦労せずできます。

1.2グラフ分割 / Graph Partitioning

グラフ問題において、頂点Vの数が偶数ある時に頂点をちょうど$\frac{V}{2}$ずつ2グループに分割した時に、お互いのグループをつなぐエッジの数が最小になる問題を求めます。

$H = (\sum_{i=1}^N s_i)^2 + B\sum_{(u,v)\in E}\frac{1-s_us_v}{2}$

1つ目のハミルトニアンは$s_i=-1$と$s_i=1$に分けた時にそれぞれのグループに含まれる頂点の数が同じになるような条件、2つ目は2つの頂点を選んだ時に違うグループに属する場合にはコストが上がるように設計された項です。これにより、違うグループ同士で接続数が多いとコストが増加するように設計されています。

(例題)1Dリングのグラフを想定しました。

頂点数が8の場合に解いて見ると、リング状なので、2つにわかれました。
[1,1,1,1,-1,-1,-1,-1]

頂点数が16の時にも2つにわかれました。
[-1,-1,-1,1,1,1,1,1,1,1,1,-1,-1,-1,-1,-1]

こちらの問題は明らかに1Dリングで綺麗に二手に別れれば良さそうですが、条件項を接続する係数Bのバランスに苦労しました。

3 クリーク問題 / Cliques

クリーク問題は、グラフ理論において、グラフ中のクリーク(任意の二頂点間に枝があるような頂点集合)を見つける問題。下記はグラフ中にKのクリークが存在するかどうかをみつけるハミルトニアン。1項目は頂点数をKに制約する条件。2項目のBで囲まれた部分は選んだ頂点が完全グラフを構成している場合にコストがもっとも小さくなるようなエッジの数の条件です。クリーク数がKのものが存在する場合、ハミルトニアンH=0となります。

$H = \left(K-\sum_v x_v\right)^2 + B\left[\frac{K(K-1)}{2}-\sum_{(u,v)\in E}x_u x_v\right]$

(例題)下記のように6つのノードで行って見ました。立式の問題ですが、少し工夫したほうがやりやすかったです。

結果は何度計算してもきちんと、
$x_i = [1,1,0,0,1,0]$
となり、1と2と5のノードが構成するクリーク数3という結果がでました。

(例題)少し複雑にして9ノードでクリーク数4を探して見ます。

結果は
$x_i = [0,0,0,0,1,1,1,1,0]$
となり、5,6,7,8のノードで構成されるクリークが見つかりました。

こちらは意外と綺麗に求まりました。

3.0-1整数計画問題 / Binary Integer Linear Programming

バイナリ値からなるベクトル$x$について$Sx=b$という制約条件を満たす中で、$c\cdot x$が最大となる$x$を求める。

ハミルトニアンは単純に上記の制約条件と最大にするコスト関数を繋げて、

$H = \sum_{j=1}^m \left[ b_j – \sum_{i=1}^N S_{ji}x_i \right]^2 -B\sum_{i=1}^N c_i x_i$

(例題)適当に作ってみました。

$$
\begin{pmatrix}
3&&2&&1\\
5&&2&&3
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2\\
x_3
\end{pmatrix}
=
\begin{pmatrix}
3\\
5
\end{pmatrix}
$$

を満たす時、

$$
\begin{pmatrix}
1 & 2 & 1
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2\\
x_3
\end{pmatrix}
$$

を最大にするようなベクトル$x$を求めます。

結果は、

$x = [0, 1, 1]$

となり最大になる$x$がきちんと求められています。

4. Covering and Packing Problems

4.1. Exact Cover

Exact Cover問題は集合$U = \lbrace 1,2,…,n\rbrace$と、その部分集合$V_i\subseteq U$があり、下記を満たす時、要素が互いに素かつ和集合が$U$となるような$\lbrace V_i \rbrace$の集合の部分集合が存在するかどうかという問題。

$
U = \bigcup_i V_i
$

ハミルトニアンは、自然数1からnまでに対して、それぞれ部分集合$V_i$が選ばれてそのなかにその自然数が含まれていれば$x_i=1$、含まれてなければ$x_i=0$として下記のようになる。

$
H = \sum_{\alpha = 1}^n\left(1-\sum_{i:\alpha \in V_i} x_i \right)^2
$

(例題)自然数1から10にたいして次の集合があるとき、上記の条件を満たすようなものはあるかどうか。{1,2},{3,4,5,6},{7,8,9,10},{1,3,5},{10}

解いてみたところ、[1, 1, 1, 0, 0]となりました。{1,2},{3,4,5,6},{7,8,9,10}が条件を満たすとのこと。

(例題)上記にもう少し集合を加えてみました。
{1,2},{3,4,5,6},{7,8,9,10},{1,3,5},{10},{7,9},{2,4,6,8}

解いてみたところ、上記の他に[0, 0, 0, 1, 1, 1, 1]も条件を満たすという答えが出ました。{1,3,5},{10},{7,9},{2,4,6,8}も答えに加わります。

上記のハミルトニアンに下記の条件を加えるとsmallest exact coverになります。

$
H_B = B\sum_{i} x_i
$

4.2 Set Packing

上記のような条件で互いに素な$V_i$の集合のうちもっとも数の多いものをSet Packing問題という。$V_i \cap V_j$がemptyのとき$J_{ij} = 0$それ以外は$J_{ij} = 1$(ここらへんはちょっと元のハミルトニアンをいじってます)として、ハミルトニアンは、

$
H = \sum_{i,j \in E}J_{ij}x_i x_j – B\sum_i x_i
$

(例題)下記の集合でやってみます。このうちで互いに素なものを組み合わせてもっともたくさん選びます。
{1,2},{3,4,5,6},{7,8,9,10},{1,3,5},{10},{7,9},{2,4,6,8}

答えは[1, 1, 0, 0, 1, 1, 0]とでたので、
{1,2},{3,4,5,6},{10},{7,9}の4つが選ばれました。(厳密解かどうかは調べてません。)

4.3 頂点被覆 / Vertex Cover

グラフ理論において、グラフGの頂点からなるある集合VがGの頂点被覆(ちょうてんひふく、英: vertex cover)であるとは、Gのどの辺をとってもその端点のどちらかがVに含まれるという意味である。(https://ja.wikipedia.org/wiki/%E9%A0%82%E7%82%B9%E8%A2%AB%E8%A6%86 より)

今回求めるのは最小頂点被覆。ハミルトニアンは第一項がどちらかが集合Vに含まれるという条件。二項目はそのうち最小のものを求めるというコスト関数。$x_i=1$なら集合$V$に含まれる。

$
H =  \sum_{u,v \in E}(1-x_u)(1-x_v) + B\sum_v x_v
$

(例題)せっかくなので前に出てきたグラフを使います。

解いてみたところ、$x_i = [0, 1, 1, 0, 1, 1, 0, 1, 0]$のほか多数の解が出てきましたが、頂点数はだいたい5でした。基底状態はたくさんありそうでした。

4.4 充足可能性問題 / Satisfiability

3-SAT問題は問題の作り方次第で、maximal independent set (MIS)を解くのと同じように解ける。MISに関しては前述を参照。

4.5 Minimal Maximal Matching

グラフ構造の$G=(V,E)$の辺の部分集合$M(\subseteq E)$で$M$のどの辺も隣合わない時、$M$を$G$のマッチングと呼ぶ。

5.不等式を持つ問題 / Problems with Inequalities

5.1 Set Cover

Set Cover問題は集合$U = \lbrace 1,2,…,n\rbrace$と、その部分集合$V_\alpha\subseteq U$があり下記を満たす時、和集合が$U$となるような$V_\alpha$の最小の組み合わせはという問題。

$
U = \bigcup_{i=1}^N V_\alpha
$

ハミルトニアンは下記のようになります。

$
H = \sum_{\alpha=1}^n\left(1-\sum_{m=1}^N x_{\alpha,m}\right)^2 + \sum_{\alpha=1}^n\left(\sum_{m=1}^N m x_{\alpha,m}-\sum_{i:\alpha\in V_i}x_i\right)^2 + B\sum_{i=1}^N x_i
$

5.2. 整数の重さをもつナップザック問題 / Knapsack with Integer Weights

価値と重さをそれぞれ持つようなN個のものから重さがW以内で価値が最大になるようなものを選ぶ組合せ最適化問題。$y_n$は重さに対応するもので、重さW以内という記述を具体的に$16.彩色問題 / Coloring Problems

6.1 グラフ彩色問題 / Graph Coloring

n色の中から1色選んで全てのノードを塗り、かつエッジで接続されているノード間は異なる色となる時の塗り方を選びます。1項目は各ノード1色に制限する制約項、2項目はエッジで接続されているノード間は異なる色となる条件です。

$
H = \sum_v \left(1-\sum_{i=1}^n x_{v,i} \right)^2 + B\sum_{(u,v)\in E}\sum_{i=1}^n x_{u,i} x_{v,i}
$

(例題) 6つのエリアを4色で塗り分ける問題を想定します。

隣接するエリアのテーブルが上、下はそれぞれのエリアをノード表現したものとエッジの接続状況です。1ノードに4色あるので、4ノードがあります。隣接するエリアとは同じ色同士のノードがエッジを持っています。

行列を作って解いてみたところ、基底状態がたくさんあるらしく簡単に解けました。

上の段ひだりから
1:[0, 1, 0, 0]
2:[0, 0, 0, 1]
3:[0, 0, 1, 0]

下の段ひだりから
4:[1, 0, 0, 0]
5:[0, 1, 0, 0]
6:[1, 0, 0, 0]

たとえば、[青、赤、黄、緑]と仮定すると、
左上から順番に、[赤、緑、黄、青、赤、青]と塗り分けられ、隣接する部分が被らず塗り分けられているのがわかります。

6.2 Clique Cover

あるグラフ構造があるとして、各頂点をn色で塗り分けるとき、各々の色の集合$W_i$がそれぞれ完全結合かどうかを判断するのがClique Cover

$
H = \sum_v\left(1-\sum_{i=1}^nx_{v,i}\right)^2 + B\sum_{i=1}^n\left[\frac{1}{2}(-1+\sum_v x_{v,i})\sum_u x_{u,i} – \sum_{(u,v)\in E}x_{u,i}x_{v,i}\right]
$

6.3 Job Sequencing with Integer Lengths

$N$個のジョブと$m$台のコンピュータがあったとして、それぞれのジョブ$i$がジョブの実行時間$L_i$を持つとして、それぞれのクラスタのジョブの実行時間の合計を$M_\alpha \equiv \sum_{i \in V_\alpha}L_i$としたときに、$max(M_\alpha)$が最小になるようなジョブの組み方を考える。ジョブ$i$をマシン$\alpha$で解く時、$x_{i,\alpha} = 1$として、ハミルトニアンは下記の通り。$M_1-M\alpha = n$。一項目はジョブ1つにつきマシン1つに割り振り。二項目はM1のジョブ時間が最大になるように調整。最終項がM1のジョブ時間を短くするためのコスト関数。

$
H = \sum_{i=1}^N\left(1-\sum_\alpha x_{i,\alpha}\right)^2 + \sum_{\alpha=1}^m\left(\sum_{n=1}^M ny_{n,\alpha} + \sum_i L_i(x_{i,\alpha}-x_{i,1})\right)^2 + B\sum_i L_i x_{i,1}
$

7.ハミルトン閉路問題 / Hamiltonian Cycles

7.1 ハミルトン閉路およびハミルトン路 / Hamiltonian Cycles and Paths

ハミルトン路とは、グラフ上の全ての頂点を 1 度ずつ通る路のこと。特に、グラフ上の全ての頂点を 1 度ずつ通る閉路はハミルトン閉路という。(https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%AB%E3%83%88%E3%83%B3%E8%B7%AF より)

ハミルトニアンは、1つの頂点は1度だけ出現するという条件と1つの順位は一度だけ出現するという条件、それにノード間が繋がっていないエッジが選択された場合にはペナルティをつけるような制約項により、

$
H = \sum_{v=1}^n\left( 1-\sum_{j=1}^N x_{v,j} \right)^2 + \sum_{j=1}^N\left(1-\sum_{v=1}^Nx_{v,j} \right)^2 + \sum_{(u,v)\not\in E} \sum_{j=1}^N x_{u,j} x_{v,j+1}
$

ちょっと簡略化してしまいましたが無事解けました。

7.2 巡回セールスマン問題 / Traveling Salesman

上記ハミルトン閉路問題に距離のコスト関数を加え、最短経路問題に落とし込んだのが巡回セールスマン問題で、ハミルトニアンは、

$
H = \sum_{v=1}^n\left( 1-\sum_{j=1}^N x_{v,j} \right)^2 + \sum_{j=1}^N\left(1-\sum_{v=1}^Nx_{v,j} \right)^2 + \sum_{(u,v)\not\in E} \sum_{j=1}^N x_{u,j} x_{v,j+1} + B\sum_{(u,v)\in E}W_{u,v}\sum_{j=1}^N x_{u,j} x_{v,j}
$

こちらも完全グラフですが、解けました。

8. Tree Problems

木構造もイジングモデルで解くことのできる大事な問題です。

8.1. Minimal Spanning Tree with a Maximal Degree Constraint

重みのついたエッジをもつ無向グラフG=(V,E)に含まれる木構造のうち、すべての頂点を含み、エッジの重みが最小になるような構造を探す問題。追加の制約条件あり。ハミルトニアンは、

$
H = A\left(1-\sum_vx_{v,0}\right)^2 + A\sum_v\left(1-\sum_ix_{v,i} \right)^2 + A\sum_{uv\in E} \left( y_{uv} – \sum_i (x_{uv,i} + x_{vu,i}) \right)^2 + A\sum_v\sum_{i=1}^{N/2}\left(x_{v,i}-\sum_{u:(uv)\in E}x_{uv,i}\right)^2 + A\sum_v\left( \sum_{j=1}^\Delta jz_{v,j} -\sum_{u:(uv)\in E}\sum_i(x_{uv,i}+x_{vu,i}) \right)^2+A\sum_{(uv),(vu)\in E}\sum_{i=1}^{N/2}x_{uv,i}(2-x_{u,i-1}-x_{v,i}) + B\sum_{uv,vu\in E}\sum_{i=1}^{N/2}c_{uv}x_{uv,i}
$

8.2. Steiner Trees

上記と似ている問題。

$$
H = A\left(1-\sum_vx_{v,0}\right)^2
+ A\sum_{v\in E}\left(1-\sum_ix_{v,i} \right)^2
+ A\sum_{v\not{\in} U}\left(y_v-\sum_ix_{v,i} \right)^2
+ A\sum_v\sum_{i=1}^{N/2}\left(x_{v,i}-\sum_{u:(uv)\in E}x_{uv,i}\right)^2
+ A\sum_{uv,vu\in E}\sum_{i=1}^{N/2}x_{uv,i}(2-x_{u,i-1}-x_{v,i})
+ A\sum_{uv\in E} \left( y_{uv} – \sum_i (x_{uv,i} + x_{vu,i}) \right)^2
$$

9. Graph Isomorphisms

N個の頂点のグラフがある時、2つのグラフ$G_1$と$G_2$が同型写像かどうかを確認する。

wikipedia:グラフ同型
https://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E5%90%8C%E5%9E%8B
からの引用によると下記のようになる。

グラフを同型写像かどうかを判定するハミルトニアンは、

$
H=\sum_v \left( 1-\sum_i x_{v,i}\right)^2 + \sum_i \left( 1-\sum_v x_{v,i} \right)^2+B\sum_{ij \not{\in}E_1}\sum_{uv \in E_2}x_{u,i}x_{v,j}+B\sum_{ij \in E_1}\sum_{uv\not{\in}E_2}x_{u,i}x_{v,j}
$

あわせて読みたい