特許ウォッチ

公開番号2025174675
公報種別公開特許公報(A)
公開日2025-11-28
出願番号2024081178
出願日2024-05-17
発明の名称情報処理装置、情報処理方法、プログラム
出願人日本電気株式会社
代理人個人,個人,個人,個人
主分類G06N 99/00 20190101AFI20251120BHJP(計算;計数)
要約【課題】制約条件付きの組み合わせ最適化問題における求解時間の短縮化を図ることができないこと。
【解決手段】本開示の情報処理装置は、制約条件付きの組み合わせ最適化問題におけるエネルギーを表す定式化したモデルの目的関数を用いて、制約条件を満たして各スピンがフリップする際のエネルギー変化であるフリップエネルギー変化を計算する第一計算部と、フリップエネルギー変化に基づいて、組み合わせ最適化問題における次の解に推移する際のエネルギー変化である推移エネルギー変化を計算する第二計算部と、推移エネルギー変化に基づいて、最適化問題を疑似量子アニーリングにより求解する際に用いる逆温度を計算する第三計算部と、を備える。
【選択図】図8

特許請求の範囲【請求項１】
制約条件付きの組み合わせ最適化問題におけるエネルギーを表す定式化したモデルの目的関数を用いて、前記制約条件を満たして各スピンがフリップする際のエネルギー変化であるフリップエネルギー変化を計算する第一計算部と、
前記フリップエネルギー変化に基づいて、前記組み合わせ最適化問題における次の解に推移する際のエネルギー変化である推移エネルギー変化を計算する第二計算部と、
前記推移エネルギー変化に基づいて、前記最適化問題を疑似量子アニーリングにより求解する際に用いる逆温度を計算する第三計算部と、
を備えた情報処理装置。
続きを表示（約 1,500 文字）【請求項２】
請求項１に記載の情報処理装置であって、
前記制約条件を満たして各スピンが特定の状態となる確率を計算する第四計算部を備え、
前記第一計算部は、前記確率に基づいて、各スピンの前記フリップエネルギー変化を算出する、
情報処理装置。
【請求項３】
請求項２に記載の情報処理装置であって、
前記第一計算部は、所定のスピンに対する他のスピンの前記確率に基づいて、前記他のスピンのうち前記特定の状態にフリップする当該他のスピンの数を推定し、推定した前記他のスピンの数に基づいて前記フリップエネルギー変化を計算する、
情報処理装置。
【請求項４】
請求項３に記載の情報処理装置であって、
前記第一計算部は、前記モデルに設定された２つのスピンの組み合わせに対応する重みパラメータと、前記確率と、に基づいて前記他のスピンの数を推定する、
情報処理装置。
【請求項５】
請求項３に記載の情報処理装置であって、
前記第一計算部は、前記モデルに設定された２つのスピンの組み合わせに対応する重みパラメータのうち推定した前記他のスピンの数の前記重みパラメータの値に基づいて、前記フリップエネルギー変化を計算する、
情報処理装置。
【請求項６】
請求項１に記載の情報処理装置であって、
前記第二計算部は、特定の状態にフリップするスピンの数と、前記特定の状態とは異なる他の状態にフリップするスピンの数と、に基づいて、前記推移エネルギー変化を計算する、
情報処理装置。
【請求項７】
請求項６に記載の情報処理装置であって、
前記第二計算部は、前記特定の状態にフリップするスピンの前記フリップエネルギー変化の総和から、前記他の状態にフリップするスピンの前記フリップエネルギー変化の総和を減算した値に基づいて、前記推移エネルギー変化を計算する、
情報処理装置。
【請求項８】
請求項７に記載の情報処理装置であって、
前記第二計算部は、前記特定の状態にフリップするスピンの数と、前記特定の状態とは異なる値にフリップするスピンの数と、が同一である場合において、前記推移エネルギー変化を計算する、
情報処理装置。
【請求項９】
制約条件付きの組み合わせ最適化問題におけるエネルギーを表す定式化したモデルの目的関数を用いて、前記制約条件を満たして各スピンがフリップする際のエネルギー変化であるフリップエネルギー変化を計算し、
前記フリップエネルギー変化に基づいて、前記組み合わせ最適化問題における次の解に推移する際のエネルギー変化である推移エネルギー変化を計算し、
前記推移エネルギー変化に基づいて、前記最適化問題を疑似量子アニーリングにより求解する際に用いる逆温度を計算する、
情報処理方法。
【請求項１０】
制約条件付きの組み合わせ最適化問題におけるエネルギーを表す定式化したモデルの目的関数を用いて、前記制約条件を満たして各スピンがフリップする際のエネルギー変化であるフリップエネルギー変化を計算し、
前記フリップエネルギー変化に基づいて、前記組み合わせ最適化問題における次の解に推移する際のエネルギー変化である推移エネルギー変化を計算し、
前記推移エネルギー変化に基づいて、前記最適化問題を疑似量子アニーリングにより求解する際に用いる逆温度を計算する、
処理をコンピュータに実行させるプログラム。

