JP7468655B2 - 不整合判定装置、方法、および、プログラム - Google Patents

Description

本発明は、組合せ最適化問題におけるエネルギーを表す式の中に不整合が生じているか否かを判定する不整合判定装置、不整合判定方法および不整合判定プログラムに関する。

特許文献１には、組合せ最適化問題をシミュレーテッドアニーリングによって解くことが記載されている。

また、量子アニーリングマシンの実用化を機に、組合せ最適化問題を解くことがより一般的になりつつある。組合せ最適化問題の例として、巡回セールスマン問題、ナップサック問題、グラフ分割問題等が挙げられる。ただし、組合せ最適化問題はこれらの問題に限られない。

シミュレーテッドアニーリングまたは量子アニーリングによって、組合せ最適化問題を解くコンピュータには、イジングモデルのエネルギー関数またはＱＵＢＯ（Quadratic Unconstrained Binary Optimization ）のエネルギー関数が入力される。

イジングモデルは、個々のスピンによって磁性体の振る舞いを表わす統計力学上のモデルであるが、組合せ最適化問題の求解にも適用可能である。イジングモデルでは、個々のスピンの状態は、“１”または“－１”で表される。

また、個々のスピンの状態を“１”または“０”で表すモデルとしてＱＵＢＯも知られている。

なお、イジングモデルにおける“１”やＱＵＢＯにおける“１”を第１の値と称することができる。そして、イジングモデルにおける“－１”やＱＵＢＯにおける“０”を第２の値と称することができる。

イジングモデルのエネルギー関数と、ＱＵＢＯのエネルギー関数とは、相互に変換可能である。

現状では、主に、イジングモデルのエネルギー関数やＱＵＢＯのエネルギー関数を入力として、一般的なコンピュータを用いて、シミュレーテッドアニーリングで組合せ最適化問題の解が求められている。この手法の例を説明する。ここでは、巡回セールスマン問題の解を求める場合を例にして説明する。

まず、巡回セールスマン問題におけるエネルギーを表わす式を作成する。組合せ最適化問題におけるエネルギーを表わす式の作成を、定式化と称する場合がある。巡回セールスマン問題の定式化によって得られる式の例として、以下に示す式（１）が挙げられる。

式（１）において、ｊは時刻を表わし、ｖ，ｕは都市を表わす。また、ｘ_ｖ，ｊは、時刻ｊにセールスマンが都市ｖにいるか否かを表わす変数であり、スピンに該当する。ｘ_ｖ，ｊ＝１ならば、時刻ｊにセールスマンが都市ｖにいることを表わし、ｘ_ｖ，ｊ＝０ならば、時刻ｊにセールスマンが都市ｖにいないことを表わす。また、式（１）において、Ｗ_ｕｖは、都市ｕと都市ｖの距離であり、都市の組毎に予め定数として定められている。αおよびβは、予め定数として定められる。

式（１）における右辺の第１項は、セールスマンは同じ都市を２回以上通過することはないという制約を表わす。

式（１）における右辺の第２項は、１つの時刻において、セールスマンが１つの都市にしか存在しないという制約を表わす。

式（１）における右辺の第３項は、セールスマンが通過する都市間の距離を表わす。この右辺の第３項は、制約を表す項ではない。一方、この右辺の第３項は、巡回セールスマン問題の解を得たいユーザにとっては値を最小化したい事項を表す項である。このように、制約を表さない項であって、組合せ最適化問題の解を得たいユーザにとって値を最小化したい事項を表す項を、目的関数と称する。すなわち、式（１）における右辺の第３項は、目的関数である。

式（１）に例示するような組合せ最適化問題におけるエネルギーを表わす式を作成したならば、その式を、イジングモデルのエネルギー関数、または、ＱＵＢＯのエネルギー関数に変換する。この変換方法は、公知である。

イジングモデルのエネルギー関数は、以下の式（２）のように表される。

式（２）におけるｓ_ｉ，ｓ_ｊは、スピンの状態を表わす変数である。この変数における添え字によってスピンが識別される。Ｊ_ｉｊは、ｉ，ｊに応じた定数であり、ｈ_ｉは、ｉに応じた定数である。

また、ＱＵＢＯのエネルギー関数は、以下の式（３）のように表される。

式（３）におけるｘ_ｉ，ｘ_ｊは、スピンの状態を表わす変数である。この変数における添え字によってスピンが識別される。Ｑ_ｉｊは、ｉ，ｊに応じた定数である。

式（２）および式（３）は、スピンの状態を表す変数の２次式である。また、式（１）も、スピンの状態を表す変数の２次式である。従って、式（１）を、式（２）または式（３）に変換することができる。

定式化によって得た式において、スピンの状態を表す変数の次数が３次以上であったとしても、スピンの状態を表す複数の変数を１つの変数に置き換えることによって、スピンの状態を表す変数の次数を２まで下げることができる。上記の置き換えに用いられる変数を補助変数と称する。従って、定式化によって得た式において、スピンの状態を表す変数の次数が３次以上であったとしても、補助変数を用いることによって、イジングモデルのエネルギー関数（式（２））、または、ＱＵＢＯのエネルギー関数（式（３））を得ることができる。

イジングモデルまたはＱＵＢＯのエネルギー関数が得られたならば、そのエネルギー関数をシミュレーテッドアニーリングに適用し、エネルギーが最小になるときの各スピンの状態を特定する。そして、その各スピンの状態を、組合せ最適化問題（本例では、巡回セールスマン問題）に応じて解釈することで、最適解が得られる。

また、非特許文献１には、ＱＵＢＯのエネルギー関数に変換される、定式化された式（組合せ最適化問題におけるエネルギーを表す式）において、種々の制約がどの様に表現されるかが記載されている。

特開平１０－２９３７５６号公報

Fred Glover, Gary Kochenberger, Yu Du, "Quantum Bridge Analytics I: A Tutorial on Formulating and Using QUBO Models", ［２０２０年６月３日検索］、インターネット<URL : https://arxiv.org/ftp/arxiv/papers/1811/1811.11538.pdf>

