はじめに
量子コンピューターに興味を持ち、D-Waveという量子アニーリング型量子コンピューターの仕組みは勉強したのですが、いつまでもコンピューティングしていないのでそろそろコンピューティングしたいです。前提知識に乏しく、わりとつらいです。
すでにチュートリアルに関する記事は出ていますが、勉強のため、私もチュートリアルに取り組んでいこうと思います。
Wildqatとは
日本の量子コンピューティングベンチャー企業であるMDRさんが開発されている開発ツールで、
Wildqatはpythonをベースとしてイジングモデルという物理モデルを扱いながら、物理の知識がなくても計算を行うことのできる開発ツールです。
物理の知識がなくても計算を行うことのできる開発ツールとのことなのでこれを使ってコンピューティングしたいです。
チュートリアル
Wildqatはありがたいことに日本語でのチュートリアルが非常に充実しています。
チュートリアル1：QUBOにおける計算の基礎
QUBO(Quadratic unconstrained binary optimization)はイジングモデルへ変換可能な形式とのことです。
イジングモデルが
H = \sum_{ i \ne j}{J_{ij}\sigma_i \sigma_j} + \sum_i{h_i \sigma_i} \qquad \left( \sigma \in \left\{-1, +1\right\} \right)
で表され、QUBOが
H = \sum_{i,j} Q_{ij}q_i q_j \qquad \left( q \in \left\{0,1\right\} \right)
で表されるようです。
QUBOの方がビットと相性が良いらしいのですが、まだイマイチ実感できず。
ともかくチュートリアルを進めてみます。
import wildqat as wq
a = wq.opt()
a.qubo = [[4,-4,-4],[0,4,-4],[0,0,4]]
a.sa()
このチュートリアルではあらかじめ与えられたQUBOモデルをSA(シミュレーテッドアニーリング)で解いています。
つまり、
- インスタンスの準備
- QUBOの入力
- SAで計算
のステップでやれば良いということが分かりました。
チュートリアル2：QUBOで足し算を行う
楽しそう！
今回解きたい問題は、$$1 + 1 = x$$となるような $x$を求めます。
QUBOにおいて足し算は上記右辺から左辺を引いてその最小値を求めることに相当しますので、$$E = (x - 2)^2 $$というコスト関数ができます。
なるほど、$x = 2$となるとき、$E$が0になり、最小となるため、このコスト関数の最小値が今回の問題設定の解となるということですね。
こちらを展開すると、$$E = x^2 - 4x + 4$$という式が得られます。
わかります。
一方、$x$は量子ビットを使って、$$x = q_0 + 2q_1$$という二進数表記ができますので
いきなり分からなくなりました！
ええと、今回はチュートリアルなので量子ビット数をなるべく少なくするため、2量子ビットに設定しているということでしょうか。
今回のケースだと最小の解は2であることが明白なので、ビット数は少ないに越したことがないですね。
もし3量子ビット使いたい場合は、$$x = q_0 + 2q_1 + 4q_2$$で考えればよいと理解しました。
さらにこれを上記のコスト関数に代入すると、$$H = q_0^2 + 4q_0q_1 - 4q_0 + 4q_1^2 - 8q_1 + 4$$と展開されます。
わかります。
ここで、QUBOはバイナリ値$\{0,1\}$を取りますので、二乗の項はすべて指数がとれます。$$q_0^2 = q_0$$ $$q_1^2 = q_1$$より、$$H = -3q_0 + 4q_0q_1 - 4q_1 +4$$となります。
おーなるほど。
QUBOで問題を扱うと二乗の項は指数を取ることができるのですね。
となります。これを行列表記すると、下記のようになります。
a.qubo = [[-3,4],[0,-4]]
また分からなくなりました！
@okd46さんの記事を参考にすると、つまり、a.quboに代入する値は
{\begin{align*}
H &= \left(
\begin{array}{c}
q_0 & q_1
\end{array}
\right)
\left(
\begin{array}{cc}
a & b \\
c & d
\end{array}
\right)
\left(
\begin{array}{c}
q_0 \\
q_1
\end{array}
\right)
\end{align*}
}
の行列だということですね。そして展開された式は$$H = aq_0 + (b + c)q_0q_1 + dq_1$$となることから、$q_0q_1$を表現するための係数は$b$のみで良く、$c=0$としても問題ないと。
つまり、
{\begin{align*}
H &= \left(
\begin{array}{c}
q_0 & q_1
\end{array}
\right)
\left(
\begin{array}{cc}
a & b \\
0 & d
\end{array}
\right)
\left(
\begin{array}{c}
q_0 \\
q_1
\end{array}
\right)
\end{align*}
}
の行列式として扱えるということでしょうか。
3量子ビットとなった場合は、
{\begin{align*}
H &= \left(
\begin{array}{c}
q_0 & q_1 & q_2
\end{array}
\right)
\left(
\begin{array}{cc}
a & b & c \\
d & e & f \\
g & h & i \\
\end{array}
\right)
\left(
\begin{array}{c}
q_0 \\
q_1 \\
q_2
\end{array}
\right)
\end{align*}
}
という行列式ですが、展開すると$$H = aq_0 + eq_1 + iq_2 + (b+d)q_0q_1 + (c+g)q_0q_2 + (f+h)q_1q_2$$となり、$d=0$、$g=0$、$h=0$としても良いため、
{\begin{align*}
H &= \left(
\begin{array}{c}
q_0 & q_1 & q_2
\end{array}
\right)
\left(
\begin{array}{cc}
a & b & c \\
0 & e & f \\
0 & 0 & i \\
\end{array}
\right)
\left(
\begin{array}{c}
q_0 \\
q_1 \\
q_2
\end{array}
\right)
\end{align*}
}
という形式で表すことができるということですね！
なので今回の問題では、
{\begin{align*}
H &= \left(
\begin{array}{c}
q_0 & q_1
\end{array}
\right)
\left(
\begin{array}{cc}
-3 & 4 \\
0 & -4
\end{array}
\right)
\left(
\begin{array}{c}
q_0 \\
q_1
\end{array}
\right)
\end{align*}
}
と表すことができるため、
a.qubo = [[-3,4],[0,-4]]
という値を代入するということですね！
これをシミュレーテッドアニーリングで計算すると、
a.sa()
$[0, 1]$が得られるため、$x = q_0 + 2q_1$に代入すると$x = 2$という解が得られる！なるほど！！
おわりに
チュートリアルを2つやっただけですが、コスト関数さえ定義できればそこから任意の量子ビットでQUBOへ変換できることが分かりとても勉強になりました。
参考URL
https://quantum.fixstars.com/introduction_to_quantum_computer/quantum_annealing/ising_model/
https://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization
http://blog.mdrft.com/post/32
https://qiita.com/okd46/items/92f2855b37f79112e7c5