考察

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

2 22.1

3 12.2

4 65.7

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

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

めていると言える．

図 5.13: one-hot制約を破る状態を経由した暫定解の改善

ϭ Ϭ Ϭ Ϭ

Ϭ Ϭ Ϭ ϭ

S_i-1 S_i q=1

q=2 q=3 q=4

J>0 J J J

ϭ Ϭ Ϭ Ϭ

J J J J

S_i+1

;ĂͿᬻᐃゎ

Ϭ

͗㒊ศၥ㢟䛸䛧䛶ᢳฟ

ϭ Ϭ Ϭ Ϭ

ϭ Ϭ Ϭ ϭ

S_i-1 S_i q=1

q=2 q=3 q=4

J J J J

ϭ Ϭ Ϭ Ϭ

J J J J

S_i+1

;ďͿ᭦᪂ᚋ

dž_Ƌϭ䛾᭦᪂䛻䜘䛳䛶┦஫స⏝Ϯᮏศ䛾 䜶䝛䝹䜼䞊䛜పୗ

x_1i x_1,i-1 x_1i x_1,i+1

図5.14: 1^{次元強磁性}Pottsモデルにおける暫定解の改善例

部分問題は更新先の候補に許容解を含まない．部分問題の変数をx_1i = 0からx_1i = 1に 更新した場合のエネルギー変化∆Eは

∆E =−2J+λ, (5.13)

となる．ここで，第一項はx1,i−1 = x1i = x1,i+1 = 1となることで得するエネルギーを 表しており，第二項はone-hot制約を破ることによるペナルティを表している[図5.14(b) 参照]．1次元強磁性Pottsモデルの基底状態を正しく表現するためにはλ > J で十分で あることは簡単に示すことができ，J < λ <2Jと設定されている場合はone-hot制約を 破るにも関わらずエネルギーが減少（∆E <0）する．つまり，わざわざ整数分割のよう な方法を用いるまでもなく，one-hot制約を破る組合せを経由して暫定解を改善していけ る．ここで重要なことは，x1iの更新によって複数のブール変数間の局所エネルギーが同 時に最小化されていることであり，その結果として制約を破ることによるペナルティを打 ち消してエネルギーが下がっていることである．複数の局所エネルギーを同時に最小化で きるか否かは問題に依存して決まり，フラストレーションが存在するPottsグラスモデル

やPottsゲージグラスモデルではこのような状況は発生しにくい．一方で，強磁性や反強

磁性Pottsモデルの基底状態では全ての整数変数間の局所エネルギーを最小化できるため，

ランダム分割を用いても暫定解を改善していけると考えられる．

2番目の疑問に対する答えとして，2値分割を用いた場合はドメインウォールを解消で きる部分問題が選択されにくいことが挙げられる．ここでも，簡単のため1次元強磁性

Pottsモデルを例にとって説明する．10個の整数変数をもつ1次元強磁性Pottsモデル

ϭ Ϭ Ϭ Ϭ

ϭ Ϭ Ϭ Ϭ S₁ S₂ q=1

q=2 q=3 q=4

ϭ Ϭ Ϭ Ϭ S₃

ϭ Ϭ Ϭ Ϭ

ϭ Ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ S₄ S₅ S₆ S₇ S₈ S₉ S₁₀

䝗䝯䜲䞁䜴䜷䞊䝹

図5.15: 1^{次元強磁性}Pottsモデルにおけるドメインウォールの例

ϭ Ϭ Ϭ Ϭ

ϭ Ϭ Ϭ Ϭ S₁ S₂ q=1

q=2 q=3 q=4

ϭ Ϭ Ϭ Ϭ S₃

ϭ Ϭ Ϭ Ϭ

ϭ Ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ S₄ S₅ S₆ S₇ S₈ S₉ S₁₀

図5.16: Si = 1の最適解に更新可能な部分問題

でドメインウォールが発生した状況を図5.15に示してあり，{S_i = 1|i = 1,2, ...,5}^と {Si = 2|i= 6,7, ...,10}^の2つの領域に別れている．この暫定解に対して2^{値分割を用い} てドメインウォールを解消するためには，以下に示す2値の部分問題のいずれかを抜き出 さなければならない．

• S₆からS₁₀に関する2値の部分問題として，q= 1に割当てられたブール変数を選択

• S₁からS₅に関する2値の部分問題として，q= 2に割当てられたブール変数を選択

• ^{全ての整数変数で，}q= 3に割当てられたブール変数を2値の部分問題として選択

• ^{全ての整数変数で，}q= 4に割当てられたブール変数を2値の部分問題として選択 1^番目と3番目の部分問題で抜き出されるブール変数を図5.16^と5.17^に示す．2^値分割で はx_q′i= 0となっているブール変数をランダムに選択するため，1^番目と2^{番目の部分問題} が選択される確率は(1/3)⁵であり，3番目と4番目の部分問題が選択される確率は(1/3)¹⁰ となる．この確率は整数変数の数に対して指数関数的に減少するため，ドメインウォール を2値分割を用いて解消するのは難しい．

