Ising/QUBO 問題¶

Blueqat wq モジュールはイジング問題と制約なし二次形式二値変数最適化(QUBO)問題のためのモジュールです。ローカル環境で動作するシミュレーテッドアニーリング(SA)とシミュレーテッド量子アニーリング(SQA)のソルバーが組み込まれています。wq モジュールを使用してD-Waveクラウドマシンに問題をサブミットすることも可能です。

イジングモデルとは¶

実際の量子アニーリング (QA) マシンはイジングモデルと呼ばれる物理モデルで構築されており、シミュレーテッドアニーリング (SA) またはシミュレーテッド量子アニーリング(SQA)と呼ばれるアルゴリズムをパソコン上でシミュレートすることが可能です一次元イジングモデルは量子ビット(qubits)の一次元配列であり、それぞれが+1 (up) か-1 (down) のスピンを持ちます。二次元イジングモデルも同様に平面格子から成り、一次元イジングモデルよりも多くの隣接量子ビットを持ちます。これらの物理は複雑なので圧倒されるかもしれませんが、wq moduleはそれらの知識が無くとも簡単にモデルの計算を行うことができます。

組合せ最適化問題とシミュレーテッドアニーリング¶

シミュレーテッドアニーリング(SA)はいくつかの形式の組合せ最適化問題を解くのに用いられます。イジングモデルはそのうちの一つです。そのような問題を解く手順の中で、モンテカルロ法に基づいたメトロポリスサンプリングが使用されます。

ハミルトニアン¶

SAを用いてイジングモデルを解くために、Jij/hiを設定しなければなりません。これらは、量子ビットのペアがどれほど強く相互作用しているか、一つの量子ビットにどれほどの磁場がかかっているかをそれぞれ表しています。

シミュレーテッドアニーリングとシミュレーテッド量子アニーリング¶

イジング問題を解くためのシミュレーテッド量子アニーリング(SQA)と呼ばれるアルゴリズムもあります。この手法では量子効果を考慮に入れています。量子重ね合わせ効果は異なる世界線での並列実行によって近似され、より自然に近い量子の性質を効率的にシミュレートすることが可能です。技術的には、鈴木-トロッタ分解に基づく経路積分法が使用されています。

解の確認と検証¶

解の「エネルギー」を計算することで解の良し悪しを割り出すことができ、wq moduleではこれを一行(のプログラム)で実行可能です。繰り返しイジングモデルを解いた後、エネルギーを比較してどれがその問題にとって最良またはより良い解であるかを知ることが可能です。もしNP問題なら、制約が満たされているかどうかを確認することで多項式時間で計算することも可能です。

QUBO¶

イジングモデルの問題は二次非制約二項最適化問題(QUBO)によって表現されます。組み合わせ最適化問題では変数は{0, 1}で表しますが、上述の量子スピンは{-1, 1}によって表現されるので、表現を変換しなければなりません。 wq moduleは自動的にそれらの変換を行うため、みなさんがその変換について知っている必要はありません。

QUBOについてより学ぶ¶

ここでQUBOについてより深くみてみましょう。

箱の表にそれぞれ \(x_{0}, x_{1}, x_{2}\) と書かれた3つの箱があるときに、その中からいくつかの箱を選ぶ問題を考えます。

まず、箱が選ばれた場合を1、選ばれなかった場合を0と決めます。\(x_{0}\) の箱を選んだ場合、 \(x_{0} = 1, x_{1} = 0, x_{2} = 0\) と表現します。コンピュータで扱い易いように、これを配列で表現すると[1,0,0]のようになります。

今回解きたい問題が「3個から任意の2個を選ぶ」という問題だとします。この問題を解くために関数E(x)を考えるのですが、正しい選び方をした場合に関数E(x)が最小になるような関数を考えます。今回は、次の関数を考えました。

\[E(x) = (x_{0} + x_{1} + x_{2} - 2) ^ 2\]

どうなるか見てみましょう。

If you choose \(x_{0}\) alone, \(E(x) = (1 + 0 + 0 - 2) ^ 2 = (-1) ^ 2 = 1\)
If you choose \(x_{0}\) and \(x_{1}\), \(E(x) = (1 + 1 + 0 - 2) ^ 2 = (0) ^ 2 = 0\)
3つとも選んだ場合、 \(E(x) = (1 + 1 + 1 - 2) ^ 2 = (1) ^ 2 = 1\) になります。

2つ選んだときだけ、最小値である0をとりますので、ここで考えたE(x)はこの問題を解くために最適な関数のようです。このE(x)を少し展開していきます。