ユーザによって定式化された式（組合せ最適化問題におけるエネルギーを表す式）の中に不整合が生じていたとしても、その式を、イジングモデルのエネルギー関数またはＱＵＢＯのエネルギー関数に変換することができる。そして、そのエネルギー関数に対してアニーリングを実行することで、組合せ最適化問題の解を得ることができる。

しかし、組合せ最適化問題の解が、適切でない場合がある。組合せ最適化問題の解が適切でないとユーザが判断することができた場合であっても、ユーザがその原因を特定することは困難である。アニーリングは確率的な処理であるので、入力されるエネルギー関数が適切であったとしても、適切でない解が導出されることもあり得る。また、上記のように、ユーザによって定式化された式の中に不整合が生じていることに起因して、適切でない解が導出されることもある。

そこで、定式化された式（組合せ最適化問題におけるエネルギーを表す式）の中に不整合が生じているか否かを判定できることが好ましい。

そこで、組合せ最適化問題におけるエネルギーを表す式に不整合が生じているか否かを判定できる不整合判定装置、不整合判定方法および不整合判定プログラムを提供することを目的とする。

本発明による不整合判定装置は、個々のスピンの状態を第１の値または第２の値で表すモデルのエネルギー関数に変換される、組合せ最適化問題におけるエネルギーを表す式を目的関数を表す項および複数の項に分割する分割手段と、複数の項が表す制約間に不整合が生じているか否かを判定する不整合判定手段を備えることを特徴とする。

本発明による不整合判定方法は、コンピュータが、個々のスピンの状態を第１の値または第２の値で表すモデルのエネルギー関数に変換される、組合せ最適化問題におけるエネルギーを表す式を目的関数を表す項および複数の項に分割し、複数の項が表す制約間に不整合が生じているか否かを判定することを特徴とする。

本発明による不整合判定プログラムは、コンピュータに、個々のスピンの状態を第１の値または第２の値で表すモデルのエネルギー関数に変換される、組合せ最適化問題におけるエネルギーを表す式を目的関数を表す項および複数の項に分割する分割処理、および、複数の項が表す制約間に不整合が生じているか否かを判定する不整合判定処理を実行させる。

本発明によれば、組合せ最適化問題におけるエネルギーを表す式に不整合が生じているか否かを判定できる。

本発明の第１の実施形態の不整合判定装置の構成例を示すブロック図である。 第１の実施形態の処理経過の例を示すフローチャートである。 第２の実施形態の処理経過の例を示すフローチャートである。 本発明の第３の実施形態の不整合判定装置の構成例を示すブロック図である。 スピンの状態を表す各変数を定義した文字列の例を示す図である。 第３の実施形態の処理経過の例を示すフローチャートである。 本発明の各実施形態の不整合判定装置に係るコンピュータの構成例を示す概略ブロック図である。 本発明の不整合判定装置の概要を示すブロック図である。

以下、本発明の実施形態を図面を参照して説明する。

以下に示す各実施形態では、定式化された式（組合せ最適化問題におけるエネルギーを表す式）がＱＵＢＯのエネルギー関数に変換される場合を例にして説明する。この場合、スピンの状態を表す変数は、１または０の値をとる。ただし、後述するように、定式化された式がイジングモデルのエネルギー関数に変換される場合にも、本発明を適用してよい。

実施形態１．
図１は、本発明の第１の実施形態の不整合判定装置の構成例を示すブロック図である。第１の実施形態の不整合判定装置１は、入力部２と、分割部３と、不整合判定部４と、提示部５とを備える。

入力部２には、定式化された式（組合せ最適化問題におけるエネルギーを表す式）が入力される。

入力部２は、例えば、光学ディスクなどのデータ記録媒体に記録されたデータ（本実施形態では、組合せ最適化問題におけるエネルギーを表す式）を読み込むデータ読み込み装置によって実現されてもよい。ただし、入力部２は、そのようなデータ読み込み装置に限定されず、ユーザが式を入力するためのキーボード等の入力デバイスであってもよい。

分割部３は、入力部２を介して、式（組合せ最適化問題におけるエネルギーを表す式）を取り込む。そして、分割部３は、その式を、複数の項に分割する。

例えば、入力部２に、以下に示す式（４）が入力されたとする。

式（４）において、α、β、γは定数である。また、ｘ_ｉ，ｘ_１，ｘ_２は、スピンの状態を表す変数であり、この変数における添え字によってスピンが識別される。各実施形態では、スピンの状態を表す変数は、１または０の値をとる。式（４）の例では、スピンは１からＮまでの整数によって識別される。ｃ_ｉは、iに対応する定数である。

式（４）が入力された場合、分割部３は、式（４）の右辺を項毎に分割する。この結果、

と、β（１－ｘ_１）^２と、γ（１－ｘ_２）^２と、

の各項が得られる。

分割部３が項毎に式を分割することによって得られる項は、制約を表す項と、目的関数とに分けられる。以下、制約を表す項を、制約項と記す。上記の例では、

と、β（１－ｘ_１）^２と、γ（１－ｘ_２）^２とが制約項に該当する。

また、

が目的関数に該当する。前述のように、目的関数は、制約を表さない項であって、組合せ最適化問題の解を得たいユーザにとって値を最小化したい事項を表す項である。

本実施形態では、制約項が２個以上得られるものとする。

また、ここでは、制約項が“定数×（式Ａ－式Ｂ）^２”で表される場合を例にして説明する。また、この形式の制約項は、式Ａ＝式Ｂであるという制約を表している。ここで、式Ａおよび式Ｂは、スピンの状態を表す変数そのものであってもよい。また、式Ａおよび式Ｂは、スピンの状態を表す変数を用いた式であってもよい。また、式Ａおよび式Ｂは、例えば、定数（例えば、“１”等）であってもよい。

上記のように３つの制約項が得られた場合、１番目の制約項は、以下に示す式（５）という制約を表している。

換言すれば、１番目の制約項は、１＝ｘ_１＋ｘ_２＋・・・＋ｘ_Ｎという制約を表している。

また、上記の２番目の制約項は、１＝ｘ_１という制約を表している。

また、上記の３番目の制約項は、１＝ｘ_２という制約を表している。

