特許ウォッチ

公開番号2025067403
公報種別公開特許公報(A)
公開日2025-04-24
出願番号2023177358
出願日2023-10-13
発明の名称エネルギー関数の最小値探索装置、エネルギー関数の最小値探索方法、及びプログラム。
出願人日本電信電話株式会社,学校法人早稲田大学
代理人個人,個人,個人
主分類G06N 99/00 20190101AFI20250417BHJP(計算;計数)
要約【課題】初期解を設定できないイジングマシンにおいて、疑似的に初期解を設定し、探索し得る準最適解の改良を図る。
【解決手段】上記課題を解決するため、エネルギー関数の最小値探索装置は、初期解取得部と、相互作用係数補正部と、暫定解管理部とを含む。初期解取得部は、第1エネルギー関数の計算に必要な、第1暫定解スピン/バイナリ変数を取得する。相互作用係数補正部は、前記第1エネルギー関数について、相互作用係数を前記第1暫定解スピン/バイナリ変数の再現に寄与する値に補正して、第2エネルギー関数を生成する。暫定解管理部は、イジングマシンで前記第2エネルギー関数の最小値を探索し、最小値を与えるスピン/バイナリ変数を第2暫定解スピン/バイナリ変数とし、前記第1暫定解スピン/バイナリ変数と前記第2暫定解スピン/バイナリ変数を用いて、前記第1エネルギー関数の値を評価する。
【選択図】図4
特許請求の範囲【請求項１】
イジングモデル／QUBOモデルで表現したエネルギー関数の最小値をイジングマシンで探索する、エネルギー関数の最小値探索装置であって、
第１エネルギー関数の計算に必要な、第１暫定解スピン／バイナリ変数を取得する初期解取得部と、
前記第１エネルギー関数について、相互作用係数を前記第１暫定解スピン／バイナリ変数の再現に寄与する値に補正して、第２エネルギー関数を生成する相互作用係数補正部と、
イジングマシンで前記第２エネルギー関数の最小値を探索し、最小値を与えるスピン／バイナリ変数を第２暫定解スピン／バイナリ変数とし、前記第１暫定解スピン／バイナリ変数と前記第２暫定解スピン／バイナリ変数を用いて、前記第１エネルギー関数の値を評価する暫定解管理部と、
を含む、エネルギー関数の最小値探索装置。
続きを表示（約 1,300 文字）【請求項２】
請求項１に記載のエネルギー関数の最小値探索装置であって、
前記相互作用係数補正部は、前記第１エネルギー関数について、前記第１暫定解スピン／バイナリ変数の組のうち、前記組の積が１／１のエッジでは相互作用係数を増加させる補正を行い、前記組の積が－１／０のエッジでは相互作用係数を減少させる補正を行うものである、
エネルギー関数の最小値探索装置。
【請求項３】
請求項１に記載のエネルギー関数の最小値探索装置であって、
前記相互作用係数補正部は、補正を行う相互作用係数を所定の割合で選択する、
エネルギー関数の最小値探索装置。
【請求項４】
請求項１に記載のエネルギー関数の最小値探装置であって、
終了判断部をさらに備え、
前記暫定解管理部は、前記第１暫定解スピン／バイナリ変数と前記第２暫定解スピン／バイナリ変数を用いて、前記第１エネルギー関数から第１暫定最小値と第２暫定最小値を計算し、前記第２暫定最小値が前記第１暫定最小値より小さい場合、前記第１暫定解を前記第２暫定解で更新し、
前記終了判断部が探索終了を判断するまで、前記相互作用係数の補正と、前記第２エネルギー関数の最小値探索と、前記第１暫定解の更新を繰り返す、
エネルギー関数の最小値探索装置。
【請求項５】
イジングモデル／QUBOモデルで表現したエネルギー関数の最小値をイジングマシンで探索する、エネルギー関数の最小値探索方法であって、
初期解取得部が、第１エネルギー関数の計算に必要な、第１暫定解スピン／バイナリ変数を取得し、
相互作用係数補正部が、前記第１エネルギー関数について、相互作用係数を前記第１暫定解スピン／バイナリ変数の再現に寄与する値に補正して、第２エネルギー関数を生成し、
暫定解管理部が、イジングマシンで前記第２エネルギー関数の最小値を探索し、最小値を与えるスピン／バイナリ変数を第２暫定解スピン／バイナリ変数とし、前記第１暫定解スピン／バイナリ変数と前記第２暫定解スピン／バイナリ変数を用いて、前記第１エネルギー関数の値を評価する
エネルギー関数の最小値探索方法。
【請求項６】
請求項５に記載のエネルギー関数の最小値探索方法であって、
前記相互作用係数補正部は、前記第１エネルギー関数について、前記第１暫定解スピン／バイナリ変数の組のうち、前記組の積が１／１のエッジでは相互作用係数を増加させる補正を行い、前記組の積が－１／０のエッジでは相互作用係数を減少させる補正を行う、
エネルギー関数の最小値探索方法。
【請求項７】
請求項５に記載のエネルギー関数の最小値探索方法であって、
前記相互作用係数補正部は、補正を行う相互作用係数を所定の割合で選択する、
エネルギー関数の最小値探索方法。
【請求項８】
請求項１，２，３，４のいずれか一項に記載の、エネルギー関数の最小値探索装置としてコンピュータを機能させるためのプログラム。