\[\begin{split}E(x) &= (x_{0} + x_{1} + x_{2} - 2) ^ 2 \\ &= (x_{0} + x_{1} + x_{2} - 2) (x_{0} + x_{1} + x_{2} - 2) \\ &= x_{0} ^ 2 + x_{1} ^ 2 + x_{2} ^ 2 + 2 x_{0} x_{1} + 2 x_{0} x_{2} + 2 x_{1} x_{2} - 4 x_{0} - 4 x_{1} - 4 x_{2} + 4\end{split}\]

ここで、 \(x\) は0か1の値しか取らないことを思い出してください。その場合、\(x = x ^ 2 = x x\) と変換することができます。それを使うと上記の式は、さらに次のように変形できます。

\[\begin{split}E(x) &= x_{0} ^ 2 + x_{1} ^ 2 + x_{2} ^ 2 + 2 x_{0} x_{1} + 2 x_{0} x_{2} + 2 x_{1} x_{2} - 4 x_{0} - 4 x_{1} - 4 x_{2} + 4 \\ &= x_{0} ^ 2 + x_{1} ^ 2 + x_{2} ^ 2 + 2 x_{0} x_{1} + 2 x_{0} x_{2} + 2 x_{1} x_{2} - 4 x_{0} x_{0} - 4 x_{1} x_{1} - 4 x_{2} x_{2} + 4 \\ &= -3 x_{0} x_{0} −3 x_{1} x_{1} -3 x_{2} x_{2} + 2 x_{0} x_{1} + 2 x_{0} x_{2} + 2 x_{1} x_{2} + 4\end{split}\]

ここで、上記のE(x)を計算するために、次の様なマトリックスを考えます。

	\(x_{0}\)	\(x_{1}\)	\(x_{2}\)
\(x_{0}\)
\(x_{1}\)
\(x_{2}\)

上記の式の最初の部分は \(x_{0}\) と \(x_{0}\) をかけたものを-3倍するということですよね。なので、マトリックスの \(x_{0}\) と \(x_{0}\) が交わるところに-3と入れます。

	\(x_{0}\)	\(x_{1}\)	\(x_{2}\)
\(x_{0}\)	-3
\(x_{1}\)
\(x_{2}\)

次の2つも \(x_{1}\) と \(x_{1}\) の交点、 \(x_{2}\) と \(x_{2}\) の交点にそれぞれ-3を入れます。

	\(x_{0}\)	\(x_{1}\)	\(x_{2}\)
\(x_{0}\)	-3
\(x_{1}\)		-3
\(x_{2}\)			-3

その次は \(x_{0}\) と \(x_{1}\) をかけたものを2倍するということなので、 \(x_{0}\) と \(x_{1}\) が交わるところに2といれます。

	\(x_{0}\)	\(x_{1}\)	\(x_{2}\)
\(x_{0}\)	-3	2
\(x_{1}\)		-3
\(x_{2}\)			-3

次の2つも \(x_{0}\) と \(x_{2}\) の交点、 \(x_{1}\) と \(x_{2}\) の交点にそれぞれ2を入れます。最後の4は定数なので、エネルギーの最小値を求める際には影響しないので、無視します。

結果としてできたマトリックスはつぎのようになります。実はこれが「3つの箱から任意の2つを選ぶ」問題を解くためのQUBOなのです。

	\(x_{0}\)	\(x_{1}\)	\(x_{2}\)
\(x_{0}\)	-3	2	2
\(x_{1}\)		-3	2
\(x_{2}\)			-3

このQUBOを使ってwqモジュールのシミュレーティッドアニーリングに解かせるコードは次のようになります。

import blueqat.wq as wq
a = wq.Opt()
a.qubo = [[-3,2,2], [0,-3,2], [0,0,-3]]
answer = a.sa()
print(answer)

実行してみると、[1,1,0]と表示されました。これは \(x_{0}, x_{1}\) が選ばれたことを表します。「3つの箱から任意の2つを選ぶ」問題がちゃんと解けていますね。今回の場合、実行する毎に違う答えが表示されます。それは、今回の問題が、3つの箱から2つを選ぶ問題であり、その答えは実際に3通りあるからです。

問題の解き方を整理すると次のようになります。

その問題が解けたときに、最小になる関数E(x)を考えます。
E(x)を式展開してQUBOマトリックスを作成します。
QUBOマトリックスをwq moduleに与えて、シミュレーティッドアニーリングで解かせます。

この中で難しいのは1.ですが、チュートリアルに問題とその関数の例が多数掲載されていますので、その中から合うものを見つけると良いでしょう。

QUBOの行番号を \(i\) 、列番号を \(j\) とし、QUBOの各要素を \(Q_{ij}\) と表すとE(x)は次の様に表現できます。

\[E(x) = \sum_{i} \sum_{j} Q_{ij} x_{i} x_{j}\]

ここで \(Q_{ij}\) がまさにQUBOです。上の方でE(x)を計算している最後の式をよく見てみると、この形になっていることが分かると思います。

Wikipedia の説明（英語）も参考にしてください。