発明の詳細な説明【技術分野】
【０００１】
本開示は、情報処理装置、情報処理方法、プログラムに関する。
続きを表示（約 2,100 文字）【背景技術】
【０００２】
制約条件付きの組み合わせ最適化問題を、問題におけるエネルギーの式を定式化したモデルの形式に変換して求解することが行われている。例えば、特許文献１では、組み合わせ最適化問題のエネルギーをイジングモデルに変換して、疑似量子アニーリングにより求解することが記載されている。
【０００３】
疑似量子アニーリングでは、所定のスピンをフリップする際のエネルギーの変化を計算し、かかるエネルギーの変化と、設定された温度パラメータである逆温度と、に応じて、スピンをフリップさせるかどうかを決定して解の探索を行う。このとき、逆温度を上げたり下げたりしながら解の探索を行うこととなるが、最適解への到達に時間がかかることから、特許文献１では、局所解から抜け出せるような逆温度を推定することが記載されている。
【先行技術文献】
【特許文献】
【０００４】
特許第７４２８２６８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した特許文献１に記載の技術では、制約条件付きの組み合わせ最適化問題において制約項に関するエネルギー変化を考慮して逆温度を推定しているため、制約条件を満たしながら求解する求解装置を用いる場合には適切に適用することができない。このため、制約条件付きの組み合わせ最適化問題における求解時間の短縮化を図ることができない、という問題が生じる。
【０００６】
このため、本開示の目的の一つは、上述した課題である、制約条件付きの組み合わせ最適化問題における求解時間の短縮化を図ることができない、ことを解決することにある。
【課題を解決するための手段】
【０００７】
本開示の一形態である情報処理装置は、
制約条件付きの組み合わせ最適化問題におけるエネルギーを表す定式化したモデルの目的関数を用いて、前記制約条件を満たして各スピンがフリップする際のエネルギー変化であるフリップエネルギー変化を計算する第一計算部と、
前記フリップエネルギー変化に基づいて、前記組み合わせ最適化問題における次の解に推移する際のエネルギー変化である推移エネルギー変化を計算する第二計算部と、
前記推移エネルギー変化に基づいて、前記最適化問題を疑似量子アニーリングにより求解する際に用いる逆温度を計算する第三計算部と、
を備えた、
という構成をとる。
また、本開示の一形態である情報処理方法は、
制約条件付きの組み合わせ最適化問題におけるエネルギーを表す定式化したモデルの目的関数を用いて、前記制約条件を満たして各スピンがフリップする際のエネルギー変化であるフリップエネルギー変化を計算し、
前記フリップエネルギー変化に基づいて、前記組み合わせ最適化問題における次の解に推移する際のエネルギー変化である推移エネルギー変化を計算し、
前記推移エネルギー変化に基づいて、前記最適化問題を疑似量子アニーリングにより求解する際に用いる逆温度を計算する、
という構成をとる。
また、本開示の一形態であるプログラムは、
制約条件付きの組み合わせ最適化問題におけるエネルギーを表す定式化したモデルの目的関数を用いて、前記制約条件を満たして各スピンがフリップする際のエネルギー変化であるフリップエネルギー変化を計算し、
前記フリップエネルギー変化に基づいて、前記組み合わせ最適化問題における次の解に推移する際のエネルギー変化である推移エネルギー変化を計算し、
前記推移エネルギー変化に基づいて、前記最適化問題を疑似量子アニーリングにより求解する際に用いる逆温度を計算する、
処理をコンピュータに実行させる、
という構成をとる。
【発明の効果】
【０００８】
本開示は、以上のように構成されることにより、制約条件付きの組み合わせ最適化問題における求解時間の短縮化を図ることができる。
【図面の簡単な説明】
【０００９】
本開示にかかる情報処理装置の構成の一例を示すブロック図である。
本開示に関連するデータの一例を示す図である。
本開示にかかる情報処理装置の処理動作の一例を示すフローチャートである。
本開示にかかる情報処理装置の構成の一例を示すブロック図である。
本開示に関連するデータの一例を示す図である。
本開示にかかる情報処理装置の処理動作の一例を示すフローチャートである。
本開示にかかる情報処理装置のハードウェア構成の一例を示すブロック図である。
本開示にかかる情報処理装置の構成の一例を示すブロック図である。
【発明を実施するための形態】
【００１０】
＜第１の実施形態＞
本開示の第１の実施形態について、図面を参照して説明する。なお、図面はいずれの実施形態においても関連しうる。
（【００１１】以降は省略されています）

関連特許