特許ウォッチ

公開番号2025021843
公報種別公開特許公報(A)
公開日2025-02-14
出願番号2023125848
出願日2023-08-01
発明の名称モデル生成装置、モデル生成方法、順列生成システム、およびプログラム
出願人株式会社NTTデータグループ,国立大学法人広島大学
代理人弁理士法人志賀国際特許事務所
主分類G06N 99/00 20190101AFI20250206BHJP(計算;計数)
要約【課題】順列あるいは部分順列を生成するための、従来より、2次項の少ないモデルを生成できるモデル生成装置を提供すること。
【解決手段】モデル生成装置は、解く問題が入力されると、m≦nを満たす2つの自然数m、nについて、n個の数から重複なくm個の数を選んでならべた1つの順列を求めるためのモデルに変換する問題変換部を備え、問題変換部は、n個の数からm個を選んだ第1の列Aと、m個の数からn個を選んだ第2の列Bが所定の条件を満たすことを、1つの順列を求める際の制約条件として、モデルに含め、所定の条件は、第1の列Aが順列であり、第2の列Bが、第1の列Aの逆順列であることである。
【選択図】図1
特許請求の範囲【請求項１】
解く問題が入力されると、m≦nを満たす２つの自然数m、nについて、n個の数から重複なくm個の数を選んでならべた１つの順列を求めるためのモデルに変換する問題変換部を備え、
前記問題変換部は、前記n個の数からm個を選んだ第１の列Aと、m個の数からn個を選んだ第２の列Bが所定の条件を満たすことを、前記１つの順列を求める際の制約条件として、前記モデルに含め、
前記所定の条件は、前記第１の列Aが順列であり、前記第２の列Bが、前記第１の列Aの逆順列であることである、
モデル生成装置。
続きを表示（約 1,500 文字）【請求項２】
前記第１の列Aと、前記第２の列Bの各々を構成する整数を、２値ベクトルを用いて表し、
前記２値ベクトルを用いて表すための制約条件を表す式における２次項の個数が、前記２値ベクトルの要素の数の１次式で表される、請求項１に記載のモデル生成装置。
【請求項３】
前記第１の列Aと、前記第２の列Bの各々を構成する整数を、domain-wall表現を用いて表す、請求項２に記載のモデル生成装置。
【請求項４】
前記モデルは、値が最小となるときに前記制約条件を満たし、前記第１の列Aと、前記第２の列Bの各々を構成する整数を表す２値ベクトルを引数とする目的関数である、請求項２または請求項３に記載のモデル生成装置。
【請求項５】
m<nであり、
前記所定の条件は、前記第１の列Aが表す順列が、補助変数行列が表す順列と一致し、前記第２の列Bが表す逆順列のうち、少なくとも前記第１の列Aが表す順列により定義される部分が、前記補助変数行列が表す逆順列と一致していることである、請求項１に記載のモデル生成装置。
【請求項６】
m=nであり、
前記所定の条件は、前記第１の列Aが表す順列が、補助変数行列が表す順列と一致し、前記第２の列Bが表す逆順列が、前記補助変数行列が表す逆順列と一致していることである、請求項１に記載のモデル生成装置。
【請求項７】
解く問題を、m≦nを満たす２つの自然数m、nについて、n個の数から重複なくm個の数を選んでならべた１つの順列を求めるためのモデルに変換するステップを有し、
前記ステップにおいて、前記n個の数からm個を選んだ第１の列Aと、m個の数からn個を選んだ第２の列Bが所定の条件を満たすことを、前記１つの順列を求める際の制約条件として、前記モデルに含め、
前記所定の条件は、前記第１の列Aが順列であり、前記第２の列Bが、前記第１の列Aの逆順列であることである、
モデル生成方法。
【請求項８】
モデル生成装置と、モデル解法装置とを備え、
前記モデル生成装置は、
解く問題が入力されると、m≦nを満たす２つの自然数m、nについて、n個の数から重複なくm個の数を選んでならべた１つの順列を求めるためのモデルに変換する問題変換部を備え、
前記問題変換部は、前記n個の数からm個を選んだ第１の列Aと、m個の数からn個を選んだ第２の列Bが所定の条件を満たすことを、前記１つの順列を求める際の制約条件として、前記モデルに含め、
前記所定の条件は、前記第１の列Aが順列であり、前記第２の列Bが、前記第１の列Aの逆順列であることであり、
前記モデル解法装置は、前記モデルの示す値が最小となる最適解、あるいは最適解の近似解を算出する、
順列生成システム。
【請求項９】
コンピュータを、
解く問題が入力されると、m≦nを満たす２つの自然数m、nについて、n個の数から重複なくm個の数を選んでならべた１つの順列を求めるためのモデルに変換する問題変換部として機能させるためのプログラムであって、
前記問題変換部は、前記n個の数からm個を選んだ第１の列Aと、m個の数からn個を選んだ第２の列Bが所定の条件を満たすことを、前記１つの順列を求める際の制約条件として、前記モデルに含め、
前記所定の条件は、前記第１の列Aが順列であり、前記第２の列Bが、前記第１の列Aの逆順列であることである、
プログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、モデル生成装置、モデル生成方法、順列生成システム、およびプログラムに関する。
続きを表示（約 2,200 文字）【背景技術】
【０００２】
＜量子アニーラーと疑似量子アニーラー＞
量子アニーラーとは、量子効果を用いて組合せ最適化問題を短時間で解く専用計算機である。一方、量子アニーラーには、量子ビットの数が少ないことや、ノイズが原因で正しい計算結果が求まらない場合があるなどの課題もある。疑似量子アニーラーは、通常のCPUやGPU、FPGA、ASICなどの半導体を用いて、量子効果を使わずに、後述するIsingモデルあるいはQUBOモデルを解く装置やソフトウェアである。
【０００３】
＜IsingモデルとQUBOモデル＞
量子アニーラーは、－１または＋１の値をとる量子ビットを変数とする２次式であるIsingモデルを直接扱う。一方、疑似量子アニーラーは、QUBO（Quadratic Unconstrainted Binary Optimization）モデルを扱うことが多い。QUBOモデルは、アルゴリズムの設計が行いやすいように、各量子ビットが０または１の値をとるようにIsingモデルを変更したものであり、QUBOモデルとIsingモデルとは、モデルのトポロジー(２次項で表される相互作用の形状)を変えることなく相互に等価変換可能である。
【０００４】
Isingモデルは、下記の式（１）で表される。式（１）において、集合Ｖは、n個のノードの集合であり、集合Ｅは、ノードを結ぶ辺の集合であり、重みJ
i,j
は、ノードiとノードjを結ぶ辺((i、j)∈E)における相互作用（interaction）の重みであり、重みh
i
は、ノードiのバイアス（bias）の重みであり、変数s
i
は、ノードi（i∈V）のスピンを表し、－１または＋１の値をとる量子ビット（qubit）である。H(S)は、s
i
（iは０からn-1）を要素とするnビットのスピンベクトルSのハミルトニアンである。なお、定数Cはオフセットであり、記述しない場合もある。式（１）における第１和項は、２次項と呼ばれ、第２和項は、１次項と呼ばれる。
【０００５】
TIFF
2025021843000002.tif
17
170
【０００６】
例えば、図１１に示すようなノード構成のIsingモデルは、下記の式（２）となる。なお、図１１において、丸印各々がノードであり、丸印内の数はノードの番号iであり、丸印に付した数はバイアスの重みh
i
であり、丸印を結ぶ辺に付した数は該線により結ばれたノード間の相互作用の重みJ
i,j
である。式（２）においては、式（１）の第１和項に対応する第１項から第８項が２次項であり、式（１）の第２和項に対応する第９から第１３項が１次項である。量子アニーラーあるいは疑似量子アニーラーは、式（２）が入力されると、H(S)が最小となるベクトルS（最適解）を算出する。式（２）の場合、H(S)=-32となる、ベクトルS=[+1, -1, -1, +1, +1, -1]が最適解として算出される。
【０００７】
TIFF
2025021843000003.tif
19
170
【０００８】
QUBOモデルは、下記の式（３）で表される。式（３）においても、集合Vは、n個のノードの集合であり、集合Eは、ノードを結ぶ辺の集合である。重みW
i,j
は、ノードiとノードjを結ぶ辺((i、j)∈E)における相互作用（interaction）の重みであり、重みW
i,i
は、ノードiのバイアス（bias）の重みである。なお、重みW
i,i
は、自己ループ辺（i, i）の重みとみなしてもよい。変数x
i
は、0または１の値をとるビットである。E(X)、すなわち、式（3）は、x
i
（iは０からn-1）を要素とするnビットのベクトルXのエネルギーである。なお、定数Cはオフセットであり、記述しない場合もある。式（３）においても、第１和項は、２次項であり、第２和項は、１次項である。
【０００９】
TIFF
2025021843000004.tif
17
170
【００１０】
例えば、図１２に示すようなノード構成のQUBOモデルは、下記の式（4）となる。なお、図１２において、丸印各々がノードであり、丸印内の数はノードの番号iであり、丸印に付した数はバイアスの重みW
i,i
であり、丸印を結ぶ辺に付した数は該線により結ばれたノード間の相互作用の重みW
i,j
である。式（４）においては、式（３）の第１和項に対応する第１項から第８項が２次項であり、式（３）の第２和項に対応する第９から第１２項が１次項である。疑似量子アニーラーは、式（４）が入力されると、E(X)が最小となるベクトルX（最適解）を算出する。式（４）の場合、E(X)=-7となる、ベクトルX=[1, 0, 0, 1, 1, 0]が最適解として算出される。
（【００１１】以降は省略されています）

関連特許