制限付きボルツマンマシンに対する経路積分モンテカルロ法の実験的評価

(1)

制限付きボルツマンマシンに対する

経路積分モンテカルロ法の実験的評価

Experimental Evaluation of Path-integral Quantum Monte Carlo

for Restricted Boltzman Machine

張亨碩

1∗

_{橋本朔弥}

1

_{平石秀史}

1

_{今井浩}

1

Hyungseok Chang

1

_{Sakuya Hashimoto}

1

_{Hidefumi Hiraishi}

1

_{Hiroshi Imai}

1

_{東京大学情報理工学系研究科コンピュータ科学専攻}

1

_{Department of Computer Science, IST, The University of Tokyo}

Abstract: 近年，計算機で解くことが要請される問題の多様化により，広範な問題に適用可能なメ タヒューリスティクスの構築と，それをデバイス実装した専用コンピュータが注目されている．その中で代表的なメタヒューリスティクスとしては，焼きなまし法（Simulated Annealing，SA）とその量子計算への拡張である量子焼きなまし法（Quantum Annealing, QA），さらにその経路積分モンテカルロ法による古典シミュレーションを行う Simulated Quantum Annealing, SQA がある． Crosson と Harrow は QA が SA を凌駕していたある種の問題について，SQA が QA に近い性能を達成することを示し，SQA が SA を指数時間倍で凌駕する場合があることを示した．一方で，SQA が他の広範な問題に対して，効率的に動作するかどうかについて，不明な点は多い．本研究では，深層学習で基礎的な構成要素として知られる制限付きボルツマンマシン RBM や，組合せ最適化問題の基礎的な問題である 3SAT のインスタンスに関して，SA と SQA の実験的比較を行った．結果，我々の設定の元では得られる解の精度および計算時間の両面で，RBM では問題サイズが大きくなるにつれ SQA のほうが SA より若干よい解を与えるが，3SAT においては，逆の傾向が見られ，二つの手法に大きな差はないという結果が得られた．人工知能研究の観点からは，RBM への QA, SQA の適用により深層学習が効率化できるかさらなる検討が必要である．

1 はじめに

量子計算とは，量子力学の原理による超並列性を用いることで，古典計算では困難な規模の計算を可能にすることが期待されいている計算パラダイムである．量子計算には様々なモデルが提案されており，最も知られているであろう量子回路モデル以外にも，多種多様な計算モデルが存在する．Kadowaki, Nishimori [5] によって提唱された量子焼きなまし法（Quantum Annealing, QA）は，量子計算モデルの中でも，最適化問題を高速に解く枠組みとして特に有望視されており，実際に D-wave により，量子アニーリングの枠組みに基づく小規模の量子コンピュータが実現されていることが報告されているなど，近年，大きな注目を集めている．量子焼きなまし法は，Kirkpatrick, Gelatt, Vecchi [6] によって提案された（古典）焼きなまし法（Simulated Annealing, SA）を量子並列性を用い拡張したもので，最適化問題，なかでも組合せ最適化問題を広範かつ高速に解くため ∗_{連絡先：東京大学情報理工学系研究科コンピュータ科学専攻} 東京都文京区本郷 7-3-1 E-mail: [email protected] のメタヒューリスティクスである．量子焼きなまし法は，古典焼きなまし法よりも高速に動作することが，いくつかの重要なケースに関して理論的に示されている．例えば，ハミルトニアンのエネルギーギャップが，問題 の入力サイズを n として 1 poly(n)程度である場合においては，量子焼きなまし法は，古典焼きなまし法よりも指数的に速く所望の解を計算することが知られている他，ある種類の目的関数に関しては，量子焼きなまし法の優越性が示されている．また，量子焼きなまし法が指数時間かかる問題の存在も知られている．一方，Crosson と Harrow [2] によって，これまで量子焼きなまし法の優位が知られていたハミング重みに関するある問題に関して，量子焼きなまし法と同等の計算速度を達成することを（古典計算の枠組みでの）メタヒューリスティクス・経路積分量子モンテカルロ法（Path-integral Quantum Monte Carlo）においても発見した．この手法は Simulated Quantum Annealing （SQA）と呼ばれる古典計算のメタヒューリスティクスの一つであり，経路積分を用いる過程で鈴木・Trotter 展開によって得られるハミルトニアンの分配関数の近

