blueqatを用いた最適化問題の解き方
Last Update:2021/12/09
(株式会社アカデメイア)
1. はじめに
blueqatはPythonで書かれた量子ゲートシミュレータで、オープンソースのソフトウェアとなっています。ここでは、単純な最適化問題をblueqatを用いて解いてみます。
2. インストール・コンパイル方法
ここでは、AnacondaのPython3.8.5、Mac OS 10.15上でのインストールについて記載します。
インストールはpipコマンドで実行して下さい。
pip install blueqat
上記コマンド実行で、blueqatがインストールされます。
インストールの確認は以下の通りです。
python
として、起動するPythonの対話モードで、
import blueqat
と入力してEnterを押し、なにもエラーが出なければ、無事にインストール出来ています。
バージョンは
blueqat.__version__
と入力してEnterを押す事で確認が出来、’0.3.18’などのバージョン番号が下の行に出力されます。
注意：pipやpythonコマンドはpython3のものを想定しています。お使いのデフォルト環境がpython2系の場合はpip, pythonの代わりにpip3, python3をそれぞれ使用してください。なお、MateriApps LIVE! ver. 3.2の場合は、pip3, python3を使えば本記事の内容を実行できます。
3. 計算実行、結果
それでは実際にblueqatを動かしてみましょう。blueqatは公式ページのチュートリアルが充実しているので、その中から今回は、Ising/QUBO問題を取り上げて実行してみます。（blueqatは量子ゲートについての関数も充実していますが、今回は用いていません）
https://blueqat.readthedocs.io/ja/latest/ising.html
ここで取り上げているQUBOとは、二次非制約二項最適化(Quadratic unconstrained binary optimization)の略で、blueqatでは組合せ最適化問題のコスト関数をこの表現で表して解きます。
上記リンク先にある、「3個から任意の2個を選ぶ」という時には、以下のコスト関数を用います。
\begin{equation}
E(x) = (x_0 + x_1 + x_2 -2)^2
\end{equation}
上記式で、x0, x1, x2は{0, 1}の値を取り、いずれか2つが1の時に最小となる関数となっています。
以下この式をQUBOの形式にするために展開します。
\begin{align}
E(x)
&= x_0^2 + x_1^2 + x_2^2 + 2x_0 x_1 + 2x_1 x_2 + 2x_0 x_2 – 4x_0 – 4x_1 – 4x_2 + 4 \\
&=-3x_0 x_0 – 3x_1 x_1 – 3x_2 x_2 + 2x_0 x_1 + 2x_1 x_2 + 2x_2 x_0 + 4
\end{align}
上記式変形で、x∈{0,1}の時x2=xとなる事を用いています。
上記式より、この問題に対するQUBO行列が導出出来ます。
| x0 | x1 | x2 | |
| x0 | -3 | 2 | 2 |
| x1 | -3 | 2 | |
| x2 | -3 |
上記のQUBO行列をリストの形で与える事で、元あった「3個から任意の2個を選ぶ」問題を説くことが出来ます。
コードとしては、以下のようにファイルqubo.pyを作成します。
import blueqat.wq as wq # 最適化に用いるblueqat.wqモジュールをインポート a = wq.Opt() # wqのOptクラスとしてaを宣言 a.qubo = [[-3,2,2], [0,-3,2], [0,0,-3]] # a内のQUBOとして上記のQUBO行列を与える（デフォルトでは空のリスト[]となっている） answer = a.sa() # シミュレーテッドアニーリングした結果をanswerに渡す print(answer)
このプログラムでは、与えられたQUBOに対してシミュレーテッドアニーリングを用いて最適解を求めています。プログラム内では、QUBOをIsing模型に置き換えて計算がされています。QUBOコスト関数のxを、x=s+1/2として、s∈{-1/2, 1/2}で置き換える事で、Ising模型のハミルトニアンとして表現する事が可能です。ここで用いたE(x)のxをsで置き換えた関数（ハミルトニアン）E(s)は以下のようになります。
\begin{equation}
E(s) = 2s_0 s_1 + 2s_1 s_2 + 2s_2 s_0-s_0-s_1-s_2+1
\end{equation}
上記変換において、
\begin{equation}
s_i s_i =\frac{1}{4} \qquad (i = 0, 1, 2)
\end{equation}
を用いています。
このような変換は、使用時には特に意識する必要がなく、プログラム内で自動的に置き換えられます。
このプログラムを実行します。
$ python qubo.py
上記計算は3秒程度で終了し、例えば以下のように出力されます。
[0, 1, 1]
今回の問題では、[0, 1, 1], [1, 0, 1], [1, 1, 0]は当確率となるので、毎回結果が変わります。
上記コードでsa→sqaとする事で、量子アニーリングでのアニーリングも実行可能です。
ただし、answerとしては、トロッター数(※)分の結果（デフォルトでは8個）が出力され、また、{0, 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]]
※トロッター数：量子系を古典系と対応付ける鈴木-トロッター分解における分割数
4. 終わりに
ここではblueqatを用いたIsing/QUBO問題の簡単な計算例について計算しました。このような問題は、コスト関数を定義し、そこからQUBO行列を導出し、最適化を実行する、という手順で解く事が出来ます。一般的な問題についても{0, 1}の変数で表す事が出来れば、同様の方法で解くことが出来ます。
他の例としては、GitHubのBlueqat-tutorialsにいくつか掲載されていますので、これらをご参照ください。例えば、以下のものがあります。
https://github.com/Blueqat/Blueqat-tutorials/blob/1ccedf15a6de189dce4fc239ae7f9f729b60dc1f/tutorial-ja/307_exactcover_ja.ipynb