イジングマシンで解くための手順は大まかに下記のようになります。弊社で開発中のイジングマシンは④の工程を行います。

適切な文章題の設定①と、適切な定式化②、最初の２つはイジングマシンで適切に解を導き出すためのとても重要な作業工程です。

(1)文章題

アプリ開発の最初の一歩は、文章題と言う「文章で書いた課題」を数式に置き換える「定式化」作業です。 求めたい値を変数で表し、特定の変化する量や制約条件等を加えます。 組み合わせ最適化問題の例としてクリーク被覆問題と呼ばれるものを取り上げます。

  • 下記のグラフを３色に色分けしてみます。
  • 10個の頂点はそれぞれ３色のいずれかに着色します。
  • 同色の点同志を線でつなぎます。
  • 各色が最も効率よくつながるパターンを見つけます。

(2)定式化

作った文章題を「定式化」する作業です。事例のクリーク被覆問題の定式は下記になります。

点や色の数、さらに条件が加わることで、組み合わせの候補数が非常に多くなり、従来のコンピュータでは計算が難しくなります。

(3)QUBO*化

定式化しただけではすぐに解が得られるわけではありません。 分析をすすめるためには、これをQUBOと呼ばれるイジングマシンで 投入できる行列の形に変換する必要があります。

* Quadratic Unconstrained Binary Optimization：制約なし二次形式二値変数最適化

(4)計算実行

QUBOに変換した定式を、FPGA上の「Qalmo」に対して送り、組合せ最適化の計算を実行します。

(5)結果表示

「Qalmo」からの答えをPCが受信し結果を画面に表示します。

上図のように３つのグループに分割されれば成功です。 解の候補が複数あれば、その優先順位順に表示されます。