人工知能学会研究会資料 SIG-FPAI-B507-02

(2)

似値から，マルコフ連鎖モンテカルロ法によりランダムウォークを生成するという手法を用いることで量子焼きなまし法の挙動を古典的に模倣し得られる．以下では経路積分量子モンテカルロ法のことを Simulated Qnautm Annealing (SQA) と呼ぶことにする．前述のとおり，SQA は，量子的な計算過程を古典的に模倣したアルゴリズムである．そのため，量子焼きなまし法の古典焼きなまし法に対する優越性は，SQA が再現した通り，量子計算過程を古典的計算に巧みに還元することにより，解消可能なのではないかという問題意識が自然と得られる．Crosson と Harrow [2] の研究では SQA が QA に比べて，（ハミング重みに対応するような）特定の目的関数に関しては，SQA が QA の挙動を効率的に模倣することができることを示している一方で，より広範な関数に対して，SQA が QA と同等の計算能力を持ちうるのか，ひいては SQA が SA と比べて，真に効率的であるのかなどについては未だ分かっていない．そこで，本研究では，SA と SQA に関して，より広範な問題に関して実験的な評価を行った．実験に用いた問題は，深層学習の deep belief network の基礎的な構成要素である制限付きボルツマンマシン（Restricted Boltzmann Machine, RBM）と組合せ最適化問題の基礎的な問題である論理式の充足問題の節の数を 3 に限定した 3SAT のインスタンスを用いた．この実験の設定においては，SQA が SA に対して明らかな優位性を示す結果は得られなかった．具体的には，制限付きボルツマンマシンにおいては，SQA が若干良い解に至る傾向があったものの，有意な差とは見られず，また， 3SAT においては，SA の方が高速に，かつより高い頻度で元の問題を充足させたという結果が得られた．なお，我々の別実験では，基本的な組合せ最適化問題として知られる Max cut という問題を対象にした場合， SQA よりも SA のほうがより高速によい解を求めることができるといった結果も得られている．これらの結果は，SQA は特定の問題に対して，SA に対し高い能力をもつものの，一般の問題に対しては，優位ではないといったことを示唆していると考えられる．

2 実験の概要

2.1 SA と SQA の概要

SA と SQA はともに，ランダムウォークを用いて, 任 意の目的関数 f に関して大域最適解を求めるアルゴリ ズムである. ここでは f を最小化する問題として，両 アルゴリズムの概要を示す．また，両アルゴリズムは各々パラメータを持ち，これらのパラメータ調整次第でアルゴリズムの性能が大きく左右されることを注記しておく．

Simulated Annealing (SA)

パラメータ: T0, Tf 1. 解 S を選び現在の解 SC = S, 温度パラメー タ T = T0を設定する 2. 現在の解 S の近傍 SN を求める． 3. 確率 min (1, exp (f (SC)−f(SN) T )) で現在の解 SCを SN へ変更 4. 温度 T を, 決められたスケジュールに沿って 減少させる 5. 温度が T < Tf でないならば 2 へ戻る

Simulated Quantum Annealing (SQA)

パラメータ: G0, Gf, P , T 1. 解 S を一つ選び， G = G0と設定する 2. S 複製しスライス Si (i∈ {1, ..., P }) を作成 する．各スライスを現在の解 SiC (i∈ {1, ...P, }) とする 3. 各スライス SiCの近傍 SiNを求める. 4. 確率 min (1, exp (f (SiC)−f(SiN)+J p P T )) で, 現 在の解 SiCを SiNへ変更 (Jpは境界条件と 呼ばれる G によって定まる値) 5. 各 SiCの近傍 SiNを求める.

