特許ウォッチ

公開番号2025033424
公報種別公開特許公報(A)
公開日2025-03-13
出願番号2023139132
出願日2023-08-29
発明の名称量子アニーリング制御装置
出願人KDDI株式会社
代理人個人,個人
主分類G06Q 10/04 20230101AFI20250306BHJP(計算;計数)
要約【課題】規模の大きな最適化問題の求解に効率的に量子アニーリングを適用することのできる、量子アニーリング制御装置を提供する。
【解決手段】量子アニーリング装置に対して貪欲法で繰り返して最適化問題を解かせるように制御する、量子アニーリング制御装置であって、前記最適化問題を構成する目的関数の一部を、制約に読み替えた読替制約を設定する第1処理S2と、前記読替制約に少なくとも基づくコストを最小化させるよう前記量子アニーリング装置に指示S6を行い、量子アニーリング結果として前記最適化問題の最適解を得る第2処理を繰り返し実行S8し、繰り返しの各回ごとに読替制約の強さを緩和して適用し、各回での結果を構成する要素を合成した合成要素への更新を行い、繰り返し処理が収束した時点での最適解を構成する要素及び/または合成要素に基づいて、前記最適化問題の最適解を得る。
【選択図】図3
特許請求の範囲【請求項１】
量子アニーリング装置に対して貪欲法で繰り返して最適化問題を解かせるように制御する、古典コンピュータで構成された量子アニーリング制御装置であって、
前記最適化問題を構成する目的関数の一部を、制約に読み替えた読替制約を設定する第１処理と、
前記読替制約に少なくとも基づくコストを最小化させるよう前記量子アニーリング装置に指示を行い、量子アニーリング結果として前記最適化問題の最適解を得る第２処理と、を実行し、
前記第２処理を繰り返し実行し、繰り返しの各回ごとに前記読替制約の強さを緩和して適用し、各回での結果を構成する要素を合成した合成要素への更新を行い、繰り返し処理が収束した時点での最適解を構成する要素及び／または合成要素に基づいて、前記最適化問題の最適解を得ることを特徴とする量子アニーリング制御装置。
続きを表示（約 1,600 文字）【請求項２】
前記最適化問題はバッチスケジューリング問題であって、各バッチには読込処理、計算処理、書込処理の所要時間が設定されており、
前記第１処理では、前記目的関数の一部として総処理時間最小の目的関数を、全てのバッチについて読込または書込の状態に該当していない時刻として定義される隙間の時刻に該当する個数を指定するものとして、前記読替制約を設定することを特徴とする請求項１に記載の量子アニーリング制御装置。
【請求項３】
前記第２処理を繰り返し実行するに際して、前記読替制約における隙間の時刻に該当する個数を、初期値のゼロから繰り返しの各回において増分することを特徴とする請求項２に記載の量子アニーリング制御装置。
【請求項４】
前記第２処理を繰り返し実行する各回において、前記コストを最小化させるものとして、複数のバッチのスケジューリング結果である部分解を得て、当該部分解から１つの合成バッチを得ることを特徴とする請求項３に記載の量子アニーリング制御装置。
【請求項５】
前記合成バッチを構成している要素バッチのうち少なくとも１つのバッチにおける読込処理または書込処理と重複しない箇所が存在する場合に、当該箇所に基づいて当該合成バッチの計算処理の箇所を設定したうえで、当該合成バッチを、前記第２処理の繰り返しの各回において得るスケジューリング問題の部分解を構成する候補として継続して用いることを特徴とする請求項４に記載の量子アニーリング制御装置。
【請求項６】
前記合成バッチを構成している要素バッチのうち少なくとも１つのバッチにおける読込処理または書込処理と重複しない箇所が存在しない場合、当該合成バッチを、前記第２処理の繰り返しの各回において得るスケジューリング問題の部分解を構成する候補からは除外することを特徴とする請求項４に記載の量子アニーリング制御装置。
【請求項７】
前記最適化問題はバッチスケジューリング問題であって、
前記第２処理では、前記最適化問題を構成する前記一部以外の目的関数として、
バッチ処理が並列で処理されている工程の数の総和として定義されるオーバーラップ最大の目的関数と、
バッチ処理の開始時刻である読込時刻の総和としてフェアスケジューリングの目的関数と、
のうち少なくとも１つを用いることを特徴とする請求項２に記載の量子アニーリング制御装置。
【請求項８】
前記前記最適化問題はバッチスケジューリング問題であって、
前記第２処理では、前記コストを定める制約としてさらに、
２つの異なるバッチ同士において同時刻に、読込処理と読込処理が重複せず、読込処理と書込処理が重複せず、書込処理と書込処理が重複しないこととして定義される並列処理不可能の制約を用いることを特徴とする請求項２に記載の量子アニーリング制御装置。
【請求項９】
前記第２処理を繰り返し実行するに際して、前記読替制約における隙間の時刻に該当する個数を、初期値のゼロから繰り返しの各回において増分し、実行可能解として部分解が得られた時点で、前記読替制約における隙間の時刻に該当する個数を、初期値のゼロへと再設定することを特徴とする請求項２に記載の量子アニーリング制御装置。
【請求項１０】
前記第２処理では、前記量子アニーリング装置に対して処理させる決定変数として、
スケジュールを構成する１番目のバッチを指定する第１決定変数と、
当該第１決定変数によって指定された１番目のバッチについて、読込処理を省略して計算処理及び書込処理のみの情報を有し、２番目以降のバッチについて、読込処理、計算処理及び書込処理の情報を有する第２決定変数と、
を用いることを特徴とする請求項２に記載の量子アニーリング制御装置。