不整合判定部４は、分割部３が項毎に式を分割することによって得られる項の中から、２個以上の制約項を全て抽出し、制約項毎に、制約を特定する。上記の例では、前述の３つの制約項を全て抽出し、制約項毎に、１＝ｘ_１＋ｘ_２＋・・・＋ｘ_Ｎという制約、１＝ｘ_１という制約、１＝ｘ_２という制約をそれぞれ特定する。

そして、不整合判定部４は、特定した制約間に不整合がある場合に、入力された式（組合せ最適化問題におけるエネルギーを表す式）の中に、制約に関する不整合が生じていると判定する。また、不整合判定部４は、特定した制約間に不整合がない場合には、入力された式の中に、制約に関する不整合が生じていないと判定する。

ここで、不整合判定部４が、特定した制約間に不整合があるか否かを判定する動作について説明する。不整合判定部４は、「制約を表す式」を、別の「制約を表す式」に代入し、その結果、不整合が生じているか否かを判定する。なお、不整合判定部４は、１つの「制約を表す式」に、複数の「制約を表す式」を代入してもよい。「制約を表す式」を、別の「制約を表す式」に代入し、その結果、不整合が生じているならば、不整合判定部４は、「代入した式」に対応する制約と、「代入された式」に対応する制約との間に不整合があると判定する。なお、不整合判定部４は、「代入した式」および「代入された式」以外の式に対応する制約は、上記の不整合とは関連がないと判定する。また、代入の結果、不整合が生じていないならば、不整合判定部４は、「代入した式」に対応する制約と、「代入された式」に対応する制約との間に不整合がないと判定する。

より具体的に説明する。不整合判定部４が、前述の制約を表す式“１＝ｘ_１＋ｘ_２＋・・・＋ｘ_Ｎ”、“１＝ｘ_１”および“１＝ｘ_２”を特定したとする。そして、“１＝ｘ_１”および“１＝ｘ_２”を、“１＝ｘ_１＋ｘ_２＋・・・＋ｘ_Ｎ”に代入できるので、不整合判定部４は、“１＝ｘ_１”および“１＝ｘ_２”を、“１＝ｘ_１＋ｘ_２＋・・・＋ｘ_Ｎ”に代入する。すると、“１＝１＋１＋ｘ_３＋ｘ_４＋・・・＋ｘ_Ｎ”となり、この式を変形すると、“ｘ_３＋ｘ_４＋・・・＋ｘ_Ｎ＝－１”となる。ここで、ｘ_３，ｘ_４，・・・，ｘ_Ｎは、いずれも、１または０の値をとるので、“ｘ_３＋ｘ_４＋・・・＋ｘ_Ｎ＝－１”における左辺の取り得る値は、０からＮ－２までの整数であり、左辺の値が－１になることはない。よって、不整合判定部４は、代入した式“１＝ｘ_１”および“１＝ｘ_２”に対応する制約と、代入された式“１＝ｘ_１＋ｘ_２＋・・・＋ｘ_Ｎ”に対応する制約の間に不整合があると判定する。そして、その結果、不整合判定部４は、入力された式に、制約に関する不整合が生じていると判定する。

提示部５は、不整合判定部４による判定結果を、例えば、不整合判定装置１が備えるディスプレイ装置（図１において図示略）に表示する。例えば、上記の場合、提示部５は、１＝ｘ_１＋ｘ_２＋・・・＋ｘ_Ｎという制約、１＝ｘ_１という制約、および１＝ｘ_２という制約の間に不整合があり、入力された式の中に、制約に関する不整合が生じているということを、ディスプレイ装置上に表示する。また、入力された式の中に、制約に関する不整合が生じていないと判定された場合、提示部５は、その判定結果をディスプレイ上に表示する。

制約に関する不整合の他の例を示す。以下に示す式（６）が入力されたとする。

この場合、分割部３は、式（６）の右辺の第１項および第２項を得る。この２つの項はいずれも制約項であるので、不整合判定部４は、この２つの制約項を抽出する。そして、不整合判定部４は、第１項から、１＝ｘ_１＋ｘ_２＋・・・＋ｘ_Ｎという制約を特定し、第２項から、２＝ｘ_１＋ｘ_２＋・・・＋ｘ_Ｎという制約を特定する。後者の式を前者の式に代入すると、“１＝２”という成立し得ない式が得られる。よって、不整合判定部４は、１＝ｘ_１＋ｘ_２＋・・・＋ｘ_Ｎという制約と、２＝ｘ_１＋ｘ_２＋・・・＋ｘ_Ｎという制約との間に不整合があり、入力された式の中に、制約に関する不整合が生じていると判定する。なお、式（６）の右辺の第１項は、変数ｘ_１～ｘ_Ｎのうち１つだけが１であることを表し、式（６）の右辺の第２項は、変数ｘ_１～ｘ_Ｎのうち２つだけが１であることを表しているので、確かに、制約に関する不整合があることになる。

分割部３、不整合判定部４および提示部５は、例えば、不整合判定プログラムに従って動作するコンピュータのＣＰＵ（Central Processing Unit ）によって実現される。この場合、ＣＰＵは、コンピュータのプログラム記憶装置等のプログラム記録媒体から不整合判定プログラムを読み込み、その不整合判定プログラムに従って、分割部３、不整合判定部４および提示部５として動作すればよい。この点は、後述の第２の実施形態でも同様である。

次に、処理経過について説明する。図２は、第１の実施形態の処理経過の例を示すフローチャートである。既に説明した事項については、適宜、説明を省略する。

入力部２に、組合せ最適化問題におけるエネルギーを表す式が入力されると、分割部３は、その式を、複数の項に分割する（ステップＳ１）。

次に、不整合判定部４は、ステップＳ１で得られた各項の中から、２個以上の制約項を全て抽出し、制約項毎に、制約を特定する（ステップＳ２）。

そして、不整合判定部４は、特定した制約間に不整合があるか否かを判定する（ステップＳ３）。不整合判定部４は、「制約を表す式」を、別の「制約を表す式」に代入し、その結果、不整合が生じるか否かを判定すればよい。代入の結果、不整合が生じるならば、不整合判定部４は、代入した式に対応する制約と、代入された式に対応する制約との間に不整合があると判定すればよい。また、代入の結果、不整合が生じないならば、不整合判定部４は、代入した式に対応する制約と、代入された式に対応する制約との間に不整合がないと判定すればよい。