6. 確率 min (1, exp (∑Pi=1f (SiC)−f(SiN)

P T )) で， すべての i において，SiCから SiN へ変更する 7. G を決められたスケジュールに従って減少さ せる 8. G < Gfでないならば 2 へ戻る T と G は焼きなまし法に特有のパラメータである． もしこれらのパラメータが大きい場合は，悪い値を持つ解への遷移が盛んに起こりうる. 一方でパラメータが小さい場合には, ほとんどの遷移は良い値を持つ解への遷移である. これらのパラメータを適切に設定することで，各アルゴリズムは局所最適解にとらわれ続けることなく，大域最適解に至ることができる．SA においては，遷移が起きる確率は現在の解と候補解の差によって決定される一方，SQA においては，解同士の差に加 え境界条件と呼ばれる定数 Jpによっても決まる．詳しくは 2.2 を参照のこと.

(3)

2.2 実験手法

本実験においてはイジング模型が重要な役割を占める．イジング模型は元来，統計力学において強磁性をモデル化するために導入されたものであり，後年になって計算機科学や離散数学においてもその重要性が認識されるようになった．その理由の一つとして，様々な組合せ最適化問題がイジング模型の形で表現することが挙げられる．QA とは本質的にはイジング模型の基底状態（つまり最小エネルギー状態をもつ解）を計算するアルゴリズムである．QA を用いて組合せ最適化問題を解く量子コンピュータは，各問題を一旦イジング模型の形に変換した上で計算を行う．このことからも分かるとおり，イジング模型は量子計算においても大きな重要性を持っている．さらに，深層学習の基礎的な構成要素である制限付きボルツマンマシンや，組合せ最適化問題で NP-Hard と呼ばれる計算困難な問題の最も基礎的なものである Max cut などといった問題は簡単な変換を行うことで，イジング模型上で基底状態を求める問題と等価であることが知られている．我々の実験においては，制限付きボルツマンマシンを中心に様々な組合せ最適化問題に関して，SA と SQA の性能評価を統一的に行うために，各問題をイジング模型の基底状態を求める問題として変換した上で SA と SQA を適用し性能評価を行う．また SA と SQA の実装に関しては，Hazard [8] によるコードに調整を加えたものを用いる．次にイジング模型に関して簡単な説明を行う．イジング模型とは点と枝に実数値の重みが割り当てられて いるような無向グラフである．n 点からなる無向グラ フに対し，点 i に hi，枝{i, j} に J_{i,j}の重みが割り当てられているとする．イジング模型上におけるスピンとは各点に割り当てられる二値からなる状態のこと であり，点 i に対して σi ∈ {−1, 1} が付与される．与 えられたスピンに対し，そのスピンに対応するエネル ギー E が次の式で与えられる．イジング模型における 最小化問題とは，このエネルギーが最小になるようなスピンを見つける問題のことである． E = n ∑ i,j Jijσiσj+ ∑ i=1 hiσi k 番目のスライスにおける境界条件は次のように表 すことができる． Jp=−P T log (tanh ( G

P T))σi,k(σi,k−1+ σi,k+1)

ここで，k 番目のスライスにおける点 i のスピンを σi,k と表し，また σi,0= σi,P +1と定める．この境界条件の値は，イジング模型の分配関数の近似に由来する値であることを注記しておく．また，本アルゴリズムにおいては，近傍の解を探すのに 1 ビットのビット反転を 用い，また T と G を減少させるスケジュールとしては， s をある定数とし，A = _1+s1 A (A = T or G) を用いる． SQA にはスライス全体の遷移を行うフェーズと，スライス内部での遷移を行うフェーズがある．そのため， SA と SQA の近傍の探索・解の更新の回数を公平に同期させるため，SA に関しては，下記のようなものとする．

