(57)【要約】【課題】  有用性及び信頼性の高い情報処理装置及び情報処理方法を提案する。【解決手段】  問題の解をイジングモデルの基底状態として求める情報処理装置及び当該情報処理装置において実行される情報処理方法であって、情報処理装置に、イジングモデルにおける各スピン間の相互作用を模擬するイジングチップと、イジングモデルの一部又は全部のスピンにそれぞれ対応させてイジングチップに設けられ、それぞれ対応するスピンの値を取得する複数の第１のスピン値観測部と、イジングチップを制御する情報処理部とを設け、情報処理部が、問題をイジングモデルに変換し、問題をイジングモデルに変換する際に得られた制約条件と、各第１のスピン値観測部によりそれぞれ取得されたイジングモデルの基底状態探索時における対応する各スピンの値とに基づいて、イジングモデルが問題の性質を正しく反映しているか否かを検証するようにした。
2017017807.tif 000002
【特許請求の範囲】
【請求項１】
問題の解をイジングモデルの基底状態として求める情報処理装置において、
前記問題を前記イジングモデルに変換する情報処理部と、
前記イジングモデルにおける各スピン間の相互作用を模擬するイジングチップと、
前記イジングモデルの一部又は全部の前記スピンにそれぞれ対応させて前記イジングチップに設けられ、それぞれ対応する前記スピンの値を取得する複数の第１のスピン値観測部と
を備え、
前記情報処理部は、
前記問題を前記イジングモデルに変換する際に得られた当該イジングモデルの各前記スピンが満たすべき制約条件と、各前記第１のスピン値観測部によりそれぞれ取得された前記イジングモデルの基底状態探索時における対応する各前記スピンの値とに基づいて、前記イジングモデルが前記問題の性質を正しく反映しているか否かを検証する
ことを特徴とする情報処理装置。
【請求項２】
前記情報処理部は、
前記第１のスピン値観測部により取得された各前記スピンの値に基づいて、対応する前記スピンの値が前記制約条件を満たすか否かを判定し、
判定結果に基づいて、対応する前記スピンの値が所定の第１の時間内に前記制約条件を満たす割合を時系列に沿って順次算出し、
当該割合が収束するか否かに基づいて、前記イジングモデルが前記問題の性質を正しく反映しているか否かを検証する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記情報処理部は、
前記イジングチップを制御する制御部と、
前記イジングチップ内に設けられたコントローラとを備え、
前記制御部は、
前記問題を前記イジングモデルに変換すると共に、対応する前記スピンの値が前記制約条件を満たすか否かを判定する判定処理の処理内容を表す第１の処理情報を前記コントローラに送信し、
前記コントローラは、
前記イジングモデルの基底状態探索時に、前記第１のスピン値観測部により取得される対応する前記スピンの値と、前記第１の処理情報とに基づいて、当該スピンの値が前記制約条件を満たすか否かを判定し、
前記制御部は、
前記コントローラの判定結果に基づいて、対応する前記スピンの値が前記第１の時間内に前記制約条件を満たす割合を時系列に沿って順次算出し、
当該割合が収束するか否かに基づいて、前記イジングモデルが前記問題の性質を正しく反映しているか否かを検証する
ことを特徴とする請求項２に記載の情報処理装置。
【請求項４】
乱数パルスを発生する乱数発生器と、
前記イジングモデルの一部又は全部のスピンにそれぞれ対応させて前記イジングチップに設けられ、それぞれ対応する前記スピンの値を取得する複数の第２のスピン値観測部と
をさらに備え、
前記情報処理部は、
各前記第２のスピン値観測部によりそれぞれ取得された前記イジングモデルの基底状態探索時における対応する各前記スピンの値に基づいて前記スピンが平衡状態に達したか否かを断続的に判断し、前記スピンが平衡状態に達したと判断した場合に、前記乱数発生器における前記乱数パルスの発生頻度を制御する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項５】
前記情報処理部は、
前記スピンごとに、一定時間内に当該スピンの値が所定値となる確率を断続的に算出すると共に、算出した前記スピンごとの当該確率の平均値を断続的に算出し、今回算出した当該平均値と、前回算出した当該平均値との差分が予め定められた第２の閾値を下回った場合に前記スピンが平衡状態に達したと判断する
ことを特徴とする請求項４に記載の情報処理装置。
【請求項６】
問題の解をイジングモデルの基底状態として求める情報処理装置において実行される情報処理方法であって、
前記情報処理装置は、
前記イジングモデルにおける各スピン間の相互作用を模擬するイジングチップと、
前記イジングモデルの一部又は全部の前記スピンにそれぞれ対応させて前記イジングチップに設けられ、それぞれ対応する前記スピンの値を取得する複数の第１のスピン値観測部と
前記イジングチップを制御する情報処理部と
を有し、
前記情報処理部が、前記問題を前記イジングモデルに変換する第１のステップと、
前記情報処理部が、前記問題を前記イジングモデルに変換する際に得られた当該イジングモデルの各前記スピンが満たすべき制約条件と、各前記第１のスピン値観測部によりそれぞれ取得された前記イジングモデルの基底状態探索時における対応する各前記スピンの値とに基づいて、前記イジングモデルが前記問題の性質を正しく反映しているか否かを検証する第２のステップと
を備えることを特徴とする情報処理方法。
【請求項７】
前記第２のステップにおいて、前記情報処理部は、
前記第１のスピン値観測部により取得された各前記スピンの値に基づいて、対応する前記スピンの値が前記制約条件を満たすか否かを判定し、
判定結果に基づいて、対応する前記スピンの値が所定の第１の時間内に前記制約条件を満たす割合を時系列に沿って順次算出し、
当該割合が収束するか否かに基づいて、前記イジングモデルが前記問題の性質を正しく反映しているか否かを検証する
ことを特徴とする請求項６に記載の情報処理方法。
【請求項８】
前記情報処理部は、
前記イジングチップを制御する制御部と、
前記イジングチップ内に設けられたコントローラとを有し、
前記第２のステップでは、
前記制御部が、前記問題を前記イジングモデルに変換すると共に、対応する前記スピンの値が前記制約条件を満たすか否かを判定する判定処理の処理内容を表す第１の処理情報を前記コントローラに送信し、
前記コントローラが、前記イジングモデルの基底状態探索時に、前記第１のスピン値観測部により取得される対応する前記スピンの値と、前記第１の処理情報とに基づいて、当該スピンの値が前記制約条件を満たすか否かを判定し、
前記制御部が、前記コントローラの判定結果に基づいて、対応する前記スピンの値が前記第１の時間内に前記制約条件を満たす割合を時系列に沿って順次算出し、当該割合が収束するか否かに基づいて、前記イジングモデルが前記問題の性質を正しく反映しているか否かを検証する
ことを特徴とする請求項７に記載の情報処理方法。
【請求項９】
前記情報処理装置は、
乱数パルスを発生する乱数発生器と、
前記イジングモデルの一部又は全部のスピンにそれぞれ対応させて前記イジングチップに設けられ、それぞれ対応する前記スピンの値を取得する複数の第２のスピン値観測部と
をさらに有し、
前記第２のステップにおいて、前記情報処理部は、
各前記第２のスピン値観測部によりそれぞれ取得された前記イジングモデルの基底状態探索時における対応する各前記スピンの値に基づいて前記スピンが平衡状態に達したか否かを断続的に判断し、前記スピンが平衡状態に達したと判断した場合に、前記乱数発生器における前記乱数パルスの発生頻度を制御する
ことを特徴とする請求項６に記載の情報処理方法。
【請求項１０】
前記第２のステップにおいて、前記情報処理部は、
前記スピンごとに、一定時間内に当該スピンの値が所定値となる確率を断続的に算出すると共に、算出した前記スピンごとの当該確率の平均値を断続的に算出し、今回算出した当該平均値と、前回算出した当該平均値との差分が予め定められた第２の閾値を下回った場合に前記スピンが平衡状態に達したと判断する
ことを特徴とする請求項９に記載の情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置及び方法に関し、特に、問題の解をイジングモデルの基底状態として求める情報処理装置に適用して好適なものである。
【背景技術】
【０００２】
イジングモデルは磁性体の振舞いを説明するための統計力学のモデルである。イジングモデルは＋１／−１（ないしは、０／１、上／下）の２値をとるスピンと、スピン間の相互作用を示す相互作用係数、及び、スピン毎にある外部磁場係数で定義される。イジングモデルは与えられたスピン配列、相互作用係数、及び、外部磁場係数から、その時のエネルギーを計算することができる。【０００３】
イジングモデルの基底状態探索とは、イジングモデルのエネルギー関数を最小化するスピンの配列を求める最適化問題である。トポロジが非平面グラフであるイジングモデルの基底状態を求めることはＮＰ困難問題であることが知られている。【０００４】
イジングモデルの基底状態探索は、ＮＰ困難なグラフ問題として知られている最大カット問題とも対応している。このようなグラフ問題は、ソーシャルネットワークにおけるコミュニティの検出や、画像処理におけるセグメンテーションなど、幅広い応用を持っている。そのため、イジングモデルの基底状態探索を行うソルバがあれば、このような様々な問題に適用することができる。【０００５】
イジングモデルに含まれるスピンの取り得る状態の組み合わせは莫大な数にのぼるため、基底状態を求めるにあたってそのすべてを探索することは実質的に不可能である。このため、基底状態を効率よく求めるには、探索するスピンの組み合わせを絞り込む必要がある。しかしながら、絞り込みによって局所解を選んでしまい、近似的な基底状態しか得られなくなるといった弊害も起こるため、探索の過程で見つかった局所解を避けることでよりよい解を得られる手法が必要である。【０００６】
このような手法として、超電導素子を用いた量子的なゆらぎを活用して基底状態探索を行う方法が提案されている。このような装置として、例えば特許文献１に記載の装置がある。【０００７】
また、シミュレーテッドアニーリングのように、一時的に解の悪化を許容するヒューリスティクスを用いて、良い解を求める方法もある。このような方法を用いる場合、例えば非特許文献１に示されるようなハードウェアを用いることで、高速に基底状態探索を行うことができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】国際公開第２０１２／１１８０６４号
【非特許文献】
【０００９】
【非特許文献１】Michael G. Wrighton, Andre M. DeHon, Hardware-Assisted SimulatedAnnealing with Application for Fast FPGA Placement, FPGA '03 Proceedings of the2003 ACM/SIGDA eleventh international symposium on Field programmable gatearrays, Pages 33 - 42
【発明の概要】
【発明が解決しようとする課題】
【００１０】
特許文献１及び非特許文献１に記載の装置を用いて問題を解く場合、解きたい問題をイジングモデルの基底状態探索に変換する処理が必要となるが、従来、このような変換はプログラムにより行われている。この際、かかる変換により得られたイジングモデルが元の問題の性質を正しく反映していないと、このイジングモデルの基底状態探索を行っても、元の問題の正しい解を得ることはできない。【００１１】
一方、基底状態探索を行うハードウェアはランダムな挙動をするので、最終結果だけ見ても、かかる変換により得られたイジングモデルが元の問題の性質を正しく反映しているか否かを判断することは困難である。【００１２】
本発明は以上の点を考慮してなされたもので、イジングモデルが元の問題の性質を正しく反映しているか否かを容易に判断可能な有用性及び信頼性の高い情報処理装置及び判定方法を提供しようとするものである。
【課題を解決するための手段】
【００１３】
かかる課題を解決するため本発明においては、問題の解をイジングモデルの基底状態として求める情報処理装置において、前記問題を前記イジングモデルに変換する情報処理部と、前記イジングモデルにおける各スピン間の相互作用を模擬するイジングチップと、前記イジングモデルの一部又は全部の前記スピンにそれぞれ対応させて前記イジングチップに設けられ、それぞれ対応する前記スピンの値を取得する複数の第１のスピン値観測部とを設け、前記情報処理部が、前記問題を前記イジングモデルに変換する際に得られた当該イジングモデルの各前記スピンが満たすべき制約条件と、各前記第１のスピン値観測部によりそれぞれ取得された前記イジングモデルの基底状態探索時における対応する各前記スピンの値とに基づいて、前記イジングモデルが前記問題の性質を正しく反映しているか否かを検証するようにした。【００１４】
また本発明においては、問題の解をイジングモデルの基底状態として求める情報処理装置において実行される情報処理方法であって、前記情報処理装置は、前記イジングモデルにおける各スピン間の相互作用を模擬するイジングチップと、前記イジングモデルの一部又は全部の前記スピンにそれぞれ対応させて前記イジングチップに設けられ、それぞれ対応する前記スピンの値を取得する複数の第１のスピン値観測部と前記イジングチップを制御する情報処理部とを有し、前記情報処理部が、前記問題を前記イジングモデルに変換する第１のステップと、前記情報処理部が、前記問題を前記イジングモデルに変換する際に得られた当該イジングモデルの各前記スピンが満たすべき制約条件と、各前記第１のスピン値観測部によりそれぞれ取得された前記イジングモデルの基底状態探索時における対応する各前記スピンの値とに基づいて、前記イジングモデルが前記問題の性質を正しく反映しているか否かを検証する第２のステップとを設けるようにした。【００１５】
本発明の情報処理装置及び情報処理方法によれば、情報処理部の検証結果に基づいてユーザがそのイジングモデルが元の問題の性質を正しく反映しているか否かを容易に判断することができる。
【発明の効果】
【００１６】
本発明によれば、有用性及び信頼性の高い情報処理装置を実現できる。
【図面の簡単な説明】
【００１７】
【図１】第１及び第２の実施の形態による情報処理装置の全体構成を示すブロック図である。
【図２】イジングチップモジュールの構成を示すブロック図である。
【図３】第１の実施の形態によるイジングチップの構成を示すブロック図である。
【図４】スピンアレイの説明に供する概念図である。
【図５】スピンアレイの説明に供する概念図である。
【図６】スピンアレイの説明に供する概念図である。
【図７】スピンユニットの構成を示すブロック図である。
【図８】スピンユニットの構成を示すブロック図である。
【図９】イジングチップ上のスピンユニットの配置例を示すブロック図である。
【図１０】制約条件の説明に供する概念図である。
【図１１】制約条件の説明に供する概念図である。
【図１２】第１の実施の形態によるスピンアレイの説明に供するブロック図である。
【図１３】第１のスピン値観測部の説明に供するブロック図である。
【図１４】第１の観測結果の説明に供する図表である。
【図１５】第１の処理情報の説明に供する図表である。
【図１６】第１の処理結果の説明に供する図表である。
【図１７】（Ａ）及び（Ｂ）は、判定処理の説明に供するグラフである。
【図１８】（Ａ）及び（Ｂ）は、判定処理の説明に供するグラフである。
【図１９】判定処理の説明に供する図表である。
【図２０】第１の実施の形態による基底状態探索処理の処理手順を示すフローチャートである。
【図２１】第２の実施の形態によるイジングチップの構成を示すブロック図である。
【図２２】第２の実施の形態によるスピンアレイの説明に供するブロック図である。
【図２３】第２の観測結果の説明に供する図表である。
【図２４】第２の処理情報の説明に供する図表である。
【図２５】第２の処理結果の説明に供する図表である。
【図２６】第２の実施の形態による基底状態探索処理の処理手順を示すフローチャートである。
【発明を実施するための形態】
【００１８】
以下図面について、本発明の一実施の形態を詳述する。
【００１９】
（１）第１の実施の形態
（１−１）イジングモデルの定義
イジングモデルは強磁性体の振る舞いを説明するときなどに用いられる統計力学のモデルである。イジングモデルは＋１又は１の２値の状態をとるスピンと、スピン間の相互作用の強さを表す相互作用係数と、各スピンに働く外部磁場の強さを表す外部磁場係数で定義される。
【００２０】
イジングモデルのエネルギー関数は、次式
【数１】
2017017807.tif 000003
で定義される。（１）式において、σはスピン全体を表し、σｉ，σｊはそれぞれｉ番目とｊ番目のスピンの値を表す。また＜ｉ，ｊ＞は全てのスピンのｉとｊの組を表しており、Ｊｉ，ｊはｉ番目とｊ番目のスピンの間の相互作用係数、ｈｉはｉ番目のスピンに対する外部磁場係数を表す。
【００２１】
ところで、イジングモデルは一般的に無向グラフで表現される相互作用を有している。上述した（１）式において、相互作用を表わす項として、Ｊｉ，ｊ×σｉ×σｊがあるが、これはｉ番目スピンからｊ番目スピンへの相互作用を示している。この場合、一般的なイジングモデルではｉ番目スピンからｊ番目スピンへの相互作用と、ｊ番目スピンからｉ番目スピンへの相互作用を区別することはない。つまり、Ｊｉ，ｊとＪｊ，ｉは同一である。しかし、本実施の形態では、このイジングモデルを有向グラフに拡張し、ｉ番目スピンからｊ番目スピンへの相互作用と、ｊ番目スピンからｉ番目スピンへの相互作用を非対称にすることを実現している。これにより、モデルの表現能力が高まり、多くの問題をより小規模のモデルで表現することが可能になる。
【００２２】
イジングモデルの基底状態を求めることは、（１）式で表されるイジングモデルのエネルギーが最小となるようなスピンの値の組み合せを求める、組合せ最適化問題を解くことに相当する。
【００２３】
例えば、グラフの最大カット問題や巡回セールスマン問題などの最適化問題をイジングモデルの基底状態探索に変換することが可能である。このとき、元の問題を変換して作ったイジングモデルの基底状態を求めた後、スピン値の値を元の問題に逆変換することで元の問題を解くことができる。イジングモデルの基底状態探索を高速に行う装置を用いることで、従来の計算機では時間のかかる最適化問題を高速に解くことができる。
【００２４】
（１−２）本実施の形態による情報処理システムの構成
（１−２−１）情報処理システムの全体構成
図１は、上述のように問題をイジングモデルに変換し、変換したイジングモデルの基底状態を探索することによりかかる問題の解を求め得るようになされた本実施の形態による情報処理装置１の概略構成を示す。
【００２５】
この情報処理装置１は、パーソナルコンピュータやワークステーション又はサーバなどから構成され、例えばＰＣＩ  ＥｘｐｒｅｓｓやＱＰＩなどから構成されるシステムバス２を介して相互に接続されたＣＰＵ（Central Processing Unit）３、メモリ４、記憶装置５及び複数のイジングチップモジュール６を備える。
【００２６】
ＣＰＵ３は、情報処理装置１全体の動作制御を司るプロセッサである。またメモリ４は、例えば揮発性の半導体メモリから構成され、各種プログラムを記憶するために利用される。記憶装置５は、例えばハードディスク装置やＳＳＤ（Solid State Drive）などから構成され、プログラムやデータを長期間保持するために利用される。
【００２７】
本実施の形態の場合、記憶装置５には、ユーザから与えられた本情報処理装置１が解くべき問題の問題データ７が格納され、メモリ４には、問題変換プログラム８及びイジングチップ制御プログラム９が格納される。問題変換プログラム８は、かかる問題をイジングモデル形式の問題に変換するプログラムである。またイジングチップ制御プログラム９は、かかるイジングモデル形式の問題をイジングチップモジュール６において解くための各種制御を行うプログラムである。またメモリ４には、問題変換プログラム８により変換されたイジングモデル形式の問題であるイジングモデル１０が格納されるほか、後述する観測結果検証プログラム１１、制約条件１２及び観測結果１３も格納される。
【００２８】
イジングチップモジュール６は、図２に示すように、インタフェース２０、モジュールコントローラ２１、相互作用クロック生成部２２、乱数発生器２３及びイジングチップ２４を備えて構成される。
【００２９】
モジュールコントローラ２１は、情報処理装置１のＣＰＵ３（図１）及びイジングチップ２４間におけるコマンドやデータの橋渡しを行う機能と、ＣＰＵ３から指示に応じて相互作用クロック生成部２２及び乱数発生器２３を制御する機能とを有するプロセッサである。モジュールコントローラ２１は、インタフェース２０及びシステムバス２（図１）を介してＣＰＵ３との間でコマンドや情報の送受を行う。
【００３０】
相互作用クロック生成部２２は、後述する相互作用クロックを生成するクロック生成器である。相互作用クロック生成部２２により生成された相互作用クロックが後述のようにイジングチップ２４に与えられ、この相互作用クロックに同期してイジングチップ２４において基底状態探索が実行される。
【００３１】
また乱数発生器２３は、イジングチップ２４において実行される基底状態探索が局所解に陥るのを防止するためのランダムなビット列である乱数を発生させる。乱数発生器２３により発生された乱数はイジングチップ２４に与えられる。
【００３２】
イジングチップ２４は、イジングモデルにおけるスピン間の相互作用を模擬する専用のハードウェアである。イジングチップ２４は、情報処理装置１のＣＰＵ３（図１）からシステムバス２（図１）を介してイジングチップモジュール６に与えられたイジングモデルのデータ（後述する各スピンの値、各スピンの外部磁場係数及び各スピン間の相互作用係数のデータであり、以下、適宜、これをイジングモデルデータと呼ぶ）をモジュールコントローラ２１を介して受け取り、受け取ったイジングモデルデータに基づくイジングモデルの基底状態探索処理を実行する。そしてイジングチップ２４は、かかる基底状態探索処理の処理結果をモジュールコントローラ２１を介してＣＰＵ３に通知する。
【００３３】
（１−２−２）イジングチップの構成
図３は、イジングチップ２４の概略構成を示す。この図３に示すように、イジングチップ２４は、スピンアレイ３０、Ｉ／Ｏ（Input/output）アドレスデコーダ３１、Ｉ／Ｏドライバ３２、相互作用アドレスデコーダ３３、コントローラ３４及びチップメモリ３５を備えて構成される。本実施の形態では、イジングチップ２４は現在広く用いられているＣＭＯＳ（Complementary Metal-Oxide Semiconductor）集積回路として実装されていることを想定して説明するが、他の固体素子でも実現可能である。
【００３４】
スピンアレイ３０は、ＳＲＡＭとしての機能とイジングモデルの基底状態探索を行う相互作用回路としての機能を併せ持つ。Ｉ／Ｏアドレスデコーダ３１及びＩ／Ｏドライバ３２は、スピンアレイ３０をＳＲＡＭ（Static Random Access Memory）として用いる際のインタフェースである。
【００３５】
Ｉ／Ｏアドレスデコーダ３１は、アドレスバス３６を介して読み書きを行うアドレスを授受する。またＩ／Ｏドライバ３２は、データバス３７を介してスピンアレイ３０に読み込み又は書き込みするビット列を授受し、Ｒ／Ｗ（Read/Write）制御線３８の信号に従って、読み取り動作と書き込み動作を切り替えることができる。Ｉ／Ｏアドレスデコーダ３１及びＩ／Ｏドライバ３２は、いずれもＩ／Ｏクロック線３９を介してイジングチップモジュール６内の図示しないクロック発生器から与えられるＩ／Ｏクロックに同期して動作する。
【００３６】
相互作用アドレスデコーダ３３は、情報処理装置１のＣＰＵ３（図１）からモジュールコントローラ２１を介して相互作用アドレス線４０を通じて与えられる相互作用アドレスを入力し、スピンアレイ３０を相互作用回路として用いる際の、相互作用の対象となるスピンを選択する。また、相互作用アドレスデコーダ３３及びスピンアレイ３０は、相互作用クロック生成部２２（図２）から相互作用クロック線４１を介して与えられる相互作用クロックに同期して動作し、相互作用クロック１周期につき１回の相互作用動作を行う。また、スピンアレイ３０は、乱数発生器２３（図２）から出力された乱数パルスを乱数注入線４２を通して入力する。
【００３７】
コントローラ３４は、後述するイジングモデル検証機能に関連する各種演算や各種制御処理を実行するプロセッサである。またチップメモリ３５は、後述するようにスピンアレイ３０の内部で対応するスピンユニット５０（図４〜図８）が保持するスピンの値の観測結果でなる第１の観測結果４３と、後述のように情報処理装置１のＣＰＵ３（図１）から与えられた第１の処理情報４４と、第１の観測結果４３に対して行った第１の処理情報４４に基づく処理の処理結果でなる第１の処理結果４５とを格納するために用いられる。
【００３８】
（１−２−３）スピンアレイの構成
スピンアレイ３０は、１個のスピンσｉ並びにそれに付随する相互作用係数Ｊｉ，ｊ及び外部磁場係数ｈｉの保持と、基底状態探索演算とを実現するスピンユニットを基本構成単位として、スピンユニットを多数個並べた構成を有する。
【００３９】
図４は、スピンユニット５０を複数並べることで、３次元格子状のトポロジを持つイジングモデルを構成する例を示す。図４の例は、３（Ｘ軸方向）×３（Ｙ軸方向）×２（Ｚ軸方向）の大きさの３次元格子である。座標軸の定義は図示した通り、図面右方向をＸ軸、図面下方向をＹ軸、図面奥行き方向をＺ軸としているが、この座標軸は実施の形態の説明上便宜的に必要なだけであり、本発明とは関係しない。３次元格子以外のトポロジ、例えばツリー状のトポロジなどを利用する場合には、座標軸とは別にツリーの段数等で表現することになる。図４の３次元格子状のトポロジにおいて、スピン間の相互作用をグラフとしてとらえると、最大で次数５のスピン（頂点）が必要となる。なお、外部磁場係数の接続も含めて考えると、最大で次数６が必要となる。
【００４０】
図４に示す１個のスピンユニット５０には、隣接するスピン（例えば隣接するスピンが５個の場合σｊ，σｋ，σｌ，σｍ，σｎ）の値が入力される。このためスピンユニット５０は、これら入力する隣接するスピンの値を保持するためのメモリセルを有している。またスピンユニット５０は、かかるスピンの値に加え、外部磁場係数と、上述した隣接するスピンとの相互作用係数（隣接する５スピンとの相互作用係数Ｊｊ，ｉ，Ｊｋ，ｉ，Ｊｌ，ｉ，Ｊｍ，ｉ，Ｊｎ，ｉ）とをそれぞれ保持するメモリセルをも有している。
【００４１】
１個のスピンユニットをｉ番目スピンσｉと考えた時に、このスピンユニット５０が保持する相互作用係数であるＪｊ，ｉ、Ｊｋ，ｉ、Ｊｌ，ｉ、Ｊｍ，ｉ、Ｊｎ，ｉは、隣接するｊ番目、ｋ番目、ｌ番目、ｍ番目、ｎ番目のスピンσｊ、σｋ、σｌ、σｍ、σｎから、ｉ番目スピンσｉへの相互作用を決めるものである。このことは、図５において、スピンユニット５０に含まれている相互作用係数が対応する矢印（相互作用）が、図示されているスピンユニット５０の外部のスピンから、スピンユニット５０の内部のスピンに向かっていることに対応している。
【００４２】
（１−２−４）スピンユニットの構成
スピンユニット５０の構成について、図７及び図８を用いて説明する。スピンユニット５０は２つの側面をもっており、便宜上、図７及び図８に分けて説明するが、１個のスピンユニット５０は図７及び図８の構成の双方を含む。図７はスピンユニット５０間の相互作用を実現するための回路を示し、図８はスピンユニット５０が有するメモリセルＮ，ＩＳ０，ＩＳ１，ＩＵ０，ＩＵ１，ＩＬ０，ＩＬ１，ＩＲ０，ＩＲ１，ＩＤ０，ＩＤ１，ＩＦ０，ＩＦ１にイジングチップ２４外からアクセスするためのインタフェースであるビット線５１とワード線５２とに注目してスピンユニット５０の構成を図示したものである。
【００４３】
スピンユニット５０は、イジングモデルのスピンσｉ、相互作用係数Ｊｊ，ｉ〜Ｊｎ，ｉ及び外部磁場係数ｈｉを保持するために、複数の１ビットのメモリセルＮ，ＩＳ０，ＩＳ１，ＩＵ０，ＩＵ１，ＩＬ０，ＩＬ１，ＩＲ０，ＩＲ１，ＩＤ０，ＩＤ１，ＩＦ０，ＩＦ１を備えている。なお、メモリセルＩＳ０及びＩＳ１、メモリセルＩＵ０及びＩＵ１、メモリセルＩＬ０及びＩＬ１、メモリセルＩＲ０及びＩＲ１、メモリセルＩＤ０及びＩＤ１、並びに、メモリセルＩＦ０及びＩＦ１は、それぞれ２個１組で役割を果たすものであるため、適宜、これらをそれぞれまとめてメモリセル対ＩＳｘ，ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ又はＩＦｘと略記する（図５参照）。
【００４４】
ここで、スピンユニット５０はｉ番目のスピンを表現するものとして説明を行う。メモリセルＮはスピンを表現するためのメモリセルであり、スピンの値を保持する。スピンの値はイジングモデルでは＋１／−１（＋１を上、−１を下とも表現する）であるが、これをメモリセルが保持可能な２値である０／１に対応させる。例えば、＋１を１、−１を０に対応させる。
【００４５】
図５を用いて、スピンユニット５０が有するメモリセル対ＩＳｘ，ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ及びＩＦｘと、図４に示したイジングモデルのトポロジとの対応関係を示す。メモリセル対ＩＳｘは外部磁場係数を記憶する。また、メモリセル対ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ及びＩＦｘは、それぞれ相互作用係数を記憶する。具体的に、メモリセル対ＩＵｘは上側のスピン（Ｙ軸方向で−１）、メモリセル対ＩＬｘは左側のスピン（Ｘ軸方向で−１）、メモリセル対ＩＲｘは右側のスピン（Ｘ軸方向で＋１）、メモリセル対ＩＤｘは下側のスピン（Ｙ軸方向で＋１）、メモリセル対ＩＦｘは奥行き方向に接続するスピン（Ｚ軸方向で＋１ないしは−１）との相互作用係数をそれぞれ記憶する。
【００４６】
また、イジングモデルを有向グラフとして捉えた場合に、あるスピンから見ると他のスピンが自スピンに及ぼす影響の係数を持つことになる。自スピンが他のスピンに与える影響の係数は、それぞれの他のスピンに属する。すなわち、このスピンユニット５０は最大で５個のスピンと接続される。本実施の形態のイジングチップ２４では、外部磁場係数及び相互作用係数として＋１／０／−１の３値に対応する。そのため、外部磁場係数及び相互作用係数を表わすためには、それぞれ２ビットのメモリセルが必要となる。
【００４７】
メモリセル対ＩＳｘ，ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ及びＩＦｘは、末尾の数字が０と１の２つのメモリセル（例えばメモリセル対ＩＳｘの場合にはメモリセルＩＳ０及びＩＳ１）の組合せで、＋１／０／−１の３値を表現する。例えば、メモリセル対ＩＳｘの場合には、メモリセルＩＳ１で＋１／−１を表現し、メモリセルＩＳ１が保持する値が１の時は＋１、メモリセルＩＳ１が保持する値が０の時には−１を表す。
【００４８】
これに加えて、メモリセルＩＳ０が保持する値が０の時には外部磁場係数を０と見なし、メモリセルＩＳ０が保持する値が１の時にはメモリセルＩＳ１が保持する値で決まる＋１／−１のいずれかを外部磁場係数とする。外部磁場係数が０の時は外部磁場係数をディセーブルしていると考えれば、メモリセルＩＳ０に保持された値は外部磁場係数のイネーブルビットであると言うことができる（ＩＳ０＝１の時に、外部磁場係数がイネーブルされる）。相互作用係数を記憶するメモリセル対ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ及びＩＦｘも同様に係数とビットの値とを対応させている。
【００４９】
スピンユニット５０内のメモリセルＮ，ＩＳ０，ＩＳ１，ＩＵ０，ＩＵ１，ＩＬ０，ＩＬ１，ＩＲ０，ＩＲ１，ＩＤ０，ＩＤ１，ＩＦ０及びＩＦ１は、それぞれイジングチップ１３の外部からリード／ライト可能でなければならない。そのために、図８に示すように、スピンユニット５０はビット線５１とワード線５２とをそれぞれ有している。
【００５０】
そしてイジングチップ１３では、図９に示すように、スピンユニット５０が半導体基板上にタイル状に並べられてビット線５１とワード線５２とが接続されており、Ｉ／Ｏアドレスデコーダ３１とＩ／Ｏドライバ３２でこれらのスピンユニット５０を駆動、制御又は読み出しすることにより、一般的なＳＲＡＭ（Static Random Access Memory）と同様にスピンユニット５０内のメモリセルをイジングチップ２４のＳＲＡＭ互換インタフェース（図３参照）でリード／ライトすることができるようになされている。
【００５１】
なお図９上で表現されているスピンユニット５０（ＮxyzというようにＸ軸、Ｙ軸及びＺ軸上の位置によって符号を付与している）が、３次元格子のトポロジでどの頂点に対応するかを図６に示す。３×３×２の３次元格子頂点を２次元平面上に配置するために、Ｘ軸方向の格子頂点配列の間隔にＺ軸方向の格子頂点配列の各格子頂点を挿入するように配置している。すなわち、図９の２次元平面上でのＹ軸方向（図面下側がＹ軸の正方向）にはＮx0z，Ｎx1z，Ｎx2zというように配置されるが、Ｘ軸方向（図面右側がＸ軸の正方向）にはＮ0y0，Ｎ0y1，Ｎ1y0，Ｎ1y1，Ｎ2y0，Ｎ2y1というように、Ｚ軸方向座標が０と１のスピンユニット５０が交互に配置される。
【００５２】
またスピンユニット５０は同時に更新を行うために、相互作用を計算して次のスピンの状態を決定するための回路を、スピンユニット５０毎に独立して持っている。図７では、スピンユニット５０は、外部とのインタフェースとして、信号線ＥＮ，ＮＵ，ＮＬ，ＮＲ，ＮＤ，ＮＦ，ＯＮ及びＲＮＤを有する。信号線ＥＮは、当該スピンユニット５０のスピンの更新を許可する切替え信号を入力するインタフェースである。この切替え信号でセレクタ５３を制御することで、メモリセルＮに保持されたスピンの値を、後述の多数決論理回路５４からＯＲ回路５５を介してセレクタ５３に与えられる値に更新することができる。
【００５３】
信号線ＯＮは、当該スピンユニット５０のスピンの値を他のスピンユニット５０（図４のトポロジで隣接するユニット）に出力するインタフェースである。信号線ＮＵ，ＮＬ，ＮＲ，ＮＤ及びＮＦは、それぞれ他のスピンユニット５０（図４のトポロジで隣接するユニット）が保持するスピンの値を入力するためのインタフェースである。信号線ＮＵは上側のスピン（Ｙ軸方向で−１）、信号線ＮＬは左側のスピン（Ｘ軸方向で−１）、信号線ＮＲは右側のスピン（Ｘ軸方向で＋１）、信号線ＮＤは下側のスピン（Ｙ軸方向で＋１）、信号線ＮＦは奥行き方向に接続するスピン（Ｚ軸方向で＋１ないしは−１）からの入力である。
【００５４】
スピンユニット５０では隣接スピンとの間でエネルギーを最小化するようにスピンの次状態を決定するが、それは隣接スピンと相互作用係数の積、及び、外部磁場係数を見たときに、正の値と負の値のどちらが支配的か判断することと等価である。例えば、ｉ番目スピンσｉに、スピンσｊ，σｋ，σｌ，σｍ及びσｎが隣接しているとして、スピンσｉの次状態は以下のように決まる。
【００５５】
まず、隣接スピンの値はσｊ＝＋１，σｋ＝−１，σｌ＝＋１，σｍ＝−１，σｎ＝＋１とし、相互作用係数はＪｊ，ｉ＝＋１，Ｊｋ，ｉ＝＋１，Ｊｌ，ｉ＝＋１，Ｊｍ，ｉ＝−１，Ｊｎ，ｉ＝−１、外部磁場係数ｈｉ＝＋１とする。このとき、相互作用係数と隣接スピンの積、及び、外部磁場係数をそれぞれ並べると、σｊ×Ｊｊ，ｉ＝＋１，σｋ×Ｊｋ，ｉ＝−１，σｌ×Ｊｌ，ｉ＝＋１，σｍ×Ｊｍ，ｉ＝＋１，σｎ×Ｊｎ，ｉ＝−１，ｈｉ＝＋１となる。外部磁場係数は、常に値が＋１のスピンとの相互作用係数と読み替えて良い。
【００５６】
ここで、ｉ番目のスピンと隣接スピンとの間での局所的なエネルギーは、前述した係数にそれぞれｉ番目スピンの値を乗じて、さらに符号を反転させたものになる。例えば、ｊ番目スピンとの間での局所的なエネルギーは、ｉ番目スピンを＋１とした時には−１、ｉ番目スピンを−１としたときには＋１となるので、ｉ番目スピンを＋１にするほうが、ここでの局所的なエネルギーを小さくする方向に働く。
【００５７】
このような局所的なエネルギーを全ての隣接スピン間と外部磁場係数について考えたときに、ｉ番目スピンを＋１／−１のどちらにしたほうがエネルギーを小さくできるかを計算する。これは、先程示した相互作用係数及び隣接スピンの積と、外部磁場係数とをそれぞれ並べたものにおいて、＋１と−１のどちらが多いか数えれば良い。先程の例では、＋１が４個、−１が２個である。仮に、ｉ番目スピンを＋１とすると、エネルギーの総和は−２、ｉ番目スピンを−１とするとエネルギーの総和は＋２になる。よって、＋１の個数が多い時にはｉ番目スピンの次状態を＋１とし、−１の個数が多い時にはｉ番目スピンの次状態を−１にするという多数決で、エネルギーを最小化するｉ番目スピンの次状態を決定することができる。
【００５８】
図７に示した論理回路５６は、上述の相互作用を行うための回路である。まず、隣接スピンの状態と、相互作用係数の＋１／−１を示すメモリセルＩＵ１，ＩＬ１，ＩＲ１，ＩＤ１，ＩＦ１が保持する値との排他的論理和の否定（ＸＮＯＲ）をＸＮＯＲ回路５７で求める。これにより、その相互作用だけを見た時にエネルギーを最小化するスピンの次状態を計算することができる（＋１は１、−１は０にエンコードされているものとする）。
【００５９】
もし、相互作用係数が＋１／−１だけであれば、ＸＮＯＲ回路５７の出力のうち＋１／−１のどちらが多いかを多数決論理回路５４において多数決論理で判定すればスピンの次状態を決定することができる。外部磁場係数に関しては、常に状態＋１のスピンとの相互作用係数に相当するものと考えれば、単に外部磁場係数の値がスピンの次状態を決定する多数決論理回路５４に入力すべき値となる。
【００６０】
次に、係数０の実現方法について考える。ｎ入力の多数決論理ｆ（Ｉ１，Ｉ２，Ｉ３，……，Ｉｎ）があるとき、以下の命題は真であると言える。まず、入力Ｉ１，Ｉ２，Ｉ３，……，Ｉｎの複製Ｉ’１，Ｉ’２，Ｉ’３，……，Ｉ’ｎがあるとする（任意のｋについて、Ｉｋ＝Ｉ’ｋである）。このとき、ｆ（Ｉ１，Ｉ２，Ｉ３，……，Ｉｎ）の出力は、複製もあわせて入力したｆ（Ｉ１，Ｉ２，Ｉ３，……，Ｉｎ，Ｉ’１，Ｉ’２，Ｉ’３，……，Ｉ’ｎ）と等しい。つまり、各入力変数をそれぞれ２個ずつ入れても、出力は不変である。さらに、入力Ｉ１，Ｉ２，Ｉ３，……，Ｉｎの他に、もう一つの入力Ｉｘと、その反転！Ｉｘがあるとする。このとき、ｆ（Ｉ１，Ｉ２，Ｉ３，……，Ｉｎ，Ｉｘ，！Ｉｘ）の出力は、ｆ（Ｉ１，Ｉ２，Ｉ３，……，Ｉｎ）と等しい。つまり、入力変数とその反転を入力すると、多数決においてその入力変数の影響をキャンセルするように働く。多数決論理のこの性質を利用して係数０を実現する。
【００６１】
具体的には、図７に示すように、ＸＯＲ回路５８を利用して、係数のイネーブルを決めるビット（ビットセルＩＳ０，ＩＵ０，ＩＬ０，ＩＲ０，ＩＤ０及びＩＦ０にそれぞれ保持されたビット）の値により、多数決論理回路５４に、先に述べたスピン次状態の候補となる値の複製か、その反転を同時に入力する。例えば、メモリセルＩＳ０が保持するビットの値が０の場合、メモリセルＩＳ１が保持するビットの値と、メモリセルＩＳ１が保持するビットの値を反転させた値が同時に多数決論理回路５４に入力されるので、外部磁場係数の影響は無い（外部磁場係数が０に相当する）ことになる。また、メモリセルＩＳ０が保持するビットの値が１の場合には、メモリセルＩＳ１が保持するビットの値と、その値と同じ値（複製）が同時に多数決論理回路５４に入力されることになる。
【００６２】
上述したスピン間の相互作用によるエネルギー最小化で、適用されたイジングモデルの基底状態探索を実現することができるが、これだけでは局所解に陥ってしまう可能性がある。基本的に、エネルギーを小さくする方向の動きしかないため、一旦局所解に陥るとそこから抜け出すことができず、大域最適解に到達しない。
【００６３】
そこで本実施の形態においては、局所解から脱出するための手法として、スピンを表現するメモリセルＮの値を確率的に反転されるために、スピンユニット５０はインタフェースとしてＲＮＤ線５９を有する。そしてスピンユニット５０には、乱数発生器２３（図２）から乱数注入線４２（図３）を介してスピンアレイ３０（図３）に与えられた乱数パルスがこのＲＮＤ線５９を介して与えられ、この乱数パルスがＯＲ回路５５に入力することで、スピンの値が確率的に反転される。
【００６４】
（１−３）イジングモデル検証機能
次に、本情報処理装置１に搭載されたイジングモデル検証機能について説明する。これに際し、まず、問題をイジングモデルに変換する際に生成される制約条件について説明する。
【００６５】
図１０は、問題変換プログラム８（図１）による問題変換の一例を示す。この例は、巡回セールスマン問題をイジングモデルに変換する場合を示している。巡回セールスマン問題は、都市の接続関係を表すグラフ６０と、各都市間の距離とが入力として与えられる。これをイジングモデルに変換するには、Ｎ個の都市数に対してＮ２個のスピンにマッピングする。
【００６６】
かかるマッピング後のイジングモデル６１において、列方向に並ぶＮ個のスピンは訪問する都市に対応し、＋１の値をとるスピンの位置で訪問する都市を表す。例えば、ある列の上から２番目のスピンが＋１でそれ以外のスピンが全て−１ならば、この列では２番目の都市に訪問することを意味する。
【００６７】
またイジングモデル６１において、行方向に並ぶＮ個のスピンは都市の訪問順に対応し、＋１の値をとるスピンの位置で、その都市が何番目に訪問されるかを表す。例えば、ある行の３列目のスピンが＋１でそれ以外のスピンが全て−１ならば、この行では３番目の都市が訪問されたことを意味する。
【００６８】
このようなマッピングを行うことで、変換後のイジングモデルの基底状態を求めれば、元の巡回セールスマン問題に対応する解が得られる。ここで、変換後のイジングモデル６１に着目すると、１行につき＋１の値を取るスピンは１つだけであり、１列につき＋１の値を取るスピンは１つだけ、という制約条件が存在する。
【００６９】
また図１１は、問題変換プログラム８による別の問題変換の例を示す。この例は、複雑な接続関係をもつイジングモデル６２から、より単純な格子状の接続関係をもつイジングモデル６３への変換を行う例である。
【００７０】
イジングチップ２４（図２）において表現可能なイジングモデルは、ハードウェアによる実装を容易にするため、格子状などの比較的単純な形状をもつイジングモデルに限られる場合がある。そのような場合に、図１１で示したようなイジングモデルの形状の変換を行う。この変換においては、イジングモデル６２における１つのスピン（図１１においてａ，ｂ，ｃ，ｄと表記）を変換後のイジングモデル６３においては複数のスピンで表現する。図１１では、変換前後で対応するスピンを同じアルファベットで表している。
【００７１】
この変換において、イジングモデル６３内の同一のアルファベットで表されたスピンは、元のイジングモデル６２では単一のスピンであったため、全て同じ値を取る必要がある。従って、この例でもイジングモデル６３において、特定のスピンのグループ（以下、これをスピングループと呼ぶ）が全て同じ値をとらなければならないという制約条件が存在する。
【００７２】
このように問題をイジングモデルに変換した場合、そのイジングモデルの基底状態について何らかの制約条件が存在することがある。そこで、本情報処理装置１には、解くべき問題から変換されたイジングモデルの基底状態探索時における当該イジングモデルのスピンの値（スピン値）を観測し、これらのスピンの値が制約条件を満たしているか否かに基づいて、問題変換プログラム８による問題からイジングモデルへの変換に誤りがないか否か（変換後のイジングモデルが元の問題の性質を正しく反映しているか否か）を検証し、検証結果をユーザに提示するイジングモデル検証機能が搭載されている。
【００７３】
このようなイジングモデル検証機能を実現するための手段として、図１２に示すように、イジングチップ２４に搭載されたスピンアレイ３０を構成するスピンユニット５０のうちの一部には、そのスピンユニット５０が保持するスピンの値（スピン値）を観測する第１のスピン値観測部７０が設けられている。
【００７４】
実際上、第１のスピン値観測部７０は、図１３に示すように、インターバル保持部７１、書込み先保持部７２、長さ保持部７３、書込みカウンタ７４及び処理部７５を備えて構成される。処理部７５は、ＣＰＵ及びメモリを含んでなるマイクロコンピュータ構成を有し、その第１のスピン値観測部７０が設けられたスピンユニット５０のメモリセルＮ（図７）からそのときメモリセルＮが保持するスピンのスピン値を読み出し、読み出したスピン値をチップメモリ３５に書き込む機能を有する。
【００７５】
またインターバル保持部７１、書込み先保持部７２及び長さ保持部７３は、情報処理装置１のＣＰＵ３（図１）の制御のもとにイジングチップ２４のコントローラ３４（図３）によりその第１のスピン値観測部７０に設定されたインターバル、書込み先又は長さといったスピン値の観測条件をそれぞれ保持する機能を有する機能部である。
【００７６】
ここで「インターバル」は、処理部７５が対応するスピンユニット５０のメモリセルＮからスピン値を読み出す間隔を表す。例えば、インターバルの値が「０」の場合、処理部７５は、相互作用クロックの１クロックごとにスピン値を読み出し、インターバルの値が「４」の場合、処理部７５は、スピン値を読み出してから４クロック待って次のスピン値を読み出す（つまり５クロックに１度の割合でスピン値を読み出す）。
【００７７】
また「書込み先」は、処理部７５が対応するスピンユニット５０のメモリセルＮから読み出したスピン値の書込み先を表す。すなわち本実施の形態の場合、各第１のスピン値観測部７０に対して、スピンセルＮから読み出したスピン値を書き込むための領域として、チップメモリ３５内の所定大きさの記憶領域（スピン値を数〜数十程度書き込める程度の記憶領域）ＡＲが割り当てられるが、「書込み先」は、その記憶領域ＡＲの先頭アドレスを表す。
【００７８】
さらに記憶領域ＡＲは１つのスピン値を格納するための複数の小領域ＳＡＲに区分して管理されるが、「長さ」は、その第１のスピン値観測部７０に割り当てられた記憶領域ＡＲを構成する小領域ＳＡＲの数を表す。
【００７９】
書込みカウンタ７４は、その第１のスピン値観測部７０に対応付けられたかかる記憶領域ＡＲのうちの処理部７５がスピン値を書き込むべき小領域ＳＡＲの先頭からのオフセット数をカウントするために利用される。処理部７５は、スピン値をチップメモリ３５内の自己に割り当てられた記憶領域ＡＲに書き込む際、当該記憶領域ＡＲ内の書込みカウンタ７４のカウンタ値に対応する小領域ＳＡＲにそのスピン値を書き込み、その後、書込みカウンタ７４のカウンタ値をインクリメントする。そして処理部７５は、書込みカウンタ７４のカウンタ値が上述の「長さ」を超えた場合にはカウント値を「０」にリセットする。これにより、第１のスピン値観測部７０に割り当てられた記憶領域ＡＲの各小領域ＳＡＲ内にスピン値が上書きされながら循環的に順次格納されていくことになる。
【００８０】
このように本実施の形態においては、第１のスピン値観測部７０によるスピン値の観測は、単に対応するスピンユニット５０のメモリセルＮに格納されたスピン値を読み出すことにより行われる。このとき、第１のスピン値観測部７０が設けられたスピンユニット５０のスピン値を保持するメモリセルＮの構成として、相互作用動作と同時にスピン値を読み出すことができるよう、一般的に用いられるマルチポートＳＲＡＭの構成を適用することができる。
【００８１】
図１４〜図１６は、イジングチップ２４のチップメモリ３５（図３）に保持される第１の観測結果４３（図１４）、第１の処理情報４４（図１５）、及び第１の処理結果４５（図１６）をそれぞれ示す。
【００８２】
第１の観測結果４３は、図１２について上述したようにイジングチップ２４のスピンアレイ３０の一部のスピンユニット５０に設けられた各第１のスピン値観測部７０によりチップメモリ３５にそれぞれ書き込まれた対応する各スピンの値の観測結果であり、図１４に示すように、観測結果（図１４の１行）ごとに時刻４３Ａ、スピンＩＤ４３Ｂ及び値（スピン値）４３Ｃの各情報をそれぞれ含む。
【００８３】
このうち時刻４３Ａは、観測を行った時刻（ここでは、計算開始から経過した相互作用クロックのクロック数）を表し、スピンＩＤ４３Ｂは、観測対象のスピンに付与されたスピンＩＤを表す。また値４３Ｃは、対応するスピンのそのときのスピン値を表す。
【００８４】
従って、図１４の例の場合、例えば、時刻「100」におけるスピンＩＤが「１」、「３」、「５」及び「６」の各スピンのスピン値が「＋１」であり、同時刻におけるスピンＩＤが「２」及び「４」の各スピンのスピン値が「−１」であったことが示されている。
【００８５】
第１の処理情報４４は、上述の制約条件に基づく判定処理の内容を表す情報である。情報処理装置１のＣＰＵ３（図１）は、問題データ７（図１）をイジングモデルに変換する際に得られたそのイジングモデルに関する制約条件に基づいて、そのイジングモデルの対応するスピンの値がその制約条件を満たすか否かを判定するための判定処理を生成する。そしてＣＰＵ３は、そのイジングモデルをイジングチップモジュール６のイジングチップ２４にマッピングする際に、生成した判定処理の内容を第１の処理情報４４として、そのイジングチップモジュール６内のモジュールコントローラ２１（図２）に送信する。かくしてモジュールコントローラ２１は、この第１の処理情報４４をチップメモリ３５（図３）に格納して管理する。
【００８６】
第１の処理情報４４は、図１５に示すように、処理ＩＤ４４Ａ、処理種別４４Ｂ、条件４４Ｃ及び対象スピン４４Ｄの各情報を含む。処理ＩＤ４４Ａは、かかる制約条件に基づき生成された各判定処理にそれぞれ付与された識別子を表し、処理種別４４Ｂは、対応する判定処理の処理内容を表す。また条件４４Ｃは、対応する判定処理における判定条件の内容を表し、対象スピン４４Ｄは、その判定処理の対象とすべきスピン（以下、これを対象スピンと呼ぶ）のスピンＩＤ（イジングチップ２４にマッピングされたイジングモデルにおける対象スピンのスピンＩＤ）を表す。
【００８７】
従って、図１５の例の場合、例えば、処理ＩＤが「１」の判定処理は、イジングモデルにおける「１，３，５，……」というスピンＩＤの各スピンから構成されるスピングループ内のこれらスピンの値が「すべて同値」であるか否かの「条件判定」であることが示されている。
【００８８】
第１の処理結果４５は、第１の処理情報４４に基づきイジングチップ２４のコントローラ３４（図３）が実行した各判定処理の処理結果を表す。コントローラ３４は、情報処理装置１のＣＰＵ３から通知されたインターバルの経過後、チップメモリ３５（図３）に蓄積されている第１の観測結果４３に対して第１の処理情報４４で規定された各判定処理を実行する。図１５の例では、「対象スピン」として指定された各スピンの値がすべて同値であるか否かを判定することがコントローラ３４の処理内容となる。従って、この場合、コントローラ３４は、同じ時刻に観測された対象とする各スピンの値を第１の観測結果４３からそれぞれ読み出し、読み出した各スピンの値がすべて同じであるか否かを判定し、その判定結果をチップメモリ３５に第１の処理結果４５として格納する。
【００８９】
第１の処理結果４５は、図１６に示すように、処理ＩＤ４５Ａ、判定処理の対象となった時刻４５Ｂ及びその判定処理の結果４５Ｃの情報を含む。第１の処理情報４４が図１５の例の場合、対象とする各スピンの値がすべて同値であったときには「１」、そうでないときには「０」がその判定処理の結果４５Ｃとしてチップメモリ３５に格納される。
【００９０】
従って、図１６の例の場合、例えば、時刻「100」に収集した対応するスピンの値に基づいて実行した処理ＩＤが「１」の判定処理（図１５を参照）の結果は「１」であり（つまり対象とする各スピンの時刻「100」における値がすべて同値であった）、時刻「100」に収集した対応するスピンの値に基づいて実行した処理ＩＤが「２」の判定処理の結果は「０」であった（つまり対象とする各スピンの時刻「100」における値がすべて同値でなかった）ことが示されている。
【００９１】
図１７（Ａ）及び（Ｂ）は、図１５の処理ＩＤが「１」及び「２」の２つの判定処理の処理結果を時系列にプロットした例を示す。図１６では、これら２つの判定処理について、時刻「100」のときの結果しか例示していないが、横軸に時刻をとり、縦軸に結果をとって処理ＩＤが「１」及び「２」の２つの判定処理の結果を時系列にプロットした場合、この図１７（Ａ）及び（Ｂ）に示すようなグラフが得られる。なお図１７（Ａ）は、図１５及び図１６における処理ＩＤが「１」の判定処理に対応し、図１７（Ｂ）は、図１５及び図１６における処理ＩＤが「２」の判定処理に対応している。
【００９２】
本実施の形態の場合、情報処理装置１のＣＰＵ３（図３）は、イジングチップ２４のチップメモリ３５に格納された第１の処理結果４５を基底状態探索の実行中に定期的に収集して観測結果１３（図１）としてメモリ４（図１）に格納し、これらの観測結果１３に基づいてイジングモデルに誤りがないか否かの検証を行う。例えば、ＣＰＵ３は、収集した観測結果１３に基づいて、図１５の判定処理ごとに、一定期間内にイジングモデルの対応するスピンの値が制約条件に基づく制約を満たしている確率を時系列に沿って順次算出する。またＣＰＵ３は、一定期間内で処理結果が「１」となる確率の移動平均を算出し、この算出結果に基づいてイジングモデルに誤りがないか否かを検証する。
【００９３】
ここで、イジングチップ２４を用いたイジングモデルの基底状態探索においては、計算開始直後にはスピンの値を頻繁に反転させる（図２の乱数発生器２３が発生する乱数パルスの発生頻度を高くする）ことで局所解からの脱出を促し、その後、時間が経過するにつれてスピンの値を反転させる確率を下げる（図２の乱数発生器２３が発生する乱数パルスの発生頻度を低減させる）ことで基底状態に向かい易くする。このため計算開始直後にはスピンの値がランダムに反転してしまうため、イジングモデルのスピンの値が制約条件を満たさない可能性が高い。
【００９４】
一方、問題を変換することにより得られたイジングモデルが正常状態にある場合には、計算終了に近い時点ではそのイジングモデルの各スピンの値が制約条件を満たしている確率が高まっていくことが期待される。この場合、情報処理装置１のＣＰＵ３により算出される上述の移動平均は、図１８（Ａ）に示すように単調に増加し、最終的に１に収束する。
【００９５】
これに対して、図１８（Ｂ）に示すように、かかる移動平均が十分高くならない、又は、時間経過に伴って増加しない場合には、イジングモデルが正しく元の問題の性質を反映していないと考えることができる。
【００９６】
そこで、ＣＰＵ３は、イジングチップ２４によるイジングモデルの基底状態探索中に、上述の判定処理（図１５において処理ＩＤが付与された判定処理）ごとに、処理結果が「１」となる確率の移動平均を順次算出する。そしてＣＰＵ３は、かかる移動平均の値が予め「１」近くに設定された所定の第１の閾値ＳＨを最終的に上回った判定処理については、イジングモデルにおける対応するスピングループが制約条件を満たしていると判断し、かかる移動平均の値が第１の閾値ＳＨを最終的に上回らなかった判定処理については、イジングモデルにおける対応するスピングループが制約条件を満たしていないと判断して、これらの判断結果をそのイジングモデルの検証結果として図示しない表示装置に表示させる。
【００９７】
具体的に、ＣＰＵ３は、制約条件を満たすスピングループを構成するスピンについては「○」、制約条件を満たさないスピングループを構成するスピンについては「×」をそれぞれ対応付けた図１９に示すような表を検証結果として表示装置に表示させる。かくしてユーザは、表示装置に表示された検証結果に基づいて、そのときイジングチップ２４にマッピングされているイジングモデルが元の問題の性質を正しく反映しているか否かを判断することができる。
【００９８】
（１−４）基底状態探索処理
図２０は、本情報処理装置１において、ユーザから与えられた問題データ７（図１）に基づく問題の解をイジングモデルの基底状態として求める際のＣＰＵ３の処理の流れを示す。この処理は、ユーザが情報処理装置１を操作して、記憶装置５に格納されている問題データ７を指定し、その解を求めるべき旨の指示を情報処理装置１に与えることにより開始される。
【００９９】
実際上、情報処理装置１のＣＰＵ３は、かかる指示が与えられるとこの基底状態探索処理を開始し、まず記憶装置５に格納されているユーザから与えられた問題データ７を取り込む（ＳＰ１）。またＣＰＵ３は、この後、問題変換プログラム８（図１）を実行することにより、記憶装置５に格納した問題データ７をイジングモデルに変換する。この際、ＣＰＵ３は、かかる変換により生成したイジングモデルにおいてスピンが満たすべき制約条件を生成する（ＳＰ２）。
【０１００】
続いて、ＣＰＵ３は、イジングチップ制御プログラム９（図１）を実行し、ステップＳＰ２で生成したイジングモデルをイジングチップモジュール６内のイジングチップ２４（図２）にマッピングした後（ＳＰ３）、そのイジングチップ２４にそのイジングモデルの基底状態の探索処理を実行させる（ＳＰ４）。
【０１０１】
次いで、ＣＰＵ３は、やがて所定回数の相互作用を実行し終えることにより、かかるイジングチップ２４におけるかかるイジングモデルの基底状態探索が完了すると、そのイジングチップ２４からそのイジングモデルのそのときの各スピンの値（つまりそのイジングモデルの基底状態のときの各スピンの値）を取得し、この後、問題変換プログラム８を実行することにより、取得した各スピンの値に基づいて、そのとき得られたそのイジングモデルの基底状態を元の問題の解に変換する（ＳＰ５）。
【０１０２】
そしてＣＰＵ３は、このようにして得られた元の問題の解を情報処理装置１の図示しない表示装置に表示させ（ＳＰ６）、この後、後述するステップＳＰ９の処理が終了するのを待って、この基底状態探索処理を終了する。
【０１０３】
一方、ＣＰＵ３は、ステップＳＰ３〜ステップＳＰ６の処理と並行して、ステップＳＰ７〜ステップＳＰ８の処理を実行することにより、かかるイジングモデルが元の問題の性質を正しく反映しているか否かを検証する。
【０１０４】
実際上、ＣＰＵ３は、イジングチップ制御プログラム９に基づいて、ステップＳＰ２で得られたイジングモデルをイジングチップ２４にマッピングする際、これと併せてそのイジングモデルの生成時に得られた制約条件に基づく上述の第１の処理情報４４と、図１３について上述したそのイジングチップ２４内の各第１のスピン値観測部７０（図１２）に設定すべき既定の第１の観測条件（インターバル、書込み先及び長さ）とをそのイジングチップ２４のコントローラ３４に送信する（ＳＰ７）。
【０１０５】
かくして、かかる制約条件及び第１の観測条件を受信したイジングチップ２４では、コントローラ３４により、第１の処理情報４４がチップメモリ３５に格納されると共に、第１の観測条件がスピンアレイ３０（図１２）内の各第１のスピン値観測部７０（図１２）にそれぞれ設定され、この結果、この後実行されるイジングモデルの基底状態探索時に、この第１の観測条件に従った対応するスピンの値の観測がこれら第１のスピン値観測部７０によりそれぞれ行われる。また、これと並行して、これら第１のスピン値観測部７０による対応するスピンの値の観測結果でなる第１の観測結果４３（図１４）に基づく図１５について上述した判定処理がコントローラ３４により逐次実行され、その処理結果が第１の処理結果４５として逐次チップメモリ３５に格納される。
【０１０６】
そしてＣＰＵ３は、イジングチップ２４においてイジングモデルの基底状態探索が実行されている間、観測結果検証プログラム１１に基づいて、上述のチップメモリ３５に格納された第１の処理結果４５を定期的に読み出し、これを観測結果１３としてメモリ４に格納すると共に、この観測結果１３に基づいて、そのときイジングチップ２４にマッピングされているイジングモデルが元の問題の性質を正しく反映しているか否かの図１７〜図１９について上述した検証処理を行う（ＳＰ８）。
【０１０７】
そしてＣＰＵ３は、かかる検証処理が終了すると、観測結果検証プログラム１１に基づいて、ステップＳＰ８の検証処理の処理結果を情報処理装置１の表示装置に表示させ（ＳＰ９）、この後、ステップＳＰ６の処理が終了するのを待って、この基底状態探索処理を終了する。
【０１０８】
（１−５）本実施の形態の効果
以上のように本実施の形態の情報処理装置１では、イジングモデルの基底状態の探索途中における各スピンの値を観測し、これらスピンの値が制約条件を満たすか否かに基づいてそのイジングモデルが元の問題の性質を正しく反映しているか否かを検証し、その検証結果を表示する。従って、本実施の形態によれば、表示された検証結果に基づいてユーザがそのイジングモデルが元の問題の性質を正しく反映しているか否かを容易に判断することができ、かくして有用性及び信頼性の高い情報処理装置を構築することができる。
【０１０９】
（２）第２の実施の形態
（２−１）乱数発生頻度制御機能
イジングモデルの基底状態探索を行う場合、局所解を脱出するためにスピン値を反転させる確率を適切にコントロールすることが重要である。通常、基底状態探索では、初期時には、局所解を脱出し、解空間の広い範囲を探索できるようにスピン値を反転させる反転確率（具体的には、図２の乱数発生器２３における乱数パルスの発生頻度）を高めに設定し、その後、徐々にかかる反転確率を下げる（乱数発生器２３における乱数パルスの発生頻度を下げる）ことで基底状態に収束し易くしている。
【０１１０】
このとき、反転確率を下げるのが早すぎると、解空間を探索できる範囲が狭まってしまい、解精度の低下につながるという問題があり、反転確率を下げるのが遅すぎると、基底状態精度は高まるものの、基底状態探索に要する時間が増加するという問題がある。一方で、反転確率を下げる適切な早さは問題ごとに異なり、事前に求めることは難しいという問題もある。
【０１１１】
そこで、本実施の形態においては、基底状態探索時におけるイジングモデルのスピンの値を観測し、ごとに、一定時間内に値が「＋１」又は「−１」（以下においては、「＋１」とする）となる確率を継続的に算出し、この確率の平均値が一定値に収束した場合（正確には、今回算出した当該平均値と、前回算出した当該平均値との差分が予め設定された所定の第２の閾値を下回った場合）にスピンが平衡状態に達したと判断して、乱数パルスの発生頻度を下げるように乱数発生器２３（図２）を制御する。
【０１１２】
以下、このように乱数発生器２３における乱数パルスの発生頻度を制御する機能（以下、これを乱数発生頻度制御機能と呼ぶ）を備えた本実施の形態による情報処理装置８０（図１）について、図１及び図２１〜図２６を参照して説明する。なお、図２１〜図２６においては、図１〜図２０との対応部分に同一符号を付し、その詳細については説明を省略する。
【０１１３】
（２−２）本実施の形態による情報処理装置の構成
図１において、８０は全体として第２の実施の形態による情報処理装置を示す。この情報処理装置８０は、第１の実施の形態について上述したイジングモデル検証機能に加えて、かかる乱数発生頻度制御機能が搭載されている点が第１の実施の形態による情報処理装置１と相違する。
【０１１４】
実際上、本実施の形態の情報処理装置８０の場合、イジングチップ制御プログラム８１は、問題変換プログラム８により問題を変換することにより得られたイジングモデルをイジングチップモジュール８２内のイジングチップにマッピングする際、上述の制約条件及び第１の観測条件に加えて、スピンの値が「＋１」となる確率を監視する際の条件（以下、これを監視条件と呼ぶ）と、その際のスピンの観測条件（以下、これを第２の観測条件と呼ぶ）とをそのイジングチップモジュール８２に送信する。
【０１１５】
具体的に、イジングチップ制御プログラム８１は、かかる監視条件として、観測対象とするスピンと、そのスピンの値が「＋１」となる確率を計算する時間間隔とをイジングチップ９０（図２１）に送信する。またイジングチップ制御プログラム８１は、かかる第２の観測条件として、第２のスピン値観測部に設定すべき上述のインターバル、書込み先及び長さをイジングチップモジュール８２に送信する。
【０１１６】
イジングチップモジュール８２は、その内部に設けられたイジングチップ９０（図２１）の構成が異なる点を除いて第１の実施の形態のイジングチップモジュール６と同様の構成を有する。また本実施の形態のイジングチップ９０は、図２１に示すように、スピンアレイ９１の構成が異なる点と、チップメモリ３５に第１の観測結果４３、第１の処理情報４４及び第１の処理結果４５に加えて、第２の観測結果９２、第２の処理情報９３及び第２の処理結果９４が格納される点と、コントローラ９５がイジングモデル検証機能に関する処理機能に加えて、上述の乱数発生頻度制御機能に関連する処理機能を備えている点とを除いて第１の実施の形態のイジングチップ２４（図３）と同様の構成を有する。
【０１１７】
この場合、本実施の形態のスピンアレイ９１は、図２２に示すように、第１のスピン値観測部７０が設けられていないスピンユニット５０のうちの一部又は全部のスピンユニットに第２のスピン値観測部１００が設けられている点が第１の実施の形態のスピンアレイ３０（図３）と相違する。この第２のスピン値観測部１００は、乱数発生頻度制御機能のために、対応するスピンユニット５０が保持するスピンの値を観測するためのものであり、第１のスピン値観測部７０と同様の構成を有する。
【０１１８】
そしてイジングチップ９０のコントローラ９５（図２１）は、情報処理装置１のＣＰＵ３から第２の観測条件が与えられた場合、その第２の観測条件に含まれるインターバル、書込み先及び長さを第２のスピン値観測部１００に設定する。かくして第２のスピン値観測部１００は、基底状態探索時、第１のスピン値観測部７０と同様にして、対応するスピンユニット５０のメモリセルＮに格納されたスピンの値を第２の観測条件として設定されたインターバルで取得し、取得したスピンの値を第２の観測結果としてチップメモリ３５内の第２の観測条件として設定された書込み先に書き込む。
【０１１９】
一方、図２３〜図２５は、イジングチップ９０のチップメモリ３５に保持される第２の観測結果９２（図２３）、第２の処理情報９３（図２４）及び第２の処理結果９４（図２５）をそれぞれ示す。
【０１２０】
第２の観測結果９２は、上述のように第２のスピン値観測部１００によりチップメモリ３５にそれぞれ書き込まれたスピンの値の観測結果であり、図２３に示すように、観測結果（図２３の１行）ごとに時刻９２Ａ、スピンＩＤ９２Ｂ及び値（スピン値）９２Ｃの各情報をそれぞれ含む。時刻９２Ａ、スピンＩＤ９２Ｂ及び値９２Ｃの内容は図１４について上述した第１の観測結果４３と同様であるため、ここでの説明は省略する。
【０１２１】
また第２の処理情報９３は、上述の監視条件を表す情報である。コントローラ９５は、情報処理装置１のＣＰＵ３から与えられた監視条件を第２の処理情報９３としてチップメモリ３５に格納して管理する。この第２の処理情報９３は、図２４に示すように、処理ＩＤ９３Ａ、処理種別９３Ｂ、時間間隔９３Ｃ及び対象スピン９３Ｄの各情報を含む。処理ＩＤ９３Ａ、処理種別９３Ｂ及び対象スピンの内容は、図１５について上述した第１の処理情報４４と同様であるため、ここでの説明は省略する。なお図２４における処理種別の「分布計算」とは、スピンの値が「＋１」となる確率を求める処理を表す。また時間間隔は、かかる確率を計算すべき間隔を表す。
【０１２２】
第２の処理結果９４は、第２の処理情報９３に基づきコントローラ９５が実行した各処理の処理結果である。コントローラ９５は、情報処理装置８０のＣＰＵ３から通知されたインターバル経過後、チップメモリ３５に蓄積されている第２の観測結果９２に対して第２の処理情報９３で規定された各処理を実行する。図２４の例では、時間間隔として指定された期間（相互作用クロックの「100」クロック分の期間）の観測結果から、対象とするスピンの値が「＋１」となる確率を求めることがコントローラ９５の処理内容となる。従って、この場合、コントローラ９５は、１つのスピンについて上述の期間内の観測結果（スピンの値）を第２の観測結果９２からすべて読み出し、読み出した各スピンの値が「＋１」となる確率を計算して、その計算結果をチップメモリ３５に第２の処理結果９４として格納する。
【０１２３】
第２の処理結果９４は、図２５に示すように、スピンＩＤ９４Ａ、処理の対象となった時刻９４Ｂ及びその処理の結果９４Ｃの情報を含む。図２５の例の場合、時刻９４Ｂは監視条件として指定された時間間隔の開始時刻を表し、結果は、対応する時間間隔における上述の計算結果（対応するスピンの値が「＋１」となる確率）を表す。
【０１２４】
従って、図２５の例の場合、スピンＩＤが「１」のスピンについては、時刻「100」から指定された時間間隔内の第２の観測結果９２に基づいて計算したその値が「＋１」となる確率が「0.45」であり、同様に計算した時刻「200」、時刻「300」、時刻「400」、時刻「500」から当該時間間隔内の第２の観測結果９２に基づいて計算したかかる確率がそれぞれ「0.38」、「0.34」、「0.33」、「0.33」であったことが示されている。
【０１２５】
図２６は、本情報処理装置８０において、ユーザから与えられた問題データ７（図１）に基づく問題の解をイジングモデルの基底状態として求める際のＣＰＵ３の処理の流れを示す。この処理は、ユーザが情報処理装置８０を操作して、記憶装置５に格納されている問題データ７を指定し、その解を求めるべき旨の指示を情報処理装置８０に与えることにより開始される。
【０１２６】
実際上、情報処理装置８０のＣＰＵ３は、かかる指示が与えられるとこの基底状態探索処理を開始し、まず、記憶装置５に格納されているユーザから与えられた問題データ７を取り込む（ＳＰ１０）。またＣＰＵ３は、問題変換プログラム８（図１）を実行することにより、記憶装置５に格納した問題データ７をイジングモデルに変換する。この際、ＣＰＵ３は、かかる変換により生成したイジングモデルにおいてスピンが満たすべき制約条件を生成する（ＳＰ１１）。
【０１２７】
この後、ＣＰＵ３は、ステップＳＰ１２〜ステップＳＰ１７の処理をイジングチップ制御プログラム８１（図１）に基づいて実行する。すなわちＣＰＵ３は、まず、ステップＳＰ１１２で生成したイジングモデルをイジングチップモジュール８２（図１）内のイジングチップ９０（図２１）にマッピングする（ＳＰ１２）。
【０１２８】
続いて、ＣＰＵ３は、予め指定された上述の監視条件及び第２の観測条件をかかるイジングチップ９０に送信する（ＳＰ１３）。かくして、かかる監視条件及び第２の観測条件を受信したイジングチップ９０では、コントローラ９５により第２の観測条件がスピンアレイ９１（図２１）内の各第２のスピン値観測部１００（図２２）にそれぞれ設定される。
【０１２９】
次いで、ＣＰＵ３は、イジングチップモジュール８２のモジュールコントローラ２１（図２）を介して相互作用クロック生成部２２（図２）を制御することにより、相互作用クロック生成部２２に相互作用クロックの生成を開始させると共に、当該モジュールコントローラ２１を介して乱数発生器２３（図２）に乱数パルスの発生頻度として初期値を設定することにより、乱数発生器２３に乱数パルスの発生を開始させる（ＳＰ１４）。これにより相互作用クロック生成部２２により生成された相互作用クロックがイジングチップ９０に与えられ、この相互作用クロックに同期して、イジングチップ９０において、イジングモデルにおけるスピン間の相互作用動作が開始される。また、乱数発生器２３において発生された乱数パルスもイジングチップ９０に与えられ、この乱数パルスに基づいてイジングチップ９０内の各スピンの値が確率的に反転される。
【０１３０】
そしてＣＰＵ３は、この後、イジングチップ９０にマッピングしたイジングモデルの各スピンの値が平衡状態となるのを待ち受ける（ＳＰ１５）。
【０１３１】
このとき、かかるイジングチップ９０のコントローラ９５（図２１）は、ステップＳＰ１３でＣＰＵ３から与えられた監視条件に基づいて、対応する各スピンの値が一定時間内に「＋１」となる確率をそれぞれ算出すると共に、当該確率の平均値を算出し、今回算出した当該平均値と、前回算出した当該平均値との差分を算出する処理を、当該監視条件において指定された時間間隔で断続的に実行する。そしてコントローラ９５は、かかる差分が上述の第２の閾値を下回った場合に、スピンが平衡状態に達したと判断して、その旨をＣＰＵ３に通知する。
【０１３２】
ＣＰＵ３は、かかる通知が与えられると、イジングチップモジュール８２（図１）のモジュールコントローラ２１（図２）を介して乱数発生器２３（図２）を制御することにより、乱数パルスの発生頻度を所定値だけ低減させ（ＳＰ１６）、低減後の発生頻度が予め規定された最終的な発生頻度に到達したか否かを判断する（ＳＰ１７）。
【０１３３】
そしてＣＰＵ３は、この判断で否定結果を得るとステップＳＰ１５に戻り、この後、ステップＳＰ１７で肯定結果を得るまでステップＳＰ１５〜ステップＳＰ１７の処理を繰り返す。そしてＣＰＵ３は、やがて乱数パルスの発生頻度が最終的な発生頻度に到達することによりステップＳＰ１７で肯定結果を得ると、そのイジングチップ９０からそのイジングモデルのそのときの各スピンの値（つまりそのイジングモデルの基底状態のときの各スピンの値）を取得し、この後、問題変換プログラム８を実行することにより、取得した各スピンの値に基づいて、そのとき得られたそのイジングモデルの基底状態を元の問題の解に変換する（ＳＰ１８）。
【０１３４】
そしてＣＰＵ３は、このようにして得られた元の問題の解を情報処理装置１の図示しない表示装置に表示させ（ＳＰ１９）、この後、後述するステップＳＰ２２の処理が終了するのを待って、この基底状態探索処理を終了する。
【０１３５】
一方、ＣＰＵ３は、ステップＳＰ１２〜ステップＳＰ１９の処理と並行して、ステップＳＰ２０〜ステップＳＰ２２の処理を実行することにより、かかるイジングモデルが元の問題の性質を正しく反映しているか否かを検証する。このステップＳＰ２０〜ステップＳＰ２２の処理内容は、図２０について上述した第１の実施の形態のステップＳＰ７〜ステップＳＰ９と同様であるため、ここでの説明は省略する。
【０１３６】
そしてＣＰＵ３は、この後、ステップＳＰ１９の処理が終了するのを待って、この基底状態探索処理を終了する。
【０１３７】
（２−３）本実施の形態の効果
以上のように本実施の形態の情報処理装置８０では、イジングモデルの基底状態の探索途中における各スピンの値を観測し、これらスピンごとにその値が一定期間内に「＋１」となる確率をそれぞれ断続的に算出すると共に、算出したスピンごとの当該確率の平均値を断続的に算出し、今回算出した当該平均値と、前回算出した当該平均値との差分が第２の閾値を下回った場合に、スピンが平衡状態に達したと判断して、乱数パルスの発生頻度を下げるように乱数発生器２３を制御する。
【０１３８】
従って、本実施の形態によれば、乱数発生器２３により発生させる乱数パルスの発生頻度の切替えタイミングを事前に算出することなく、基底状態探索の進行状況を反映しながらかかる切替えタイミングをコントロールできるため、不必要に長い相互作用を行うことなく、高い精度の解を得ることができ、かくして第１の実施の形態の情報処理装置１と比べてより一層と有用性及び信頼性の高い情報処理装置を構築することができる。
【０１３９】
（３）他の実施の形態
なお上述の第１及び第２の実施の形態においては、情報処理装置１，８０のＣＰＵ３がイジングチップ２４，９０のコントローラ３４，９５を介して第１及び又は第２のスピン値観測部７０，１００に第１又は第２の観測条件（インターバル、書込み先及び長さ）を設定するようにした場合について述べたが、本発明はこれに限らず、これら第１又は第２の観測条件の各値が予め固定値として各第１及び第２のスピン値観測部７０，１００にそれぞれ設定されているようにしても良い。
【０１４０】
また上述の第１及び第２の実施の形態においては、第１及び又は第２のスピン値観測部７０，１００の処理部７５をＣＰＵ及びメモリを含んでなるマイクロコンピュータ構成を有し、ＣＰＵがメモリに格納されたソフトウェアを実行することにより処理部７５全体として、第１又は第２の観測条件に従って対応するスピンの値を観測（取得）するようにした場合について述べたが、本発明はこれに限らず、例えば処理部７５を論理回路として構成するようにしても良い。
【０１４１】
さらに上述の実施の形態においては、イジングチップ２４，９０を制御する機能と、問題をイジングモデルに変換する機能と、問題をイジングモデルに変換する際に得られた当該イジングモデルの各スピンが満たすべき制約条件と、各第１のスピン値観測部７０によりそれぞれ取得されたイジングモデルの基底状態探索時における対応する各スピンの値とに基づいて、イジングモデルが問題の性質を正しく反映しているか否かを検証する機能と、各第２のスピン値観測部１００によりそれぞれ取得されたイジングモデルの基底状態探索時における対応する各スピンの値に基づいて、スピンごとに、所定の第２の時間内における当該スピンの値が所定値となる確率を継続的に算出し、算出結果に基づいて、乱数発生器における乱数パルスの発生頻度を制御する機能とを有する情報処理部を、情報処理装置１，８０のＣＰＵ３と、イジングチップ２４，９０内のコントローラ３４，９５とで構成するようにした場合について述べたが、本発明はこれに限らず、これらの機能をＣＰＵ３及びコントローラ３４，９５のいずれか一方に集約して持たせるようにしても良い。ただし、第１及び第２の実施の形態のようにこれらの機能をＣＰＵ３及びコントローラ３４，９５に分けて持たせることにより、これらＣＰＵ３及びコントローラ３４，９５の負荷を分散させることができる。
【０１４２】
さらに上述の第２実施の形態においては、第１のスピン値観測部７０が対応付けて設けられていないスピンに対応させて第２のスピン値観測部１００を設けるようにした場合について述べたが、本発明はこれに限らず、同じ１つのスピンに対応させて第１及び第２のスピン値観測部７０，１００を設けるようにしても良い。さらには、観測対象の各スピンにそれぞれ対応させてそれぞれ１つのスピン値観測部を設け、このスピン値観測部により第１及び第２の観測条件に従って対応するスピンの値を観測（取得）するようにしても良い。
【産業上の利用可能性】
【０１４３】
本発明は、問題の解をイジングモデルの基底状態として求める情報処理装置に適用することができる。
【符号の説明】
【０１４４】
１，８０……情報処理装置、３……ＣＰＵ、６，８２……イジングチップモジュール、８……問題変換プログラム、９，８１……イジングチップ制御プログラム、１１……観測結果検証プログラム、１２……制約条件、２２……相互作用クロック生成部、２３……乱数発生器、２４，９０……イジングチップ、３０，９１……スピンアレイ、３４，９５……コントローラ、３５……チップメモリ、４３，９２……観測結果、４４，９３……処理情報、４５，９４……処理結果、５０……スピンユニット、７０，１００……スピン値観測部、７１……インターバル保持部、７２……書込み先保持部、７３……長さ保持部、７４……書込みカウンタ、７５……処理部。
【図１】
2017017807.tif 000004
【図２】
2017017807.tif 000005
【図３】
2017017807.tif 000006
【図４】
2017017807.tif 000007
【図５】
2017017807.tif 000008
【図６】
2017017807.tif 000009
【図７】
2017017807.tif 000010
【図８】
2017017807.tif 000011
【図９】
2017017807.tif 000012
【図１０】
2017017807.tif 000013
【図１１】
2017017807.tif 000014
【図１２】
2017017807.tif 000015
【図１３】
2017017807.tif 000016
【図１４】
2017017807.tif 000017
【図１５】
2017017807.tif 000018
【図１６】
2017017807.tif 000019
【図１７】
2017017807.tif 000020
【図１８】
2017017807.tif 000021
【図１９】
2017017807.tif 000022
【図２０】
2017017807.tif 000023
【図２１】
2017017807.tif 000024
【図２２】
2017017807.tif 000025
【図２３】
2017017807.tif 000026
【図２４】
2017017807.tif 000027
【図２５】
2017017807.tif 000028
【図２６】
2017017807.tif 000029
【国際調査報告】
2017017807.tif 000030
2017017807.tif 000031