公開番号2024040542 公報種別公開特許公報(A) 公開日2024-03-26 出願番号2022144952 出願日2022-09-13 発明の名称イジングマシン選定装置、イジングマシン選定方法、プログラム 出願人日本電信電話株式会社,国立大学法人九州大学 代理人個人,個人,個人 主分類G06N 99/00 20190101AFI20240318BHJP(計算;計数) 要約【課題】イジングマシンを効率的に選定する技術を提供する。 【解決手段】選定対象イジングハミルトニアンに対応するグラフの特徴量ベクトルを計算する特徴量ベクトル計算部と、イジングハミルトニアンHmとイジングハミルトニアンHmに対応するグラフの特徴量ベクトルXmとの関係R2を用いて特徴量ベクトルとの距離が最小となる特徴量ベクトルに対応するイジングハミルトニアンHm_0を選択する第1選択部と、選定対象イジングハミルトニアンの計算に許容できる時間と最も近い許容計算時間Tk_0を選択し、イジングハミルトニアンHm、イジングマシンIn、許容計算時間TkとイジングマシンInが計算を開始してから許容計算時間Tkが経過する時点におけるイジングハミルトニアンHmの値Vm,n,kとの関係を用いて値Vm_0,n,k_0が最も小さいものから順に対応するイジングマシンを所定の数だけ選択する第2選択部とを含む。 【選択図】図4 特許請求の範囲【請求項１】 M, N, Kを2以上の整数、H m (m=1, …, M)をベンチマークとなるイジングハミルトニアン、I n (n=1, …, N)をイジングハミルトニアンの計算に用いるイジングマシン、T k (k=1, …, K)をイジングハミルトニアンの計算に許容できる時間（以下、許容計算時間という）とし、 イジングハミルトニアンH m 、イジングマシンI n 、許容計算時間T k とイジングマシンI n が計算を開始してから許容計算時間T k が経過する時点におけるイジングハミルトニアンH m の値V m,n,k との関係R 1 と、イジングハミルトニアンH m とイジングハミルトニアンH m に対応するグラフの特徴量ベクトルX m との関係R 2 とを記録する記録部と、 計算に用いるイジングマシンの選定対象となるイジングハミルトニアン（以下、選定対象イジングハミルトニアンという）に対応するグラフの特徴量ベクトルを計算する特徴量ベクトル計算部と、 関係R 2 を用いて前記特徴量ベクトルとの距離が最小となる特徴量ベクトルに対応するイジングハミルトニアンH m_0 (ただし、m 0 は1≦m 0 ≦Mを満たす)を選択する第１選択部と、 前記選定対象イジングハミルトニアンの計算に許容できる時間と最も近い許容計算時間T k_0 (ただし、k 0 は1≦k 0 ≦Kを満たす)を選択し、関係R 1 を用いて値V m_0,n,k_0 が最も小さいものから順に対応するイジングマシンを所定の数だけ選択する第２選択部と、 を含むイジングマシン選定装置。 続きを表示（約 1,000 文字）【請求項２】 M, N, Kを2以上の整数、H m (m=1, …, M)をベンチマークとなるイジングハミルトニアン、I n (n=1, …, N)をイジングハミルトニアンの計算に用いるイジングマシン、T k (k=1, …, K)をイジングハミルトニアンの計算に許容できる時間（以下、許容計算時間という）とし、 イジングハミルトニアンH m 、イジングマシンI n 、許容計算時間T k とイジングマシンI n が計算を開始してから許容計算時間T k が経過する時点におけるイジングハミルトニアンH m の値V m,n,k との関係R 1 と、イジングハミルトニアンH m とイジングハミルトニアンH m に対応するグラフの特徴量ベクトルX m との関係R 2 とを記録する記録部を含むイジングマシン選定装置が、計算に用いるイジングマシンの選定対象となるイジングハミルトニアン（以下、選定対象イジングハミルトニアンという）に対応するグラフの特徴量ベクトルを計算する特徴量ベクトル計算ステップと、 前記イジングマシン選定装置が、関係R 2 を用いて前記特徴量ベクトルとの距離が最小となる特徴量ベクトルに対応するイジングハミルトニアンH m_0 (ただし、m 0 は1≦m 0 ≦Mを満たす)を選択する第１選択ステップと、 前記イジングマシン選定装置が、前記選定対象イジングハミルトニアンの計算に許容できる時間と最も近い許容計算時間T k_0 (ただし、k 0 は1≦k 0 ≦Kを満たす)を選択し、関係R 1 を用いて値V m_0,n,k_0 が最も小さいものから順に対応するイジングマシンを所定の数だけ選択する第２選択ステップと、 を含むイジングマシン選定方法。 【請求項３】 請求項１に記載のイジングマシン選定装置としてコンピュータを機能させるためのプログラム。
発明の詳細な説明【技術分野】 【０００１】 本発明は、最適化問題を解くために用いるイジングマシンの選定技術に関する。 続きを表示（約 2,400 文字）【背景技術】 【０００２】 近年、非ノイマン型計算機の１つであるイジングマシンが注目されている。イジングマシンは組合せ最適化問題の計算、機械学習、物理や化学のモデル計算に応用されており、例えば、渋滞回避を目指す経路選択問題、工場内の無人搬送車の経路最適化問題、金融商品のポートフォリオ最適化問題、広告配信最適化問題、矩形パッキング問題、スロット配置問題、誘導部分グラフ同型問題、バイナリニューラルネットワークの問題を解くために利用されている。 【０００３】 イジングマシンはイジングモデルのハミルトニアン（以下、イジングハミルトニアンという）を最小化する新しい原理に基づくコンピュータである。上述した問題をイジングマシンで解くためには、まず問題を当該問題を表現するイジングハミルトニアンに変換し、イジングマシンを用いて当該イジングハミルトニアンの最小化を行う。イジングハミルトニアンHは次式により表される。 TIFF 2024040542000002.tif 14 46 ただし、s i (i=1, …, N)はスピン、J=(J ij )は相互作用行列、h=(h i )は外部磁場ベクトルを表す。ここで、s i は+1または-1を値として取る変数、JはN×Nの実行列、hはN次元実ベクトルである。 【０００４】 イジングマシンは相互作用行列Jと外部磁場ベクトルhが入力されると、イジングハミルトニアンHの値が小さくなるようなスピンs 1 , …, s N の組合せを出力する。 【０００５】 なお、イジングマシンの中にはイジングハミルトニアンの代わりに、QUBO(Quadratic Unconstrained Binary Optimization)の最小化を行うものもある。ただし、QUBOとイジングハミルトニアンは容易に相互変換できる（非特許文献１参照）。 【０００６】 一般にイジングハミルトニアンの値が小さくなるほど変換前の問題の解の品質がよくなるため、イジングハミルトニアンの値をより小さくできるイジングマシンを用いて問題を解くのが好ましい。 【０００７】 現在、イジングモデルの基底探索問題を解くハードウェアであるイジングマシンがいくつか開発されているが、その実装方法には違いがある。そのため、イジングマシンの特性も異なったものとなり、解の品質がイジングマシンにより大きく左右されることになる（非特許文献２参照）。具体的に説明する。計算を開始してからの経過時間と当該経過時間におけるイジングハミルトニアンの値の関係は、同じ問題であってもイジングマシンごとに異なったものとなる。また、計算を開始してからの経過時間と当該経過時間におけるイジングハミルトニアンの値の関係は、同じイジングマシンを用いたとしても問題が異なれば異なったものとなる。つまり、イジングハミルトニアンに対応する問題と計算に費やす時間との２つに依存して、最も高品質な解を得られるイジングマシンは変化することになる。 【０００８】 同じ問題をイジングマシンと古典コンピュータで解いた場合の性能の比較は従来から行われているが（非特許文献３参照）、同じ問題を様々なイジングマシンで解いた場合の性能の比較は行われていない。そのため、ある問題を解くのに最適なイジングマシンを選定するには、当該問題を実際に解き、その結果を比較する必要がある。 【先行技術文献】 【非特許文献】 【０００９】 Zhengbing Bian, Fabian Chudak, William G. Macready, and Geordie Rose, “The Ising model: teaching an old problem new tricks,” ［online］，［令和４年８月１日検索］，インターネット <URL: https://www.dwavesys.com/media/vbklsvbh/weightedmaxsat_v2.pdf>. Hamerly, Ryan, et al., “Experimental investigation of performance differences between coherent Ising machines and a quantum annealer,” Science advances, vol.5, no.5, 2019. Charles Moussa, Henri Calandra, and Vedran Dunjko, “To quantum or not to quantum: towards algorithm selection in near-term quantum optimization,” Quantum Science and Technology, vol.5, no.4, 2020. 【発明の概要】 【発明が解決しようとする課題】 【００１０】 上述の通り、ある問題を解くために用いるイジングマシンを選定するには、当該問題を解いた結果を比較することになるが、この試行錯誤による選定作業は人的労力と時間を要するものとなり、その負担は大きい。もし、計算時間に応じて課金されるイジングマシンを利用している場合には、選定作業に費用が生じることになる。また、選定作業に係る負担は解きたい問題ごとに生じることとなる。つまり、イジングハミルトニアンの計算に用いるイジングマシンの選定作業に係る負担は非常に大きなものとなるという問題がある。 （【００１１】以降は省略されています） この特許をJ-PlatPatで参照する
特許ウォッチ