Simulated Annealing (SA)

パラメータ: T0, Tf and P 1. S 複製しスライス Si (i∈ {1, ..., P }) を作成 する．各スライスを現在の解 SiC (i∈ {1, ..., P }) とする 2. 各スライス SiCの近傍 SiNを求める. 3. 確率 min (1, exp (f (SiC)−f(SiN) T )) で, 現在の 解 SiCを SiN へ変更 4. 各 SiCの近傍 SiNを求める. 5. 確率 min (1, exp ( ∑P i=1f (SiC)−f(SiN) T )) で， すべての i において SiCから SiNへ変更する 6. T を決められたスケジュールに従って減少さ せる 7. T < Tfでないならば 2 へ戻る

2.3 実験に用いたデータ

本実験では，制限付きボルツマンマシンにおける SA と SQA の比較を行った．2.2 で述べたとおり，制限付きボルツマンマシン（Restricted Boltzmann Machine）と 3SAT のインスタンスをイジング模型へと変換し，それに対して SA と SQA を適用することで性能評価を行った. 制限付きボルツマンマシン（RBM）は点・枝重みつきの無向二部グラフ上で定義されるエネルギー最小化 問題である．まず点 i に対して θi，枝{i, j} に対して w_{i,j}の重みが各々与えられる．さらに，イジング模 型の点に割り当てられるスピンと同様に，点 i に対し て状態 si∈ {0, 1} が与えられる．状態が与えられた時 に，そのエネルギーは下記のように与えらえれる． E =− n ∑ i,j wi,jsisj− n ∑ i θisi 制限付きボルツマンマシンからイジング模型のインスタンスへの変換は次のように行う．まず，グラフの枝

(4)

の重みを全て半分にする．そして，グラフに点 v を追 加し，元のグラフの k× k の各点と新しく追加した点 v との間に枝を追加し，枝_{{v, i} の重みを}θi 2 とする．最後に，点の重みを全て 0 とする．こうして得られたグ ラフを点数 2k + 1 のイジング模型として基底状態のエ ネルギーを求めれば，それは制限付きボルツマンマシンの最適値に，制限付きボルツマンマシンの点・枝の重みの総和分だけ加えたものと一致することが分かる．実験に用いる制限付きボルツマンマシンのインスタ ンスに関しては，次のように生成を行った．まず k = 50, 100, 200, 300, 400 に対して，k×k 二部グラフで，枝 数に関しては，k2 4, k2 2 および 3k2 4 のものを生成した．枝の重みに関しては_{−1 か 1，点の重みに関しても −1} か 1 を，それぞれ1 2 の確率で割り当てる．このように生成した制限付きボルツマンマシンのインスタンスに対しては，その最適解の上限が Yasuda [10] によって SDPA (Semidefinite Programming Algorithms) [3] を用いて求められている. また，今回扱った 3SAT についての変換についても触れる．変換をする際は [9] を参考にした．[9] では，3SAT を Max cut に変換する方法が書かれている．ただ，変換後の問題が簡単になるように，この変換の一部を変更した．[9] は，NAE SAT と呼ばれる，ある節を充足するためには，節に含まれるリテラルのうち，真となるものだけでなく，偽となるものも一つ以上必要とするような

問題を使う．これにより，3SAT→NAE 4SAT→NAE

3SAT→ Max cut と変換している．NAE 3SAT から

Max cut 以外は [9] に使われている方法を用いているので，ここでは NAE 3SAT から Max cut への変換のみを説明する．