特定した制約間に不整合があると判定した場合（ステップＳ３のＹｅｓ）、不整合判定部４は、入力された式に制約に関する不整合があると判定する（ステップＳ４）。この場合、提示部５は、不整合が生じている制約を提示するとともに、入力された式に制約に関する不整合があることを提示する（ステップＳ５）。

また、特定した制約間に不整合がないと判定した場合（ステップＳ３のＮｏ）、不整合判定部４は、入力された式に制約に関する不整合がないと判定する（ステップＳ６）。この場合、提示部５は、入力された式に制約に関する不整合がないことを提示する（ステップＳ７）。

なお、提示部５は、不整合判定装置１が備えるディスプレイ装置（図１において図示略）に情報を表示することによって、情報をユーザに提示すればよい。ただし、提示部５は、他の態様で、情報をユーザに提示してもよい。この点は、他の実施形態においても同様である。

上記の説明では、制約項が“定数×（式Ａ－式Ｂ）^２”で表され、この制約項が“式Ａ＝式Ｂ”という制約を表している場合を例にして説明した。制約項の形式はこの形式に限定されず、種々の形式で表された制約項が、個別に制約を表していてもよい。

以下に、種々の制約項や、それらの制約項が表す制約を示す。なお、以下に示す式Ａ、式Ｂ、式Ｃは、スピンの状態を表す変数そのものであってもよい。また、以下に示す式Ａ、式Ｂ、式Ｃは、スピンの状態を表す変数を用いた式であってもよい。また、以下に示す式Ａ、式Ｂ、式Ｃは、定数（例えば、“１”等）であってもよい。

例えば、“定数×（式Ａ×式Ｂ）”と表される制約項があってもよい。この制約項は、“式Ａ＋式Ｂ≦１”という制約を表す。すなわち、不整合判定部４は、“定数×（式Ａ×式Ｂ）”と表される制約項を抽出した場合、この制約項に対応する制約として、“式Ａ＋式Ｂ≦１”という制約を特定する。

また、例えば、“定数×（１－式Ａ－式Ｂ＋式Ａ×式Ｂ）” と表される制約項があってもよい。この制約項は、“式Ａ＋式Ｂ≧１”という制約を表す。すなわち、不整合判定部４は、“定数×（１－式Ａ－式Ｂ＋式Ａ×式Ｂ）” と表される制約項を抽出した場合、この制約項に対応する制約として、“式Ａ＋式Ｂ≧１”という制約を特定する。

また、例えば、“定数×（１－式Ａ－式Ｂ＋２×式Ａ×式Ｂ）” と表される制約項があってもよい。この制約項は、“式Ａ＋式Ｂ＝１”という制約を表す。すなわち、不整合判定部４は、“定数×（１－式Ａ－式Ｂ＋２×式Ａ×式Ｂ）” と表される制約項を抽出した場合、この制約項に対応する制約として、“式Ａ＋式Ｂ＝１”という制約を特定する。

また、例えば、“定数×（式Ａ－式Ａ×式Ｂ）”と表される制約項があってもよい。この制約項は、“式Ａ≦式Ｂ” という制約を表す。すなわち、不整合判定部４は、“定数×（式Ａ－式Ａ×式Ｂ）”と表される制約項を抽出した場合、この制約項に対応する制約として、“式Ａ≦式Ｂ”という制約を特定する。

また、例えば、“定数×（式Ａ×式Ｂ＋式Ａ×式Ｃ＋式Ｂ×式Ｃ）” と表される制約項があってもよい。この制約項は、“式Ａ＋式Ｂ＋式Ｃ≦１”という制約を表す。すなわち、不整合判定部４は、“定数×（式Ａ×式Ｂ＋式Ａ×式Ｃ＋式Ｂ×式Ｃ）” と表される制約項を抽出した場合、この制約項に対応する制約として、“式Ａ＋式Ｂ＋式Ｃ≦１”という制約を特定する。

また、例えば、“定数×（式Ａ＋式Ｂ－２×式Ａ×式Ｂ）” と表される制約項があってもよい。この制約項は、“式Ａ＝式Ｂ”という制約を表す。すなわち、不整合判定部４は、“定数×（式Ａ＋式Ｂ－２×式Ａ×式Ｂ）” と表される制約項を抽出した場合、この制約項に対応する制約として、“式Ａ＝式Ｂ”という制約を特定する。

そして、不整合判定部４は、特定した制約間に不整合があるか否かを判定する。既に説明したように、不整合判定部４は、「制約を表す式」を、別の「制約を表す式」に代入し、その結果、不整合が生じるか否かを判定すればよい。代入の結果、不整合が生じるならば、不整合判定部４は、代入した式に対応する制約と、代入された式に対応する制約との間に不整合があると判定すればよい。また、代入の結果、不整合が生じないならば、不整合判定部４は、代入した式に対応する制約と、代入された式に対応する制約との間に不整合がないと判定すればよい。

本実施形態では、不整合判定部４が、定式化された式を分割することによって得られた項のうち、制約項毎に、制約を特定する。そして、不整合判定部４は、特定した制約間に不整合があるか否かを判定し、不整合があるならば、定式化された式の中に制約に関する不整合が生じていると判定する。また、不整合がないならば、定式化された式の中に制約に関する不整合が生じていないと判定する。従って、本実施形態によれば、定式化された式の中に不整合が生じているか否かを判定することができる。

実施形態２．
本発明の第２の実施形態の不整合判定装置は、第１の実施形態の不整合判定装置と同様に、図１に示すブロック図で表すことができるので、図１を用いて第２の実施形態を説明する。第１の実施形態と同様の事項については、適宜、説明を省略する。

第２の実施形態における入力部２および分割部３は、第１の実施形態における入力部２および分割部３と同様である。

また、第２の実施形態の不整合判定装置１は、組合せ最適化問題におけるエネルギーを表す式の中に、補助変数に関する不整合が生じているか否かを判定する。補助変数は、定式化によって得た式において、スピンの状態を表す変数の次数が３次以上であった場合に、スピンの状態を表す変数の次数を２まで下げるために、スピンの状態を表す変数の置き換えに用いられる変数である。

