(57)【要約】【課題】  安価かつ容易に製造でき、任意のイジングモデルの基底状態を探索可能な情報処理装置及びその制御方法を提案する。【解決手段】  それぞれ１又は複数のスピンの値を保持し、スピン間の相互作用を模擬する複数の半導体チップと、必要な半導体チップ間をそれぞれ接続するチップ間配線と、各半導体チップに相互作用演算をそれぞれ実行させる制御部とを情報処理装置に設け、制御部が、問題のデータを、当該問題のイジングモデルの基底状態のスピン配列を変化させずに、複数の半導体チップにより表現可能な格子状のイジングモデルのデータに変換し、変換した格子状のイジングモデルのデータを分割して複数の半導体チップにそれぞれ割り当て、各半導体チップに相互作用演算をそれぞれ実行させるようにした。
2016199220.tif 000002
【特許請求の範囲】
【請求項１】
イジングモデルである問題のエネルギーを最小とするスピン配列である基底状態又は当該基底状態の近似解を前記問題の解として算出する情報処理装置において、
それぞれ１又は複数のスピンの値を保持し、前記スピン間の相互作用を模擬する複数の半導体チップと、
必要な前記半導体チップ間をそれぞれ接続するチップ間配線と、
各前記半導体チップを制御して、当該各半導体チップに相互作用演算をそれぞれ実行させる制御部と
を備え、
前記制御部は、
前記問題のデータを、当該問題のイジングモデルの基底状態のスピン配列を変化させずに、複数の前記半導体チップにより表現可能な格子状のイジングモデルのデータに変換し、
変換した前記格子状のイジングモデルのデータを分割して複数の前記半導体チップにそれぞれ割り当てる
ことを特徴とする情報処理装置。
【請求項２】
前記制御部は、
前記問題のデータを完全グラフのイジングモデルを表す中間データに変換し、
当該中間データを前記格子状のイジングモデルのデータに変換する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記制御部は、
前記問題のイジングモデルの各第１のスピンを、当該第１のスピンに相互作用を及ぼす第２のスピンと同じ数の第３のスピンの集合にそれぞれ置き換え、当該第３のスピンの集合を前記格子状のイジングモデルが全体として階段状となるように配置するようにして、当該問題のデータを前記格子状のイジングモデルのデータに変換する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項４】
前記制御部は、
ｉ番目の前記第２のスピンと、当該第２のスピンに対応するｉ番目の前記第３のスピンとの相互作用係数をＪｉとし、ｉ番目の前記第３のスピンにおける外部磁場係数をａｉとし、ｉ番目の前記第３のスピンと、ｉ＋１番目の前記第３のスピンとの間の相互作用係数をｂｉとし、前記第２のスピンの数をｎ個とし、当該第３のスピンに対応する前記第１のスピンにおける外部磁場係数をｈ０として、次式
【数５】
2016199220.tif 000007
及び、次式
【数６】
2016199220.tif 000008
を満たすように、前記格子状のイジングモデルの各相互作用係数及び各外部磁場係数をそれぞれ設定する
ことを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記制御部は、
ｉ番目の前記第２のスピンと、当該第２のスピンに対応するｉ番目の前記第３のスピンとの相互作用係数をＪｉとし、ｉ番目の前記第３のスピンにおける外部磁場係数をａｉとし、ｉ番目の前記第３のスピンと、ｉ＋１番目の前記第３のスピンとの間の相互作用係数をｂｉとし、前記第２のスピンの数をｎ個とし、当該第３のスピンに対応する前記第１のスピンにおける外部磁場係数をｈ０として、次式
【数７】
2016199220.tif 000009
で定義される定数Ｃを用いて、ｉ番目の前記第３のスピンについての相互作用係数Ｊｉ及び外部磁場係数ａｉを次式
【数８】
2016199220.tif 000010
を満たすように設定する
ことを特徴とする請求項３に記載の情報処理装置。
【請求項６】
前記制御部は、
前記相互作用演算の終了後における同一の前記第１のスピンに対応するすべての前記第３のスピンが同値である場合には、当該値を当該第１のスピンの値として決定し、
前記相互作用演算の終了後における同一の前記第１のスピンに対応するすべての前記第３のスピンが同値でない場合には、スピン数が多い方の値を当該第１のスピンの値として決定する
ことを特徴とする請求項３に記載の情報処理装置。
【請求項７】
イジングモデルである問題のエネルギーを最小とするスピン配列である基底状態又は当該基底状態の近似解を前記問題の解として算出する情報処理装置の制御方法において、
前記情報処理装置は、
それぞれ１又は複数のスピンの値を保持し、前記スピン間の相互作用を模擬する複数の半導体チップと、
必要な前記半導体チップ間をそれぞれ接続するチップ間配線と、
各前記半導体チップを制御して、当該各半導体チップに相互作用演算をそれぞれ実行させる制御部と
を有し、
前記制御部が、前記問題のデータを、当該問題のイジングモデルの基底状態のスピン配列を変化させずに、複数の前記半導体チップにより表現可能な格子状のイジングモデルのデータに変換する第１のステップと、
前記制御部が、変換した前記格子状のイジングモデルのデータを分割して複数の前記半導体チップにそれぞれ割り当てる第２のステップと、
前記制御部が、各前記半導体チップに前記相互作用演算をそれぞれ実行させる第３のステップと
を備えることを特徴とする情報処理装置の制御方法。
【請求項８】
前記第１のステップにおいて、前記制御部は、
前記問題のデータを完全グラフのイジングモデルを表す中間データに変換し、
当該中間データを前記格子状のイジングモデルのデータに変換する
ことを特徴とする請求項７に記載の情報処理装置の制御方法。
【請求項９】
前記第１のステップにおいて、前記制御部は、
前記問題のイジングモデルの各第１のスピンを、当該第１のスピンに相互作用を及ぼす第２のスピンと同じ数の第３のスピンの集合にそれぞれ置き換え、当該第３のスピンの集合を前記格子状のイジングモデルが全体として階段状となるように配置するようにして、当該問題のデータを前記格子状のイジングモデルのデータに変換する
ことを特徴とする請求項７に記載の情報処理装置の制御方法。
【請求項１０】
前記第１のステップにおいて、前記制御部は、
ｉ番目の前記第２のスピンと、当該第２のスピンに対応するｉ番目の前記第３のスピンとの相互作用係数をＪｉとし、ｉ番目の前記第３のスピンにおける外部磁場係数をａｉとし、ｉ番目の前記第３のスピンと、ｉ＋１番目の前記第３のスピンとの間の相互作用係数をｂｉとし、前記第２のスピンの数をｎ個とし、当該第３のスピンに対応する前記第１のスピンにおける外部磁場係数をｈ０として、次式
【数９】
2016199220.tif 000011
及び、次式
【数１０】
2016199220.tif 000012
を満たすように、前記格子状のイジングモデルの各相互作用係数及び各外部磁場係数をそれぞれ設定する
ことを特徴とする請求項９に記載の情報処理装置の制御方法。
【請求項１１】
前記第１のステップにおいて、前記制御部は、
ｉ番目の前記第２のスピンと、当該第２のスピンに対応するｉ番目の前記第３のスピンとの相互作用係数をＪｉとし、ｉ番目の前記第３のスピンにおける外部磁場係数をａｉとし、ｉ番目の前記第３のスピンと、ｉ＋１番目の前記第３のスピンとの間の相互作用係数をｂｉとし、前記第２のスピンの数をｎ個とし、当該第３のスピンに対応する前記第１のスピンにおける外部磁場係数をｈ０として、次式
【数１１】
2016199220.tif 000013
で定義される定数Ｃを用いて、ｉ番目の前記第３のスピンについての相互作用係数Ｊｉ及び外部磁場係数ａｉを次式
【数１２】
2016199220.tif 000014
を満たすように設定する
ことを特徴とする請求項９に記載の情報処理装置の制御方法。
【請求項１２】
前記第３のステップにおいて、前記制御部は、
前記相互作用演算の終了後における同一の前記第１のスピンに対応するすべての前記第３のスピンが同値である場合には、当該値を当該第１のスピンの値として決定し、
前記相互作用演算の終了後における同一の前記第１のスピンに対応するすべての前記第３のスピンが同値でない場合には、スピン数が多い方の値を当該第１のスピンの値として決定する
ことを特徴とする請求項９に記載の情報処理装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理装置及びその制御方法に関し、特に、イジングモデルの基底状態探索を行うようにして最低化問題を解く情報処理装置に適用して好適なものである。
【背景技術】
【０００２】
イジングモデルは磁性体の振舞いを説明するための統計力学のモデルである。イジングモデルは＋１／−１（ないしは、０／１、上／下）の２値をとるスピンと、スピン間の相互作用を示す相互作用係数、及び、スピン毎にある外部磁場係数で定義される。【０００３】
イジングモデルは与えられたスピン配列、相互作用係数、及び、外部磁場係数から、その時のエネルギーを計算することが出来る。イジングモデルのエネルギー関数は一般的に次式で表わされる。【０００４】
【数１】
2016199220.tif 000003
【０００５】
なお、σｉ，σｊはそれぞれｉ番目とｊ番目のスピンの値、Ｊｉ，ｊはｉ番目とｊ番目のスピンの間の相互作用係数、ｈｉはｉ番目のスピンに対する外部磁場係数、σはスピンの配列を表わすものとする。【０００６】
（１）式において、第一項は、スピン間の相互作用に起因するエネルギーを計算するものである。一般的にイジングモデルは無向グラフとして表現され、ｉ番目スピンからｊ番目スピンへの相互作用と、ｊ番目スピンからｉ番目スピンへの相互作用を区別することはない。そのため、第一項ではｉ＜ｊを満たすσｉ，σｊの組み合わせについて、相互作用係数の影響を計算している。また第二項は、各スピンに対する外部磁場に起因するエネルギーを計算するものである。【０００７】
イジングモデルの基底状態探索はイジングモデルのエネルギー関数（一般にハミルトニアンとも呼ばれる）を最小化するスピン配列を求める最適化問題である。非平面グラフで表されるイジングモデルの基底状態探索はＮＰ困難であることが知られている。近年この問題を効率的に解くため基底状態を探索する装置が提案されている（特許文献１）。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１２−２１７５１８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ところで、かかる特許文献１に開示された装置では、ハードウェア構成によって表現可能なグラフ構造（イジングモデル）が限定される。しかしながら、最適化問題をイジングモデルの基底状態探索問題に変換した場合、変換後のイジングモデルがその最適化問題に固有の形態となるため、変換後のイジングモデルを常に引用文献１の装置にマッピングできるとは限らない。よって、様々な最適化問題への対応を考えると、任意のイジングモデルの基底状態探索が可能なハードウェアの実現が要求される。【００１０】
完全グラフを表現可能なハードウェアによれば、この課題は解決される。しかしこの場合、ハードウェア内の配線が複雑になり、スケーラビリティおよびエネルギー効率が低下するだけでなく、安価かつ容易に製造できないという問題がある。【００１１】
そこで基底状態を変化させることなく、基底状態を求めたいイジングモデルを、ハードウェアが表現可能なグラフで表されるイジングモデルに変換することが求められる。特に、半導体装置のような固体素子でハードウェアを構成するとき、ＤＲＡＭ（Dynamic Random Access Memory）やＳＲＡＭ（Static Random Access Memory）などの記憶装置に代表されるようなアレイ構造で実現される。そのため任意のイジングモデルを基底状態不変で格子イジングモデルに変換することが望ましい。【００１２】
本発明は以上の点を考慮してなされたもので、安価かつ容易に製造でき、任意のイジングモデルの基底状態を探索可能な情報処理装置及びその制御方法を提案しようとするものである。
【課題を解決するための手段】
【００１３】
かかる課題を解決するため本発明においては、イジングモデルである問題のエネルギーを最小とするスピン配列である基底状態又は当該基底状態の近似解を前記問題の解として算出する情報処理装置において、それぞれ１又は複数のスピンの値を保持し、前記スピン間の相互作用を模擬する複数の半導体チップと、必要な前記半導体チップ間をそれぞれ接続するチップ間配線と、各前記半導体チップを制御して、当該各半導体チップに相互作用演算をそれぞれ実行させる制御部とを有し、前記制御部が、前記問題のデータを、当該問題のイジングモデルの基底状態のスピン配列を変化させずに、複数の前記半導体チップにより表現可能な格子状のイジングモデルのデータに変換し、変換した前記格子状のイジングモデルのデータを分割して複数の前記半導体チップにそれぞれ割り当てるようにした。【００１４】
また本発明においては、イジングモデルである問題のエネルギーを最小とするスピン配列である基底状態又は当該基底状態の近似解を前記問題の解として算出する情報処理装置の制御方法において、前記情報処理装置は、それぞれ１又は複数のスピンの値を保持し、前記スピン間の相互作用を模擬する複数の半導体チップと、必要な前記半導体チップ間をそれぞれ接続するチップ間配線と、各前記半導体チップを制御して、当該各半導体チップに相互作用演算をそれぞれ実行させる制御部とを有し、前記制御部が、前記問題のデータを、当該問題のイジングモデルの基底状態のスピン配列を変化させずに、複数の前記半導体チップにより表現可能な格子状のイジングモデルのデータに変換する第１のステップと、前記制御部が、変換した前記格子状のイジングモデルのデータを分割して複数の前記半導体チップにそれぞれ割り当てる第２のステップと、前記制御部が、各前記半導体チップに前記相互作用演算をそれぞれ実行させる第３のステップとを設けるようにした。【００１５】
本情報処理装置及びその制御方法によれば、任意のイジングモデルの基底状態を探索することができる。また、ある半導体チップが値を保持するスピンのうち、他の半導体チップが値を保持するスピンに相互作用を及ぼすスピンの数を低減させることができるため、結果として、半導体チップ間を接続するチップ間配線の配線量を抑えることができる。
【発明の効果】
【００１６】
本発明によれば、安価かつ容易に製造でき、任意のイジングモデルの基底状態を探索可能な情報処理装置及びその制御方法を実現できる。
【図面の簡単な説明】
【００１７】
【図１】本実施の形態による情報処理装置の全体構成を示すブロック図である。
【図２】マルチイジングチップの構成を示すブロック図である。
【図３】イジングチップの構成を示すブロック図である。
【図４】３次元格子のスピンアレイの構成の一例を説明する概念図である。
【図５】スピンアレイの構成の説明に供する概念図である。
【図６】スピンアレイの構成の説明に供する概念図である。
【図７】スピンユニットの構成を示すブロック図である。
【図８】スピンユニットの構成を示すブロック図である。
【図９】イジングチップ上のスピンユニットの配置例を示すブロック図である。
【図１０】（Ａ）及び（Ｂ）は、本実施の形態によるイジングモデル変換方法の説明に供するグラフである。
【図１１】格子イジングモデルの構成例を示す概念図である。
【図１２】（Ａ）及び（Ｂ）は、本実施の形態による格子イジングモデルの各係数の決定方法の説明に供する概念図である。
【図１３】イジングチップ間の接続例を示すブロック図である。
【図１４】格子イジングモデルのデータの複数のイジングチップへの分割割当て方法の説明に供する概念図である。
【図１５】本実施の形態によるイジングチップ間の接続例を示すブロック図である。
【図１６】本実施の形態によるイジングチップ間の接続例を示すブロック図である。
【図１７】本実施の形態によるイジングチップ間の接続例を示すブロック図である。
【図１８】基底状態探索処理の処理手順を示すフローチャートである。
【図１９】本実施の形態によるイジングモデル変換処理の処理手順を示すフローチャートである。
【図２０】（Ａ）及び（Ｂ）は、本実施の形態によるイジングモデル変換処理の説明に供する概念図である。
【図２１】３層の格子グラフからなる格子イジングモデルの構成例を示す概念図である。
【発明を実施するための形態】
【００１８】
以下図面について、本発明の一実施の形態を詳述する。
【００１９】
（１）有向グラフに拡張したイジングモデル
本実施の形態では、イジングモデルを拡張した、以下の（２）式で示されるモデルを、これ以降イジングモデルと呼ぶものとする。
【数２】
2016199220.tif 000004
【００２０】
（１）式で示したイジングモデルとの違いは、（２）式では有向グラフで示されるような相互作用が許されることにある。一般的にイジングモデルはグラフ理論では無向グラフとして描画することができる。それは、イジングモデルの相互作用は、ｉ番目スピンからｊ番目スピンへの相互作用係数Ｊｉ，ｊとｊ番目スピンからｉ番目スピンへの相互作用係数Ｊｊ，ｉとを区別していないことによる。
【００２１】
本発明はイジングモデルを拡張し、Ｊｉ，ｊとＪｊ，ｉを区別しても適用できるため、本実施の形態でも有向グラフ化したイジングモデルを取り扱う。なお、無向グラフのイジングモデルを有向グラフのイジングモデルで取り扱う場合には、単にＪｉ，ｊとＪｊ，ｉとの双方向に同じ相互作用係数を定義することで可能である。この場合、同じモデルでも（１）式のエネルギー関数に対して（２）式のエネルギー関数ではエネルギーの値が２倍になる。
【００２２】
（２）本実施の形態による情報処理装置の構成
（２−１）情報処理装置の全体構成
図１において、１は全体として本実施の形態による情報処理装置を示す。この情報処理装置１は、パーソナルコンピュータやワークステーション又はサーバなどから構成され、システムバス２を介して接続されたＣＰＵ（Central Processing Unit）３、メモリ４、記憶装置５及び複数のマルチイジングチップ６を備える。
【００２３】
ＣＰＵ３は、情報処理装置１全体の動作制御を司るプロセッサである。またメモリ４は、例えば揮発性の半導体メモリから構成され、各種プログラムを記憶するために利用される。記憶装置５は、例えばハードディスク装置やＳＳＤ（Solid State Drive）などから構成され、プログラムやデータを長期間保持するために利用される。
【００２４】
本実施の形態の場合、記憶装置５には、本情報処理装置１が解くべき単一かつイジングモデル形式の問題の問題データ７が格納され、メモリ４には、問題変換プログラム８及びマルチイジングチップ制御プログラム９が格納される。問題変換プログラムは、かかる問題のイジングモデルを必要に応じて図１１について後述する単一の格子イジングモデルに変換すると共に、この問題を必要に応じて複数の部分問題に分割し、これらの部分問題を個々のマルチイジングチップ６にそれぞれ振り分けるプログラムである。またマルチイジングチップ制御プログラム９は、個々のマルチイジングチップ６において対応する部分問題を解くための制御を行うためのプログラムである。部分問題は、それ自体が他の部分問題と独立した単一のイジングモデル形式の問題である。
【００２５】
なお、イジングモデル形式でない問題データをイジングモデル形式の問題データ７に変換するプログラムをメモリ４に格納しておくようにしてもよい。このようにすることによりイジングモデル形式でない問題についても対応可能となり、本情報処理装置１の有用性を向上させることができる。
【００２６】
マルチイジングチップ６は、イジングモデルの基底状態探索を行う専用ハードウェアであり、例えば画面描画処理のための専用ハードウェアであるＧＰＵ（Graphics Processing Unit）のように、情報処理装置１に装着する拡張カードの形態を取る。
【００２７】
マルチイジングチップ６は、図２に示すように、インタフェース１０、イジングチップ群１１及び制御部１２を備えて構成され、インタフェース１０及びシステムバス２（図１）を介してＣＰＵ３（図１）との間でコマンドや情報の送受を行う。
【００２８】
イジングチップ群１１は、それぞれがイジングモデルの基底状態探索を行う専用のハードウェアである複数のイジングチップ１３から構成される。イジングチップ１３間はチップ間配線１４により接続されており、このチップ間配線１４を介してイジングチップ１３同士が必要な情報を送受する。
【００２９】
制御部１２は、イジングチップ群１１を構成する各イジングチップ１３を制御する機能を有し、コントローラ１５、相互作用クロック生成器１６及び乱数発生器１７を備えて構成される。
【００３０】
コントローラ１５は、マルチイジングチップ６全体の動作制御を司るプロセッサであり、情報処理装置１のＣＰＵ３（図１）からシステムバス２（図１）及びインタフェース１０を介して与えられるコマンドに従ってイジングチップ群１１を構成する各イジングチップ１３の動作や、相互作用クロック生成器１６及び乱数発生器１７を制御する。
【００３１】
また相互作用クロック生成器１６は、後述する相互作用クロックを生成するクロック生成器である。相互作用クロック生成器１６により生成された相互作用クロックは、イジングチップ群１１を構成する各イジングチップ１３にそれぞれ与えられる。乱数発生器１７は、後述のように各イジングチップ１３において実行される基底状態探索が局所最適解に陥るのを防止するためのランダムなビット列でなる乱数を発生させる。乱数発生器１７により発生された乱数は、各イジングチップ１３にそれぞれ与えられる。
【００３２】
（２−２）イジングチップの構成
図３は、イジングチップ１３の概略構成を示す。この図３に示すように、イジングチップ１３は、スピンアレイ２０、Ｉ／Ｏ（Input/output）アドレスデコーダ２１、Ｉ／Ｏドライバ２２、相互作用アドレスデコーダ２３及びチップ間接続部２４を備えて構成される。本実施の形態では、イジングチップ１３は現在広く用いられているＣＭＯＳ（Complementary Metal-Oxide Semiconductor）集積回路として実装されていることを想定して説明するが、他の固体素子でも実現可能である。
【００３３】
イジングチップ１３は、スピンアレイ２０にリード／ライトを行うためのＳＲＡＭ互換インタフェース３０としてアドレスバス３１、データバス３２、Ｒ／Ｗ制御線３３及びＩ／Ｏクロック線３４を備える。またイジングチップ１３は、イジングモデルの基底状態探索の制御を行うための相互作用制御インタフェース３５として、相互作用アドレス線３６及び相互作用クロック線３７も備える。
【００３４】
イジングチップ１３では、イジングモデルのスピンσｉ、相互作用係数Ｊｉ，ｊ及び外部磁場係数ｈｉをすべてスピンアレイ２０内のメモリセルに記憶する情報で表現する。スピンσｉの初期状態の設定や基底状態探索完了後の解読み出しはＳＲＡＭ互換インタフェース３０を介して行う。またイジングチップ１３では、基底状態を探索すべきイジングモデルをスピンアレイ２０に設定するための相互作用係数Ｊｉ，ｊ及び外部磁場係数ｈｉのリード／ライトもＳＲＡＭ互換インタフェース３０を介して行う。
【００３５】
そのため、スピンアレイ２０内のスピンσｉ、相互作用係数Ｊｉ，ｊ及び外部磁場係数ｈｉにはアドレスが付与されている。そしてイジングチップ１３にスピンσｉ、相互作用係数Ｊｉ，ｊ又は外部磁場係数ｈｉをリード／ライトする場合、対応するアドレスがコントローラ１５からアドレスバス３１を介してＩ／Ｏアドレスデコーダ２１に与えられ、これらスピンσｉ、相互作用係数Ｊｉ，ｊ及び外部磁場係数ｈｉのリード／ライトを制御するＲ／Ｗ制御信号がコントローラ１５からＲ／Ｗ制御線３３を介してＩ／Ｏドライバ２２に与えられる。
【００３６】
かくしてＩ／Ｏアドレスデコーダ２１は、アドレスバス３１を介して与えられたアドレスに基づいてスピンアレイ２０のワード線をアクティベートし、Ｉ／Ｏドライバ２２は、Ｒ／Ｗ制御線３３を介して与えられたＲ／Ｗ制御信号に基づいてスピンアレイ２０内の対応するビット線を駆動する。これによりデータバス３２を介して与えられたスピンσｉの初期値や、相互作用係数Ｊｉ，ｊ及び外部磁場係数ｈｉの設定値がスピンアレイ２０に設定され、又は、基底状態探索完了後の解がスピンアレイ２０から読み出されてデータバス３２を介して外部に出力される。
【００３７】
なお、ＳＲＡＭ互換インタフェース３０を構成するアドレスバス３１、データバス３２及びＲ／Ｗ制御線３３は、Ｉ／Ｏクロック線３４を介して制御部１２からイジングチップ１３に与えられるＩ／Ｏクロックに同期して動作する。ただし、本発明においてインタフェースが同期式である必要はなく、非同期式のインタフェースでも良い。本実施の形態では、同期式のインタフェースであるという前提で説明を行う。
【００３８】
また、イジングチップ１３は、基底状態探索を行うために、スピンアレイ２０の内部でスピン間の相互作用を実現する。この相互作用を外部から制御するのが相互作用制御インタフェース３５である。具体的に、イジングチップ１３は、コントローラ１５から与えられる相互作用を行うスピン群を指定するアドレスを相互作用アドレス線３６を介して入力し、相互作用クロック線３７を介して入力される相互作用クロック生成器１６からの相互作用クロックに同期して相互作用を行う。相互作用アドレスデコーダ２３は、相互作用アドレス線３６を介して与えられたアドレスに基づいてスピンアレイ２０に対する相互作用係数Ｊｉ，ｊ及び外部磁場係数ｈｉのリード／ライトを行う。
【００３９】
加えて、イジングチップ１３は、後述のようにイジングモデルのスピンを表現するメモリセルの値を確率的に反転させる乱数を注入するための乱数注入線３８を有している。図２について上述した乱数発生器１７により発生された乱数は、この乱数注入線３８を介してスピンアレイ２０に与えられる。
【００４０】
チップ間接続部２４は、隣接して配置されたイジングチップ１３との間で必要なスピンσｉの値を送受する際のインタフェースとして機能する。チップ間接続部２４の詳細については後述する。
【００４１】
（２−３）スピンアレイの構成
スピンアレイ２０は、１個のスピンσｉ並びにそれに付随する相互作用係数Ｊｉ，ｊ及び外部磁場係数ｈｉの保持と、基底状態探索演算とを実現するスピンユニットを基本構成単位として、スピンユニットを多数個並べた構成を有する。
【００４２】
図４は、スピンユニット４０を複数個並べることで、３次元格子状のトポロジを持つイジングモデルを構成する例を示している。図４の例は、３（Ｘ軸方向）×３（Ｙ軸方向）×２（Ｚ軸方向）の大きさの３次元格子である。座標軸の定義は図示した通り、図面右方向をＸ軸、図面下方向をＹ軸、図面奥行き方向をＺ軸としているが、この座標軸は実施の形態の説明上便宜的に必要なだけであり、本発明とは関係しない。３次元格子以外のトポロジ、例えばツリー状のトポロジなどを利用する場合には、座標軸とは別にツリーの段数等で表現することになる。図４の３次元格子状のトポロジにおいて、スピン間の相互作用をグラフとしてとらえると、最大で次数５のスピン（頂点）が必要となる。なお、外部磁場係数の接続も含めて考えると、最大で次数６が必要となる。
【００４３】
図４に示す１個のスピンユニット４０には、隣接するスピン（例えば隣接するスピンが５個の場合σｊ，σｋ，σｌ，σｍ，σｎ）の値が入力される。このためスピンユニット４０は、これら入力する隣接するスピンの値を保持するためのメモリセルを有している。またスピンユニット４０は、かかるスピンの値に加え、外部磁場係数と、上述した隣接するスピンとの相互作用係数（隣接する５スピンとの相互作用係数Ｊｊ，ｉ，Ｊｋ，ｉ，Ｊｌ，ｉ，Ｊｍ，ｉ，Ｊｎ，ｉ）とをそれぞれ保持するメモリセルをも有している。
【００４４】
（２−４）スピンユニットの構成
スピンユニット４０の一構成例を図７及び図８を用いて説明する。スピンユニット４０は２つの側面をもっており、便宜上、図７及び図８に分けて説明するが、１個のスピンユニット４０は図７及び図８の構成の双方を含む。図７はスピンユニット４０間の相互作用を実現するための回路を示し、図８はスピンユニット４０が有するメモリセルＮ，ＩＳ０，ＩＳ１，ＩＵ０，ＩＵ１，ＩＬ０，ＩＬ１，ＩＲ０，ＩＲ１，ＩＤ０，ＩＤ１，ＩＦ０，ＩＦ１にイジングチップ１３外からアクセスするためのインタフェースであるビット線４１とワード線４２とに注目してスピンユニット４０の構成を図示したものである。
【００４５】
スピンユニット４０は、イジングモデルのスピンσｉ、相互作用係数Ｊｊ，ｉ〜Ｊｎ，ｉ及び外部磁場係数ｈｉを保持するために、複数の１ビットのメモリセルＮ，ＩＳ０，ＩＳ１，ＩＵ０，ＩＵ１，ＩＬ０，ＩＬ１，ＩＲ０，ＩＲ１，ＩＤ０，ＩＤ１，ＩＦ０，ＩＦ１を備えている。なお、メモリセルＩＳ０及びＩＳ１、メモリセルＩＵ０及びＩＵ１、メモリセルＩＬ０及びＩＬ１、メモリセルＩＲ０及びＩＲ１、メモリセルＩＤ０及びＩＤ１、並びに、メモリセルＩＦ０及びＩＦ１は、それぞれ２個１組で役割を果たすものであるため、適宜、これらをそれぞれまとめてメモリセル対ＩＳｘ，ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ又はＩＦｘと略記する（図５参照）。
【００４６】
ここで、スピンユニット４０はｉ番目のスピンを表現するものとして説明を行う。メモリセルＮはスピンを表現するためのメモリセルであり、スピンの値を保持する。スピンの値はイジングモデルでは＋１／−１（＋１を上、−１を下とも表現する）であるが、これをメモリセルが保持可能な２値である０／１に対応させる。例えば、＋１を１、−１を０に対応させる。
【００４７】
図５を用いて、スピンユニット４０が有するメモリセル対ＩＳｘ，ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ及びＩＦｘと、図４に示したイジングモデルのトポロジとの対応関係を示す。メモリセル対ＩＳｘは外部磁場係数を記憶する。また、メモリセル対ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ及びＩＦｘは、それぞれ相互作用係数を記憶する。具体的に、メモリセル対ＩＵｘは上側のスピン（Ｙ軸方向で−１）、メモリセル対ＩＬｘは左側のスピン（Ｘ軸方向で−１）、メモリセル対ＩＲｘは右側のスピン（Ｘ軸方向で＋１）、メモリセル対ＩＤｘは下側のスピン（Ｙ軸方向で＋１）、メモリセル対ＩＦｘは奥行き方向に接続するスピン（Ｚ軸方向で＋１ないしは−１）との相互作用係数をそれぞれ記憶する。
【００４８】
また、イジングモデルを有向グラフとして捉えた場合に、あるスピンから見ると他のスピンが自スピンに及ぼす影響の係数を持つことになる。自スピンが他のスピンに与える影響の係数は、それぞれの他のスピンに属する。すなわち、このスピンユニット４０は最大で５個のスピンと接続される。本実施の形態のイジングチップ１３では、外部磁場係数及び相互作用係数として＋１／０／−１の３値に対応する。そのため、外部磁場係数及び相互作用係数を表わすためには、それぞれ２ビットのメモリセルが必要となる。
【００４９】
メモリセル対ＩＳｘ，ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ及びＩＦｘは、末尾の数字が０と１の２つのメモリセル（例えばメモリセル対ＩＳｘの場合にはメモリセルＩＳ０及びＩＳ１）の組合せで、＋１／０／−１の３値を表現する。例えば、メモリセル対ＩＳｘの場合には、メモリセルＩＳ１で＋１／−１を表現し、メモリセルＩＳ１が保持する値が１の時は＋１、メモリセルＩＳ１が保持する値が０の時には−１を表す。
【００５０】
これに加えて、メモリセルＩＳ０が保持する値が０の時には外部磁場係数を０と見なし、メモリセルＩＳ０が保持する値が１の時にはメモリセルＩＳ１が保持する値で決まる＋１／−１のいずれかを外部磁場係数とする。外部磁場係数が０の時は外部磁場係数をディセーブルしていると考えれば、メモリセルＩＳ０に保持された値は外部磁場係数のイネーブルビットであると言うことができる（ＩＳ０＝１の時に、外部磁場係数がイネーブルされる）。相互作用係数を記憶するメモリセル対ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ及びＩＦｘも同様に係数とビットの値とを対応させている。
【００５１】
スピンユニット４０内のメモリセルＮ，ＩＳ０，ＩＳ１，ＩＵ０，ＩＵ１，ＩＬ０，ＩＬ１，ＩＲ０，ＩＲ１，ＩＤ０，ＩＤ１，ＩＦ０及びＩＦ１は、それぞれイジングチップ１３の外部からリード／ライト可能でなければならない。そのために、図８に示すように、スピンユニット４０はビット線４１とワード線４２とをそれぞれ有している。
【００５２】
そしてイジングチップ１３では、図９に示すように、スピンユニット４０が半導体基板上にタイル状に並べられてビット線４１とワード線４２とが接続されており、Ｉ／Ｏアドレスデコーダ２１とＩ／Ｏドライバ２２でこれらのスピンユニット４０を駆動、制御又は読み出しすることにより、一般的なＳＲＡＭ（Static Random Access Memory）と同様にスピンユニット４０内のメモリセルをイジングチップ１３のＳＲＡＭ互換インタフェース３０でリード／ライトすることができるようになされている。
【００５３】
なお図９上で表現されているスピンユニット（ＮxyzというようにＸ軸、Ｙ軸及びＺ軸上の位置によって符号を付与している）が、３次元格子のトポロジでどの頂点に対応するかを図６に示す。３×３×２の３次元格子頂点を２次元平面上に配置するために、Ｘ軸方向の格子頂点配列の間隔にＺ軸方向の格子頂点配列の各格子頂点を挿入するように配置している。すなわち、図９の２次元平面上でのＹ軸方向（図面下側がＹ軸の正方向）にはＮx0z，Ｎx1z，Ｎx2zというように配置されるが、Ｘ軸方向（図面右側がＸ軸の正方向）にはＮ0y0，Ｎ0y1，Ｎ1y0，Ｎ1y1，Ｎ2y0，Ｎ2y1というように、Ｚ軸方向座標が０と１のスピンユニットが交互に配置される。
【００５４】
またスピンユニット４０は同時に更新を行うために、相互作用を計算して次のスピンの状態を決定するための回路を、スピンユニット４０毎に独立して持っている。図７では、スピンユニット４０は、外部とのインタフェースとして、信号線ＥＮ，ＮＵ，ＮＬ，ＮＲ，ＮＤ，ＮＦ，ＯＮ及びＲＮＤを有する。信号線ＥＮは、当該スピンユニット４０のスピンの更新を許可する切替え信号を入力するインタフェースである。この切替え信号でセレクタ４３を制御することで、メモリセルＮに保持されたスピンの値を、後述の多数決論理回路４４からＯＲ回路４５を介してセレクタ４３に与えられる値に更新することができる。
【００５５】
信号線ＯＮは、当該スピンユニット４０のスピンの値を他のスピンユニット４０（図４のトポロジで隣接するユニット）に出力するインタフェースである。信号線ＮＵ，ＮＬ，ＮＲ，ＮＤ及びＮＦは、それぞれ他のスピンユニット４０（図４のトポロジで隣接するユニット）が保持するスピンの値を入力するためのインタフェースである。信号線ＮＵは上側のスピン（Ｙ軸方向で−１）、信号線ＮＬは左側のスピン（Ｘ軸方向で−１）、信号線ＮＲは右側のスピン（Ｘ軸方向で＋１）、信号線ＮＤは下側のスピン（Ｙ軸方向で＋１）、信号線ＮＦは奥行き方向に接続するスピン（Ｚ軸方向で＋１ないしは−１）からの入力である。
【００５６】
スピンユニット４０では隣接スピンとの間でエネルギーを最小化するようにスピンの次状態を決定するが、それは隣接スピンと相互作用係数の積、及び、外部磁場係数を見たときに、正の値と負の値のどちらが支配的か判断することと等価である。例えば、ｉ番目スピンσｉに、スピンσｊ，σｋ，σｌ，σｍ及びσｎが隣接しているとして、スピンσｉの次状態は以下のように決まる。
【００５７】
まず、隣接スピンの値はσｊ＝＋１，σｋ＝−１，σｌ＝＋１，σｍ＝−１，σｎ＝＋１とし、相互作用係数はＪｊ，ｉ＝＋１，Ｊｋ，ｉ＝＋１，Ｊｌ，ｉ＝＋１，Ｊｍ，ｉ＝−１，Ｊｎ，ｉ＝−１、外部磁場係数ｈｉ＝＋１とする。このとき、相互作用係数と隣接スピンの積、及び、外部磁場係数をそれぞれ並べると、σｊ×Ｊｊ，ｉ＝＋１，σｋ×Ｊｋ，ｉ＝−１，σｌ×Ｊｌ，ｉ＝＋１，σｍ×Ｊｍ，ｉ＝＋１，σｎ×Ｊｎ，ｉ＝−１，ｈｉ＝＋１となる。外部磁場係数は、常に値が＋１のスピンとの相互作用係数と読み替えて良い。
【００５８】
ここで、ｉ番目のスピンと隣接スピンとの間での局所的なエネルギーは、前述した係数にそれぞれｉ番目スピンの値を乗じて、さらに符号を反転させたものになる。例えば、ｊ番目スピンとの間での局所的なエネルギーは、ｉ番目スピンを＋１とした時には−１、ｉ番目スピンを−１としたときには＋１となるので、ｉ番目スピンを＋１にするほうが、ここでの局所的なエネルギーを小さくする方向に働く。
【００５９】
このような局所的なエネルギーを全ての隣接スピン間と外部磁場係数について考えたときに、ｉ番目スピンを＋１／−１のどちらにしたほうがエネルギーを小さくできるかを計算する。これは、先程示した相互作用係数及び隣接スピンの積と、外部磁場係数とをそれぞれ並べたものにおいて、＋１と−１のどちらが多いか数えれば良い。先程の例では、＋１が４個、−１が２個である。仮に、ｉ番目スピンを＋１とすると、エネルギーの総和は−２、ｉ番目スピンを−１とするとエネルギーの総和は＋２になる。よって、＋１の個数が多い時にはｉ番目スピンの次状態を＋１とし、−１の個数が多い時にはｉ番目スピンの次状態を−１にするという多数決で、エネルギーを最小化するｉ番目スピンの次状態を決定することができる。
【００６０】
図７に示した論理回路４６は、上述の相互作用を行うための回路である。まず、隣接スピンの状態と、相互作用係数の＋１／−１を示すメモリセルＩＵ１，ＩＬ１，ＩＲ１，ＩＤ１，ＩＦ１が保持する値との排他的論理和の否定（ＸＮＯＲ）をＸＮＯＲ回路４７で求める。これにより、その相互作用だけを見た時にエネルギーを最小化するスピンの次状態を計算することができる（＋１は１、−１は０にエンコードされているものとする）。
【００６１】
もし、相互作用係数が＋１／−１だけであれば、ＸＮＯＲ回路４７の出力のうち＋１／−１のどちらが多いかを多数決論理回路４４において多数決論理で判定すればスピンの次状態を決定することができる。外部磁場係数に関しては、常に状態＋１のスピンとの相互作用係数に相当するものと考えれば、単に外部磁場係数の値がスピンの次状態を決定する多数決論理回路４４に入力すべき値となる。
【００６２】
次に、係数０の実現方法について考える。ｎ入力の多数決論理ｆ（Ｉ１，Ｉ２，Ｉ３，……，Ｉｎ）があるとき、以下の命題は真であると言える。まず、入力Ｉ１，Ｉ２，Ｉ３，……，Ｉｎの複製Ｉ’１，Ｉ’２，Ｉ’３，……，Ｉ’ｎがあるとする（任意のｋについて、Ｉｋ＝Ｉ’ｋである）。このとき、ｆ（Ｉ１，Ｉ２，Ｉ３，……，Ｉｎ）の出力は、複製もあわせて入力したｆ（Ｉ１，Ｉ２，Ｉ３，……，Ｉｎ，Ｉ’１，Ｉ’２，Ｉ’３，……，Ｉ’ｎ）と等しい。つまり、各入力変数をそれぞれ２個ずつ入れても、出力は不変である。さらに、入力Ｉ１，Ｉ２，Ｉ３，……，Ｉｎの他に、もう一つの入力Ｉｘと、その反転！Ｉｘがあるとする。このとき、ｆ（Ｉ１，Ｉ２，Ｉ３，……，Ｉｎ，Ｉｘ，！Ｉｘ）の出力は、ｆ（Ｉ１，Ｉ２，Ｉ３，……，Ｉｎ）と等しい。つまり、入力変数とその反転を入力すると、多数決においてその入力変数の影響をキャンセルするように働く。多数決論理のこの性質を利用して係数０を実現する。
【００６３】
具体的には、図７に示すように、ＸＯＲ回路４８を利用して、係数のイネーブルを決めるビット（ビットセルＩＳ０，ＩＵ０，ＩＬ０，ＩＲ０，ＩＤ０及びＩＦ０にそれぞれ保持されたビット）の値により、多数決論理回路４４に、先に述べたスピン次状態の候補となる値の複製か、その反転を同時に入力する。例えば、メモリセルＩＳ０が保持するビットの値が０の場合、メモリセルＩＳ１が保持するビットの値と、メモリセルＩＳ１が保持するビットの値を反転させた値が同時に多数決論理回路４４に入力されるので、外部磁場係数の影響は無い（外部磁場係数が０に相当する）ことになる。また、メモリセルＩＳ０が保持するビットの値が１の場合には、メモリセルＩＳ１が保持するビットの値と、その値と同じ値（複製）が同時に多数決論理回路４４に入力されることになる。
【００６４】
上述したスピン間の相互作用によるエネルギー最小化で、適用されたイジングモデルの基底状態探索を実現することができるが、これだけでは局所最適解に陥ってしまう可能性がある。基本的に、エネルギーを小さくする方向の動きしかないため、一旦局所最適解に陥るとそこから抜け出すことができず、大域最適解に到達しない。そのため、局所最適解から脱出するための作用として、スピンを表現するメモリセルの値を確率的に反転されるために、スピンユニット４０はインタフェースとしてＲＮＤ線４９を有する。
【００６５】
そしてスピンユニット４０には、上述のように乱数発生器１７（図２）から乱数注入線３８（図３）を介してスピンアレイ２０（図３）に与えられた乱数がこのＲＮＤ線４９を介して与えられ、この乱数がＯＲ回路４５に入力することで、スピンの値が確率的に反転される。
【００６６】
（３）格子イジングモデルを利用した任意のイジングモデルの基底状態探索方式
次に、マルチイジングチップ６（図１）として格子状のイジングモデル（以下、これを格子イジングモデルと呼ぶ）を表現可能な半導体チップを適用し、このマルチイジングチップ６を利用して、任意のイジングモデルの基底状態を探索する本実施の形態によるイジングモデル基底状態探索方式について説明する。
【００６７】
（３−１）任意のイジングモデルの格子イジングモデルへの変換方法
複数のスピンを１つのスピンを表す集合（以下、これをスピン集合と呼ぶ）と見なしてイジングモデルを変換することにより、基底状態のスピン配列を変化させずにイジングモデルの構造を変化させる方法が知られている。この方法を利用して、任意のイジングモデルを表す問題データ７（図１）を、基底状態となるスピン配列が不変であることを保証しつつ、マルチイジングチップ６が表現可能な格子イジングモデルに変換するイジングモデル変換方法について説明する。
【００６８】
図１０（Ａ）及び（Ｂ）並びに図１１は、このようなイジングモデル変換方法の手順を表す。まず、図１０（Ａ）に示すイジングモデルを表す問題データ７を、相互作用がないスピン間を係数が「０」の相互作用と見なすことで、図１０（Ｂ）に示す完全グラフのイジングモデルのデータに変換する。次に、図１０（Ｂ）で示されたイジングモデルを、基底状態を変化させることなく図１１に示す非平面の階段状の格子イジングモデルに変換する。ただし、図１０（Ａ）に示すイジングモデルを、直接、図１１に示す格子イジングモデルに変換するようにしても良い。
【００６９】
図１０（Ｂ）の完全グラフを図１１のような２層の格子グラフからなる階段状の格子イジングモデルに変換する場合、スピン集合のスピンをこの図１１の通りに配置する。なお、図１１において、スピンの番号は、そのスピンが元のイジングモデル（図１０（Ａ）又は（Ｂ））でどのスピンに対応するものであるかを表す。「１」と記されたスピン群は元のイジングモデルにおけるスピン１を表すスピン集合に相当する。元のイジングモデルのスピン１及び図１１に示すイジングモデルのスピン集合１は、それぞれの基底状態における値が同値になることを期待する。このように変換後の格子イジングモデルが階段状となるようにスピン集合のスピンを配置することにより、問題データ７をなるべく少ないスピン及びスピン間接続からなる格子イジングモデルに変換することができる。
【００７０】
ここで、図１１のイジングモデルの構成をより詳しく説明する。なお、以下においては、図１１において、Ｚ軸方向の奥側の層の左上のスピンを原点（座標（０，０，０））とし、このスピンのＸ軸方向に順次隣接するスピンのＸ座標をそれぞれ１，２，……、原点のスピンのＹ軸方向に順次隣接するスピンのＹ座標をそれぞれ１，２，……、Ｚ軸方向の手前側の層のＺ座標を１とする。
【００７１】
図１１に示す格子イジングモデルでは、Ｚ軸方向の奥側の層（Ｚ座標が「０」の層）において、（０，０，０）、（０，１，０）、（０，２，０）、（０，３，０）及び（０，４，０）の位置にスピン「１」がそれぞれ配置され、（１，０，０）、（１，１，０）、（１，２，０）、（１，３，０）及び（１，４，０）の位置にスピン「２」がそれぞれ配置され、（３，１，０）、（３，２，０）、（３，３，０）及び（３，４，０）の位置にスピン「３」がそれぞれ配置され、（４，２，０）、（４，３，０）及び（４，４，０）の位置にスピン「４」がそれぞれ配置され、（５，３，０）及び（５，４，０）の位置にスピン「５」がそれぞれ配置される。
【００７２】
またＺ軸方向の手前側の層（Ｚ座標が「１」の層）において、（０，０，１）及び（１，０，１）の位置にスピン「２」がそれぞれ配置され、（０，１，１）、（１，１，１）及び（２，１，１）の位置にスピン「３」がそれぞれ配置され、（０，２，１）、（１，２，１）、（２，２，１）及び（３，２，１）の位置にスピン「４」がそれぞれ配置され、（０，３，１）、（１，３，１）、（２，３，１）及び（３，３，１）の位置にスピン「６」がそれぞれ配置され、（０，４，１）、（１，４，１）、（２，４，１）、（３，４，１）及び（４，４，１）の位置にスピン「６」がそれぞれ配置される。
【００７３】
さらに図１１では、相互作用を及ぼすスピン間を結ぶ辺は太線で、また相互作用を及ばさないスピン間を結ぶ辺は細線で示している。つまり、図１１の格子イジングモデルでは、Ｚ軸方向の奥側の層では、Ｙ軸方向に隣接するスピン同士のみが相互作用を及ぼし、Ｚ軸方向の手前の層では、Ｘ軸方向に隣接するスピン同士のみが相互作用を及ぼし、Ｚ軸方向の奥側の層及び手前側の層間では、Ｚ軸方向に隣接するスピン同士が相互作用を及ぼす。ただし、図１０（Ｂ）の完全グラフを生成するため、相互作用係数を「０」に設定した辺を追加した場合、図１１に示す格子イジングモデルには相互作用を及ぼさないスピン間を結ぶ辺が存在する。そのため太線で示したスピン間を結ぶ辺でも相互作用係数が０になる可能性はある。
【００７４】
スピン数Ｎの完全グラフの場合、１つのスピンに対してＮ−１の相互作用が存在する。しかし立体の格子グラフは最大でも次数が６である。そのためＮ＞８の完全グラフは、そのままでは格子グラフで表現できない。そこでスピン集合を導入してスピン当たりの次数を削減するのである。
【００７５】
すべてのスピン間の相互作用を担保するため、格子グラフでは図１１に示すようにスピン集合のスピンを配置する。つまり各層にて特定の方向のみに延びるよう各スピン集合のスピンを配置するということである。図１１は、Ｚ＝１ではＸ方向、Ｚ＝０ではＹ方向のみに各スピン集合のスピンを延ばして配置した例である。
【００７６】
（３−２）変換後の格子イジングモデルにおける各係数の決定方法
任意のイジングモデルを基底状態を変化させないように格子イジングモデルへ変換するためには、図１１の格子イジングモデルを生成するときに相互作用係数や外部磁場係数を適切に定めることが求められる。
【００７７】
そこで、図１２（Ａ）及び（Ｂ）を用いて、図１０（Ａ）又は（Ｂ）のイジングモデルを図１１の格子イジングモデルに変換する際の、当該格子イジングモデルにおける各係数の決定方法について説明する。
【００７８】
図１２（Ａ）は変換前のイジングモデルである。実際にはスピン１〜ｎの間にも相互作用があるが、説明の簡潔化のため図示していない。以下においては、スピン０とスピンｉと間の相互作用をＪｉと表す。またスピン０における外部磁場係数をｈ０とする。
【００７９】
図１２（Ｂ）は変換後のイジングモデルである。このイジングモデルでは、スピン集合を導入し、スピン０を、当該スピン０に相互作用を及ぼすスピン１〜ｎと同じ数のスピン（０１，……，０ｎ）で表現している。また図１２（Ｂ）では、このスピン集合内の各スピン０１〜０ｎ及びスピン１〜ｎ間の相互作用係数を順番にｂ１，……，ｂｎ−１とし、各スピン０１〜０ｎにおける外部磁場係数をａ１，……，ａｎとしている。変換後のイジングモデルでスピン０を表すスピン集合とスピンｉの間の相互作用はＪｉと定める。
【００８０】
図１２（Ｂ）に示すイジングモデルにおいて、当該イジングモデルが基底状態のときに局所最適解であることを考慮すると、|Ｊｉ|＋|ａｉ|＞|ｂｉ|のとき基底状態でスピン０ｉと０ｉ＋１の値が等しくなる。ゆえにこの不等式を満たすように相互作用を定めると、基底状態で０１＝０２＝…＝０ｎとなる。またａ１＋ａ２＋…＋ａｎ＝ｈ０のとき、変換前及び変換後の基底状態において、スピン０とスピン０１の値が等しくなる。よって、この２つの条件を満たすよう相互作用係数Ｊ１〜Ｊｎと外部磁場係数ａ１〜ａｎとをそれぞれ設定することにより、基底状態を変化させることなくイジングモデルのグラフ構造を変化させることができる。
【００８１】
上述の方法に加えて、次式
【数３】
2016199220.tif 000005
で定義される定数Ｃを用いて係数を定める方法も存在する。
【００８２】
具体的には、この定数Ｃを用いて変換後の相互作用係数Ｊ１〜Ｊｎ及び外部磁場係数ａ１〜ａｎを以下の通り定める。
【数４】
2016199220.tif 000006
【００８３】
ただし（４）式において、ｓｉｇｎ（ｘ）はｘが正のとき＋１、０以下のとき‐１となる関数である。このように係数を定めると変換前及び変換後の基底状態が等しくなる。
【００８４】
前述のいずれかの方法を用いることにより、図１０（Ａ）又は（Ｂ）のイジングモデルを、基底状態を変化させることなく図１１に示す格子イジングモデルに変換する際の当該格子イジングモデルの各係数の値を決定し、設定することができる。
【００８５】
（３−３）イジングチップ間の配線方式
次に、かかる格子イジングモデルを表現可能なマルチイジングチップ６内の各イジングチップ１３（図２）間の配線方式について説明する。
【００８６】
単一のイジングチップ１３に多数のスピンユニット４０（図７及び図８）を搭載しようとすると、イジングチップ１３のチップサイズが増大し、コスト増につながる。このためマルチイジングチップ６に多数のスピンユニット４０を搭載するに際しては、マルチイジングチップ６に規模がそれほど大きくないイジングチップ１３を複数実装し、これらをチップ間配線により接続する方法がコスト上昇を抑える上で効果的である。
【００８７】
この場合、イジングチップ１３の端部に設けられたスピンユニット４０と、他のイジングチップ１３内の対応するスピンユニット４０との間で配線を施すために、例えば図１３に示すように、隣接する各イジングチップ１３のチップ端部にそれぞれ設けられた対応するスピンユニット４０同士を、チップ間接続部２４（図３）の一部を構成する接続部５０とチップ間配線１４を介して接続する必要がある。なお、ここで言う「チップ端部に設けられたスピンユニット４０」とは、図４のイジングモデルで隣接するスピンの値を保持するスピンユニット４０が他のイジングチップ１３に設けられたスピンユニット４０を指す。
【００８８】
しかしながら、隣接するイジングチップ１３のチップ端部に設けられたすべての対応するスピンユニット４０同士をそれぞれ接続するよう接続部５０やチップ間配線１４（図２）を形成すると、この図１３に示すように、接続部５０の数やチップ間配線１４の配線量が大きくなり過ぎるためにコストの上昇や実装上の困難が生じる。
【００８９】
一方、図１４は、スピン数が６個のイジングモデルを図１０及び図１１について上述した変換方法を利用して変換した格子イジングモデルを表す。仮に、単一のイジングチップ１３が格子イジングモデル全体を表現するために必要な数量のスピンユニット４０を持たない場合には、この図１４に示すように格子イジングモデルを複数の領域に分割し、これら領域のデータを複数のイジングチップ１３に割り当てれば良い。図１４では、格子イジングモデルを４つの領域ＡＲ１〜ＡＲ４に分割し、これら領域ＡＲ１〜ＡＲ４のデータをそれぞれイジングチップ１〜イジングチップ４に割り当てた（マッピングした）例を示している。
【００９０】
このときＸ方向の領域間（つまり「イジングチップ１」というイジングチップ１３で表現される領域ＡＲ１及び「イジングチップ２」というイジングチップ１３で表現される領域ＡＲ２間と、「イジングチップ３」というイジングチップ１３で表現される領域ＡＲ３及び「イジングチップ４」というイジングチップ１３で表現される領域ＡＲ４間）では、いずれもＺ軸方向の手前側の層内の相互作用のみが存在する。
【００９１】
このため領域ＡＲ１及び領域ＡＲ２間については、領域ＡＲ１内の（１，１，１）に配置されたスピン及び領域ＡＲ２内の（２，１，１）に配置されたスピン間の相互作用と、領域ＡＲ１内の（１，２，１）に配置されたスピン及び領域ＡＲ２内の（２，２，１）に配置されたスピン間の相互作用とだけを考慮すれば良く、領域ＡＲ３及び領域ＡＲ４間については、領域ＡＲ３内の（１，３，１）に配置されたスピン及び領域ＡＲ４内の（２，３，１）に配置されたスピン間の相互作用と、領域ＡＲ３内の（１，４，１）に配置されたスピン及び領域ＡＲ４内の（２，４，１）に配置されたスピン間の相互作用とだけを考慮すれば良い。
【００９２】
従って、図１４のように複数のイジングチップ１３で格子イジングモデルを表現するに際しては、「イジングチップ１」というイジングチップ１３と、「イジングチップ２」というイジングチップ１３とについては、少なくとも領域ＡＲ１内の（１，２，１）に配置されたスピンを表現するスピンユニット４０、及び、領域ＡＲ２の（２，１，１）に配置されたスピンを表現するスピンユニット４０間と、領域ＡＲ１内の（１，２，１）に配置されたスピンを表現するスピンユニット４０、及び、領域ＡＲ２内の（２，２，１）に配置されたスピンを表現するスピンユニット４０間とを接続すれば良い。
【００９３】
そこで、本実施の形態の場合、「イジングチップ１」というイジングチップ１３については、図１５に示すように、「イジングチップ２」というイジングチップ１３に隣接する側のチップ端部に設けられたスピンユニット４０のうちの１つおきのスピンユニット４０（上述の（１，２，１）に配置されたスピンを表現するスピンユニット４０と、（１，２，１）に配置されたスピンを表現するスピンユニット４０とを含む）にそれぞれ対応付けて接続部５０が設けられている。
【００９４】
また、「イジングチップ２」というイジングチップ１３については、「イジングチップ１」というイジングチップ１３に隣接する側のチップ端部に設けられたスピンユニット４０のうちの１つおきのスピンユニット４０（上述の（２，１，１）に配置されたスピンを表現するスピンユニット４０と、（２，２，１）に配置されたスピンを表現するスピンユニット４０とを含む）にそれぞれ対応付けて接続部５０が設けられている。
【００９５】
そして「イジングチップ１」というイジングチップ１３及び「イジングチップ２」というイジングチップ１３間は、領域ＡＲ１内の（１，２，１）に配置されたスピンを表現するスピンユニット４０と接続された接続部５０及び、領域ＡＲ２の（２，１，１）に配置されたスピンを表現するスピンユニット４０と接続された接続部５０間と、領域ＡＲ１内の（１，２，１）に配置されたスピンを表現するスピンユニット４０、及び、領域ＡＲ２内の（２，２，１）に配置されたスピンを表現するスピンユニット４０と接続された接続部５０間とを含めて、「イジングチップ１」というイジングチップ１３及び「イジングチップ２」というイジングチップ１３の対応する接続部５０同士が接続されている。これにより本実施の形態においては、「イジングチップ１」というイジングチップ１３及び「イジングチップ２」というイジングチップ１３間の配線数を図１３に比べて低減させ得るようになされている。
【００９６】
同様に、本実施の形態の場合、「イジングチップ３」というイジングチップ１３については、「イジングチップ４」というイジングチップ１３に隣接する側のチップ端部に設けられたスピンユニット４０のうちの１つおきのスピンユニット４０（上述の（１，３，１）に配置されたスピンを表現するスピンユニット４０と、（１，４，１）に配置されたスピンを表現するスピンユニット４０とを含む）にそれぞれ対応付けて接続部５０が設けられている。
【００９７】
また、「イジングチップ４」というイジングチップ１３については、「イジングチップ３」というイジングチップ１３に隣接する側のチップ端部に設けられたスピンユニット４０のうちの１つおきのスピンユニット４０（上述の（２，３，１）に配置されたスピンを表現するスピンユニット４０と、（２，４，１）に配置されたスピンを表現するスピンユニット４０とを含む）にそれぞれ対応付けて接続部５０が設けられている。
【００９８】
そして「イジングチップ３」というイジングチップ１３及び「イジングチップ４」というイジングチップ１３間は、領域ＡＲ３内の（１，３，１）に配置されたスピンを表現するスピンユニット４０と接続された接続部５０及び、領域ＡＲ４の（２，３，１）に配置されたスピンを表現するスピンユニット４０と接続された接続部５０間と、領域ＡＲ３内の（１，４，１）に配置されたスピンを表現するスピンユニット４０、及び、領域ＡＲ４内の（２，４，１）に配置されたスピンを表現するスピンユニット４０と接続された接続部５０間とを含めて、「イジングチップ３」というイジングチップ１３及び「イジングチップ４」というイジングチップ１３の対応する接続部５０同士が接続されている。これにより本実施の形態においては、「イジングチップ３」というイジングチップ１３及び「イジングチップ４」というイジングチップ１３間の配線数を図１３に比べて低減させ得るようになされている。
【００９９】
一方、Ｙ方向の領域間（領域ＡＲ１及び領域ＡＲ３間と、領域ＡＲ２及び領域ＡＲ４間）では、いずれもＺ軸方向の奥側の層内の相互作用のみが存在する。
【０１００】
このため領域ＡＲ１及び領域ＡＲ３間については、領域ＡＲ１内の（０，２，０）に配置されたスピン及び領域ＡＲ３内の（０，３，０）に配置されたスピン間の相互作用と、領域ＡＲ１内の（１，２，０）に配置されたスピン及び領域ＡＲ３内の（１，３，０）に配置されたスピン間の相互作用とだけを考慮すれば良く、領域ＡＲ２及び領域４間については、領域ＡＲ２内の（２，２，０）に配置されたスピン及び領域ＡＲ４内の（２，３，０）に配置されたスピン間の相互作用と、領域ＡＲ２内の（３，２，０）に配置されたスピン及び領域４内の（３，３，０）に配置されたスピン間の相互作用とだけを考慮すれば良い。
【０１０１】
従って、図１４のように複数のイジングチップ１３で格子イジングモデルを表現するに際しては、「イジングチップ１」というイジングチップ１３と、「イジングチップ３」というイジングチップ１３とについては、少なくとも領域ＡＲ１内の（０，２，０）に配置されたスピンを表現するスピンユニット４０と、領域ＡＲ３内の（０，３，０）に配置されたスピンを表現するスピンユニット４０間と、領域ＡＲ１内の（１，２，０）に配置されたスピンを表現するスピンユニット４０、及び、領域ＡＲ３内の（１，３，０）に配置されたスピンを表現するスピンユニット４０間とを接続すれば良い。
【０１０２】
そこで、本実施の形態の場合、「イジングチップ１」というイジングチップ１３については、図１７に示すように、「イジングチップ３」というイジングチップ１３に隣接する側のチップ端部に設けられたスピンユニット４０のうちの１つおきのスピンユニット４０（上述の（０，２，０）に配置されたスピンを表現するスピンユニット４０と、（１，２，０）に配置されたスピンを表現するスピンユニット４０とを含む）にそれぞれ対応付けて接続部５０が設けられている。
【０１０３】
また、「イジングチップ３」というイジングチップ１３については、「イジングチップ１」というイジングチップ１３に隣接する側のチップ端部に設けられたスピンユニット４０のうちの１つおきのスピンユニット４０（上述の（０，３，０）に配置されたスピンを表現するスピンユニット４０と、（１，３，０）に配置されたスピンを表現するスピンユニット４０とを含む）にそれぞれ対応付けて接続部５０が設けられている。
【０１０４】
そして「イジングチップ１」というイジングチップ１３及び「イジングチップ３」というイジングチップ１３間は、領域ＡＲ１内の（０，２，０）に配置されたスピンを表現するスピンユニット４０と接続された接続部５０及び、領域ＡＲ３の（０，３，０）に配置されたスピンを表現するスピンユニット４０と接続された接続部５０間と、領域ＡＲ１内の（１，２，０）に配置されたスピンを表現するスピンユニット４０、及び、領域ＡＲ３内の（１，３，０）に配置されたスピンを表現するスピンユニット４０と接続された接続部５０間とを含めて、「イジングチップ１」というイジングチップ１３及び「イジングチップ３」というイジングチップ１３の対応する接続部５０同士が接続されている。これにより本実施の形態においては、「イジングチップ１」というイジングチップ１３及び「イジングチップ３」というイジングチップ１３間の配線数を図１３に比べて低減させ得るようになされている。
【０１０５】
同様に、本実施の形態の場合、「イジングチップ２」というイジングチップ１３については、「イジングチップ４」というイジングチップ１３に隣接する側のチップ端部に設けられたスピンユニット４０のうちの１つおきのスピンユニット４０（上述の（２，２，０）に配置されたスピンを表現するスピンユニット４０と、（３，２，０）に配置されたスピンを表現するスピンユニット４０とを含む）にそれぞれ対応付けて接続部５０が設けられている。
【０１０６】
また、「イジングチップ４」というイジングチップ１３については、「イジングチップ３」というイジングチップ１３に隣接する側のチップ端部に設けられたスピンユニット４０のうちの１つおきのスピンユニット４０（上述の（２，３，０）に配置されたスピンを表現するスピンユニット４０と、（３，３，０）に配置されたスピンを表現するスピンユニット４０とを含む）にそれぞれ対応付けて接続部５０が設けられている。
【０１０７】
そして「イジングチップ２」というイジングチップ１３及び「イジングチップ４」というイジングチップ１３間は、領域ＡＲ２内の（２，２，０）に配置されたスピンを表現するスピンユニット４０と接続された接続部５０、及び、領域ＡＲ４の（２，３，０）に配置されたスピンを表現するスピンユニット４０と接続された接続部５０間と、領域ＡＲ２内の（３，２，０）に配置されたスピンを表現するスピンユニット４０と接続された接続部５０、及び、領域ＡＲ４内の（３，３，０）に配置されたスピンを表現するスピンユニット４０と接続された接続部５０間とを含めて、「イジングチップ２」というイジングチップ１３及び「イジングチップ４」というイジングチップ１３の対応する接続部５０同士が接続されている。これにより本実施の形態においては、「イジングチップ２」というイジングチップ１３及び「イジングチップ４」というイジングチップ１３間の配線数を図１３に比べて低減させ得るようになされている。
【０１０８】
なお図１５及び図１６を併せた、マルチイジングチップ６におけるイジングチップ１３間の接続関係を図１７に示す。なお図１７では、図面の煩雑化を避けるため、「イジングチップ１」〜「イジングチップ３」という３つのイジングチップ１３間の接続関係を示しており、「イジングチップ４」というイジングチップ１３については、省略している。マルチイジングチップ６においてイジングチップ１３間をこのように接続することによって、イジングチップ１３間の配線を図１３に比べて１／２に削減することができる。
【０１０９】
（３−４）イジングチップの制御手順
図１８は、本情報処理装置１においてＣＰＵ３（図１）により実行される基底状態探索処理の処理手順を示す。ＣＰＵ３は、ステップＳＰ１については問題変換プログラム８（図１）に基づき、これ以降の処理（ステップＳＰ２〜ステップＳＰ１３）についてはマルチイジングチップ制御プログラム９（図１）に基づいて、必要なマルチイジングチップ６（図２）のコントローラ１５（図２）を介して当該マルチイジングチップ６内のイジングチップ１３を制御することにより、これらのイジングチップ１３において基底状態探索を実行させる。なお、ステップＳＰ１の処理と、ステップＳＰ２〜ステップＳＰ１３の処理とを別々のタイミングで実行するようにしてもよい。
【０１１０】
またＣＰＵ３は、各マルチイジングチップ６内のイジングチップ１３や、イジングチップ１３内のスピンユニット４０をマルチイジングチップ６内のコントローラ１５（図２）を介して制御するが、以下においては理解の容易化のため、コントローラ１５の存在を無視して説明を行う。
【０１１１】
ＣＰＵ３は、ユーザからの指示等によりこの基底状態探索処理を開始すると、まず、問題データ７（図１）を図１１について上述した格子イジングモデルの形式のデータに変換する（ＳＰ１）。
【０１１２】
続いて、ＣＰＵ３は、変換後の格子イジングモデルの相互作用係数及び外部磁場係数を必要なマルチイジングチップ６の各イジングチップ１３内の各スピンユニット４０にそれぞれ設定する（ＳＰ２）。
【０１１３】
次いで、ＣＰＵ３は、各スピンユニットが保持すべきスピンの値を乱数によりそれぞれ決定し、決定したスピンの値となるようにかかるマルチイジングチップ６における各イジングチップ１３内の各スピンユニット４０のスピンの値を初期化する（ＳＰ３）。
【０１１４】
さらにＣＰＵ３は、予め定められた各マルチイジングチップ６内の乱数発生器１７（図２）が発生する乱数において「１」が出現する確率（以下、これをビット確率と呼ぶ）を設定する（ＳＰ４）。本実施の形態の場合、初期時には乱数発生器１７が発生する乱数におけるビット確率を高く設定し、その後、段階的にビット確率を下げてゆく。これにより初期時には各スピンユニット４０が保持するスピンの値を反転し易くする一方、その後は徐々に当該スピンの値が反転し難く（「０」又は「１」に収束し易く）することができる。このためステップＳＰ４では、上述の各段階におけるビット確率が設定される。
【０１１５】
さらにＣＰＵ３は、予め定められたビット確率毎の相互作用演算の実行回数をそれぞれ設定し（ＳＰ５）、この後、イジングチップ１３間でのタイミングを合わせるため、各イジングチップ１３における各接続部５０（図１３〜図１５）内のカウンタをリセット（カウント値を「０」にセット）する（ＳＰ６）。
【０１１６】
続いて、ＣＰＵ３は、マルチイジングチップ６の相互作用クロック生成器１６（図２）を駆動するなどして各イジングチップ１３内の各スピンユニット４０における相互作用演算を１回実行させ（ＳＰ７）、この後、現在のビット確率について設定された回数分だけ相互作用演算を実行し終えたか否かを判断する（ＳＰ８）。そしてＣＰＵ３は、この判断で否定結果を得るとステップＳＰ７に戻り、この後、ステップＳＰ７及びステップＳＰ８の処理を繰り返す。
【０１１７】
そしてＣＰＵ３は、やがて現在設定されているビット確率について設定された回数分の相互作用演算を実行し得ることによりステップＳＰ８で肯定結果を得ると、ステップＳＰ５で設定したビット確率毎の相互作用演算をすべて実行し終えたか否かを判断する（ＳＰ９）。
【０１１８】
ＣＰＵ３は、この判断で否定結果を得ると、ビット確率を現在のビット確率よりも低い予め定められたビット確率に更新すると共に（ＳＰ１０）、その後実行すべき相互作用演算の回数をそのビット確率について予め定められた回数に更新する（ＳＰ１１）。そしてＣＰＵ３は、ステップＳＰ７に戻り、この後、ステップＳＰ７〜ステップＳＰ１１の処理を繰り返す。
【０１１９】
そしてＣＰＵ３は、やがてステップＳＰ５で設定されたビット確率毎の相互作用演算をすべて実行し終えることによりステップＳＰ９で肯定結果を得ると、そのとき対象としているマルチイジングチップ６における各イジングチップ１３内の各スピンユニット４０がそれぞれ保持するスピンの値を読み出す（ＳＰ１２）。
【０１２０】
またＣＰＵ３は、メモリ４に記憶したスピンユニットと元のイジングモデルの対応関係を表すデータと照合して、読み出したスピン値から元のイジングモデルにおける各スピンの値を決定する（ＳＰ１３）。
【０１２１】
上述の計算で基底状態が得られているならば、各スピン集合内に含まれるスピンは全て同値になる（例えば図１１のスピン１の値はすべて同値になる）。これは上述の処理によって係数設定することで担保される。従って、この場合には、各スピン集合から１つずつスピンの値を読み出すことで、元のイジングモデルにおける各スピンの値を決定する。
【０１２２】
ただし、以上までの基底状態探索処理によって必ずしもイジングモデルの基底状態が得られるとは限らない。そして、この場合にはスピン集合内で全てのスピンが同値にならない可能性がある。そこで、このような場合には、各スピン集合でスピン数の多い方の値を選ぶことで元のイジングモデルの対応するスピンの値を決定する。また、スピンごとに基底状態の値になりやすくなる傾向が異なるならば、その傾向に従って重み付けしてかかる多数決を行うようにしても良い。
【０１２３】
そしてＣＰＵ３は、この後、この基底状態探索処理を終了する。
【０１２４】
図１９は、図１８のＳＰ１におけるＣＰＵ３の具体的な処理内容を示す。なお本実施の形態の場合、問題データ７は、例えば図２０（Ａ）の左側に示す形式でメモリ４（図１）に記録される。図２０（Ａ）において、各行の１列目及び２列目はそれぞれスピン、３列目はこれらスピン間の相互作用係数を表す。また１列目及び２列目のスピンが等しい行は、３列目がそのスピンの外部磁場係数を表す。
【０１２５】
ＣＰＵ３は、まず、問題データ７を入力する（ＳＰ２０）。そしてＣＰＵ３は、複数のイジングチップ１３を用いてイジングモデルの基底状態を探索する場合であって、かつ入力した問題データ７が図１０（Ａ）のような相互作用のない箇所を持つグラフ構造を有する場合には、その箇所の係数を「０」として、問題データ７を図１０（Ｂ）のような完全グラフのイジングモデルを表す中間データ（図２０（Ａ）の右側）に変換する（ＳＰ２１）。
【０１２６】
そしてＣＰＵ３は、ステップＳＰ２０で得られた中間データを図１１について上述した格子イジングモデルを表す図２０（Ｂ）の左側に示すような出力データに変換する（ＳＰ２２）。この変換により得られた出力データは、例えば問題データ７と同様の形式で表現される。
【０１２７】
続いて、ＣＰＵ３は、ステップＳＰ２２で得られた出力データを、マルチイジングチップ６（図１）の各々が表現可能な規模のイジングモデルに必要に応じて分割する（ＳＰ２３）。
【０１２８】
そしてＣＰＵ３は、この後、この出力データをメモリ４に記録する（ＳＰ２４）。またステップＳＰ２２の変換処理ではスピン集合という考え方を用いるため、元のイジングモデルでは１つのスピンが、出力データの表すイジングモデルでは複数のスピンで表される。そこでＣＰＵ３は、ステップＳＰ２２で得られた出力データの表す格子イジングモデルにおいて、どのスピンが元のイジングモデルのスピンと対応するかを表す図２０（Ｂ）の右側のデータもメモリ４に記録する（ＳＰ２４）。なお図２０（Ｂ）の右側では、元のイジングモデルのスピン１が、変換後のイジングモデルではスピン１〜５に相当することを表す。
【０１２９】
さらにＣＰＵ３は、ステップＳＰ２４において、必要に応じて変換後の問題を分割することにより得られた部分問題についての相互作用係数、及び、外部磁場係数を、必要なマルチイジングチップ６の各イジングチップ１３内の各スピンユニット４０にそれぞれ設定し（ＳＰ２４）、この後この図１９の処理を終了して図１８の基底状態探索処理に戻る。
【０１３０】
（３−５）３層以上の格子イジングモデルへの変換
上述の説明では、任意のイジングモデルを２層の格子グラフを持つイジングモデルに変換する方法について詳述した。これと同様にスピン集合を配置することで、３層以上の格子グラフを表現可能なマルチイジングチップ６に対して、空間的に効率良く変換することが可能である。
【０１３１】
図２１は、３層の格子グラフからなる格子イジングモデルを表現可能なマルチイジングチップ６に対して、スピン集合を用いてスピン数が「７」の完全グラフを表現する場合の一例を示す。以下においては、図２１において、Ｚ軸方向の奥側の層の左上のスピンを原点（座標（０，０，０））とし、このスピンのＸ軸方向に順次隣接するスピンのＸ座標をそれぞれ１，２，……、原点のスピンのＹ軸方向に順次隣接するスピンのＹ座標をそれぞれ１，２，……、Ｚ軸方向の手前側の層のＺ座標を１とする。
【０１３２】
図２１に示す格子イジングモデルでは、Ｚ軸方向の最も奥側の層（Ｚ座標が「０」の層）及びＺ軸方向の中間の層（Ｚ座標が「１」の層）におけるスピン配列は図１１について上述した２層の格子イジングモデルと同じである。
【０１３３】
そして手前側の層（Ｚ座標が「２」の層）において、（０，０，２）、（０，１，２）、（０，２，２）、（０，３，２）及び（０，４，２）の位置と、（１，４，２）の位置とにスピン「７」がそれぞれ配置される。
【０１３４】
また図２１では、図１１と同様に、相互作用を及ぼすスピン間を結ぶ辺は太線で、また相互作用を及ばさないスピン間を結ぶ辺は細線で示している。つまり、図２１の格子イジングモデルでは、Ｚ軸方向の最も奥側の層では、Ｙ軸方向に隣接するスピン同士のみが相互作用を及ぼし、Ｚ軸方向の中間の層では、Ｘ軸方向に隣接するスピン同士のみが相互作用を及ぼし、Ｚ軸方向の手前側の層では、Ｘ軸方向又はＹ軸方向に隣接するスピン同士が相互作用を及ぼし、Ｚ軸方向の奥側の層、中間の層及び手前側の層間では、Ｚ軸方向に隣接するスピン同士が相互作用を及ぼす。
【０１３５】
（４）本実施の形態の効果
以上のように本実施の形態の情報処理装置１では、問題データ７を、当該問題のイジングモデルの基底状態のスピン配列を変化させないように、複数のイジングチップ１３により表現可能な階段状の格子イジングモデルのデータに変換し、当該格子イジングモデルのデータを分割して各イジングチップ１３に割り当てるようにしたことにより、任意のイジングモデルの基底状態を探索することができる。また、あるイジングチップ１３が値を保持するスピンのうち、他の半導体チップが値を保持するスピンに相互作用を及ぼすスピンの数を低減させることができるため、結果として、イジングチップ１３間を接続するチップ間配線の配線量を抑えることができる。かくするにつき、安価かつ容易に製造でき、任意のイジングモデルの基底状態を探索可能な情報処理装置を実現できる。
【０１３６】
（５）他の実施の形態
なお上述の実施の形態おいては、問題のイジングモデルを図１１や図２１について上述した形態の格子イジングモデルに変換するようにした場合について述べたが、本発明はこれに限らず、問題のイジングモデルを、その基底状態のスピン配列を変化させずに、複数のイジングチップ１３により表現可能な格子イジングモデルに変換するのであれば、格子イジングモデルの形態としては、この他種々の形態を広く適用することができる。
【０１３７】
また上述の実施の形態においては、イジングチップ１３間の配線方式として、イジングチップ１３のチップ端部に設けられたスピンユニット４０のうちの１つおきのスピンユニット４０にそれぞれ対応付けて接続部５０を設け、これらの接続部５０を他のイジングチップ１３の対応する接続部５０とそれぞれ接続するようにした場合について述べたが、本発明はこれに限らず、イジングチップ１３内のスピンユニット４０のうち、他のイジングチップ１３内のスピンユニット４０が値を保持するスピンと相互作用を及ぼすスピンユニット４０にのみ対応付けて接続部５０を設け、これらの接続部５０を他のイジングチップ１３の対応する接続部５０とそれぞれ接続するようにしても良い。このようにすることによって、より一層とイジングチップ１３間の配線量を抑えることができる。
【産業上の利用可能性】
【０１３８】
本発明はイジングモデルの基底状態探索を行う半導体装置に広く適用することができる。
【符号の説明】
【０１３９】
１……情報処理装置、３……ＣＰＵ、６……マルチイジングチップ、７……問題データ、８……問題変換プログラム、９……マルチイジングチップ制御プログラム、１３……イジングチップ、１４……チップ間配線、２０……スピンアレイ、２４……チップ間接続部、４０……スピンユニット、５０……接続部。
【図１】
2016199220.tif 000015
【図２】
2016199220.tif 000016
【図３】
2016199220.tif 000017
【図４】
2016199220.tif 000018
【図５】
2016199220.tif 000019
【図６】
2016199220.tif 000020
【図７】
2016199220.tif 000021
【図８】
2016199220.tif 000022
【図９】
2016199220.tif 000023
【図１０】
2016199220.tif 000024
【図１１】
2016199220.tif 000025
【図１２】
2016199220.tif 000026
【図１３】
2016199220.tif 000027
【図１４】
2016199220.tif 000028
【図１５】
2016199220.tif 000029
【図１６】
2016199220.tif 000030
【図１７】
2016199220.tif 000031
【図１８】
2016199220.tif 000032
【図１９】
2016199220.tif 000033
【図２０】
2016199220.tif 000034
【図２１】
2016199220.tif 000035
【国際調査報告】
2016199220.tif 000036
2016199220.tif 000037