特許ウォッチ

公開番号2025118413
公報種別公開特許公報(A)
公開日2025-08-13
出願番号2024013724
出願日2024-01-31
発明の名称アニーリング処理装置、アニーリング処理方法及びプログラム
出願人国立大学法人東京科学大学,学校法人早稲田大学
代理人個人
主分類G06N 99/00 20190101AFI20250805BHJP(計算;計数)
要約【課題】マージ処理及びアニーリング処理を高速に行うことが可能なアニーリング処理装置を提供する。
【解決手段】アニーリング処理装置は、アニーリング処理が行われるように制御を行うアニーリング制御部と、イジングモデルにおける複数のスピンにおけるマージされるスピンである被マージスピンと当該被マージスピンのマージ先のスピンであるマージ先スピンとを決定することを含むマージ処理を行い、マージ処理によって決定された情報であるマージ情報に対応する行列を生成するマージ処理部と、行列を用いた行列計算によって、イジングモデルにおける複数のスピンの局所場を並列に計算する局所場計算部と、局所場に基づいて、複数のスピンの反転確率を並列に計算して、前記反転確率に基づいてスピンを反転するための処理を行う反転処理部と、を有する。
【選択図】図5
特許請求の範囲【請求項１】
イジングモデルを用いて解を求めるアニーリング処理装置であって、
アニーリング処理が行われるように制御を行うアニーリング制御部と、
前記イジングモデルにおける複数のスピンにおけるマージされるスピンである被マージスピンと当該被マージスピンのマージ先のスピンであるマージ先スピンとを決定することを含むマージ処理を行い、前記マージ処理によって決定された情報であるマージ情報に対応する行列を生成するマージ処理部と、
前記行列を用いた行列計算によって、前記イジングモデルにおける複数のスピンの局所場を並列に計算する局所場計算部と、
前記局所場に基づいて、前記複数のスピンの反転確率を並列に計算して、前記反転確率に基づいてスピンを反転するための処理を行う反転処理部と、
を有する、アニーリング処理装置。
続きを表示（約 1,700 文字）【請求項２】
前記マージ処理部は、前記行列を用いた行列計算によって、マージ処理後の外部磁場を計算し、
前記局所場計算部は、前記行列を用いた行列計算によって計算されたマージ処理後のスピン間相互作用に基づいて、複数のスピンの前記局所場を並列に計算する、
請求項１に記載のアニーリング処理装置。
【請求項３】
前記マージ処理部は、前記被マージスピンと前記マージ先スピンとの関係を示すマージ先行列を生成し、前記マージ先行列に基づいて、前記被マージスピンの状態を示すパラメータと当該被マージスピンのマージ先である前記マージ先スピンの状態を示すパラメータとの積を示すスピン積行列を生成し、
前記局所場計算部は、前記マージ先行列と前記スピン積行列とを用いた行列計算によって、複数のスピンの局所場を並列に計算する、
請求項１に記載のアニーリング処理装置。
【請求項４】
前記反転処理部は、前記反転確率に基づいて反転するスピンを選択し、選択されたスピンが前記マージ先スピンである場合は、前記マージ先行列を参照して、選択されたスピンとともに、選択されたスピンにマージされた被マージスピンを反転する、
請求項３に記載のアニーリング処理装置。
【請求項５】
前記アニーリング制御部は、それぞれ独立したアニーリング処理である複数のレプリカを並列に実行するレプリカ処理が行われるように、制御を行い、
前記局所場計算部は、複数の前記レプリカについて並列に、前記局所場を計算し、
前記反転処理部は、複数の前記レプリカについて並列に、スピンを反転する処理を行う、
請求項１に記載のアニーリング処理装置。
【請求項６】
前記マージ処理部は、複数の前記レプリカについて共通の、前記被マージスピンと前記マージ先スピンとの関係を示すマージ先行列を生成する、
請求項５に記載のアニーリング処理装置。
【請求項７】
前記マージ処理部は、前記マージ先行列に基づいて、複数の前記レプリカそれぞれについての、前記被マージスピンの状態を示すパラメータと前記マージ先スピンの状態を示すパラメータとの積を示す、１つのスピン積行列を生成する、
請求項６に記載のアニーリング処理装置。
【請求項８】
イジングモデルを用いて解を求めるアニーリング処理方法であって、
アニーリング処理が行われるように制御を行い、
前記イジングモデルにおける複数のスピンにおけるマージされるスピンである被マージスピンと当該被マージスピンのマージ先のスピンであるマージ先スピンとを決定することを含むマージ処理を行い、前記マージ処理によって決定された情報であるマージ情報に対応する行列を生成し、
前記行列を用いた行列計算によって、前記イジングモデルにおける複数のスピンの局所場を並列に計算し、
前記局所場に基づいて、前記複数のスピンの反転確率を並列に計算して、前記反転確率に基づいてスピンを反転するための処理を行う、
アニーリング処理方法。
【請求項９】
イジングモデルを用いて解を求めるアニーリング処理方法を実現するプログラムであって、
アニーリング処理が行われるように制御を行う処理と、
前記イジングモデルにおける複数のスピンにおけるマージされるスピンである被マージスピンと当該被マージスピンのマージ先のスピンであるマージ先スピンとを決定することを含むマージ処理を行い、前記マージ処理によって決定された情報であるマージ情報に対応する行列を生成する処理と、
前記行列を用いた行列計算によって、前記イジングモデルにおける複数のスピンの局所場を並列に計算する処理と、
前記局所場に基づいて、前記複数のスピンの反転確率を並列に計算して、前記反転確率に基づいてスピンを反転するための処理を行う処理と、
をコンピュータに実行させる、プログラム。