3番目の疑問に対する答えとして，暫定解を改善可能な更新先が複数存在することが挙 げられる．ここでは，1^{次元反強磁性}Pottsモデルを例にとって説明する．反強磁性Potts モデルにおける整数変数間の局所エネルギーはJ δ(Si, Sj)^（Si ̸=Sjのときに局所エネル ギーが小さくなる）であり，図5.18(a)に示した暫定解ではS_i−1とS_iの間の局所エネル ギーが最大化されている．この暫定解を改善するため，S_iを更新することを考える．この 場合は，S_i = 1またはS_i = 3に更新することで暫定解を改善できるため，暫定解を改善

ϭ Ϭ Ϭ Ϭ

ϭ Ϭ Ϭ Ϭ S₁ S₂ q=1

q=2 q=3 q=4

ϭ Ϭ Ϭ Ϭ S₃

ϭ Ϭ Ϭ Ϭ

ϭ Ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ S₄ S₅ S₆ S₇ S₈ S₉ S₁₀

図5.17: Si = 3の最適解に更新可能な部分問題

Ϭ ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ

S_i-1 S_i q=1

q=2 q=3 q=4

-J<0 -J -J -J

Ϭ Ϭ Ϭ ϭ

-J -J -J -J

S_i+1

;ĂͿᬻᐃゎ

Ϭ ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ

S_i-1 S_i

Ϭ Ϭ Ϭ ϭ

S_i+1

;ďͿᬻᐃゎ䜢ᨵၿྍ⬟䛺Ϯ್䛾㒊ศၥ㢟

Ϭ ϭ Ϭ Ϭ

Ϭ ϭ Ϭ Ϭ

S_i-1 S_i

Ϭ Ϭ Ϭ ϭ

S_i+1

図5.18: 1^{次元反強磁性}Pottsモデルにおける暫定解の改善例

可能な2値の部分問題が複数存在することが分かる[図5.18(b)参照]．結果として，反強

磁性Potts^{モデルでは}2値問題に落とし込んでも暫定解の改善を続けていける可能性が高

い．このように，2値問題に限定しても特段の問題が発生しない状況であれば，部分問題の 解空間に許容解を多く含む2値分割を用いるのが最も効率的と考えられる．同様のことは

PottsグラスモデルやPottsゲージグラスモデルに対しても言える．ここでは，Pottsゲー

ジグラスモデルを例に図5.19を用いて説明する．このモデルにはフラストレーションが存 在し，全ての整数変数間の局所エネルギー−J δ(S_i, S_j+ ∆_ij)を最小化することはできな い．基底状態では1つの整数変数間の局所エネルギーが最大化されており，図5.19(a)^に 示した例ではS1とS4の間の相互作用が最大化されている．図5.19(b)^には2^{つの整数変} 数間の局所エネルギーが最大化された第一励起状態が示されている．ここで，図5.19(b) の第一励起状態を改善するために，S₄を更新することを考える．この場合は，S₄ = 1ま たはS₄ = 2に更新することで基底状態に到達することができ，Pottsゲージグラスモデ ルでも第一励起状態を改善可能な2値の部分問題が複数存在することが分かる[図5.19(c)

参照]^．Pottsゲージグラスモデルのようなフラストレーションが存在するモデルでは，局

所エネルギーを最大化させたまま残しておく整数変数ペアの選び方が複数存在することに 対応して，第一励起状態を改善できる部分問題の数が増加する．以上の理由から，強磁性

Pottsモデルを除くすべてのモデルに対して，2値分割を用いた場合の性能が最も高くなっ

たと考えられる．

q=1 q=2 q=3 q=4

S₁

S₂ S₃

J>0

J

J

J

S₁

S₂ S₃

J>0

J

J

J

S₄ S₄

;ĂͿᇶᗏ≧ែ䛾౛ ;ďͿ➨୍ບ㉳≧ែ䠄ᬻᐃゎ䠅

;ĐͿ➨୍ບ㉳≧ែ䠄ᬻᐃゎ䠅䜢ᨵၿྍ⬟䛺Ϯ್䛾㒊ศၥ㢟 䠖᭱኱໬䛥䜜䛶䛔䜛ᩚᩘኚᩘ㛫䛾ᒁᡤ䜶䝛䝹䜼䞊

䠖㒊ศၥ㢟䛾᭱㐺໬ᚋ䜒᭱኱໬䛥䜜䛶䛔䜛ᒁᡤ䜶䝛䝹䜼䞊 図5.19: 1次元反強磁性Pottsモデルにおける暫定解の改善例

ドキュメント内 大規模な組合せ最適化問題に対する量子アニーリングマシンの活用方法に関する研究 (ページ 62-66)