第２の実施形態では、不整合判定部４は、補助変数を用いた式を予め記憶している。以下の説明では、この予め記憶されている式をパターン式と記す。パターン式において、補助変数以外の変数は、ＱＵＢＯにおけるスピンの状態を表す変数である。そして、パターン式では、スピンの状態を表す変数の次数は２である。

パターン式の例として、以下に示す式（７）が挙げられる。

ｘ_１ｘ_２－２ｘ_１ｙ－２ｘ_２ｙ＋ｘ_３ｙ＋３ｙ ・・・（７）

式（７）において、ｘ_１，ｘ_２，ｘ_３は、スピンの状態を表す変数であり、この変数における添え字によってスピンが識別される。また、ｙは、補助変数である。

式（７）は、スピンの状態を表す変数の３次式であるｘ_１ｘ_２ｘ_３の次数を２に下げるために、ｙ＝ｘ_１ｘ_２として、表された式である。

式（７）に示すパターン式が存在する場合、ｙは補助変数であるということができる。また、補助変数は、式（７）を包含する式では、式（７）以外で用いられないことが一般的である。

以下、不整合判定部４が、式（７）に例示するパターン式を予め記憶している場合を例にして説明する。ただし、不整合判定部４は、他のパターン式を予め記憶していてもよい。また、不整合判定部４は、複数のパターン式を記憶していてもよい。

第１の実施形態と同様に、分割部３は、入力部２を介して、組合せ最適化問題におけるエネルギーを表す式を取り込む。そして、分割部３は、その式を、複数の項に分割する。

不整合判定部４は、分割部３による分割によって得られた項の組合せであって、予め記憶しているパターン式に該当する項の組合せの有無を判定する。そして、不整合判定部４は、その組合せが存在した場合に、補助変数を特定する。

本例では、不整合判定部４は、式（７）に例示するパターン式を予め記憶している。従って、不整合判定部４は、分割によって得られた項の組合せであって、予め記憶しているパターン式に該当する項の組合せとして、“ｘ_１ｘ_２”，“－２ｘ_１ｙ”，“－２ｘ_２ｙ”，“ｘ_３ｙ”，“３ｙ”に当てはまる５つの項の組合せが存在するか否かを判定する。そして、その組合せが存在した場合には、不整合判定部４は、“ｙ”に該当する変数を、補助変数として特定する。

そして、不整合判定部４は、特定した補助変数が、上記の組合せに含まれない項で用いられている場合に、組合せ最適化問題におけるエネルギーを表す式の中に、補助変数に関する不整合が生じていると判定する。前述のように、補助変数は、式（７）を包含する式では、式（７）以外で用いられないことが一般的であるので、このように判定してよい。

また、上記の組合せが存在しない場合や、特定した補助変数が、上記の組合せに含まれない項で用いられていない場合には、不整合判定部４は、組合せ最適化問題におけるエネルギーを表す式の中に、補助変数に関する不整合が生じていないと判定する。

第２の実施形態において、提示部５は、定式化された式の中に、補助変数に関する不整合が生じているかいなかの判定結果を、ディスプレイ装置に表示する。また、不整合判定部４によって特定された補助変数が、上記の組合せに含まれない項で用いられている場合には、その項も併せて表示してよい。

次に、処理経過について説明する。図３は、第２の実施形態の処理経過の例を示すフローチャートである。既に説明した事項については、適宜、説明を省略する。

入力部２に、組合せ最適化問題におけるエネルギーを表す式が入力されると、分割部３は、その式を、複数の項に分割する（ステップＳ１１）。ステップＳ１１は、第１の実施形態におけるステップＳ１（図２参照）と同様である。

次に、不整合判定部４は、分割部３による分割によって得られた項の組合せであって、予め記憶しているパターン式に該当する項の組合せがあるか否かを判定する（ステップＳ１２）。

そのような組合せがある場合（ステップＳ１２のＹｅｓ）、不整合判定部４は、補助変数を特定する（ステップＳ１３）。

次に、不整合判定部４は、補助変数がその組合せに含まれない項で用いられているか否かを判定する（ステップＳ１４）。

補助変数がその組合せに含まれない項で用いられている場合（ステップＳ１４のＹｅｓ）、不整合判定部４は、入力された式に補助変数に関する不整合があると判定する（ステップＳ１５）。そして、提示部５は、入力された式に補助変数に関する不整合があることを提示する（ステップＳ１６）。このとき、提示部５は、その組合せに含まれない項であって、補助変数が用いられている項を併せて提示してもよい。

補助変数がその組合せに含まれない項で用いられていない場合（ステップＳ１４のＮｏ）、不整合判定部４は、入力された式に補助変数に関する不整合がないと判定する（ステップＳ１７）。そして、提示部５は、入力された式に補助変数に関する不整合がないことを提示する（ステップＳ１８）。

また、ステップ１２において、分割によって得られた項の組合せであって、予め記憶しているパターン式に該当する項の組合せがないと判定された場合にも（ステップＳ１２のＮｏ）、ステップＳ１７，Ｓ１８を実行する。

補助変数は、パターン式を包含する式では、パターン式以外で用いられないことが一般的である。そして、本実施形態では、不整合判定部４は、分割によって得られた項の組合せであって、予め記憶しているパターン式に該当する項の組合せがあると判定した場合、補助変数を特定する。そして、不整合判定部４は、補助変数がその組合せに含まれない項で用いられている場合に、定式化された式の中に補助変数に関する不整合が生じていると判定する。また、不整合判定部４は、補助変数がその組合せに含まれない項で用いられていない場合には、定式化された式の中に補助変数に関する不整合が生じていないと判定する。従って、本実施形態によれば、定式化された式の中に不整合が生じているか否かを判定することができる。

実施形態３．
図４は、本発明の第３の実施形態の不整合判定装置の構成例を示すブロック図である。第１の実施形態や第２の実施形態の要素と同様の要素には、図１に示す符号と同一の符号を付す。第３の実施形態の不整合判定装置１は、入力部２と、不整合判定部４と、提示部５とを備える。

