特許ウォッチ

公開番号2024092146
公報種別公開特許公報(A)
公開日2024-07-08
出願番号2022207874
出願日2022-12-26
発明の名称計算方法、計算システム、及びプログラム
出願人学校法人早稲田大学
代理人弁理士法人ドライト国際特許事務所
主分類G06N 99/00 20190101AFI20240701BHJP(計算;計数)
要約【課題】イジングマシンを用いて制約付き組合せ最適化問題を解く際に必要なスピン変数の個数を削減し、イジングマシンの性能を改善させる。
【解決手段】線形の等式制約のある組合せ最適化問題を複数のスピン変数で表されるイジングモデルで解くために、古典コンピュータ20は、複数のスピン変数のうち少なくとも1つを第1スピンとして選択し、第1スピン以外を第2スピンとして設定し、線形の等式制約に基づいて第1スピンを第2スピンの一次式で表すことで、目的関数項と制約項との和で与えられるイジングモデルのハミルトニアンを第2スピンの関数として定義し、イジングマシン30は、ハミルトニアンに対する最適解を計算する。古典コンピュータ20は、イジングマシン30で計算された最適解から、第2スピンの一次式に基づいて第1スピンの値を計算することによって、イジングモデルの最適解を計算する。
【選択図】図8

特許請求の範囲【請求項１】
線形の等式制約のある組合せ最適化問題を複数のスピン変数で表されるイジングモデルで解くための計算方法であって、
古典コンピュータにより、
前記複数のスピン変数のうち少なくとも１つを第１スピンとして選択し、前記複数のスピン変数のうち前記第１スピン以外を第２スピンとして設定し、前記線形の等式制約に基づいて前記第１スピンを前記第２スピンの一次式で表すことで、目的関数項と制約項との和で与えられる前記イジングモデルのハミルトニアンを前記第２スピンの関数として定義し、
イジングマシンにより、
前記ハミルトニアンに対する最適解を計算し、
前記古典コンピュータにより、
前記イジングマシンで計算された最適解から、前記一次式に基づいて前記第１スピンの値を計算することによって、前記イジングモデルの最適解を計算する、計算方法。
続きを表示（約 820 文字）【請求項２】
前記一次式における一次の項の係数及び定数項は整数である、請求項１に記載の計算方法。
【請求項３】
線形の等式制約のある組合せ最適化問題を複数のスピン変数で表されるイジングモデルで解くための計算システムであって、
前記複数のスピン変数のうち少なくとも１つを第１スピンとして選択し、前記複数のスピン変数のうち前記第１スピン以外を第２スピンとして設定し、前記線形の等式制約に基づいて前記第１スピンを前記第２スピンの一次式で表すことで、目的関数項と制約項との和で与えられる前記イジングモデルのハミルトニアンを前記第２スピンの関数として定義する古典コンピュータと、
前記ハミルトニアンに対する最適解を計算するイジングマシンと、
を備え、
前記古典コンピュータは、前記イジングマシンで計算された最適解から、前記一次式に基づいて前記第１スピンの値を計算することによって、前記イジングモデルの最適解を計算する、計算システム。
【請求項４】
線形の等式制約のある組合せ最適化問題を複数のスピン変数で表されるイジングモデルで解くための計算方法をイジングマシンと併用して古典コンピュータに実行させるためのプログラムであって、
前記複数のスピン変数のうち少なくとも１つを第１スピンとして選択し、前記複数のスピン変数のうち前記第１スピン以外を第２スピンとして設定し、前記線形の等式制約に基づいて前記第１スピンを前記第２スピンの一次式で表すことで、目的関数項と制約項との和で与えられる前記イジングモデルのハミルトニアンを前記第２スピンの関数として定義し、
前記イジングマシンで計算された前記ハミルトニアンに対する最適解から、前記一次式に基づいて前記第１スピンの値を計算することによって、前記イジングモデルの最適解を計算するプロセスを実行させるためのプログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、組合せ最適化問題を解くための計算方法、計算システム、及びプログラムに関する。
続きを表示（約 2,200 文字）【背景技術】
【０００２】
多数の組合せの中から最も良い組合せを選ぶ組合せ最適化問題をイジングモデル、又はイジングモデルと等価なquadratic unconstrained binary optimization（ＱＵＢＯ）モデルに変換し、イジングマシンを用いて求解する技術が知られている。組合せ最適化問題とは、与えられた制約のもとで目的関数を最小化又は最大化する変数の組合せを求める問題である。
【０００３】
等式制約のある組合せ最適化問題をイジングモデルに変換する際、ハミルトニアンＨは、スピンと呼ばれる変数（以下、スピン変数）を用いて目的関数Ｈoと制約項Ｈcの和で与えられる。従来、制約項Ｈcはペナルティ法を用いて与えられてきた。制約を満たすときＨc＝０となり、制約を満たす解を実行可能解と呼ぶ。ペナルティ法は、非実行可能解（制約を満たさない解）のエネルギーを増加させる。そのため、スピン配置空間において、エネルギーの小さな実行可能解がエネルギーの大きな非実行可能解によって分離される（例えば、非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００４】
Andrew Lucas, “Ising formulations of many NP problems”, Frontiers in Physics, Volume 2, Article 5, 2014.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、ペナルティ法では、量子揺らぎや熱揺らぎが小さいとき、分離された実行可能解の間の遷移確率が小さくなるため、イジングマシンの性能が悪化するという課題がある。また、イジングマシンに入力可能なスピン変数の個数には上限があるため、イジングマシンを用いて大規模な組合せ最適化問題を解くことができないという課題がある。
【０００６】
本発明は、上記課題に鑑みてなされたものであり、イジングマシンを用いて制約付き組合せ最適化問題を解く際に必要なスピン変数の個数を削減し、イジングマシンの性能を改善させる計算方法、計算システム、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係る計算方法は、線形の等式制約のある組合せ最適化問題を複数のスピン変数で表されるイジングモデルで解くための計算方法であって、古典コンピュータにより、複数のスピン変数のうち少なくとも１つを第１スピンとして選択し、複数のスピン変数のうち第１スピン以外を第２スピンとして設定し、線形の等式制約に基づいて第１スピンを第２スピンの一次式で表すことで、目的関数項と制約項との和で与えられるイジングモデルのハミルトニアンを第２スピンの関数として定義し、イジングマシンにより、ハミルトニアンに対する最適解を計算する。古典コンピュータは、イジングマシンで計算された最適解から、一次式に基づいて第１スピンの値を計算することによって、イジングモデルの最適解を計算する。
【０００８】
本発明に係る計算システムは、線形の等式制約のある組合せ最適化問題を複数のスピン変数で表されるイジングモデルで解くための計算システムであって、複数のスピン変数のうち少なくとも１つを第１スピンとして選択し、複数のスピン変数のうち第１スピン以外を第２スピンとして設定し、線形の等式制約に基づいて第１スピンを第２スピンの一次式で表すことで、目的関数項と制約項との和で与えられるイジングモデルのハミルトニアンを第２スピンの関数として定義する古典コンピュータと、ハミルトニアンに対する最適解を計算するイジングマシンと、を備える。古典コンピュータは、イジングマシンで計算された最適解から、一次式に基づいて第１スピンの値を計算することによって、イジングモデルの最適解を計算する。
【０００９】
本発明に係るプログラムは、線形の等式制約のある組合せ最適化問題を複数のスピン変数で表されるイジングモデルで解くための計算方法をイジングマシンと併用して古典コンピュータに実行させるためのプログラムであって、複数のスピン変数のうち少なくとも１つを第１スピンとして選択し、複数のスピン変数のうち第１スピン以外を第２スピンとして設定し、線形の等式制約に基づいて第１スピンを第２スピンの一次式で表すことで、目的関数項と制約項との和で与えられるイジングモデルのハミルトニアンを第２スピンの関数として定義し、イジングマシンで計算されたハミルトニアンに対する最適解から、一次式に基づいて第１スピンの値を計算することによって、イジングモデルの最適解を計算するプロセスを実行させる。
【発明の効果】
【００１０】
本発明によれば、線形の等式制約のある組合せ最適化問題を複数のスピン変数で表されるイジングモデルで解くために、古典コンピュータが、線形の等式制約に基づいてあるスピン変数を他のスピン変数の一次式で表すようにした。これにより、イジングマシンがイジングモデルの最適解を計算する際に必要なスピン変数を削減することができ、イジングマシンの性能を改善させることが可能となる。
【図面の簡単な説明】
（【００１１】以降は省略されています）

関連特許