発明の詳細な説明【技術分野】
【０００１】
開示技術は、イジングマシンを用いて組合せ問題の準最適解を求める技術に関する。
続きを表示（約 3,100 文字）【背景技術】
【０００２】
組合せ最適化は、特定の条件を満たす多数の組合せの中から、特定の評価指標についてできるだけ良いものを選択する数理モデルである。組合せ最適化は、人員計画、経路探索、創薬といったビジネスでの意思決定から学術的な研究まで広い分野で現れる。
一方、組合せ最適化問題を効率的に（問題サイズに対して多項式時間で）解くことは従来のコンピュータでは難しい（ＮＰ問題）。そのため、物理現象などを利用して最適解の探索を行う計算機ハードウェアを用いて、高速に組合せ最適化を行う技術が重要な技術となっている。
【０００３】
イジングマシン（後述）は、イジングモデル（後述）の基底状態を探索する計算機である。組合せ最適化問題をイジングモデルで表現することで、イジングマシンは効率的に組合せ最適化問題の準最適解を求められる。イジングマシンによって得られる解は、スピンの初期状態に依存する。組合せ最適化問題の制約を満たした上で比較的良い解を初期解としてイジングマシンに設定すると、初期解を設定しないときと比較して、最終的に得られる解がより最適解に近づくことが知られている（非特許文献1）。
【０００４】
＜イジングモデル＞
イジングモデルは磁性体の性質を表す模型である。イジングモデルの例を図１に示す。
イジングモデルは、スピン（例えば１０１のσ
３
）と、スピンをつなぐエッジ（例えば１０２のJ
２，３
）からなる模型であり、スピンσ
ｉ
は、＋１（１０４は上向き矢印で＋１を示した例）あるいは－１（１０５は下向き矢印で－１を示した例）のいずれかの値をとる。h
ｉ
（例えば１０３のh
１
）は外部磁場係数であり、スピンσ
ｉ
に対する強制力を表す。J
ｉ，ｊ
は相互作用係数であり、２つのスピンσ
ｉ
、σ
ｊ
の間にはたらく相互作用を表す。J
ｉ，ｊ
の値が大きいほど、σ
ｉ
とσ
ｊ
は同じ値を取りやすく、J
ｉ，ｊ
の値が小さいほど、σ
ｉ
とσ
ｊ
は異なる値を取りやすい。
【０００５】
イジングモデルのエネルギーは、式（１）のように表される。
TIFF
2025067403000002.tif
32
169
ただし、Nはスピン数を表し、σ~はスピンの集合σ~＝{σ
１
,σ
２
,...,σ
Ｎ
}を表す。エネルギーH(σ~)が最小の状態を基底状態と呼ぶ。図１では隣接するスピン間のエッジのみ図示したが、式（１）の第1項では、全てのスピン間の相互作用の和を取っていることに注意されたい。
なお、イジングモデルの「スピン」や「外部磁場係数」は、数理的モデルを表現するための抽象概念として上記の通り定義されるものであり、必ずしも物理学における「スピン」や「磁場」と関連しない。そして、イジングモデルは「スピン」や「磁場」以外の物理的手段によっても実装可能である。
【０００６】
＜QUBO＞
QUBO（Quadratic Unconditional Binary Optimization）は、イジングモデルにおけるスピンσ
ｉ
を、0あるいは1のいずれかの値をとるバイナリ変数q
ｉ
で置き換えたモデルであり、そのエネルギーは式（２）のように表される。
TIFF
2025067403000003.tif
32
169
ただし、Nはバイナリ変数の数を表し、q~はバイナリ変数の集合q~＝{q
１
,q
２
,...,q
Ｎ
}を表す。
式（１）、式（２）をエネルギー関数と呼ぶ。
下記式（３）に示す変数変換を行い、J
ｉ，ｊ
ならびにh
ｉ
の値を修正することで、QUBOとイジングモデルは相互に変換できるため、QUBOとイジングモデルは等価である。
TIFF
2025067403000004.tif
22
169
エネルギー関数の定式化にイジングモデルを用いるかQUBOモデルを用いるかは、組合せ問題の性質に応じて、使い分ければよい。
【０００７】
＜イジングマシン＞
イジングマシンは、イジングモデルあるいはQUBOモデルの基底状態を探索する計算機である。組合せ最適化問題をイジングモデルあるいはQUBOモデルで表現することで、イジングマシンは効率的に組合せ最適化問題の準最適解を求められる。イジングマシンには、量子アニーリングマシン、シミュレーテッドアニーリングに基づくマシン、シミュレーテッド分岐マシン、コヒーレントイジングマシンなどがある。
【０００８】
＜量子アニーリング＞
量子アニーリングでは、初期状態としてスピンの状態を量子力学的に不確定にし、各スピンで同時に「＋１」と「－１」の２つの値を取る状態（重ね合わせ状態）とする（図２（ａ））。初期状態から量子ゆらぎの効果を徐々に小さくすることで、スピン間の相互作用「J
ｉ，ｊ
」と外部磁場「h
ｉ
」の影響を強くし、基底状態に近づけながら各変数の値が自律的に定まるようにする（図２（ｂ））。
【先行技術文献】
【非特許文献】
【０００９】
K. Fukada et al, "A Three-Stage Annealing Method Solving Slot-Placement Problems Using an Ising Machine," IEEE Access, vol. 9, pp. 134413-134426, 2021.
S. Kawakami et al, "Giving a Quasi-Initial Solution to Ising Machines by Controlling External Magnetic Field Coefficients," IEICE TRANS on Fundamentals of Electronics, Communications and Computer Sciences, 2023KEP0004, 2023.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
いくつかのイジングマシンでは、そのハードウェアの原理上、初期解を設定できない。
例えば、量子アニーリングを求解原理とするイジングマシンでは、上述の通り、各スピンの初期状態は、値が未確定な重ね合わせ状態にする必要があり、スピンの確定値である初期解を初期状態とすることはできない。ランダムなDOPO（縮退光パラメトリック発振器）のパルスの位相が時間発展して基底状態に近づくことで解が求まるコヒーレントイジングマシンも同様である。
このようなイジングマシンでは、初期解を用いて準最適解を改良することができなかった。
（【００１１】以降は省略されています）

関連特許