発明の詳細な説明【技術分野】
【０００１】
本開示は、アニーリング処理装置、アニーリング処理方法及びプログラムに関する。
続きを表示（約 2,700 文字）【背景技術】
【０００２】
例えば量子アニーリング又はシミュレーテッドアニーリング等の、イジングモデルの基底状態を探索する問題を求解するためのアニーリングアルゴリズム（焼き鈍し法）が知られている。例えば、非特許文献１は、イジングマシンにおけるマルチスピンフリップを設計するためのマージ処理を開示する。マージ処理は、イジングモデルにおけるスピンを他のスピンにマージするような処理である。マージ処理を行うことにより、より良質な解を得ることが可能となる。
【先行技術文献】
【非特許文献】
【０００３】
Tatsuhiko Shirai and Nozomu Togawa、"Multi-Spin-Flip Engineering in an Ising Machine"、IEEE Transactions On Computers, Vol. 72, No. 3, March 2023、https://www.computer.org/csdl/journal/tc/2023/03/09783142/1DIx1TTQmB2
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１にかかる技術では、マージ処理は、１つのスピンずつ逐次的に行われる。これに対し、アニーリング処理は、複数のスピンについて並列に行われる。したがって、アニーリング処理を実行する装置でマージ処理を行うと、処理速度が遅くなるおそれがある。一方、アニーリング処理を実行する装置とは別の装置でマージ処理を行うと、これらの装置の間で通信を行う必要があるので、やはり遅延が発生するおそれがある。したがって、マージ処理及びアニーリング処理を高速に行うことは困難である。
【０００５】
本開示は、マージ処理及びアニーリング処理を高速に行うことが可能なアニーリング処理装置、アニーリング処理方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本開示にかかるアニーリング処理装置は、イジングモデルを用いて解を求めるアニーリング処理装置であって、アニーリング処理が行われるように制御を行うアニーリング制御部と、前記イジングモデルにおける複数のスピンにおけるマージされるスピンである被マージスピンと当該被マージスピンのマージ先のスピンであるマージ先スピンとを決定することを含むマージ処理を行い、前記マージ処理によって決定された情報であるマージ情報に対応する行列を生成するマージ処理部と、前記行列を用いた行列計算によって、前記イジングモデルにおける複数のスピンの局所場を並列に計算する局所場計算部と、前記局所場に基づいて、前記複数のスピンの反転確率を並列に計算して、前記反転確率に基づいてスピンを反転するための処理を行う反転処理部と、を有する。
【０００７】
本開示にかかるアニーリング処理方法は、イジングモデルを用いて解を求めるアニーリング処理方法であって、アニーリング処理が行われるように制御を行い、前記イジングモデルにおける複数のスピンにおけるマージされるスピンである被マージスピンと当該被マージスピンのマージ先のスピンであるマージ先スピンとを決定することを含むマージ処理を行い、前記マージ処理によって決定された情報であるマージ情報に対応する行列を生成し、前記行列を用いた行列計算によって、前記イジングモデルにおける複数のスピンの局所場を並列に計算し、前記局所場に基づいて、前記複数のスピンの反転確率を並列に計算して、前記反転確率に基づいてスピンを反転するための処理を行う。
【０００８】
本開示にかかるプログラムは、イジングモデルを用いて解を求めるアニーリング処理方法を実現するプログラムであって、アニーリング処理が行われるように制御を行う処理と、前記イジングモデルにおける複数のスピンにおけるマージされるスピンである被マージスピンと当該被マージスピンのマージ先のスピンであるマージ先スピンとを決定することを含むマージ処理を行い、前記マージ処理によって決定された情報であるマージ情報に対応する行列を生成する処理と、前記行列を用いた行列計算によって、前記イジングモデルにおける複数のスピンの局所場を並列に計算する処理と、前記局所場に基づいて、前記複数のスピンの反転確率を並列に計算して、前記反転確率に基づいてスピンを反転するための処理を行う処理と、をコンピュータに実行させる。
【発明の効果】
【０００９】
本開示によれば、マージ処理及びアニーリング処理を高速に行うことが可能なアニーリング処理装置、アニーリング処理方法及びプログラムを提供できる。
【図面の簡単な説明】
【００１０】
マージ処理を導入する意義について説明する図である。
マージ処理について説明するための図である。
比較例にかかるアニーリング処理を示すフローチャートである。
比較例にかかるマージ処理後のスピン間相互作用及びマージ処理後の外部磁場の具体的な算出方法を説明するための図である。
実施の形態１にかかるアニーリング処理装置の構成を示す機能ブロック図である。
実施の形態１にかかるマージ処理部によって行われるマージ処理について説明するための図である。
実施の形態１にかかる反転処理部の処理の例を示す図である。
実施の形態１にかかるアニーリング処理装置によって行われるアニーリング処理方法を示す図である。
実施の形態１にかかるマージ先行列及びスピン積行列を用いたマージ処理後のスピン間相互作用及びマージ処理後の外部磁場の具体的な算出方法を示す図である。
実施の形態１にかかるマージ処理を一般化した場合について説明するための図である。
実施の形態１においてレプリカ処理を行う場合のスピン積行列について説明するための図である。
実施の形態１においてレプリカ処理を行う場合の局所場の計算方法について説明するための図である。
実施の形態１にかかるアニーリング処理装置によって実行されたアニーリングアルゴリズムの実験結果を示す図である。
実施の形態１にかかるアニーリング処理装置によって実行されたアニーリングアルゴリズムの実験結果を示す図である。
【発明を実施するための形態】
（【００１１】以降は省略されています）

関連特許