NAE 3SAT から Max cut への，[9] での変換方法を 説明する．まず NAE 3SAT の，各論理変数 x に対し， x と¬x をグラフの点とする．そして，点を真となる論 理変数の集合を S とすると，S のカットが NAE 3SAT の充足節数に対応するように枝重みを振る．具体的に は，頂点 x と¬x は同時に真となることがないため，こ の二つの頂点に辺を張り，重み M を与える．また，各 節において，充足されるには正となるリテラルの数と，負となるリテラルの数が，片方が 2 でもう片方が 1 となることに限られる．そこで，節のリテラル三つを重み 1 の辺で結んだ三角形を考える．この時，充足される時は，カットの重みが 2 となるが，充足されない時は必ず 0 となる．これらを用いると，NAE 3SAT の論 理変数の数を k 個，節を c 個とすると，最大カットが， kM + 2c となる．そして，これが満たすカットが存在 する時，元の NAE 3SAT が満たされる．一方，我々は，この際，頂点数が NAE 3SAT の論理変数の 2 倍となってしまうことを避けるようにした．具体的には，[9] を用いて，グラフを作成したのちに，論 理変数 x に対応する頂点 x と¬x の間の辺を縮約し，x と_{¬x 頂点を単一の頂点にまとめた．その際に，頂点} ¬x に接続する辺の符号は反転させた．このような操作 を行うと，正と負の論理変数の両方をリテラルとして持つ節は充足時に 0 の重みのカットを持ち，非充足時に-2 の重みのカットを持つ．一方，全てが正または負の論理変数をリテラルとして持つ節は充足時に重み 2 のカットを，非充足時には重み 0 のカットを持つ． このことから，NAE 3SAT の節が m 個真になるこ とと，カットのサイズが 2 (m− (正リテラルと負リテラル両方を含む節数)) であることが等価となる．m を NAE 3SAT の全ての 節数とすることで，最大カット問題への変換ができる 3SAT のインスタンスに関しては，[4] にあるものを用いた．全て充足可能なものを用いた．そのため，最適解が全てわかっている．一様ランダムのものと，バックボーンと呼ばれるものが付いている一様ランダムのものを用いた．ここで，バックボーンとはリテラルの集合のことで，その集合の要素が全て真であるなら，その SAT は必ず充足されるという条件を満たす集合のことである．また，ランダムな 3SAT においては [1] より， #{ 節 } = 4.26 × #{ 変数 } の時，最も難しくなるこ とが知られている．今回は，難しいインスタンスで比較を行うことが考えた．なので，扱ったインスタンスは全て，この式に近いような比率の変数，節数のものを用いた．インスタンスの論理変数の数は 20，50，10， 150，200，250，600，1000，2000 のものを扱った．また，バックボーン付きのインスタンスは，論理変数の数が 100 で，バックボーンが 10，30，50，70，90 のものを扱った．

2.4 実験評価方法と結果

SQA における 3∼6，および SA における 2∼4 のまとまりを 1 ステップと呼ぶことにする．SA と SQA の速度評価は，ステップ数の比較によって行うこととする． SQA のパラメータに関して P = 1, 40, 80 ととり，また T に関しては P T = 1 となるように設定する．SA のパ ラメータ T に関しては，SQA の G と一致させる．こ のような設定のもとで得られた実験結果は表 1 に示す．

3 まとめ

本研究では，制限付きボルツマンマシンや 3SAT という問題に対して，古典計算におけるメタヒューリスティクス手法である SA と SQA の比較を行った．得られた解の精度に関しては，若干の差は観察されたが，本質的に大きな差があるとはいえない程度であると思われる．さらには，3SAT に関しては，イジング模型の

(5)

表 1: 制限付きボルツマンマシンと 3SAT に関する SA と SQA の性能比較. LU は最後に解の更新が行われたステップ数を表す．最適値を達成してる箇所は太字で示す．# が付けられている値は，[10] で示されている上界と一致しているもの. 実験環境は，Linux server, CPU: Intel(R) Xeon(R) CPU X5675 3.07GHz, Memory: 300GBytes

Problem n m Opt SA SQA SA-SQA Total steps Ave Best LU Ave Best LU Ave Best

