解精度の比較

表5.1: ハミルトニアンのパラメータ設定

モデル Jij ∆ij

強磁性Potts^モデル +1 0

反強磁性Potts^モデル -1 0

Potts^{グラスモデル} +1(50%) or -1(50%) 0

Pottsゲージグラスモデル -1 0(50%) or +1(25%) or -1(25%)

;ĂͿȴ_ŝũсϬ䛾ሙྜ

S_i S_j

x_1i x_2i x_3i x_4i

x_1j x_2j x_3j x_4j

;ďͿȴ_ŝũснϭ䛾ሙྜ ;ĐͿȴ_ŝũсͲϭ䛾ሙྜ

J_ij J_ij J_ij J_ij

S_i S_j

x_1i x_2i x_3i x_4i

x_1j x_2j x_3j x_4j J_ij

J_ij J_ij J_ij

S_i S_j

x_1i x_2i x_3i x_4i

x_1j x_2j x_3j x_4j J_ij

J_ij J_ij J_ij

図5.7: 隣接する整数変数に割当てられたブール変数間の相互作用

となる．ここで，第二項はone-hot制約に起因するペナルティ項であり，式(5.9)^と式(5.10) の基底状態を一致させるためにはλを十分大きな正の値に設定しなければならない．隣接 する整数変数間の相互作用が，one-hot表示でどのように表現されるかを示したのが図5.7 である．ブール変数間の相互作用の強さは全てJ_ij で与えられるが，∆_ijの値に依存して 相互作用するブール変数のペアが異なる．

今回の評価で実行した最適化処理を図5.8に示す．部分問題への分割方法の違いによる 解精度への影響を確認するため，部分問題をランダム分割，整数分割，2^値分割の3^つの 方法で抜き出して比較する．ここで，ランダム分割ではone-hot制約の構造を無視して，

前章の部分問題埋め込みアルゴリズムを直接適用する．部分問題はD-Wave^{マシンを用} いて最適化する．D-Waveマシンに1000個の近似解を出力させ，部分問題の変数は最も エネルギーの低い解の値に更新される．ここで，D-Waveマシンの出力は近似解であり，

マシン内部の熱ノイズ等の影響も受けてone-hot制約を満たさない解や，局所最適解から ズレた解が出力される可能性があることに注意が必要である．そこで，本評価では古典 コンピュータによる事後処理として制約の修復と山登り法による極小化を行う．制約の修 復では，one-hot制約を破っているブール変数{xqi}q=1,2,3,4を整数変数単位で抜き出し，

one-hot制約を満たす組合せの中でエネルギーを最も小さくするものに更新する．この処

理をone-hot制約を破っている全てのブール変数{x_qi}q=1,2,3,4に対して実行し，D-Wave 出力の近傍にある許容解を作り出す．その後，山登り法による極小化では整数変数S_iを ランダムに1つ選択し，エネルギーを最も小さくする値にSiを更新する．全ての整数変 数に対して，Siの更新によるエネルギー変化が0以上になった時点で山登り法による改良 が終了する．最後に，最適化処理の中で得られた最もエネルギーの低い解を記憶して，上 記の処理を繰り返す．

評価条件は表5.2に示した通りである（λの設定理由に関しては付録.Aを参照）．Potts グラスモデルとPottsゲージグラスモデルに関しては，それぞれ表5.1に示した確率に従っ て{J_ij}^と{∆_ij}^{の実現値が異なる}8個の問題を生成して平均を取る．各インスタンス {Jij},{∆ij}^{と初期条件}σinitに対して，D-Waveマシンによる部分問題の最適化がNopt回 終了した時点でのエネルギーをE(Nopt,{Jij},{∆ij},σinit)とおいたとき，各モデルに対

䝷䞁䝎䝮ศ๭

ᩚᩘศ๭

Ϯ್ศ๭

ϯḟඖWŽƚƚƐ䝰䝕䝹

ϭϬdžϭϬdžϭϬኚᩘ 㒊ศၥ㢟䛾᭱㐺໬

1,000ಶ䛾ゎ 䜢ฟຊ

䜶䝛䝹䜼䞊᭱ᑠ䛾

᭱Ⰻゎ䛾᭦᪂ ᒣⓏ䜚ἲ ไ⣙䛾ಟ᚟ ゎ䜢᥇⏝

図5.8: 解精度の評価方法 表5.2: ^評価条件

モデル インスタンスの数（N_problem^{） 初期条件の数（}Ninit） λ

強磁性Potts^モデル 1 16 3.3

反強磁性Potts^モデル 1 16 1.0

Pottsグラスモデル 8 8 3.3

Pottsゲージグラスモデル 8 8 3.3

して

E_ave(N_opt)≡ 1 NproblemNinit

∑

{Jij}

∑

{∆ij}

∑

σinit

E(N_opt,{J_ij},{∆_ij},σ_init), (5.11) を評価する．ここで，2値分割を用いた場合には，部分問題がone-hot^{制約のペナルティ} 項を含まないのでλを決める必要はない．表5.2^のλはランダム分割と整数分割を用いた 場合に利用する．

強磁性Pottsモデルと反強磁性Pottsモデルに対する評価結果を図5.9と5.10に示す．

横軸はD-Waveマシンによる部分問題の最適化を繰り返した回数を表し，N_integerは整数

変数の数（Ninteger = 1,000)^{を表す．強磁性}Pottsモデルの基底エネルギーは-3^であり，

反強磁性Pottsモデルの基底エネルギーは0である．これらのモデルでは予想に反して，

ランダム分割と整数分割の解精度がほぼ同等となっている．また，2^{値分割に関しては，}

反強磁性Pottsモデルではランダム分割に対して少ない繰り返し回数で最適解が得られて

いるが，強磁性Pottsモデルではランダム分割に対して解精度が悪化している．図5.11と

5.12はPottsグラスモデルとPottsゲージグラスモデルに対する評価結果である．これら

-3.2 -3.0 -2.8 -2.6 -2.4 -2.2 -2.0

1 10 100 1000

Optimal value Eave(Nopt) / Ninteger

The number of iterations: N_opt Random partition Integer partition Binary partition

図 5.9: 強磁性Pottsモデルに対する解精度の評価結果

のモデルでは，ランダム分割に対して整数分割と2値分割の解精度が良くなるという期待 通りの結果が得られている．また，その中でも2値分割の解精度が最も良い．ここでの評 価結果に対しては，以下の3つの疑問が湧く．

1. ^{強磁性と反強磁性}Pottsモデルで，ランダム分割の解精度が改善しないのは何故か．

2. ^強磁性Potts^モデルで2値分割の解精度が著しく悪化するのは何故か．

3. ^強磁性Potts^{モデル以外で}2値分割の解精度が最も良いのは何故か．

これらの疑問に関しては次節で考察する．ここでの評価結果で注目すべきことは，フラス トレーションが存在し，基底状態を探索するのが難しいと考えられるPotts^{グラスモデル}

とPottsゲージグラスモデルに対して，分割方法の工夫によって高精度な解が得られてい

るということである．