Wildqatの紹介

Wildqatは制約なし二次形式二値変数最適化(QUBO)のためのオープンソースのPythonフレームワークです。 あなたのパソコンにインストールし、すぐに開発を始めることができます。 現在、SDKにはローカル環境で動作するシミュレーテッドアニーリング(SA)とシミュレーテッド量子アニーリング(SQA)のソルバーが組み込まれています。 今後はクラウドで動作するソルバーも提供される予定です。

イジングモデルとは

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

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

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

ハミルトニアン

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

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

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

QUBO

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

QUBOについては QUBO入門 に詳しい説明があります。

解の確認と検証

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