第３の実施形態では、入力部２には、定式化された式（組合せ最適化問題におけるエネルギーを表す式）、および、スピンの状態を表す各変数を定義した文字列が入力される。

入力部２は、例えば、例えば、光学ディスクなどのデータ記録媒体に記録されたデータ（本実施形態では、組合せ最適化問題におけるエネルギーを表す式、および、スピンの状態を表す各変数を定義した文字列）を読み込むデータ読み込み装置によって実現されてもよい。ただし、入力部２は、そのようなデータ読み込み装置に限定されず、ユーザが式および文字列を入力するためのキーボード等の入力デバイスであってもよい。

ここで、スピンの状態を表す各変数を定義した文字列は、例えば、ＰｙＱＵＢＯ（登録商標）に従って記述されてもよい。図５は、ＰｙＱＵＢＯに従って記述された、スピンの状態を表す各変数を定義した文字列の例を示す。図５に例示する文字列は、スピンの状態を表す変数として、ｘ_１からｘ_ＮまでのＮ個の変数を定義した文字列である。ただし、スピンの状態を表す各変数を定義した文字列の記述態様は、ＰｙＱＵＢＯに従った記述態様に限定されない。

不整合判定部４は、入力部２を介して、定式化された式（組合せ最適化問題におけるエネルギーを表す式）、および、スピンの状態を表す各変数を定義した文字列を取り込む。そして、不整合判定部４は、その文字列で定義された各変数（スピンの状態を表す各変数）を特定する。

そして、不整合判定部４は、その文字列で定義された各変数のうち、定式化された式で用いられていない変数があるか否かを判定する。文字列で定義された各変数のうち、定式化された式で用いられていない変数がある場合、不整合判定部４は、定義されているにも関わらわず定式化された式で用いられていない変数が存在するという不整合が、定式化された式の中に生じていると判定する。また、文字列で定義された各変数のうち、定式化された式で用いられていない変数がない場合（換言すれば、文字列で定義された各変数が全て、定式化された式で用いられている場合）、不整合判定部４は、定式化された式の中に不整合が生じていないと判定する。

提示部５は、不整合判定部４による判定結果を、例えば、不整合判定装置１が備えるディスプレイ装置（図４において図示略）に表示する。例えば、定義されているにも関わらわず定式化された式で用いられていない変数が存在するという不整合が、定式化された式の中に生じていると判定された場合、提示部５は、その旨の情報を、ディスプレイ装置に表示する。このとき、提示部５は、定義されているにも関わらわず定式化された式で用いられていない変数を併せて表示してもよい。また、定式化された式の中に不整合が生じていないと判定された場合、提示部５は、その旨の情報を、ディスプレイ装置に表示する。

不整合判定部４および提示部５は、例えば、不整合判定プログラムに従って動作するコンピュータのＣＰＵによって実現される。この場合、ＣＰＵは、コンピュータのプログラム記憶装置等のプログラム記録媒体から不整合判定プログラムを読み込み、その不整合判定プログラムに従って、不整合判定部４および提示部５として動作すればよい。

次に、処理経過について説明する。図６は、第３の実施形態の処理経過の例を示すフローチャートである。既に説明した事項については、適宜、説明を省略する。

不整合判定部４は、入力部２を介して、組合せ最適化問題におけるエネルギーを表す式、および、スピンの状態を表す各変数を定義した文字列を取り込む（ステップＳ３１）。本例では、不整合判定部４が、図５に示す文字列を取り込む場合を例にして説明する。

ステップＳ３１の次に、不整合判定部４は、取り込んだ文字列で定義された各変数を特定する（ステップＳ３２）。本例では、不整合判定部４は、図５に示す文字列で定義されたｘ_１，ｘ_２，ｘ_３，・・・，ｘ_ＮのＮ個の変数を特定する。

次に、不整合判定部４は、取り込んだ文字列で定義された各変数(本例では、ｘ_１，ｘ_２，ｘ_３，・・・，ｘ_Ｎ)のうち、取り込んだ式で用いられていない変数があるか否かを判定する（ステップＳ３３）。

取り込んだ文字列で定義された各変数のうち、取り込んだ式で用いられていない変数がある場合（ステップＳ３３のＹｅｓ）、不整合判定部４は、定義されているにも関わらず定式化された式で用いられていない変数が存在するという不整合が、定式化された式の中に生じていると判定する（ステップＳ３４）。そして、提示部５は、定式化された式の中に不整合が生じていることを提示する（ステップＳ３５）。このとき、提示部５は、定義されているにも関わらわず定式化された式で用いられていない変数を併せて提示してもよい。

また、取り込んだ文字列で定義された各変数が全て、取り込んだ式で用いられているならば（ステップＳ３３のＮｏ）、不整合判定部４は、定式化された式の中に不整合が生じていないと判定する（ステップＳ３６）。そして、提示部５は、式化された式の中に不整合が生じていないことを提示する（ステップＳ３７）。

定義された変数（スピンの状態を表す変数）は、定式化された式で用いられることが一般的である。そして、本実施形態では、定義された変数のうち、定式化された式で用いられていない変数があるならば、定式化された式に不整合が生じていると判定し、定義された変数が全て定式化された式で用いられているならば、定式化された式に不整合が生じていないと判定する。従って、本実施形態によれば、定式化された式の中に不整合が生じているか否かを判定することができる。

上記の各実施形態では、定式化された式（組合せ最適化問題におけるエネルギーを表す式）がＱＵＢＯのエネルギー関数に変換される場合を例にした。この場合、スピンの状態を表す変数は、１または０の値をとる。定式化された式がイジングモデルのエネルギー関数に変換される場合にも、本発明を適用してよい。なお、この場合、スピンを表す変数は１または－１の値をとる。

また、ＱＵＢＯのエネルギー関数とイジングモデルのエネルギー関数とは、相互に変換可能である。従って、不整合が生じていないと判定された定式化された式を、ＱＵＢＯのエネルギー関数に変換し、さらに、そのエネルギー関数をイジングモデルのエネルギー関数に変換してもよい。