RBM 101 650 -276 -271.6 -276.0 7484 -271.2 -276.0 887 -0.4 0.0 3× 105 with P = 1 101 1300 -450.43# -378.0 -384.0 3680 -382.4 -384.0 5937 4.4 0.0 3× 105 101 1950 -544.8# -460.8 -470.0 1871 -467.2 -470.0 5928 6.4 0.0 3× 105 201 2550 -887.95# _-723.6 _-746.0 ₇₈₂₅ _-728.0 _-740.0 ₂₁₅₁₀ _4.4 _-6.0 ₃_{× 10}5 201 5100 -1252.2# _-1013.6 _-1034.0 ₇₁₆₀ _-1013.2 _-1028.0 ₁₄₂₄₅ _-0.4 _-6.0 ₃_{× 10}5 201 7650 -1578.5# -1274.4 -1294.0 5740 -1292.4 -1302.0 20473 18.0 8.0 3× 105 401 10100 -2591.3# -2038.0 -2116.0 16742 -2050.0 -2128.0 22916 12.0 12.0 3× 105 401 20200 -3673.5# -2842.2 -2878.0 21906 -2892.8 -2952.0 37810 50.4 74.0 3× 105 401 30300 -4540.8# -3511.6 -3546.0 15585 -3612.8 -3704.0 34050 101.2 158.0 3× 105 601 22650 -4810.5# _-3690.4 _-3826.0 ₁₇₆₉₆ _-3668.8 _-3730.0 ₂₁₂₉₄ _-21.6 _-96.0 ₃_{× 10}5 601 45300 -6843.3# -5241.6 -5374.0 10747 -5326.8 -5384.0 61842 85.2 10.0 3× 105 601 67950 -8400.1# -6335.6 -6508.0 14373 -6540.0 -6614.0 40669 204.4 106.0 3× 105 801 40200 -7500.6# -5566.4 -5640.0 10797 -5650.4 -5692.0 21869 84.0 52.0 3× 105 801 80400 -10706.7# -8016.4 -8096.0 17110 -8252.0 -8380.0 40180 235.6 284.0 3× 105 801 120600 -13038.5# -9756.8 -10026.0 14302 -9989.6 -10270.0 56377 232.8 244.0 3× 105 RBM 101 650 -276 -276 -276 3204 -276 -276 1059 0 0 3× 105 with P = 40 101 1300 -450.43# -384 -384 1815 -384 -384 862 0 0 3× 105 101 1950 -544.8# -470 -470 681 -470 -470 604 0 0 3× 105 201 2550 -887.95# -746.4 -748 5339 -743.6 -748 11536 -2.8 0 3× 105 201 5100 -1252.2# _-1034.8 _-1040 ₁₄₄₂₁ _-1038.8 _-1042 ₇₅₂₃ ₄ ₂ ₃_{× 10}5 201 7650 -1578.5# -1301.6 -1306 12047 -1302 -1302 2301 0.4 -4 3× 105 401 10100 -2591.3# -2085.6 -2118 18927 -2102.8 -2116 23352 17.2 -2 3× 105 401 20200 -3673.5# -2910.8 -2930 13250 -2936.8 -2946 52357 26 16 3× 105 401 30300 -4540.8# -3592 -3626 17047 -3694.8 -3718 83655 102.8 92 3× 105 601 22650 -4810.5# _-3755.6 _-3790 ₁₄₁₆₇ _-3799.2 _-3822 ₄₅₁₀₃ _43.6 ₃₂ ₃_{× 10}5 601 45300 -6843.3# _-5338.8 _-5384 ₁₅₈₅₅ _-5419.6 _-5452 ₃₇₉₁₅ _80.8 ₆₈ ₃_{× 10}5 601 67950 -8400.1# -6528.4 -6572 28096 -6573.6 -6608 166590 45.2 36 3× 105 801 40200 -7500.6# -5786.8 -5866 27505 -5792.4 -5810 123116 5.6 -56 3× 105 801 80400 -10706.7# -8218 -8286 49513 -8355.2 -8504 177883 137.2 218 3× 105 801 120600 -13038.5# -10078 -10184 41759 -10136 -10178 118568 58 -6 3× 105 RBM 101 650 -276 -276.0 -276.0 2327 -276.0 -276.0 719 0.0 0.0 3× 105 with P = 80 101 1300 -450.43# -384.0 -384.0 1403 -384.0 -384.0 968 0.0 0.0 3× 105 101 1950 -544.8# -470.0 -470.0 780 -470.0 -470.0 593 0.0 0.0 3× 105 201 2550 -887.95# -747.6 -748.0 6153 -747.2 -748.0 7009 -0.4 0.0 3× 105 201 5100 -1252.2# _-1036.8 _-1042.0 ₇₈₂₇ _-1040.0 _-1042.0 ₄₄₁₃ _3.2 _0.0 ₃_{× 10}5 201 7650 -1578.5# _-1302.0 _-1306.0 ₉₅₉₇ _-1304.4 _-1306.0 ₄₇₈₉₁ _2.4 _0.0 ₃_{× 10}5 401 10100 -2591.3# -2120.0 -2130.0 10591 -2116.8 -2132.0 214375 -3.2 2.0 3× 105 401 20200 -3673.5# -2930.4 -2948.0 20682 -2943.6 -2966.0 21696 13.2 18.0 3× 105 401 30300 -4540.8# -3627.2 -3708.0 18296 -3718.0 -3734.0 93866 90.8 26.0 3× 105 601 22650 -4810.5# -3790.4 -3852.0 19956 -3802.8 -3816.0 16322 12.4 -36.0 3× 105 601 45300 -6843.3# _-5381.2 _-5454.0 ₂₈₉₄₈ _-5422.8 _-5464.0 ₂₇₀₈₄₉ _41.6 _10.0 ₃_{× 10}5 601 67950 -8400.1# -6578.4 -6698.0 35514 -6621.6 -6694.0 265910 43.2 -4.0 3× 105 801 40200 -7500.6# -5828.8 -5870.0 63689 -5846.4 -5884.0 171317 17.6 14.0 3× 105 801 80400 -10706.7# -8292.4 -8386.0 57013 -8397.2 -8432.0 162629 104.8 46.0 3× 105 801 120600 -13038.5# -10070.8 -10158.0 65049 -10124.4 -10168.0 257695 53.6 10.0 3× 105 3SAT 112 450 -34 -34.0 -34.0 9870 -34.0 -34.0 2084 0.0 0.0 3× 105 (Uniform Random) 269 1114 -108 -107.2 -108.0 225443 -105.2 -106.0 69766 -2.0 -2.0 1× 106 with P = 80 531 2206 -222 -220.8 -222.0 758315 -217.6 -220.0 82825 -3.2 -2.0 1× 106 796 3323 -320 -319.6 -320.0 251528 -313.2 -316.0 235527 -6.4 -4.0 1× 106 1061 4435 -460 -455.6 -456.0 376690 -448.8 -452.0 321052 -6.8 -4.0 1× 106 1316 5494 -578 -574.0 -576.0 932288 -562.4 -572.0 952095 -11.6 -4.0 1× 106 3151 13196 -1322 -1303.2 -1304.0 2144382 -1267.2 -1276.0 2488531 -36.0 -28.0 3× 106 5251 22037 -2064 -2017.6 -2026.0 2507788 -1965.6 -1978.0 2355012 -52.0 -48.0 3× 106 10501 44068 -4352 -4222.4 -4236.0 2975762 -4054.4 -4140.0 2833100 -168.0 -96.0 3× 106 (Backbone Random) 519 2113 -230 -228.8 -230.0 263483 -228.4 -230.0 475970 -0.4 0.0 1× 106 519 2120 -192 -191.6 -192.0 350875 -185.6 -188.0 639152 -6.0 -4.0 1× 106 519 2120 -176 -174.0 -174.0 80019 -170.4 -174.0 107696 -3.6 0.0 1× 106 519 2115 -212 -210.8 -212.0 520573 -208.4 -210.0 76716 -2.4 -2.0 1× 106 519 2114 -210 -208.8 -210.0 689922 -203.2 -206.0 91054 -5.6 -4.0 1× 106

