アニーリング多体相互作用シミュレータを作ってみた。

はじめに

量子アニーリングを解いている際に問題になるのは、多体相互作用と呼ばれる量子ビットが３つ以上かけ合わさっている状態で、実機の量子アニーリングマシンやシミュレータは二次元や三次元で実装されることが普通なので、２量子ビットの掛け算でしか表現できません。そのため、組合せ最適化問題をイジングモデルに落とし込んでもブール代数などの分解手法を利用してせっかくマッピングした問題を新しいハイパーパラメータと共に分解して無駄な労力を消費します。

また、量子ゲート方式の断熱量子計算の量子シミュレーションは時間発展シミュレーションを利用し、多体相互作用を解けますが、量子シミュレーションのステップ数が必要となる上、現在はNISQと呼ばれるエラーありの中規模マシンのため、量子変分原理を利用したハイブリッド方式が主流となっており、計算時間がとてもかかります。

組合せ最適化問題を特には量子ゲート方式のように多体相互作用を解きたいものですが、量子アニーリングやシミュレーテッドアニーリングのイジングマシンは２体相互作用メインの実装のため利点が活かせません。

そこで今回は単純にそのような状況に新しい視点を入れるために、多体相互作用シミュレータを実装して試してみたいと思います。
##　早速例題
通常のハミルトニアンはコスト関数の形で書かれます。通常２体相互作用のハミルトニアンは、 $h_i$ と $J_{ij}$ を利用して、

H = -\sum h_i q_i- \sum J_{ij} q_i q_j

のように量子ビットの局所磁場と相互作用の組み合わせで評価されます。例えば、

H = q_0 + 2q_0q_1

のような式があった場合、 $q_0,q_1$ の組み合わせは離散値で{-1,+1}を取るとして、{-1,-1},{-1,+1},{+1,-1},{+1,+1}の４通りで表現され、それぞれの場合のコストは、

H_a = -1+2 = 1\\\ H_b = -1-2=-3\\\ H_c=1-2=-1\\\ H_d=1+2=3

となり、 $q_0=-1,q_1=+1$ の時に最小のエネルギー-3を取ることがわかります。こちらをアニーリングで解く際には、とりあえず簡単のためにシミュレーテッドアニーリングと呼ばれる温度を利用した計算を利用してみます。

シミュレーテッドアニーリングはモンテカルロ法と呼ばれる乱数を利用して、ある関数に乱数から得られた値を適用することで状態を変化させるかどうかを評価しながら答えをサンプリングしていく手法で、現在のコンピュータで比較的高速にシミュレートすることができます。ここではモンテカルロ法にフリップ判定にメトロポリス法を使ってみます。

pythonで試しに実装してみると、

import numpy as np

q = np.random.choice([-1,1],2)
T = 5
J = np.array([[1,2],[2,0]])

while T>0.02:
  x_list = np.random.randint(0, 2, 1000)
  for x in x_list:
    q2 = np.ones(2)*q[x]
    q2[x] = 1
    dE = -2*sum(q*q2*J[:,x])
    
    if np.exp(-dE/T) > np.random.random_sample():
      q[x] *= -1
  T *= 0.99
  
print(q)

#[-1  1]

[-1  1]

-1と+1の答えが出ました。立式をしてアニーリングをすることで答えを出せます。

多体相互作用の問題

今度はこれを応用して、別の問題を解いてみます。問題は素因数分解の問題です。

問題の分解が必要になりますが、今回はこれを分解せずにできるかどうかやってみます。使うハミルトニアンは下記の通りです。定数項は無視しても大丈夫です。

H = 128q_0q_1q_2 + 16q_0q_1 - 56q_0q_2 - 52q_0 - 48q_1q_2 - 96q_1 - 52q_2 + 196

import numpy as np
import copy

q = np.random.choice([0,1],3)
T = 5

while T>0.02:
  x_list = np.random.randint(0, 3, 1000)
  for x in x_list:
    q2 = copy.copy(q)
    q2[x] = 1-q[x]
    dE = 128*(q2[0]*q2[1]*q2[2]-q[0]*q[1]*q[2]) +16*(q2[0]*q2[1]-q[0]*q[1]) -56*(q2[0]*q2[2]-q[0]*q[2]) -48*(q2[1]*q2[2]-q[1]*q[2]) -52*(q2[0]-q[0]) -96*(q2[1]-q[1]) - 52*(q2[2]-q[2])
    if np.exp(-dE/T) > np.random.random_sample():
      q[x] = 1-q[x]
  T *= 0.99

print(q)

#[0,1,1]

[0 1 1]

このように0,1,1のように正しい答えが出ました。もっと大きな問題でも動くのでしょうか。時間がある時にやってみたいと思います。

アニーリング多体相互作用シミュレータを作ってみた。

Yuichiro Minato

はじめに

多体相互作用の問題