なお、既に述べたように、ＱＵＢＯにおける“１”やイジングモデルにおける“１”を第１の値と称することができる。そして、ＱＵＢＯにおける“０”やイジングモデルにおける“－１”を第２の値と称することができる。

図７は、本発明の各実施形態の不整合判定装置１に係るコンピュータの構成例を示す概略ブロック図である。コンピュータ１０００は、ＣＰＵ１００１と、主記憶装置１００２と、補助記憶装置１００３と、インタフェース１００４と、データ読み込み装置１００５と、ディスプレイ装置１００６とを備える。

本発明の各実施形態の不整合判定装置１は、コンピュータ１０００によって実現される。不整合判定装置１の動作は、不整合判定プログラムの形式で補助記憶装置１００３に記憶されている。ＣＰＵ１００１は、その不整合判定プログラムを補助記憶装置１００３から読み出して主記憶装置１００２に展開し、その不整合判定プログラムに従って、上記の各実施形態で説明した処理を実行する。

補助記憶装置１００３は、一時的でない有形の媒体の例である。一時的でない有形の媒体の他の例として、インタフェース１００４を介して接続される磁気ディスク、光磁気ディスク、ＣＤ－ＲＯＭ（Compact Disk Read Only Memory ）、ＤＶＤ－ＲＯＭ（Digital Versatile Disk Read Only Memory ）、半導体メモリ等が挙げられる。また、プログラムが通信回線によってコンピュータ１０００に配信される場合、配信を受けたコンピュータ１０００がそのプログラムを主記憶装置１００２に展開し、そのプログラムに従って上記の各実施形態で説明した処理を実行してもよい。

また、各構成要素の一部または全部は、汎用または専用の回路（circuitry ）、プロセッサ等やこれらの組合せによって実現されてもよい。これらは、単一のチップによって構成されてもよいし、バスを介して接続される複数のチップによって構成されてもよい。各構成要素の一部または全部は、上述した回路等とプログラムとの組合せによって実現されてもよい。

各構成要素の一部または全部が複数の情報処理装置や回路等により実現される場合には、複数の情報処理装置や回路等は集中配置されてもよいし、分散配置されてもよい。例えば、情報処理装置や回路等は、クライアントアンドサーバシステム、クラウドコンピューティングシステム等、各々が通信ネットワークを介して接続される形態として実現されてもよい。

次に、本発明の概要について説明する。図８は、本発明の不整合判定装置の概要を示すブロック図である。本発明の不整合判定装置１は、不整合判定手段９を備える。

不整合判定手段９（例えば、不整合判定部４）は、個々のスピンの状態を第１の値または第２の値で表すモデルのエネルギー関数に変換される、組合せ最適化問題におけるエネルギーを表す式の中に不整合が生じているか否かを判定する。

上記の本発明の実施形態は、以下の付記のようにも記載され得るが、以下に限定されるわけではない。

（付記１）
個々のスピンの状態を第１の値または第２の値で表すモデルのエネルギー関数に変換される、組合せ最適化問題におけるエネルギーを表す式の中に不整合が生じているか否かを判定する不整合判定手段を備える
ことを特徴とする不整合判定装置。

（付記２）
前記エネルギーを表す式を複数の項に分割する分割手段を備え、
前記不整合判定手段は、
前記複数の項の中から、制約を表す項である制約項を２個以上抽出し、
抽出した２個以上の制約項が表す制約間に不整合がある場合に、前記エネルギーを表す式の中に不整合が生じていると判定する
付記１に記載の不整合判定装置。

（付記３）
制約項が表す制約が式で表され、
前記不整合判定手段は、
制約を表す式を、別の制約を表す式に代入したときに不整合が生じるならば、代入した式に対応する制約と、代入された式に対応する制約の間に不整合があると判定する
付記２に記載の不整合判定装置。

（付記４）
前記エネルギーを表す式を複数の項に分割する分割手段を備え、
前記不整合判定手段は、
スピンの状態を表す変数の次数を２に下げるための補助変数を用いた式を予め記憶し、
分割によって得られた項の組合せであって、予め記憶している前記式に該当する項の組合せの有無を判定し、
前記組合せが有る場合に、前記補助変数を特定し、
前記組合せに含まれない項で前記補助変数が用いられている場合に、前記エネルギーを表す式の中に不整合が生じていると判定する
付記１に記載の不整合判定装置。

（付記５）
前記不整合判定手段は、
前記エネルギーを表す式とともに、スピンの状態を表す各変数を定義した文字列を取り込み、
前記文字列で定義された各変数のうち、前記エネルギーを表す式で用いられていない変数がある場合に、前記エネルギーを表す式の中に不整合が生じていると判定する
付記１に記載の不整合判定装置。

（付記６）
コンピュータが、
個々のスピンの状態を第１の値または第２の値で表すモデルのエネルギー関数に変換される、組合せ最適化問題におけるエネルギーを表す式の中に不整合が生じているか否かを判定する
ことを特徴とする不整合判定方法。

（付記７）
前記コンピュータが、
前記エネルギーを表す式を複数の項に分割し、
前記複数の項の中から、制約を表す項である制約項を２個以上抽出し、
抽出した２個以上の制約項が表す制約間に不整合がある場合に、前記エネルギーを表す式の中に不整合が生じていると判定する
付記６に記載の不整合判定方法。

（付記８）
前記コンピュータが、
前記エネルギーを表す式を複数の項に分割し、
スピンの状態を表す変数の次数を２に下げるための補助変数を用いた式を予め記憶し、
分割によって得られた項の組合せであって、予め記憶している前記式に該当する項の組合せの有無を判定し、
前記組合せが有る場合に、前記補助変数を特定し、
前記組合せに含まれない項で前記補助変数が用いられている場合に、前記エネルギーを表す式の中に不整合が生じていると判定する
付記６に記載の不整合判定方法。

（付記９）
前記コンピュータが、
前記エネルギーを表す式とともに、スピンの状態を表す各変数を定義した文字列を取り込み、
前記文字列で定義された各変数のうち、前記エネルギーを表す式で用いられていない変数がある場合に、前記エネルギーを表す式の中に不整合が生じていると判定する
付記６に記載の不整合判定方法。