(6)

解としての差は若干であったが，SA の方が SQA よりも多くの問題で最適解に達することができ，元の問題を充足させる解を見つけた．. また本稿では，掲載しなかったが，制限付きボルツマンマシン以外にも多様な組合せ最適化問題に関し，SA と SQA の実験的性能評価を行っている. それによると，イジング模型とボルツマンマシンと等価な問題として知られる，グラフ上の Max cut を求める問題に関して，グラフの平面性を仮定すると，SA の方が高精度の解が得られることが実験的に確認でき，また，厳密計算は計算困難だが高速な近似計算手法が存在する問題である頂点被覆に関しても SQA のほうが SA よりも効率的であるという結果が得られた. 注目する点として挙げられるのは，SQA と SA の性能は，問題が定義されるグラフの性質によって左右される可能性があることである. 今回の実験結果から，制限付きボルツマンマシンのように二部グラフ上での問題に関しては SA, SQA のふるまいをさらに実際の深層学習でのパラメタを用いてさらなる実験を行うことが望まれる．平面性を満たすようなグラフに関する計算は，SQA の方が高速であるという可能性が検討される．SQA と SA に関して各々が得意な入力インスタンスに関して，本実験結果を元に理論的に解析することが今後の検討課題として挙げられる．

謝辞

第 3,4 著者による本研究は JSPS 科研費 JP15H01677, JP16K12392, JP17K12639 の助成を受けたものである．

