部分問題に含まれる許容解の数

-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ゲージグラスモデルに対して，分割方法の工夫によって高精度な解が得られてい

るということである．

-0.01 0.00 0.01 0.02 0.03 0.04 0.05 0.06

1 10 100 1000

Optimal value Eave(Nopt) / Ninteger

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

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

-1.10 -1.05 -1.00 -0.95 -0.90 -0.85 -0.80

1 10 100 1000

Eave(Nopt) / Ninteger

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

図5.11: Pottsグラスモデルに対する解精度の評価結果

-2.00 -1.95 -1.90 -1.85 -1.80 -1.75 -1.70 -1.65

1 10 100 1000

Eave(Nopt) / Ninteger

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

図5.12: Pottsゲージグラスモデルに対する解精度の評価結果

表5.3: 部分問題の解空間に含まれる許容解の数: logN_feasible

前章で提案した埋め込みアルゴリズム 完全グラフの埋め込み

ランダム分割 25.3

-整数分割 33.9 9.6

2値分割 122.8 19.3

• 2値分割によって抜き出した部分問題の解空間は許容解のみを含む

• 2値分割の部分問題の方が多くのブール変数をキメラグラフ上に埋め込める

2番目の理由は，2値分割の部分問題のハミルトニアンがone-hot制約のペナルティ項を 含まないことが重要な寄与をしている．つまり，ペナルティ項は同じ整数変数に割当てら れたブール変数間に全結合相互作用を発生させるが，2値分割で抜き出した部分問題のハ ミルトニアンはペナルティ項を含まない．この結果として，部分問題の相互作用の数が整 数分割に対して減少し，多くのブール変数を埋め込めるようになる．部分問題埋め込みア ルゴリズムを用いてキメラグラフ上に埋め込まれたブール変数の数を，それぞれの分割方 法で比較したのが表5.4である．

表5.4: 各分割方法でキメラグラフ上に埋め込まれたブール変数の数 分割方法 ブール変数の数

ランダム分割 354.1

整数分割 225.6

2^値分割 408.1

表5.5: 各整数変数で埋め込まれたブール変数の数の内訳 ブール変数の数 割合[%]

2 22.1

3 12.2

4 65.7

また，前章の部分問題の埋め込みアルゴリズムを用いて整数分割の部分問題が想定通り 埋め込まれていることも確認する必要がある．2値分割では2値の部分問題を抜き出すた め，整数分割では各整数変数に割当てられた4つのブール変数の中で3つ以上が埋め込ま れていることが望ましい．部分問題に含まれる各整数変数に対して，埋め込まれたブール 変数の数の内訳を示したのが表5.5である．部分問題に含まれる整数変数の中で65.7%^は 4つのブール変数が全て埋め込まれており，3つ以上のブール変数が埋め込まれる割合は

77.9%となっている．この結果から，整数分割では2値分割とは異なる部分問題を埋め込

めていると言える．