（付記１０）
コンピュータに、
個々のスピンの状態を第１の値または第２の値で表すモデルのエネルギー関数に変換される、組合せ最適化問題におけるエネルギーを表す式の中に不整合が生じているか否かを判定する不整合判定処理を実行させる
不整合判定プログラムを記録したコンピュータ読取可能な記録媒体。

（付記１１）
前記コンピュータに、
前記エネルギーを表す式を複数の項に分割する分割処理を実行させ、
前記不整合判定処理で、
前記複数の項の中から、制約を表す項である制約項を２個以上抽出させ、
抽出した２個以上の制約項が表す制約間に不整合がある場合に、前記エネルギーを表す式の中に不整合が生じていると判定させる
不整合判定プログラムを記録した付記１０に記載のコンピュータ読取可能な記録媒体。

（付記１２）
前記コンピュータは、スピンの状態を表す変数の次数を２に下げるための補助変数を用いた式を予め記憶し、
前記コンピュータに、
前記エネルギーを表す式を複数の項に分割する分割処理を実行させ、
前記不整合判定処理で、
分割によって得られた項の組合せであって、予め前記コンピュータに記憶されている前記式に該当する項の組合せの有無を判定させ、
前記組合せが有る場合に、前記補助変数を特定させ、
前記組合せに含まれない項で前記補助変数が用いられている場合に、前記エネルギーを表す式の中に不整合が生じていると判定させる
不整合判定プログラムを記録した付記１０に記載のコンピュータ読取可能な記録媒体。

（付記１３）
前記コンピュータに、
前記不整合判定処理で、
前記エネルギーを表す式とともに、スピンの状態を表す各変数を定義した文字列を取り込ませ、
前記文字列で定義された各変数のうち、前記エネルギーを表す式で用いられていない変数がある場合に、前記エネルギーを表す式の中に不整合が生じていると判定させる
不整合判定プログラムを記録した付記１０に記載のコンピュータ読取可能な記録媒体。

以上、実施形態を参照して本願発明を説明したが、本願発明は上記の実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。

産業上の利用の可能性

本発明は、組合せ最適化問題におけるエネルギーを表す式の中に不整合が生じているか否かを判定する不整合判定装置に好適に適用される。

１ 不整合判定装置
２ 入力部
３ 分割部
４ 不整合判定部
５ 提示部

Claims (10)

1. 個々のスピンの状態を第１の値または第２の値で表すモデルのエネルギー関数に変換される、組合せ最適化問題におけるエネルギーを表す式を目的関数を表す項および複数の項に分割する分割手段と、
   前記複数の項が表す制約間に不整合が生じているか否かを判定する不整合判定手段を備える
   ことを特徴とする不整合判定装置。
2. 前記不整合判定手段は、
   前記複数の項の中から、制約を表す項である制約項を２個以上抽出し、
   抽出した２個以上の制約項が表す制約間に不整合がある場合に、前記エネルギーを表す式の中に不整合が生じていると判定する
   請求項１に記載の不整合判定装置。
3. 制約項が表す制約が式で表され、
   前記不整合判定手段は、
   制約を表す式を、別の制約を表す式に代入したときに不整合が生じるならば、代入した式に対応する制約と、代入された式に対応する制約の間に不整合があると判定する
   請求項２に記載の不整合判定装置。
4. 前記不整合判定手段は、
   スピンの状態を表す変数の次数を２に下げるための補助変数を用いた式を予め記憶し、
   分割によって得られた項の組合せであって、予め記憶している前記式に該当する項の組合せの有無を判定し、
   前記組合せが有る場合に、前記補助変数を特定し、
   前記組合せに含まれない項で前記補助変数が用いられている場合に、前記エネルギーを表す式の中に不整合が生じていると判定する
   請求項１に記載の不整合判定装置。
5. コンピュータが、
   個々のスピンの状態を第１の値または第２の値で表すモデルのエネルギー関数に変換される、組合せ最適化問題におけるエネルギーを表す式を目的関数を表す項および複数の項に分割し、
   前記複数の項が表す制約間に不整合が生じているか否かを判定する
   ことを特徴とする不整合判定方法。
6. 前記コンピュータが、
   前記複数の項の中から、制約を表す項である制約項を２個以上抽出し、
   抽出した２個以上の制約項が表す制約間に不整合がある場合に、前記エネルギーを表す式の中に不整合が生じていると判定する
   請求項５に記載の不整合判定方法。
7. 前記コンピュータが、
   スピンの状態を表す変数の次数を２に下げるための補助変数を用いた式を予め記憶し、
   分割によって得られた項の組合せであって、予め記憶している前記式に該当する項の組合せの有無を判定し、
   前記組合せが有る場合に、前記補助変数を特定し、
   前記組合せに含まれない項で前記補助変数が用いられている場合に、前記エネルギーを表す式の中に不整合が生じていると判定する
   請求項５に記載の不整合判定方法。
8. コンピュータに、
   個々のスピンの状態を第１の値または第２の値で表すモデルのエネルギー関数に変換される、組合せ最適化問題におけるエネルギーを表す式を目的関数を表す項および複数の項に分割する分割処理、および、
   前記複数の項が表す制約間に不整合が生じているか否かを判定する不整合判定処理を実行させる
   不整合判定プログラム。
9. 前記コンピュータに、
   前記不整合判定処理で、
   前記複数の項の中から、制約を表す項である制約項を２個以上抽出させ、
   抽出した２個以上の制約項が表す制約間に不整合がある場合に、前記エネルギーを表す式の中に不整合が生じていると判定させる
   請求項８に記載の不整合判定プログラム。
10. 前記コンピュータは、スピンの状態を表す変数の次数を２に下げるための補助変数を用いた式を予め記憶し、
    前記コンピュータに、
    前記不整合判定処理で、
    分割によって得られた項の組合せであって、予め前記コンピュータに記憶されている前記式に該当する項の組合せの有無を判定させ、
    前記組合せが有る場合に、前記補助変数を特定させ、
    前記組合せに含まれない項で前記補助変数が用いられている場合に、前記エネルギーを表す式の中に不整合が生じていると判定させる
    請求項８に記載の不整合判定プログラム。

Images