参考文献

[1] P. Cheeseman and B. Kanefsky, and William M. Tay-lor: Where the Really Hard Problems Are, The 12th

International Joint Conference on Artificial Intelli-gence, Vol. 91, pp. 331–337 (1991)

[2] E. Crosson and Aram W. Harrow: Simulated Quan-tum Annealing Can Be Exponentially Faster than Classical Simulated Annealing, 57th Annual

Sympo-sium on Foundations of Computer Science, pp. 714–

723 (2016)

[3] K. Fujisawa, M. Fukuda, Y. Futakata, K. Kobayashi, M. Kojima, K. Nakata, M. Nakata, M. Yamashita: SDPA (Semidefinite Programming Algorithms) Oﬃ-cial Page, http://sdpa.sourceforge.net/

[4] H. H. Hoos and T. St¨utzle: SATLIB - Benchmark

Problems, http://www.cs.ubc.ca/˜hoos/SATLIB/ benchm.html, Last Updated: 1st May 2011

[5] T. Kadowaki and H. Nishimori: Quantum Annealing in the Transverse Ising model, Physical Review E, Vol. 58, No. 5, pp. 5355 (1998)

[6] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi: Opti-mization by Simulated Annealing, Science, Vol. 220, No. 4598, pp. 671–680 (1983)

[7] F. Rendl, G. Rinaldi and A. Wiegele: A Branch and Bound Algorithm for Max-Cut Based on Combin-ing Semidefinite and Polyhedral Relaxations,

nterna-tional Conference on Integer Programming and Com-binatorial Optimization, pp. 295–309 (2007)

[8] E. Savard: Quantum Monte Carlo Code in Github, https://github.com/ezrasavard/qmc, Last Visited: 3rd February 2017

[9] D. Steurer: Reduction from 3SAT to max cut, lec-ture notes, Introduction to Analysis of Algorithms CS4820 Cornell University, march 2014.

[10] S. Yasuda: Analyses of Modern RBMs: Expressive-ness in Selective Settings and Benchmark Tests on Relaxation, Master Thesis, Department of Computer Science, the University of Tokyo (2017)

制限付きボルツマンマシンに対する経路積分モンテカルロ法の実験的評価