発明の詳細な説明【技術分野】
【０００１】
本発明は、量子アニーリング装置を制御して最適化問題を解く量子アニーリング制御装置に関する。
続きを表示（約 2,400 文字）【背景技術】
【０００２】
情報処理システムには次の2つの処理方法がある。
●リアルタイム処理：システムに入力された情報を、逐次処理する
●バッチ処理：システムに入力された情報を蓄積し、任意のトリガーで一括処理する。
【０００３】
このうちバッチ処理は通常、以下の特徴を持つ。
●必要とする計算能力が大きい。なぜならば、蓄積した分、情報が多いからであり、この多い情報を期限内に完了させる必要があることがよくある。例えば、営業時間が日中である場合に日中に蓄積して、営業時間外の夜間にバッチ処理する場合、翌営業時間までの完了が必要となるといった状況がよくある。
●様々なデータベース(DB)を参照する処理が多い。ここで、DBの更新タイミングによる参照内容の前後を防ぐべく、バッチ処理が導入されている。すなわち、バッチ処理においてはDBの書き換え等が間違った順番で行われることでDBの記録やDBを参照した処理結果が不適切なものとなることを防ぐ必要がある。
【０００４】
このような要求に対して、バッチ処理において効率的で実行可能なスケジュールを設定する手法が一般に知られており、当該分野（最適化問題）では次のような用語が用いられている。
●「実行可能」とは、システムを成り立たせるうえで必要不可欠な条件を満たしていることを指す。
●システムを成り立たせるうえで必要不可欠な条件を「制約」と呼ぶ。
例えば同時に処理できない工程が存在する場合、それを満たすことが制約である。
例えば前後してはいけない工程が存在する場合、それを満たすことが制約である。
●制約を満たしていないスケジュールを「制約違反」と呼ぶ。
●「効率的」とは、リソースやコストの消費量が最小限であることを指す。
●最小限または最大限であることが望ましい数値を「目的関数」と呼ぶ。
例えば総処理時間(makespan)を最小にする目的関数が考えられる。
例えば並列に処理できるバッチ数を最大にする目的関数が考えられる。
【０００５】
効率的で実行可能なスケジュールを設定するタスクを「スケジューリング問題」と呼ぶ。スケジューリング問題は、「組合せ最適化問題」の一つである。より一般に「最適化問題」とは、目的関数を持つタスクにおいて最もよい設定値を求める問題であり、制約はあってもなくてもよい。例えば制約として四角形の辺の合計長さが固定された状態で、目的関数として最も面積の大きい四角形を求める問題が最適化問題に相当する。
【０００６】
組合せ最適化問題とは、最適化問題の中でも、上記の最大面積を求める問題のように設定値が連続であるのではなく、設定値が非連続値の問題である。すなわち、不連続な設定値(以下、要素)を組合せることから組合せ最適化問題と呼ばれており、例えば巡回セールスマン問題やナップザック問題が組合せ最適化問題に相当する。設定値が連続値である問題よりも解くことが難しく、計算量理論においてNP困難クラスの問題として知られている。
【０００７】
組合せ最適化問題の分野では、以下のような用語を使用する。
●制約：問題としているタスクが満たさなくてはいけない条件
●目的関数：問題としているタスクで数値がよければよいほど望ましい数値
●要素：組合わせる対象（例えば、バッチ処理を構成する個別のバッチ）
●決定変数：これを決めると問題の答えが確定する変数（例えば、バッチ処理における各バッチの処理順序など）
●解：決定変数に実数を入れた状態のリスト（解は必ずしも現実で実行できるとは限らない。）
■実行可能解：制約をクリアした解（すなわち、現実で実行できる解）
■最適解：アルゴリズムが出した解の中でもっとも目的関数値がよい実行可能解
■大域最適解：すべての実行可能解の中でもっとも目的関数値がよい実行可能解
■近似解：実用上それなりの目的関数値を得られている実行可能解
【０００８】
組合せ最適化問題は主にヒューリスティック手法やメタヒューリスティクス手法で求解される。大規模な問題では計算量削減のため、大域最適解ではなく近似解を出す手法が採用される。非特許文献２等に開示される通り、近似解を得られるメタヒューリスティクス手法として、イジングマシン等によるアニーリング法、貪欲法、局所探索法、タブー探索法、遺伝的アルゴリズム等があり、それぞれ研究されている。これらの手法を現実問題に適用する既存技術は多数あり、例えば特許文献２を挙げることができる。アニーリング法は量子デバイスを使うことで高速に解を出す研究があり、例えば非特許文献１に開示されている。
【０００９】
アニーリング法を実行するには、求解可能な形の立式をする必要がある。この際、決定変数自体が目的関数となる問題設定が生まれる場合があり、答えが出うる余裕を持った数の決定変数を用意する方法が考えられる。一方で、決定変数の数が大きいことは問題が大規模になることと同義であり、解の精度が落ちてしまう。
【００１０】
このような点について、特許文献４では、決定変数の数を先に調整したのち、求解するようにしている。また、一般的な大規模問題に対して問題を分割して要素数を疑似的に減らす手法もあり、アニーリングで行った例として特許文献１がある。また、大規模問題に強い手法と弱い手法を併用することで精度を高める手法もあり、貪欲法を使ったのちにアニーリング使う例として、特許文献３がある。
【先行技術文献】
【特許文献】
（【００１１】以降は省略されています）

関連特許