ブール代数を使ったイジングの多体問題の２体問題への分解

はじめに

最近は量子アニーリングやイジングモデルと呼ばれる問題を実装する必要があります。その中で、実はイジングモデルにおいて最近の量子コンピュータ関係が解けるのは２体問題、つまり量子ビット同士の掛け算が２個までの問題に限られています。

しかし世の中色々な問題はこの多体問題が出てくることがあります。そんな時にテクニックとして２体問題に分解する方法があります。今回はそのあたりを見ていきたいと思います。

ちなみに使用するマシンはD-Waveで紹介します。

参考文献

勉強会でも質問が多かったのが、下記のタンパク質折りたたみ問題に関するイジング実装で、
有名なのが2012年のハーバード大学のAlán Aspuru-Guzik先生から出ている下記の論文です。

Finding low-energy conformations of lattice protein models by quantum annealing
Alejandro Perdomo-Ortiz, Neil Dickson, Marshall Drew-Brook, Geordie Rose & Alán Aspuru-Guzik

他にも色々な資料がありますが、今回は上記の論文に出てきている通り、多体問題を分解して見たいと思います。

他の資料
Non-perturbative k-body to two-body commuting conversion Hamiltonians and
embedding problem instances into Ising spins
https://arxiv.org/pdf/0801.3800.pdf

使用するマシン

カナダD-Wave社のマシン。
https://www.dwavesys.com/

二体問題の解き方

簡単です。例えば下記のようなハミルトニアン（エネルギー関数）があった時には、そのままその係数をD-waveにかけられます。

H = q_0-q_0q_1

$q_0$ の係数1を磁場項に、 $q_0q_1$ の係数を相互作用項に作用させて計算するとすぐに答えがかえってきます。

三体問題はどうか？

では、三体問題という量子ビットが複数掛け算されているものはどうでしょうか？
相互作用項は二量子ビット同士の係数しかないので、そのままでは設定できません。

H = q_0-q_0q_1q_2

どうするのか？

その際に量子アニーリングマシン、イジングマシンの特性を利用して、ペナルティをつけます。
これらのマシンは数式の最小値を取るようになっているので、新しい余剰量子ビットを導入して、
その量子ビットに対して条件を最小値において（大概が0の場合）満たすように制約条件を付け加えます。

Supplementary Information: Finding low-energy conformations of lattice protein
models by quantum annealing

を参考として、下記の新しい量子ビットをつけ加えます。

q_1q_2 = q_3

という新しい量子ビットを導入して、これらの量子ビットの関係式を満たす場合に0になり、それ以外は+になる（マイナスになる場合は成り立たない）という新しいペナルティを作ることになります。

満たすべき条件は、

\delta(3q_3+q_1q_2-2q_1q_3-2q_2q_3)

というペナルティを導入すれば良いことになります。なので、例題は、

H = q_0-q_0q_1q_2=q_0-q_0q_3+\delta(3q_3+q_1q_2-2q_1q_3-2q_2q_3)

と分解できました。デルタはハイパーパラメータです。

確認方法

これらのペナルティ項を作るために何をすれば良いのか確認していきましょう。
多元連立方程式をつくって、適当に係数を決めていきたいと思います。

q_1q_2 = q_3

この式を満たす条件を考えて見ます。 $q_1,q_2,q_3$ の２次までの一般式について考えると、係数を $a_i$ とおいて、定数項をCとして、

H’ = a_1q_1+a_2q_2+a_3q_3+a_4q_1q_2+a_5q_1q_3+a_6q_2q_3+C

この式を下記の表を満たすように、 $a_i$ の係数を探していきます。

$q_1,q_2,q_3$ の関係性を保つ時にエネルギーが最小の0になるように設計し、その他は正の値になるようにします。

実際に成り立つのかD-Waveでやってみる

H = q_0-q_0q_1q_2=q_0-q_0q_3+\delta(3q_3+q_1q_2-2q_1q_3-2q_2q_3)

という式ですが、最小値を取るのは、 $q_i$ はバイナリなので、

の時になりそうです。 $\delta$ はハイパーパラメータなので、 $\delta = 0.5$ と置いてみて、

H = q_0-q_0q_3+1.5q_3+0.5q_1q_2-q_1q_3-q_2q_3

QUBOmatrixに

これを縦横4量子ビットずつのQUBOmatrixに置いてみると、

\begin{array} -&q_0&q_1&q_2&q_3\\ q_0& 1 & 0 & 0 & -1\\ q_1& & 0 & 0.5 & -1 \\ q_2& & & 0 & -1\\ q_3& & & & 1.5 \end{array}

となります。

QUBO変換でイジングへ

ここでQUBOmatrixをイジングへ変換します。

\begin{array} -&q_0&q_1&q_2&q_3\\ q_0& 0.25 & 0 & 0 & -0.25\\ q_1& & -0.125 & 0.125 & -0.25 \\ q_2& & & -0.125 & -0.25\\ q_3& & & & 0 \end{array}

そのままD-Waveにかけてみる

かけてみて、とりあえず100回計算を試行してみました。

いい感じでエネルギー基底状態の時に解がもとまっています。
ちなみに、0.125を設定しないといけない時に、設定の都合上0.13にまるまってしまっているので、
五番目の近い答えも求めるべき解でした。

ということで、簡単な立式でしたがうまく多体問題を分解してD-Waveで求まりました。