(57)【要約】  イジングモデルの基底状態を求めるために基本構成単位となる構成要素をアレイ状に配置した半導体装置を実現する。該半導体装置では、イジングモデルの１つのスピンの値を記憶するメモリセルと、該スピンに相互作用を及ぼす隣接するスピンからの相互作用係数を記憶するメモリセルと、前記１つのスピンの外部磁場係数を記憶するメモリセルと、並びに、前記各隣接スピンの値と前記対応する相互作用係数の積、及び前記外部磁場係数において、２値の多数決論理によって前記１つのスピンの次状態を決定する回路とを有するスピンユニットが構成され、前記イジングモデルの各スピンをそれぞれ割り付けられた複数の前記スピンユニットが、前記イジングモデルのトポロジを維持した状態で、半導体基板上の２次元平面に配置、接続されて構成されたスピンアレイを備える。
2015132883.tif 000002
【特許請求の範囲】
【請求項１】
イジングモデルの１つのスピンの値を記憶するメモリセルと、該スピンに相互作用を及ぼす隣接するスピンからの相互作用係数を記憶するメモリセルと、前記１つのスピンの外部磁場係数を記憶するメモリセルと、並びに、前記各隣接スピンの値と前記対応する相互作用係数の積、及び前記外部磁場係数において、２値の多数決論理によって前記１つのスピンの次状態を決定する回路とを有するスピンユニットが構成され、
前記イジングモデルの各スピンをそれぞれ割り付けられた複数の前記スピンユニットが、前記イジングモデルのトポロジを維持した状態で、半導体基板上の２次元平面に配置、接続されて構成されたスピンアレイを備えたことを特徴とする半導体装置。
【請求項２】
前記スピンユニットを構成する前記１つのスピンの値を記憶するメモリセルは２値を表現する１ビットメモリにより構成され、
前記スピンユニットを構成する前記１つのスピンの外部磁場係数を記憶するメモリセルと、及び前記１つのスピンに相互作用を及ぼす隣接するスピンからの相互作用係数を記憶するメモリセルは、それぞれ３値を表現する１組の１ビットメモリ２個より構成されていることを特徴とする請求項１に記載の半導体装置。
【請求項３】
前記スピンアレイ内に配置された各スピンユニットが有する前記スピンの値を記憶するメモリセルに、その他のメモリセル、及び回路へ電源を供給する電源線とは区別する専用の電源線が接続され、
前記各スピンユニットにおいて、前記スピンの次状態を決定する処理を実行時に、前記専用の電源線を介して前記スピンの値を記憶するメモリセルへ供給する電源電圧を下げる制御が為されることを特徴とする請求項１に記載の半導体装置。
【請求項４】
前記スピンアレイ内に配置された各スピンユニットに相互作用制御インタフェースが接続され、
前記隣接して相互作用を及ぼす関係にあるスピンがそれぞれ割り付けられた前記スピンユニット同士を別々のグループに分けて、前記各グループ分けされたスピンユニットに対して、各グループに属する全てのスピンユニットにスピンの次状態を決定する処理を許可する信号を入力する信号線が接続されていることを特徴とする請求項１に記載の半導体装置。
【請求項５】
前記グループ分けされたスピンユニットを、同時に実行する消費電力に応じて更に細分割したグループに分け、前記分割された各グループに属する全てのスピンユニットにスピンの次状態を決定する処理を許可する信号を入力する信号線が接続されていることを特徴とする請求項４に記載の半導体装置。
【請求項６】
請求項１に記載の半導体装置において、
前記イジングモデルの各スピンをそれぞれ割り付けられた複数の前記スピンユニットが、前記イジングモデルのトポロジを維持した状態で、半導体基板上の２次元平面に配置、接続されて構成されたスピンアレイとは、
前記スピンアレイ内に配置された各スピンユニットが、３次元格子のイジングモデルの各格子頂点を２次元平面に配置する方法として、Ｘ軸方向の格子頂点配列の各間隔にＺ軸方向の格子頂点配列の各格子頂点を挿入するように、及びＹ軸方向の格子頂点配列は同様の配列で、各格子頂点のスピンを割り付けた各スピンユニットが半導体基板上に配置され、並びに、前記各スピンユニット間を３次元格子のトポロジを維持した状態で配線接続されたことであることを特徴とする半導体装置。
【請求項７】
前記メモリセルは、ＣＭＯＳインバータ２個で構成されるデータ保持部と、パスゲートトランジスタとを備えることを特徴とする請求項１乃至３のいずれかの請求項に記載の半導体装置。
【請求項８】
ＣＰＵ、ＲＡＭ、ＨＤＤ、及び請求項1乃至６のいずれかの請求項に記載された半導体装置をシステムバスに接続した情報処理装置であって、
前記ＣＰＵ上で実行された前記半導体装置の制御プログラムは、
対象問題を表現するイジングモデルの相互作用係数と外部磁場係数を生成し、
前記イジングモデルの各スピンを前記半導体装置上の前記スピンアレイ内の前記スピンユニットへの割当てを決定し、
初期スピン配列をランダムに生成し、
前記イジングモデルの各スピンを割当てた前記半導体装置上の前記スピンアレイ内の前記スピンユニットへ、前記初期スピン配列、前記相互作用係数、及び前記外部磁場係数を書き込み、
グループ分けした前記スピンユニットの基底状態探索処理を所定の回数繰り返し実行し、
基底状態に達した前記スピンユニットのスピン配列を読み出して対象問題の解を得ることを特徴とする情報処理装置。
【請求項９】
ＣＰＵ、ＲＡＭ、ＨＤＤ、及びアクセラレータとして適用が可能な半導体装置をシステムバスに接続した情報処理装置であって、
前記半導体装置は、
イジングモデルの１つのスピンの値を記憶するメモリセルと、該スピンに相互作用を及ぼす隣接するスピンからの相互作用係数を記憶するメモリセルと、前記１つのスピンの外部磁場係数を記憶するメモリセルと、並びに、前記各隣接スピンの値と前記対応する相互作用係数の積、及び前記外部磁場係数において、２値の多数決論理によって前記１つのスピンの次状態を決定する回路とを有するスピンユニットが構成され、
前記イジングモデルの各スピンをそれぞれ割り付けられた複数の前記スピンユニットが、前記イジングモデルのトポロジを維持した状態で、半導体基板上の２次元平面に配置、接続されて構成されたスピンアレイと、
前記スピンアレイ内に配置されたスピンユニットのメモリセルをリード／ライトするＩ／Ｏインタフェースと、
グループ分けされたスピンユニットに対して、グループ毎に、相互作用を許可する信号を供給する相互作用制御インタフェースとを備え、
前記ＣＰＵ上で実行された前記半導体装置の制御プログラムは、
対象問題を表現するイジングモデルの相互作用係数と外部磁場係数を生成し、
前記イジングモデルの各スピンを前記半導体装置上の前記スピンアレイ内の前記スピンユニットへの割当てを決定し、
初期スピン配列をランダムに生成し、
前記イジングモデルの各スピンを割当てた前記半導体装置上の前記スピンアレイ内の前記スピンユニットへ、前記初期スピン配列、前記相互作用係数、及び前記外部磁場係数を書き込み、
グループ分けした前記スピンユニットの基底状態探索処理を所定の回数繰り返し実行し、
基底状態に達した前記スピンユニットのスピン配列を読み出して対象問題の解を得ることを特徴とする情報処理装置。
【請求項１０】
前記ＣＰＵ上で実行された前記半導体装置の制御プログラムが、グループ分けした前記スピンユニットの基底状態探索処理を所定の回数繰り返し実行するステップは、
前記スピンユニットのグループを選択するアドレスを設定し、
前記選択したグループのスピンユニットの相互作用を起こさせるクロックを生成し、
前記スピンユニットのスピンの値を記憶するメモリセルに接続する電源線に供給される電圧をスケジューリングに沿って下げる制御を行い、
前記選択するグループを順次変えて、上記処理を所定の回数繰り返し実行するステップであることを特徴とする請求項８、または請求項９に記載の情報処理装置。
【請求項１１】
請求項８、または請求項９に記載の情報処理装置において、
前記ＣＰＵ上で実行された前記半導体装置の制御プログラムは、
前記イジングモデルの各スピンを前記半導体装置上の前記スピンアレイ内の前記スピンユニットへの互いに異なる割当てマップを複数生成し、
第１の割当てマップに従って、前記スピンユニットへ、前記初期スピン配列、前記相互作用係数、及び前記外部磁場係数を書き込み、
グループ分けした前記スピンユニットの基底状態探索処理を所定の回数繰り返し実行し、
前記スピンユニットのスピン配列を読み出して記録し、
次に適用する割当てマップに従って、前記記録したスピン配列を新たな割当てスピンユニットの初期スピン配列とし、イジングモデルの相互作用係数と外部磁場係数を再生成して、前記スピンユニットへ、前記初期スピン配列、前記相互作用係数、及び前記外部磁場係数を書き込み、
新たな割当てマップに従って、グループ分けした前記スピンユニットの基底状態探索処理を所定の回数繰り返し実行することを特徴とする情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、イジングモデルの基底状態を求める半導体装置に関するものであり、特に、イジングモデルのスピンをＣＭＯＳのフリップフロップとして模擬する半導体装置と、その半導体装置をアクセラレータとして制御する情報処理装置に関する。
【背景技術】
【０００２】
現在、コンピュータアーキテクチャの主流はノイマン型である。ノイマン型アーキテクチャでは逐次的な命令列であるプログラムでその動作が定義される。プログラムを変更することにより、様々な用途に利用可能な汎用性を有している。コンピュータの中心的な役割を果たすＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）のみならず、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）のような特定用途向けの演算装置もノイマン型アーキテクチャで構成されており、その基本動作は命令列の逐次的な実行にある。【０００３】
これまで、コンピュータの性能向上は主としてクロック周波数の向上に依っていた。ノイマン型アーキテクチャの根幹は命令例の逐次的な実行であるから、命令の実行速度を高速化すれば性能向上が期待できる。しかし、パーソナルコンピュータやサーバに用いられる汎用的なＣＰＵにおいては、クロック周波数の向上は２０００年代初頭に３ＧＨｚ前後で頭打ちとなっている。近年では頭打ちになったクロック周波数にかわって、マルチコア化による並列処理で性能向上を実現する方策が主流になっている。【０００４】
マルチコア化による並列処理では、逐次的な命令列から並列実行可能な箇所を見出し（並列性の抽出）、並列実行することで性能向上を図る。しかし、逐次的なアルゴリズムを命令列として書き下したプログラムから並列性を抽出することは容易ではない。命令のレベルで並列性を抽出するＩＬＰ（Ｉｎｓｔｒｕｃｔｉｏｎ  Ｌｅｖｅｌ  Ｐａｒａｌｌｅｌｉｓｍ）は既に限界に達しており、近年ではＴＬＰ（Ｔｈｒｅａｄ Ｌｅｖｅｌ  Ｐｒａｌｌｅｌｉｓｍ）やＤＬＰ（Ｄａｔａ  Ｌｅｖｅｌ  Ｐａｒａｌｌｅｌｉｓｍ）のように、より粒度の粗い並列性を利用する方向になっている。【０００５】
このような状況を鑑みると、今後、コンピュータの性能向上を図っていくためには、従来のように逐次的な命令列の実行を基本とするのではなく、本質的に並列な情報処理に移行していく必要がある。そのためには、従来の逐次的な命令列による問題の記述方法に替わって、本質的に並列な情報処理を実現するために適した問題の記述方法が必要となる。
その一つの候補としてイジングモデルがある。イジングモデルは磁性体の振舞いを説明するための統計力学のモデルであり、磁性体の研究に用いられている。イジングモデルはサイト（＋１／−１の２値をとるスピン）間の相互作用として定義される。トポロジが非平面グラフになるイジングモデルの基底状態を求めることはＮＰ困難問題であることが知られている。イジングモデルは空間方向に広がった相互作用係数で問題を表現するため、本質的な並列性を利用した情報処理を実現できる可能性がある。【０００６】
ところで、イジングモデルの基底状態を求めることは、前述した通りＮＰ困難問題であるから、ノイマン型コンピュータで解くことは計算時間の面で困難を伴う。ヒューリスティックを導入して高速化を図るアルゴリズムも提案されているが、ノイマン型コンピュータではなく物理現象をより直接的に利用した計算、すなわちアナログコンピュータでイジングモデルの基底状態を高速に求める方法が提案されている。例えば、このような装置として、例えば特許文献１に記載の装置がある。このような装置では、解くべき問題に対応した並列度が必要になってくる。イジングモデルの場合では、基底状態を探索すべきイジングモデルのスピン数に対応して、スピンや相互作用を実現する素子が必要となる。例えば特許文献１に記載の装置ではスピンとレーザーを対応させており、スピン数に比例した数のレーザーが必要となる。すなわち、多数の素子を実現できるスケーラビリティの高さが必要となる。そのため、構成単位となる要素を規則的に多数並べて実現できる、半導体装置のような固体素子でイジングモデルの基底状態探索を行えることが望ましい。特にＤＲＡＭやＳＲＡＭなどの記憶装置に代表されるようなアレイ構造であり、かつ集積性を高められるように構成単位となる要素が単純な構造であるほうが望ましい。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】国際公開第２０１２／１１８０６４号
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明は、イジングモデルの基底状態を求めるために基本構成単位となる構成要素をアレイ状に配置した半導体装置を、現在主流のＣＭＯＳ集積回路など容易に製造可能な手段で実現することを目的とする。
【課題を解決するための手段】
【０００９】
上記課題を解決するために本発明では、半導体装置を、イジングモデルの１つのスピンの値を記憶するメモリセルと、該スピンに相互作用を及ぼす隣接するスピンからの相互作用係数を記憶するメモリセルと、前記１つのスピンの外部磁場係数を記憶するメモリセルと、並びに、前記各隣接スピンの値と前記対応する相互作用係数の積、及び前記外部磁場係数において、２値の多数決論理によって前記１つのスピンの次状態を決定する回路とを有するスピンユニットが構成され、前記イジングモデルの各スピンをそれぞれ割り付けられた複数の前記スピンユニットが、前記イジングモデルのトポロジを維持した状態で、半導体基板上の２次元平面に配置、接続されて構成されたスピンアレイを備えて構成した。【００１０】
また、上記課題を解決するために本発明では、前記半導体装置において、前記スピンアレイ内に配置された各スピンユニットが有する前記スピンの値を記憶するメモリセルに、その他のメモリセル、及び回路へ電源を供給する電源線とは区別する専用の電源線が接続され、前記各スピンユニットにおいて、前記スピンの次状態を決定する処理を実行時に、前記専用の電源線を介して前記スピンの値を記憶するメモリセルへ供給する電源電圧を下げる制御が為されるように構成した。【００１１】
また、上記課題を解決するために本発明では、前記半導体装置において、前記イジングモデルの各スピンをそれぞれ割り付けられた複数の前記スピンユニットが、前記イジングモデルのトポロジを維持した状態で、半導体基板上の２次元平面に配置、接続されて構成されたスピンアレイを、前記スピンアレイ内に配置された各スピンユニットが、３次元格子のイジングモデルの各格子頂点を２次元平面に配置する方法として、Ｘ軸方向の格子頂点配列の各間隔にＺ軸方向の格子頂点配列の各格子頂点を挿入するように、及びＹ軸方向の格子頂点配列は同様の配列で、各格子頂点のスピンを割り付けた各スピンユニットが半導体基板上に配置され、並びに、前記各スピンユニット間を３次元格子のトポロジを維持した状態で配線接続されるように構成した。【００１２】
また、上記課題を解決するために本発明では、ＣＰＵ、ＲＡＭ、ＨＤＤ、及びアクセラレータとして適用が可能な半導体装置をシステムバスに接続した情報処理装置を、前記半導体装置は、イジングモデルの１つのスピンの値を記憶するメモリセルと、該スピンに相互作用を及ぼす隣接するスピンからの相互作用係数を記憶するメモリセルと、前記１つのスピンの外部磁場係数を記憶するメモリセルと、並びに、前記各隣接スピンの値と前記対応する相互作用係数の積、及び前記外部磁場係数において、２値の多数決論理によって前記１つのスピンの次状態を決定する回路とを有するスピンユニットが構成され、前記イジングモデルの各スピンをそれぞれ割り付けられた複数の前記スピンユニットが、前記イジングモデルのトポロジを維持した状態で、半導体基板上の２次元平面に配置、接続されて構成されたスピンアレイと、前記スピンアレイ内に配置されたスピンユニットのメモリセルをリード／ライトするＩ／Ｏインタフェースと、グループ分けされたスピンユニットに対して、グループ毎に、相互作用を許可する信号を供給する相互作用制御インタフェースとを備え、前記ＣＰＵ上で実行された前記半導体装置の制御プログラムは、対象問題を表現するイジングモデルの相互作用係数と外部磁場係数を生成し、前記イジングモデルの各スピンを前記半導体装置上の前記スピンアレイ内の前記スピンユニットへの割当てを決定し、初期スピン配列をランダムに生成し、前記イジングモデルの各スピンを割当てた前記半導体装置上の前記スピンアレイ内の前記スピンユニットへ、前記初期スピン配列、前記相互作用係数、及び前記外部磁場係数を書き込み、グループ分けした前記スピンユニットの基底状態探索処理を所定の回数繰り返し実行し、基底状態に達した前記スピンユニットのスピン配列を読み出して対象問題の解を得るように構成した。
【発明の効果】
【００１３】
本発明によれば、現在幅広く用いられているＣＭＯＳ集積回路のプロセスで製造することができるイジングモデルの基底状態を求める半導体装置を提供することができる。さらに、半導体の製造工程で生じるデバイスの製造ばらつきに適応して基底状態探索を行うことができる。 
【図面の簡単な説明】
【００１４】
【図１】本発明の半導体装置であるイジングチップの構成の一例を説明する図である。
【図２】本発明の半導体装置であるイジングチップを制御する情報処理装置の構成の一例を説明する図である。
【図３】スピンユニットの構成の一例を、スピンユニット間の相互作用を行う回路の構成について説明する図である。
【図４】スピンユニットの構成の一例を、スピンユニットが有するメモリセルにアクセスするための構成について説明する図である。
【図５】３次元格子のスピンアレイの構成の一例を説明する図である。
【図６】イジングチップの制御手順の一例を説明するフローチャートである。
【図７】イジングチップの制御手順の一例を説明するフローチャートである。
【図８】３次元格子のスピンアレイとスピンユニットの対応関係の一例を説明する図である。
【図９】イジングチップ上のスピンユニットの配置の一例を説明する図である。
【図１０】スピンユニット間の相互作用を行う配線の一例を説明する図である。
【図１１】イジングチップが解くグラフ問題の一例を説明する図である。
【図１２】イジングチップが解くグラフ問題の一例を説明する図である。
【図１３】イジングチップが解くグラフ問題の一例を説明する図である。
【図１４】グラフ問題に対応するイジングモデルの一例を説明する図である。
【図１５】グラフ問題に対応するイジングモデルの一例を説明する図である。
【図１６】イジングモデルのイジングチップへの割り付けの一例を説明する図である。
【図１７】イジングモデルのイジングチップへの割り付けの一例を説明する図である。
【図１８】イジングモデルのイジングチップへの割り付けの一例を説明する図である。
【図１９】メモリセルの構成の一例を説明する図である。
【図２０】イジングチップのメモリマップの一例を説明する図である。
【図２１】イジングモデルの基底状態探索を行わせるために、イジングチップに書き込むべきデータの一例を説明する図である。
【図２２】イジングチップによるイジングモデルの基底状態探索をイジングチップが行った後に、イジングチップから読み出したデータの一例を説明する図である。
【図２３】イジングモデルのイジングチップへの割り付けの一例を説明する図である。
【図２４】イジングモデルの基底状態探索を行わせるために、イジングチップに書き込むべきデータの一例を説明する図である。
【図２５】スピンユニットのグループ分けと相互作用クロック、及び、相互作用アドレスの関係について説明する図である。
【図２６】スピンユニットのグループ分けを、３次元格子のスピンアレイに対応させて説明する図である。
【図２７】イジングチップの動作の一例を示すタイムチャートである。
【図２８】スピンユニット内のメモリセルとスピンアレイのトポロジとの対応関係を説明する図である。
【発明を実施するための形態】
【００１５】
以下、実施例を図面を用いて説明する。
【実施例１】
【００１６】
本実施例では、イジングモデルの基底状態を求める半導体装置であるイジングチップ１００、及びイジングチップ１００を制御する情報処理装置２００の例を説明する。【００１７】
（１）解くべき問題をイジングモデルの基底状態探索問題に変換
イジングモデルは磁性体の振舞いを説明するための統計力学のモデルである。イジングモデルは＋１／−１（または、０／１、上／下）の２値をとるスピンと、スピン間の相互作用を示す相互作用係数、および、スピン毎にある外部磁場係数で定義される。【００１８】
イジングモデルは与えられたスピン配列、相互作用係数、および、外部磁場係数から、その時のエネルギーを計算することが出来る。イジングモデルのエネルギー関数Ｅ(σ)は一般的に次式(数１)で表わされる。なお、σｉ，σｊはそれぞれｉ番目とｊ番目のスピンの値、Ｊi,jはｉ番目とｊ番目のスピンの間の相互作用係数、ｈｉはｉ番目のスピンに対する外部磁場係数、＜ｉ，ｊ＞は隣接する２つのサイトの組合せ、σはスピンの配列を表わすものとする。【００１９】
【数１】
2015132883.tif 000003
【００２０】
イジングモデルの基底状態を求めるというのは、イジングモデルのエネルギー関数を最小化するスピンの配列を求める最適化問題である。
例えば、因数分解や巡回セールスマン問題など、一見すると磁性体と何ら関係の無い問題をイジングモデルに変換することができる。そして、変換して得られたイジングモデルの基底状態は、元の問題の解に対応している。このことから、イジングモデルの基底状態を探索することのできる装置は、汎用的な用途に利用可能なコンピュータであると言える。【００２１】
本実施例において、解きたい問題からイジングチップの設定までを一例通して説明するために、例題としてグラフの最大カット問題を示す。まず、図１１を用いてグラフを説明する。図１１のグラフＧ＝（Ｖ，Ｅ）は頂点の集合Ｖ＝｛Ａ，Ｂ，Ｃ，Ｄ｝と、辺の集合Ｅ＝｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ｝から構成される。各辺は重み係数を持っており、ａ，ｂ，ｃ，ｄ，ｅ，ｆと書いたときにその重み係数を表わすものとする。【００２２】
図１２に示すように、このグラフの頂点Ｖを２つの部分集合Ｖ’とＶ’＼Ｖに分割することをカットと呼ぶ。Ｖ’＼ＶはＶからＶ’を除いた集合を示す。ここで、分割されたＶ’とＶ’＼Ｖの間を跨っている辺（図１２の例ではｃ，ｄ，ｅ，ｆ）をカットを跨いでいるエッジ、もしくは、カットエッジと呼ぶ。重みが無いグラフの場合にはカットエッジの本数、図１２のように重み付きのグラフの場合にはカットエッジの重みの総和を、カットの大きさと呼ぶ。図１２の例では、カットの大きさはｃ＋ｄ＋ｅ＋ｆである。
なお、図１１、及び、図１２は無向グラフの例であるが、有向グラフに拡張することも出来る。【００２３】
最大カット問題とは、グラフＧ＝（Ｖ，Ｅ）を与えられた時、カットの大きさを最大化するカットを求めることである。換言すれば、カットの大きさを最大化するように、頂点の集合ＶをＶ’とＶ’＼Ｖにグループ分けすることと言っても良い。
最大カット問題の具体的な例を図１３に示す。この例では頂点ＶをＶ’＝｛Ａ，Ｂ｝とＶ’＼Ｖ＝｛Ｃ,Ｄ｝に分けるようにカットした時に、カットの大きさｗ（Ｖ’）＝２となり、このグラフにおける最大カットとなる。【００２４】
図１２に戻ってグラフのカットとイジングモデルの関係について説明する。図１２のグラフでは、カットの大きさｗ（Ｖ’）＝ｃ＋ｄ＋ｅ＋ｆである。ここで、図１２のグラフをイジングモデルと見なすと、辺Ｅ＝｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ｝の重みは、イジングモデルの相互作用係数となる。そして、頂点Ｖ＝｛Ａ，Ｂ，Ｃ，Ｄ｝はイジングモデルではそれぞれ＋１／−１の２値の状態を持つスピンとなる。ここで、カットした頂点Ｖ’に属する頂点は＋１のスピン、Ｖ’＼Ｖに属する頂点は−１のスピンとする。つまり、Ａ＝＋１，Ｂ＝＋１，Ｃ＝−１，Ｄ＝−１とする。このときのイジングモデルのエネルギーは、数１に示したエネルギー関数に沿って計算すると、−（ａ＋ｂ−ｃ−ｄ−ｅ−ｆ）＝−ａ−ｂ＋ｃ＋ｄ＋ｅ＋ｆとなる。ところで、カットの大きさｗ（Ｖ’）＝ｃ＋ｄ＋ｅ＋ｆであることから、このエネルギー関数は数２のように書くことが出来る。【００２５】
【数２】
2015132883.tif 000004
【００２６】
図１２の例に沿って具体的に計算してみると、−（（ａ＋ｂ＋ｃ＋ｄ＋ｅ＋ｆ）−２（ｃ＋ｄ＋ｅ＋ｆ））＝−（ａ＋ｂ−ｃ−ｄ−ｅ−ｆ）となることが確かめられよう。数２を見るとカットの大きさｗ（Ｖ’）を最大化すれば、エネルギーＥ（σ）も大きくなることが分かる。つまり、カットも大きさを最大化すると、イジングモデルのエネルギーは最大化される。逆に、カットの大きさを最小化すると、イジングモデルのエネルギーは最小化される。つまり、イジングモデルの基底状態探索は、最小カットを求めることに対応している。そこで、最小カットを求めるためには、最大カット問題の重みの符号を全て反転させることで、最小カットを求めることに変換する。【００２７】
なお、最小カット問題は重みの符号が全て正である場合に限り、最大フロー最小カット定理によりフォード・ファルカーソンのアルゴリズムにより効率的に求められることが知られている。しかし、最大カット問題の重みの符号を反転させて最小カット問題を作った場合には、多くの場合負の重みが含まれるため、フォード・ファルカーソンのアルゴリズムを適用することはできない。また、重みの符号が全て正の最大カット問題は半正定値計画問題を用いる近似解法が存在するが正の重みに限定されている。それに対して、イジングモデルの基底状態探索で最大カット問題、または、最小カット問題を表現する場合には、重みの正負を問わない。【００２８】
図１３に示した最大カット問題を、イジングモデルの基底状態探索問題に変換した例を図１４に示す。図１４の各辺についている相互作用係数ＪＡＢ、ＪＡＣ、ＪＡＤ、ＪＢＣ、ＪＢＣ、ＪＣＤを見ると、図１３の重みの符号を反転したものになっている。これが前述した最大カット問題から最小カット問題への変換に対応する。そして、図１４のイジングモデルの基底状態を探索し、エネルギーが最小となるようにスピンσＡ，σＢ，σＣ，σＤを決定したものを図１５に示す。なお、図１５の例ではσＡ＝＋１，σＢ＝＋１，σＣ＝−１，σＤ＝−１だが、イジングモデルでは全てのスピンの状態を反転させたものも同じエネルギーとなるので、σＡ＝−１，σＢ＝−１，σＣ＝＋１，σＤ＝＋１も基底状態となる。図１５の例をみると、カットＶ’に属する頂点はスピンの値が＋１となり、Ｖ’＼Ｖに属する頂点はスピンの値が−１となっている。このように、イジングモデルの基底状態探索を行い、スピンの値で頂点をグループ分けすることで、最大カット、または、最小カットを実現することができるのである。【００２９】
ここで、図１４に示したようなイジングモデルの基底状態探索を実現する装置と、その制御方法を本発明では示す。前述したように、トポロジが非平面グラフになるイジングモデルの基底状態を求めることはＮＰ困難問題であることが知られていることから、３次元格子のイジングモデルの基底状態探索を実現する装置の例を示す。しかし、本発明は３次元格子のイジングモデルに限られるものではなく、任意のトポロジ、任意のスピン数に対して適用可能である。【００３０】
（２）イジングチップの構成
図１は、本実施例のイジングチップ１００の構成図の例である。イジングチップ１００はスピンアレイ１１０、Ｉ／Ｏドライバ１２０、Ｉ／Ｏアドレスデコーダ１３０、および、相互作用アドレスデコーダ１４０から構成される。本実施例ではイジングチップ１００は現在広く用いられているＣＭＯＳ集積回路として実装されることを想定して説明するが、他の固体素子でも実現可能である。イジングチップ１００は、スピンアレイ１１０にリード／ライトを行うためのＳＲＡＭ互換インタフェース１５０を持っており、アドレスバス１９０、データバス１９１、Ｒ／Ｗ制御線１９３、および、Ｉ／Ｏクロック１９２である。また、イジングモデルの基底状態探索の制御を行うための相互作用制御インタフェース１６０として、相互作用アドレス１８０、および、相互作用クロック１８１を有している。イジングチップ１００は通常電源線１４２で供給される電圧で動作するが、スピンアレイ１１０の一部はスピン用電源線１４１で供給される電圧で動作する。具体的には、スピンアレイ１１０を構成するスピンユニット３００（図３）が有するメモリセルのうち、スピン情報を保持するメモリセルＮはスピン用電源線１４１で供給される電圧で動作する。【００３１】
イジングチップ１００では、イジングモデルのスピンσｉ、相互作用係数Ｊi,j、および、外部磁場係数ｈｉを全てスピンアレイ１１０内のメモリセルに記憶する情報で表現する。スピンの初期状態の設定、及び、基底探索完了後の解読み出しのためにスピンσｉのリード／ライトをＳＲＡＭ互換インタフェース１５０で行う。また、基底状態を探索すべきイジングモデルをイジングチップ１００に設定するために、相互作用係数Ｊi,j、および、外部磁場係数ｈｉのリード／ライトもＳＲＡＭ互換インタフェース１５０で行う。そのため、スピンアレイ１１０内のスピンσｉ、相互作用係数Ｊi,j、および、外部磁場係数ｈｉにはアドレスが付与されている。なお、ＳＲＡＭ互換インタフェース１５０を構成するアドレスバス１９０、データバス１９１、および、Ｒ／Ｗ制御線１９３は、Ｉ／Ｏクロック１９２に入力されるクロックに同期して動作する。但し、本発明においてインタフェースが同期式である必要性は無く、非同期式のインタフェースでも良い。本実施例では、同期式のインタフェースであるという前提で説明を行う。【００３２】
また、イジングチップ１００は基底状態探索を行うために、スピンアレイ１１０の内部でスピン間の相互作用を実現する。この相互作用を外部から制御するのが相互作用制御インタフェース１６０であり、具体的には相互作用を行うスピン群を指定するアドレスを相互作用アドレス１８０で入力し、相互作用クロック１８１に入力されるクロックに同期して相互作用を行う。なお、相互作用は必ずしもクロック同期回路で実現される必要はなく、非同期回路であっても構わない。この場合、相互作用クロック１８１の役割はクロックの入力ではなく、相互作用の実行を許可するイネーブル信号であるものとする。相互作用制御インタフェースについても必ずしも同期式である必要はなく非同期式のインタフェースでも良いが、本実施例では同期式のインタフェースを用い、相互作用が相互作用クロック１８１に同期して行われるという前提で説明を行う。【００３３】
（３）スピンアレイのメモリセル製造ばらつきへの適応
イジングチップ１００ではスピンアレイ１１０が多数のスピンユニット３００（詳細は後述する）を持つことで、高い並列性を実現している。このように空間的に多数の並列性を利用する上では、その多数の構成要素に生じる特性のばらつきに適応することが必要となる。このような製造ばらつきへの適応は、例えばデバイスに対して製造ばらつきを吸収するための回路を付加し、その回路にある抵抗値等の回路定数を調整することで個体差に適応することが一般的に考えられる。また、複数個のデバイス（トランジスタ）を並列接続することで、個体差を平均化するという方法もある。いずれの場合でも、個体差に適応するために回路やデバイスの付加ないしは冗長化を行っており、回路規模の増大を招くという副作用を持っている。【００３４】
特に、並列度を高めようとして多数の構成要素を並べようとすると、製造ばらつきの影響は構成要素数に比例して大きくなる。さらに、半導体装置の場合には集積度を高めるために必要な半導体プロセスの微細化自体が製造ばらつきを大きくする原因となっている。一方で、前述したような回路の付加による製造ばらつきへの適応は、基本構成単位となる構成要素の内部構造を複雑化させ、スケーラビリティを低下させてしまう。すなわち、スケーラビリティを高めようとするほど製造ばらつきの影響が大きくなるが、一方で製造ばらつきへの適応を進めようとするとスケーラビリティを低下させてしまうという、二律背反的な関係がある。【００３５】
また、本発明では後述するように、スピンユニット３００内のメモリセルに供給する電源電圧を下げることで生じるランダムな挙動を利用する形態を採用しているが、このような形態とした理由は特に製造ばらつきからの影響が大きい。
そこで、本発明では後述するように、解くべきイジングモデルのスピンと、スピンアレイ１１０内のスピンユニット３００との対応関係を変更しながら基底状態探索を行うことで、ハードウェアが複雑化することを最小限に抑えながら、製造ばらつきに適応することを実現する。これによって、高いスケーラビリティを実現する。【００３６】
（４）情報処理装置の構成
このイジングチップ１００を１個、または、複数個用いて情報処理を実現するわけであるが、そのためには前述したようなインタフェースを制御しなければならない。そのために、イジングチップ１００は図２に示すような情報処理装置２００の一部として利用される。【００３７】
情報処理装置２００は、現在一般的に用いられているパーソナルコンピュータやサーバのような装置に、イジングチップ１００で構成されたアクセラレータを装着したものと考えて良い。情報処理装置２００は、ＣＰＵ２１０、ＲＡＭ２２０、ＨＤＤ２６０、ＮＩＣ２４０を有し、これらがシステムバス２３０で結合されている。これは、現在のパーソナルコンピュータやサーバに一般的に見られる構成である。加えて、システムバス２３０にイジングチップコントローラ２５０が接続され、その先に１個ないしは複数個のイジングチップ（図２の例では、２個のイジングチップ１００−１、及び、イジングチップ１００−２を有する。これ以降、２個のイジングチップを特に区別する必要の無いときには、単にイジングチップ１００と称する。）を持つ。このイジングチップコントローラ２５０とイジングチップ１００がアクセラレータに相当するものであり、例えばＰＣＩ  Ｅｘｐｒｅｓｓのようなペリフェラル拡張用インタフェースに挿入して使う拡張カードのような形態を取る。イジングチップコントローラ２５０はシステムバス２３０（例えばＰＣＩ  ＥｘｐｒｅｓｓやＱＰＩ）のプロトコルをイジングチップのインタフェースに合せて変換するものである。情報処理装置２００のＣＰＵ２１０上で動作するソフトウェアは、一般的には特定のアドレスに対してリード／ライトを行うことで（いわゆるＭＭＩＯ、Ｍｅｍｏｒｙ  Ｍａｐｐｅｄ  Ｉ／Ｏ）、イジングチップコントローラ２５０を経由して、イジングチップ１００を制御することが出来る。また、このような情報処理装置を、装置間ネットワーク２９０を介して、複数台結合して利用しても良い。【００３８】
（５）スピンアレイの構成
スピンアレイ１１０は、１個のスピンとそれに付随する相互作用係数、及び、外部磁場係数の保持と、基底状態探索処理を実現するスピンユニット３００を基本構成単位として、スピンユニット３００を多数個並べて構成する。図５はスピンユニット３００を複数個並べることで、３次元格子状のトポロジを持つイジングモデルを構成する例を示している。図５の例は、３（Ｘ軸方向）×３（Ｙ軸方向）×２（Ｚ軸方向）の大きさの３次元格子である。座標軸の定義は図示した通り、図面右方向をＸ軸、図面下方向をＹ軸、図面奥行き方向をＺ軸としているが、この座標軸は実施例の説明上便宜的に必要なだけであり、発明とは関係しない。３次元格子以外のトポロジ、例えばツリー状のトポロジなどを利用する場合には、座標軸とは別にツリーの段数等で表現することになる。図５の３次元格子状のトポロジにおいて、スピン間の相互作用をグラフとしてとらえると、最大で次数５のスピン（頂点）が必要となる。なお、外部磁場係数の接続も含めて考えると、最大で次数６が必要となる。【００３９】
図５に示す１個のスピンユニット３００は隣接するスピン（例えば隣接するスピンが５個の場合）σj，σｋ，σｌ，σｍ，σｎの値が入力される。また、スピンユニット３００はスピンσｉと外部磁場係数ｈｉに加え、前記した隣接するスピンとの相互作用係数であるＪj,i，Ｊk,i，Ｊl,i，Ｊm,i，Ｊn,i（隣接する５スピンとの相互作用係数）を保持するメモリセルを有している。【００４０】
ところで、イジングモデルは一般的に無向グラフで表現される相互作用を有している。前記した数１では、相互作用を表わす項として、Ｊi,j×σｉ×σｊがあるが、これはｉ番目スピンからｊ番目スピンへの相互作用を示している。この時、一般的なイジングモデルではｉ番目スピンからｊ番目スピンへの相互作用と、ｊ番目スピンからｉ番目スピンへの相互作用を区別することはない。つまり、Ｊi,jとＪj,iは同一である。しかし、本発明のイジングチップ１００では、このイジングモデルを有向グラフに拡張し、ｉ番目スピンからｊ番目スピンへの相互作用と、ｊ番目スピンからｉ番目スピンへの相互作用を非対称にすることを実現している。これにより、モデルの表現能力が高まり、多くの問題をより小規模のモデルで表現することが可能になる。【００４１】
そのため、１個のスピンユニット３００をｉ番目スピンσｉと考えた時に、このスピンユニットが保持する相互作用係数であるＪj,i，Ｊk,i，Ｊl,i，Ｊm,i，Ｊn,iは、隣接するｊ番目、ｋ番目、ｌ番目、ｍ番目、ｎ番目のスピンσj，σｋ，σｌ，σｍ，σｎから、ｉ番目スピンσｉへの相互作用を決めるものである。このことは、図５において、スピンユニット３００に含まれている相互作用係数が対応する矢印（相互作用）が、図示されているスピンユニット３００の外部のスピンから、スピンユニット３００の内部のスピンに向かっていることに対応している。【００４２】
（６）スピンユニットの構成
スピンユニット３００の構成の一例を図３と図４を用いて説明する。スピンユニット３００は２つの側面をもっており、便宜上、図３と図４に分けて説明するが、１個のスピンユニット３００に図３と図４の構成の双方が含まれるものである。図３はスピンユニット間の相互作用を実現するための回路を図示し、図４はスピンユニットが有するメモリセルにイジングチップ１００外からアクセスするためのインタフェースであるワード線とビット線に注目して図示したものである。なお、図３の相互作用を実現するための回路において図示されているインタフェースであるＥＮ，ＮＵ，ＮＬ，ＮＲ，ＮＤ，ＮＦ，Ｎを、複数のスピンユニット間でどのように結線するかについては、後に図１０及び図２５を参照して説明する。また、図４のワード線及びビット線を複数のスピンユニット間でどのように結線するかについては、後に図９を参照して説明する。【００４３】
スピンユニット３００は、イジングモデルのスピンσｉ、相互作用係数Ｊj,i、……Ｊn,iおよび、外部磁場係数ｈｉを保持するために、１ビットのメモリセルを複数個備えている。この１ビットのメモリセルは図中に、Ｎ，ＩＳ０，ＩＳ１，ＩＵ０，ＩＵ１，ＩＬ０，ＩＬ１，ＩＲ０，ＩＲ１，ＩＤ０，ＩＤ１，ＩＦ０，ＩＦ１として図示されているものである。なお、ＩＳ０とＩＳ１、ＩＵ０とＩＵ１、ＩＬ０とＩＬ１、ＩＲ０とＩＲ１、ＩＤ０とＩＤ１、および、ＩＦ０とＩＦ１はそれぞれ２個１組で役割を果たすものであるため、それぞれまとめてＩＳｘ，ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ，および、ＩＦｘと略記する。【００４４】
スピンユニット３００が有する各メモリセルの構造の一例を図１９のメモリセル１９００に示す。メモリセル１９００はＣＭＯＳインバータ２個で構成されるデータ保持部１９６０を有し、パスゲートトランジスタ１９５０をワード線１９２０及びビット線１９３０で制御することで、データ保持部１９６０へのデータ読み書きを実現する。
ここで、スピンユニット３００はｉ番目のスピンを表現するものとして説明を行う。メモリセルＮはスピンσｉを表現するためのメモリセルでありスピンの値を保持する。スピンの値はイジングモデルでは＋１／−１（＋１を上、−１を下とも表現する）であるが、これをメモリセルの２値である０／１に対応させる。例えば、＋１を１、−１を０に対応させる。【００４５】
図２８を用いて、スピンユニット３００が有するメモリセルと、図５に示したイジングモデルのトポロジとの対応関係を示す。ＩＳｘは外部磁場係数を表現する。また、ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ，ＩＦｘはそれぞれ相互作用係数を表現する。ＩＵｘは上側のスピン（Ｙ軸方向で−１）、ＩＬｘは左側のスピン（Ｘ軸方向で−１）、ＩＲｘは右側のスピン（Ｘ軸方向で＋１）、ＩＤｘは下側のスピン（Ｙ軸方向で＋１）、ＩＦｘは奥行き方向に接続するスピン（Ｚ軸方向で＋１ないしは−１）との相互作用係数を示している。また、イジングモデルを有向グラフとして捉えた場合に、あるスピンから見ると他のスピンが自スピンに及ぼす影響の係数を持つことになる。自スピンが他のスピンに与える影響の係数は、それぞれの他のスピンに属する。すなわち、このスピンユニット３００は最大で５個のスピンと接続される。本実施例のイジングチップ１００では、外部磁場係数、及び、相互作用係数として＋１／０／−１の３値に対応する。そのため、外部磁場係数、および、相互作用係数を表わすためには、それぞれ２ビットのメモリセルが必要となる。ＩＳｘ，ＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ，ＩＦｘは、末尾の数字が０と１の２つのメモリセル（例えばＩＳｘの場合にはＩＳ０とＩＳ１）の組合せで、＋１／０／−１の３値を表現する。例えば、ＩＳｘの場合には、ＩＳ１で＋１／−１を表現し、ＩＳ１が１の時は＋１，０の時には−１を表現する。これに加えて、ＩＳ０が０の時には外部磁場係数を０と見なし、ＩＳ０が１の時にはＩＳ１で決まる＋１／−１のいずれかを外部磁場係数とする。外部磁場係数が０の時は外部磁場係数をディセーブルしていると考えれば、ＩＳ０は外部磁場係数のイネーブルビットであると言うことができる（ＩＳ０＝１の時に、外部磁場係数がイネーブルされる）。相互作用係数を表現するＩＵｘ，ＩＬｘ，ＩＲｘ，ＩＤｘ，ＩＦｘも同様に係数とビットの値を対応させている。【００４６】
スピンユニット３００内のメモリセルＮ，ＩＳ０，ＩＳ１，ＩＵ０，ＩＵ１，ＩＬ０，ＩＬ１，ＩＲ０，ＩＲ１，ＩＤ０，ＩＤ１，ＩＦ０，ＩＦ１は、それぞれイジングチップ１００の外部からリード／ライト可能でなければならない。そのために、図４に示すようにスピンユニット３００はビット線４１０とワード線４２０をそれぞれ有している。スピンユニット３００を半導体基板上にタイル状に並べてビット線４１０とワード線４２０を接続し、Ｉ／Ｏアドレスデコーダ１３０とＩ／Ｏドライバ１２０で駆動、制御、読み出しすることで、一般的なＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）と同様にスピンユニット３００内のメモリセルをイジングチップ１００のＳＲＡＭ互換インタフェース１５０でリード／ライトすることが出来る。よって、イジングチップ１００のメモリマップを書くことができ、図５に示した３×３×２の３次元格子イジングモデルのイジングチップ１００のメモリマップを図２０のメモリマップ２０００に示す。なお、Ｎ０００やＮ００１という符号はスピンユニットの座標を示しており、Ｎに引き続き、Ｘ軸方向の座標、Ｙ軸方向の座標、Ｚ軸方向の座標を示している。例えば、図５でスピンユニット３００と図示されているスピンユニット（３次元格子前面の真ん中にあるスピンユニット）は、Ｎ１１０と表現される。【００４７】
（７）スピンアレイ内のスピンユニット配置
スピンアレイ１１０の構成を、半導体装置としてのレイアウトの観点から図９で説明する。本実施例のスピンアレイ１１０は図５に示したように３次元格子のトポロジを持つため、２次元平面上に回路を構成する半導体装置として実現するためには、レイアウト上の工夫が必要となる。そこで、図９に示すような配置を取る。なお、図９上で表現されているスピンユニット３００（ＮｘｙｚというようにＸ軸、Ｙ軸、Ｚ軸上の位置によって符号を付与している）が、３次元格子のトポロジでどの頂点に対応するかを図８で示す。３×３×２の３次元格子頂点を２次元平面上に配置するために、Ｘ軸方向の格子頂点配列の間隔にＺ軸方向の格子頂点配列の各格子頂点を挿入するように配置している。すなわち、図９の２次元平面上でのＹ軸方向（図面下側がＹ軸正の方向）にはＮｘ０ｚ，Ｎｘ１ｚ，Ｎｘ２ｚというように配置されるが、Ｘ軸方向（図面右側がＸ軸正の方向）にはＮ０ｙ０，Ｎ０ｙ１，Ｎ１ｙ０，Ｎ１ｙ１，Ｎ２ｙ０，Ｎ２ｙ１というように、Ｚ軸方向座標が０と１のスピンユニットが交互に配置される。【００４８】
イジングチップ１００上には物理的にはスピンユニット３００を図９に示すように配置し、その上に図９に示すようなワード線９０１−１，９０１−２，９０１−３と、ビット線９０２−１，９０２−２，９０２−３，９０２−４，９０２−５，９０２−６を配線する。これらのワード線、ビット線は図４に示したスピンユニット３００のワード線４２０とビット線４１０に結線される。各スピンユニットはワード線の配列方向に１３個のメモリセルを有する（ワード線４２０は１３ビット）ので、ワード線９０１−１，９０１−２，９０１−３はそれぞれ１３ビットとなる。【００４９】
（８）イジングモデルの基底状態探索処理の制御
イジングモデルの基底状態探索を実現するためには、イジングモデル全体のエネルギーがより低いスピン配列になるように遷移していくように、スピン間の相互作用を実現しなければならない。このための相互作用は、与えられた相互作用係数と外部磁場係数に基づいて行われる。つまり、あるスピンの次の値を、そのスピンに接続されている他のスピンからの相互作用と、そのスピンが持つ外部磁場係数から決定する。このとき、スピンの次の値は、そのスピンが接続されている範囲内での局所的なエネルギーを最小化するような値になる。【００５０】
このスピンの更新は、それぞれのスピンを１個ずつ逐次的に更新することがまず考えられるが、この方法ではスピン数に比例した時間がかかってしまい、並列性を利用することが出来ない。そこで、スピン間の相互作用を全てのスピンについて同時並行的に行うことが望ましい。【００５１】
しかし、全てのスピンを同時に更新しようとすると、あるスピンを更新するときに、隣接スピンの値を見て、隣接スピンとの間でエネルギーを最小化するようにスピンを更新するので、それと同時に隣接スピンの値を更新すると、両方の更新が重複してしまい、エネルギーを最小化できず振動してしまう。すなわち、あるスピンを更新するときに、そのスピンに接続されているスピン（あるスピンに相互作用係数を介して直接接続されているスピンをこれ以降隣接スピンと呼ぶ）を同時に更新することはできない。【００５２】
そこで、本発明では隣接スピンは同時に更新しないように、スピンアレイ１１０内のスピンユニット３００をグループ分けして、一度に同時に更新するのは１つのグループだけにする。図５に示すようなトポロジであれば、２グループに分ければ良い。そして、この２グループを交互に更新していくわけである。あるタイミングで更新するグループを指示するために、イジングチップ１００は相互作用アドレス１８０を入力インタフェースとして有する。相互作用アドレス１８０は前述したグループのうち、更新するグループを指定するためのインタフェースであり、相互作用クロック１８１の入力によって、相互作用アドレス１８０で指定されるグループに属するスピン（スピンユニット３００）が同時に更新される。【００５３】
この方法であれば、スピンユニット３００内に追加のハードウェアは必要なく、イジングチップ１００全体に対して一組の相互作用アドレスデコーダ１４０を設けるだけで良い。そのため、構成単位であるスピンユニット３００を複雑化することなく、前記の問題が解決できる。【００５４】
前記グループ分けについて、図２５を用いて説明する。図２５ではスピンユニットＮｘｙzがそれぞれグループＡとグループＢの２グループにグループ分けされている。各スピンユニット３００は後述するように、スピンの更新を許可する信号を入力するインタフェース（ＥＮ）を有する。そこで、相互作用アドレス１８０で指定されるアドレス（グループの識別子）を相互作用アドレスデコーダ１４０でデコードし、グループ毎の更新許可信号を生成する。図２５の例では、グループＡ指定信号２５１０、及び、グループＢ指定信号２５２０がグループ毎の更新許可信号である。そして、相互作用クロック１８１でその時に更新が許可されているグループに属するスピンユニットの更新が行われる。なお、図２５に示すグループ分けによって、図５のトポロジで隣接スピンが必ず異なるグループになっていることは、図２６によって容易に分かる。【００５５】
また、スピンユニット３００のグループ分けは前述した同時更新の衝突回避に加えて、消費電力の都合からさらに細分化してもよい。例えば前述した例では２グループに分ければ更新の衝突を回避できるが、同時に全てのスピンを更新しようとすると電力消費が問題になる場合には、例えば１つのグループをさらに細かく分割してもよい。例えば、２グループ分けにおいて、１つのグループを消費電力都合で４分割して、合計８グループに分ける。【００５６】
（９）スピンユニット内に備えた次のスピンの状態を決定するための回路構成  
スピンユニット３００は同時に更新を行うために、相互作用を計算して次のスピンの状態を決定するための回路を、スピンユニット毎に独立して持っている。スピンの次状態を決定するための回路を図３に示す。図３ではスピンユニットは外部とのインタフェースとして、ＥＮ，ＮＵ，ＮＬ，ＮＲ，ＮＤ，ＮＦ，Ｎを有する。ＥＮは当該スピンユニットのスピンの更新を許可する信号を入力するインタフェースである。Ｎは当該スピンユニットのスピンの値を他のスピンユニット（図５のトポロジで隣接するユニット）に出力するインタフェースである。ＮＵ，ＮＬ，ＮＲ，ＮＤ，ＮＦはそれぞれ他のスピンユニット（図５のトポロジで隣接するユニット）の有するスピンの値を入力するためのインタフェースである。ＮＵは上側のスピン（Ｙ軸方向で−１）、ＮＬは左側のスピン（Ｘ軸方向で−１）、ＮＲは右側のスピン（Ｘ軸方向で＋１）、ＮＤは下側のスピン（Ｙ軸方向で＋１）、ＮＦは奥行き方向に接続するスピン（Ｚ軸方向で＋１ないしは−１）からの入力である。なお、イジングモデルのトポロジを考える上で、端の処理を決める必要がある。図５のトポロジのように単に端は打ち切るのであれば、ＮＵ，ＮＬ，ＮＲ，ＮＤ，ＮＦのうち端に対するものは何も入力しなくて良い（回路上は０ないしは１の固定値に接続するなど、未使用入力端子として適切な処理をとる）。例えばＮ０００のスピンユニットの場合には、ＮＵ及びＮＬの２端子は入力が無い。【００５７】
スピンユニット３００では隣接スピンとの間でエネルギーを最小化するようにスピンの次状態を決定するが、それは隣接スピンと相互作用係数の積、及び、外部磁場係数を見た時に、正の値と負の値のどちらが支配的か判断することと等価である。例えば、ｉ番目スピンσｉに、スピンσj，σｋ，σｌ，σｍ，σｎが隣接しているとして、スピンσｉの次状態は以下のように決まる。まず、隣接スピンの値はσj＝＋１，σｋ＝−１，σｌ＝＋１，σｍ＝−１，σｎ＝＋１とし、相互作用係数はＪj,i＝＋１，Ｊk,i＝＋１，Ｊl,i＝＋１，Ｊm,i＝−１，Ｊn,i＝−１、外部磁場係数ｈｉ＝＋１とする。このとき、相互作用係数と隣接スピンの積、及び、外部磁場係数をそれぞれ並べると、σj×Ｊj,i＝＋１，σｋ×Ｊk,i＝−１，σｌ×Ｊl,i＝＋１，σｍ×Ｊm,i＝＋１，σｎ×Ｊn,i＝−１，ｈｉ＝＋１となる。外部磁場係数は、常に値が＋１のスピンとの相互作用係数と読み替えて良い。【００５８】
ここで、ｉ番目のスピンと隣接スピンとの間での局所的なエネルギーは、前述した係数にそれぞれｉ番目スピンの値を乗じて、さらに符号を反転させたものになる。例えば、ｊ番目スピンとの間での局所的なエネルギーは、ｉ番目スピンを＋１とした時には−１、ｉ番目スピンを−１としたときには＋１となるので、ｉ番目スピンを＋１にするほうが、ここでの局所的なエネルギーを小さくする方向に働く。このような局所的なエネルギーを全ての隣接スピン間と外部磁場係数について考えた時に、ｉ番目スピンを＋１／−１のどちらにしたほうがエネルギーを小さくできるかを計算する。これは、先程示した相互作用係数と隣接スピンの積、及び、外部磁場係数をそれぞれ並べたものにおいて、＋１と−１のどちらが多いか数えれば良い。先程の例では、＋１が４個、−１が２個である。仮に、ｉ番目スピンを＋１とするとエネルギーの総和は−２、ｉ番目スピンを−１とするとエネルギーの総和は＋２になる。よって、＋１の個数が多い時にはｉ番目スピンの次状態を＋１とし、−１の個数が多い時にはｉ番目スピンの次状態を−１にするという多数決で、エネルギーを最小化するｉ番目スピンの次状態を決定することが出来る。【００５９】
図３のスピンユニット３００に図示する論理回路は前記した相互作用を行うための回路である。まず、隣接スピンの状態と相互作用係数の＋１／−１を示すメモリセルとの排他的論理和の否定（ＸＮＯＲ）で、その相互作用だけを見た時にエネルギーを最小化するスピンの次状態を計算することができる（＋１は１、−１は０にエンコードされているものとする）。もし、相互作用係数が＋１／−１だけであれば、この出力のうち＋１／−１のどちらが多いか多数決論理で判定すればスピンの次状態を決定することができる。外部磁場係数に関しては、常に状態＋１のスピンとの相互作用係数に相当するものと考えれば、単に外部磁場係数の値がスピンの次状態を決定する多数決論理に入力すべき値となる。【００６０】
次に、係数０の実現方法について考える。ｎ入力の多数決論理ｆ（Ｉ１，Ｉ２，Ｉ３，．．．，Ｉｎ）があるとき、以下の命題は真であると言える。まず、入力Ｉ１，Ｉ２，Ｉ３，．．．，Ｉｎの複製Ｉ’１，Ｉ’２，Ｉ’３，．．．，Ｉ’ｎがあるとする（任意のｋについて、Ｉｋ＝Ｉ’ｋである）。このとき、ｆ（Ｉ１，Ｉ２，Ｉ３，．．．，Ｉｎ）の出力は、複製もあわせて入力したｆ（Ｉ１，Ｉ２，Ｉ３，．．．，Ｉｎ，Ｉ’１，Ｉ’２，Ｉ’３，．．．，Ｉ’ｎ）と等しい。つまり、各入力変数をそれぞれ２個ずつ入れても、出力は不変である。さらに、入力Ｉ１，Ｉ２，Ｉ３，．．．，Ｉｎの他に、もう一つの入力Ｉｘと、その反転！Ｉｘがあるとする。このとき、ｆ（Ｉ１，Ｉ２，Ｉ３，．．．，Ｉｎ，Ｉｘ，！Ｉｘ）の出力は、ｆ（Ｉ１，Ｉ２，Ｉ３，．．．，Ｉｎ）と等しい。つまり、入力変数とその反転を入力すると、多数決においてその入力変数の影響をキャンセルするように働く。多数決論理のこの性質を利用して係数０を実現する。具体的には、図３に示すように、ＸＯＲを利用して、係数のイネーブルを決めるビット（ＩＳ０など）の値により、多数決論理に、先に述べたスピン次状態の候補となる値の複製か、その反転を同時に入力する。例えば、ＩＳ０が０の場合、ＩＳ１の値と、ＩＳ１の反転の値が同時に多数決論理に入力されるので、外部磁場係数の影響は無い（外部磁場係数が０に相当する）ことになる。また、ＩＳ０が１の場合には、ＩＳ１の値と、その値と同じ値（複製）が同時に多数決論理に入力されることになる。【００６１】
（１０）イジングモデルの基底状態探索における局所最適解の回避手段
前述したスピン間の相互作用によるエネルギー最小化で、適用されたイジングモデルの基底状態探索を実現することが出来るが、これだけでは局所最適解に陥ってしまう可能性がある。基本的に、エネルギーを小さくする方向の動きしかないため、一旦局所最適解に陥るとそこから抜け出すことが出来ず、大域最適解に到達しない。そのため、局所最適解から脱出するための作用として、スピンを表現するメモリセルに供給する電源電圧を下げることで、メモリセルのビットエラーを誘発することで、スピン配列をランダムに変化させる。そのため、スピンユニット３００が有するメモリセルＮ，ＩＳ０，ＩＳ１，ＩＵ０，ＩＵ１，ＩＬ０，ＩＬ１，ＩＲ０，ＩＲ１，ＩＤ０，ＩＤ１，ＩＦ０，ＩＦ１のうち、係数を保持するメモリセルＩＳ０，ＩＳ１，ＩＵ０，ＩＵ１，ＩＬ０，ＩＬ１，ＩＲ０，ＩＲ１，ＩＤ０，ＩＤ１，ＩＦ０，ＩＦ１は通常電源線１４２で供給する電圧で動作するが、スピンを表現するメモリセルＮはスピン用電源線１４１で供給する電圧で動作する。なお、メモリセル以外の構成要素、例えば相互作用を計算するための論理ゲート等は全て通常電源線１４２で供給する電圧で動作する。【００６２】
メモリセルのビットエラーレートはメモリセルへの供給電圧に比例しており、例えば１Ｖでは１０−９程度のビットエラーレートであり、このビットエラーレートは記憶内容を保持するというメモリ本来の目的に適したものである。よって、一般的にはメモリセルにこの程度の電圧を供給し、記憶内容の保持に適したビットエラーレートで用いる。前述したメモリセルＩＳ０，ＩＳ１，ＩＵ０，ＩＵ１，ＩＬ０，ＩＬ１，ＩＲ０，ＩＲ１，ＩＤ０，ＩＤ１，ＩＦ０，ＩＦ１は常にこの状態で用いる。この電圧から、さらに電圧を下げていくと、電圧の下げ幅に比例してビットエラーレートも悪化していく。例えば、０．６Ｖ程度まで電圧を下げることで、１０−１程度のビットエラーレートになり、このようなビットエラーが発生しやすい状態を、局所最適解からの脱出に用いる。そのため、前述したメモリセルＮは、例えば基底状態探索の初期では解空間をより広く探索することで局所最適解に陥らないようにするため、０．６Ｖなどの低い電源電圧をスピン用電源線１４１に供給して、ランダムなビットエラーが生じる状況で相互作用による基底状態探索を行う。この状況では、基本的には相互作用によってエネルギーが小さい状態に遷移していくが、それと並行してビットエラーにより、状態がランダムに遷移していくことで、相互作用だけでは遷移しえない状態への遷移も発生し、解空間を広く探索することができる。基底状態探索の進行と共に、状態を安定させていくために、ビットエラーレートが起こりにくい状態へと少しずつ電圧を変化させていく。つまり、最初はビットエラーレートが起こりやすい電圧である０．６Ｖが供給されていたところを、ビットエラーレートが起こりにくい１Ｖ程度に少しずつ近づけていく。このような供給電圧のスケジューリングと、相互作用によるエネルギー最小化を併用することで、局所最適解から脱出しつつ、大域最適解を目指す基底状態探索が実現できる。【００６３】
なお、メモリセルへの供給電圧によるランダムなビットエラーの発生に替わって、乱数発生回路を利用してランダムなビットエラーを模擬的に起こしても良い。この場合、スピンユニット３００内に乱数発生回路を設けても良いし、イジングチップ１００内に乱数発生回路を設けて各スピンユニットに乱数を配送して利用しても良い。また、イジングチップ１００の外に乱数発生回路を設けて、チップではチップ外からの乱数を配送するようにしても良い。【００６４】
（１１）スピンユニット間の配線
図３で示したスピンユニットのインタフェースである、ＥＮ，ＮＵ，ＮＬ，ＮＲ，ＮＤ，ＮＦ，Ｎについて、ＥＮの配線に関しては図２５で説明した通りだが、ＮＵ，ＮＬ，ＮＲ，ＮＤ，ＮＦ，Ｎの配線の例については図１０に示す。図１０は、ある１個のスピンユニットＮｘｙｚに注目した時に、図５に示すようなトポロジを図９のように配置したスピンユニットで実現するために必要な配線を示している。このような配線をスピンユニット毎に行うことで、図５のトポロジを実現することが出来る。【００６５】
（１２）イジングチップの制御手順１
このイジングチップ１００を組みこんだ情報処理装置２００において、イジングチップ１００をＣＰＵ２１０が制御して基底状態探索を行う手順を図６に示す。
ステップＳ６００において、対象問題を表現するイジングモデルの相互作用係数と外部磁場係数を生成する。これは、最大カット問題の例で言えば、図１３に示すような最大カット問題が与えられた時に、図１４に示すようなイジングモデルを生成することである。【００６６】
ステップＳ６０１において、スピン割当てマップを生成する。スピン割当てマップとは、解きたいイジングモデルをイジングチップ１００で解く際に、イジングチップ１００にどのようにイジングモデルを割当てるか定義した情報である。例として、図１４のイジングモデルを本実施例のイジングチップ１００に割当てる例を示す。図１４のイジングモデルは４個のスピンが全対全接続されている完全グラフである。これをイジングチップ１００が有する図５のような三次元格子に埋め込まなくてはならない。【００６７】
図１６に図１４のイジングモデルに対するスピン割当てマップを示す。図１６では相互作用係数が＋１ないしは−１の辺にはその旨図示し、値が付記されていない辺は相互作用係数０（接続されていないことと同義）である。図１６では図１４のイジングモデル（これ以降、元のイジングモデルと称する）のスピンＡ，Ｂ，Ｃ，Ｄをそれぞれスピンσ０００，σ１００，σ０１０，σ１１０に割当てている。なお、σｘｙｚというスピンはイジングチップ１００上ではＮｘｙｚで示されるスピンユニットが対応する。元のイジングモデルにある、ＪＡ，Ｂ（スピンＡ，Ｂ間の相互作用係数）、ＪＡ，Ｃ（スピンＡ，Ｃ間の相互作用係数）、ＪＢ，Ｄ（スピンＢ，Ｄ間の相互作用係数）、ＪＣ，Ｄ（スピンＣ，Ｄ間の相互作用係数）はイジングチップ上でも図１６に示すようにＺ軸方向の座標が０であるＸ−Ｙ平面を利用して表現することが出来る。ところが、元のイジングモデルで格子の対角線にあるＪＡ，Ｄ（スピンＡ，Ｄ間の相互作用係数）、ＪＢ，Ｃ（スピンＢ，Ｃ間の相互作用係数）を前記のＸ−Ｙ平面では表現することが出来ない。【００６８】
そこで、スピン割当てマップの生成では、コピースピンという概念を導入する。コピースピンとは、コピー元のスピンと連動して同じ値を取るスピンである。イジングモデルでは正の相互作用係数はスピンの値を揃える効果を持つことから、イジングチップ１００においては単に相互作用係数１でコピー元のスピンに接続することで、コピースピンを実現することが出来る。図１６ではＪＡ，Ｄを実現するために、スピンＤ（σ１１０）のコピースピンをスピンＡ（σ０００）に隣接するσ００１に用意する。スピンＤ（σ１１０）の値をσ００１まで伝搬させるために、σ１１０−σ１１１−σ１０１−σ００１間の相互作用係数は全て＋１とする。そして、σ０００−σ００１間に元のイジングモデルのＪＡ，Ｄ（この例の場合には−１）を設定する。同様に、ＪＢ，Ｃを実現するために、スピンＣ（σ０１０）をσ０２０−σ１２０−σ２２０−σ２１０−σ２００とコピーし、スピンＣのコピースピンであるσ２００とスピンＢ（σ１００）の間にＪＢ，Ｃ（この例の場合には＋１）を設定する。【００６９】
図１６のイジングモデルの基底状態探索を行うことで、元のイジングモデルの基底状態探索が出来ることを図１７、及び、図１８を用いて説明する。元のイジングモデルの基底状態は図１５の通りである。なお、前述したように、図１５のスピンを全て反転させたものも基底状態である。図１７、及び、図１８は図１６のイジングモデルの基底状態探索の結果、基底状態として求められるスピン配列の例である。なお、図１７、及び、図１８のスピンを全て反転させたものも基底状態であるが、これは図１５の反転の時の基底状態に対応する。【００７０】
図１７、及び、図１８のスピンＡ，Ｂ，Ｃ，Ｄに対応するσ０００，σ１００，σ０１０，σ１１０を見ると、図１５のスピンＡ，Ｂ，Ｃ，Ｄと同じ値が得られており、図１６のイジングモデルの基底状態探索を行うことで、図１５と同じ結果が得られることが確認できよう。なお、図１６で導入したコピースピンの値については、図１７と図１８で若干異なる。具体的にはスピンＣのコピースピンであるσ０２０−σ１２０−σ２２０−σ２１０−σ２００が図１７では全て−１であり、図１８では全て＋１である。これは、スピンＢとスピンＣは相互作用係数が＋１であり、この間の関係だけを見るとスピンＢとスピンＣは値がそろうはずであるが、他の相互作用の影響の方が大きく、いわばスピンＢとスピンＣ間の相互作用が負けている状態にある。コピースピン間の相互作用係数は全て＋１であるため、σ０２０−σ１２０−σ２２０−σ２１０−σ２００は全て同じ値になろうとする。そして、前述した通りスピンＢとスピンＣは他の相互作用の影響で値が決まっているため、コピースピンが＋１になっても−１になっても全体のエネルギーとしては変わらない。そのため、スピンＣのコピースピンが＋１になっている基底状態と−１になっている基底状態の２種類の基底状態が存在するのである。【００７１】
ステップＳ６０２において、スピン配列の初期値である初期スピン配列を生成する。初期スピン配列の生成は乱数でランダムにスピン配列を生成する。
ステップＳ６０３において、ステップＳ６００で得られた係数と、ステップＳ６０２で得られた初期スピン配列を、イジングチップ１００のメモリセルに書込む。この時、イジングチップ１００に書き込むデータを図２１にデータ２１００として示す。データ２１００でＮ／Ａとされている箇所は未使用のスピンなので値は問わない。ランダムとされている箇所はステップＳ６０２でランダムに生成された初期スピン配列である。それ以外の０／１の値が入っている箇所は、ステップＳ６００で得られた係数である。これで初期設定が完了する。【００７２】
その後、ステップＳ６０４において、相互作用アドレス１８０をイジングチップ１００に入力し、ステップＳ６０５において、相互作用クロック１８１を生成してイジングチップ１００内で相互作用を起こさせる。また、ステップＳ６０６において、スピン用電源線１４１に供給される電圧をスケジューリングに沿って制御する。このような制御を所定の回数繰り返して（ステップＳ６０７）、所定の回数が完了した後に、イジングチップ１００からスピン配列を読み出して答えを得る（ステップＳ６０８）。【００７３】
（１３）メモリセルの特性ばらつきに対処するイジングチップの制御手順２
ところで、前述したようにこのようなイジングチップ１００を製造すると、スピンアレイ１１０内のスピンユニット３００によって、メモリセルの特性にばらつきが生じる。ばらつきの原因は様々であるが、メモリセルを構成するトランジスタの強い閾値電圧（Ｖｔｈ）がばらつき、それによってメモリセルにおいて電源電圧を下げるなど不安定な状態にしたときに、０になりやすいか、１になりやすいかの個体差が生まれてくる。ばらつきの要因はＲＤＦ（Ｒａｎｄｏｍ  Ｄｏｐａｎｔ  Ｆｌｕｃｔｕａｔｉｏｎ）の様に製造時に固定的に決まるものもあれば、ＲＴＮ（Ｒａｎｄｏｍ  Ｔｅｌｅｇｒａｐｈ  Ｎｏｉｓｅ）の様に使用時に動的に変化するばらつきもある。いずれにしても、ばらつきがあるメモリセルは局所最適解から抜け出そうとしてメモリセルのランダム性を得ようとするときに、偏ったランダム性を生みだすことになり、その結果として探索できる解空間の範囲を狭めてしまう。【００７４】
そこで、本発明ではメモリセルのばらつきの影響に適応するために、図７に示す手順でイジングチップ１００を制御する。ステップＳ７０１はステップＳ６００と同様である。その次に、ステップＳ７０２において、スピン割当てマップを複数個（ｎ個）作成する。例えば、図１６に示したスピン割当てマップに加えて、図２３に示すスピン割当てマップの合計２個のスピン割当てマップを生成する。【００７５】
図２３に示すスピン割当てマップは、図１６と同様に図１４のイジングモデル（元のイジングモデル）と同等のイジングモデルになっている。しかし、図１６とは元のイジングモデルのスピンＡ，Ｂ，Ｃ，Ｄに対応するイジングチップ上のスピンユニットの割り当てが異なっており、図２３の例ではスピンＡ，Ｂ，Ｃ，Ｄにそれぞれスピンσ００１，σ１０１，σ０１１，σ１１１に割り当てられている。このように、元のイジングモデルのスピンに対応するスピンが異なる複数のスピン割当てマップを生成するのがステップＳ７０２の役割なのである。また、スピンの割当てが変わることで、それに付随してスピン間の相互作用係数の付け方、コピースピンの位置も変わってくる。【００７６】
その上で、ステップＳ６０２と同様に初期スピン配列をステップＳ７０３において、乱数でランダムに生成する。そして、ステップＳ７０４において、ステップＳ７０２で生成した複数のスピン割当てマップのうちの、１個のマップに従って、係数と初期スピン配列をイジングチップ１００に設定する。例えば、1個目のマップが図１６の場合には、図２１のデータ２１００をイジングチップ１００に書き込む。【００７７】
その後、ステップＳ７０５〜Ｓ７０７では、ステップＳ６０４〜Ｓ６０６と同様に相互作用を行わせるための相互作用クロック及び相互作用アドレスの制御と、メモリセルをランダムに変化させるためのスピン用電源電圧の制御を行う。ここで、所定の回数を実行した後に（ステップＳ７０８で判定）、ステップ７０９で一度スピン配列をイジングチップ１００から読み出して、情報処理装置２００のＲＡＭ２２０に退避する（読み出してＲＡＭ２２０上に置かれたスピン配列を以降では、途中スピン配列と呼ぶ）。【００７８】
この時にイジングチップ１００から読み出せるデータの例を図２２にデータ２２００として示す。データ２２００のうち、相互作用係数や外部磁場係数に対応する箇所は、ステップＳ７０４でイジングチップ１００に書き込んだ値（データ２１００）と変わらない。しかし、スピンの値はステップＳ７０５〜Ｓ７０８における基底状態探索の結果、変わっている。データ２２００中でＮ／Ａとしている箇所は未使用スピンなので読み出す必要はない。また、ｔｍｐ１，ｔｍｐ２，ｔｍｐ３，ｔｍｐ４，ｔｍｐ５，ｔｍｐ６，ｔｍｐ７，ｔｍｐ８（これ以降、総称してｔｍｐＸと称する）は、コピースピンとして使用されている箇所なので読み出さなくて良い。ステップＳ７０９において、データ２２００中でＡ，Ｂ，Ｃ，Ｄとされている箇所、すなわち元のイジングモデルのスピンＡ，Ｂ，Ｃ，Ｄが割り当てられているスピンの値(該当メモリ箇所を点線の丸で囲む。)だけ読み出せばよい。【００７９】
途中スピン配列を読み出した後、ステップＳ７１０では今まで使ってきたスピン割当てマップとは異なるマップを使って、係数と途中スピン配列をイジングチップ１１０に書込む。これによって、先程とは異なるスピンユニット３００がスピンに割当てられるため、スピンユニット３００のばらつきによる影響が平均化する。この動作を繰り返していくことで、スピンとスピンユニット３００の対応関係を途中で変えながら基底状態探索を実行し、スピンユニット３００のばらつきによる影響が特定のスピンに留まってしまう（例えば、特定のスピンの値は＋１にしかならない）ことなく、ばらつきに適応して基底状態探索を実現することができる。【００８０】
例えば、次に使うスピン割当てマップ(i=i+1)を図２３とする。そして、ステップＳ７０９でスピンＡ，Ｂ，Ｃ，Ｄの途中の値を読み出してある。そこで、図２４のデータ２４００に示すようなデータをイジングチップ１００に書き込む。Ｎ／Ａという箇所は未使用スピンであり、値は任意である。データ２４００の相互作用係数、外部磁場係数は図２３のスピン割当てマップから生成されたものである。そして、スピンＡ，Ｂ，Ｃ，Ｄの値を図２３のマップに対応して当てはめている。つまり、図２３ではσ００１，σ１０１，σ０１１，σ１１１がそれぞれスピンＡ，Ｂ，Ｃ，Ｄに対応しているので、ステップＳ７０９で読み出したスピンＡ，Ｂ,Ｃ，Ｄの値を書き込む(該当メモリ箇所を点線の丸で囲む。)。そして、σ０２１−σ１２１−σ２２１−σ２１１−σ２０１はスピンＣのコピースピンであることからスピンＣの値を、σ１１０−σ１００−σ０００はスピンＤのコピースピンであることからスピンＤの値を、それぞれ書き込む。これにより、図１６のスピン割当てマップで途中まで基底状態探索を行った結果を引き継ぎ、今度は図２３のスピン割当てマップに基づいて基底状態探索を行うことが出来る。【００８１】
そして、ステップＳ７１１で終了条件（所定の回数の実行完了、及びステップＳ７０２で作成した全てのスピン割当てマップに沿ってスピンの基底状態探索処理を実行完了）を満たしたことを判定した後に、ステップＳ７１２でスピン配列を読み出して終了する。終了条件を満たしていない時には、ステップＳ７０５〜Ｓ７１１を繰り返す。
すなわち、本発明では、基底状態探索の途中で、対象問題のイジングモデルのスピンと、イジングチップ１００上のスピンユニット３００の対応関係を変えながら基底状態探索を行う。スピンとスピンユニットの対応関係を変えるためには、途中のスピン配列を一時的に保存して、別のスピンユニット３００に係数と共に書込み直さなければならない。これを前述した図７の動作で実現し、それによってスピンユニット３００の製造ばらつきに適応したイジングチップ１００を実現するものである。【００８２】
図７に示す手順でイジングチップ１００を制御するときのタイムチャートを図２７に示す。
まず、初期設定フェーズではステップＳ７０４に対応する動作が行われる。この時、ＳＲＡＭ互換インタフェース１５０を制御して、データ２１００の書き込みを行う。なお、スピン用電源線１４１に供給する電圧は、メモリセルの記憶を保持するために十分な電圧とする。
その後、基底状態探索フェーズ１ではステップＳ７０５〜Ｓ７０８に対応する動作が行われる。この時、相互作用制御インタフェース１６０を制御して、グループＡとグループＢの相互作用を交互に行う。それと並行して、スピン用電源線１４１に供給する電源電圧を徐々に下げていく。これによって、基底状態探索が行われる。【００８３】
基底状態探索の途中で、イジングチップ１００のスピンユニット３００と解くべきイジングモデルのスピンとの対応関係を変える再配置フェーズがある。再配置フェーズはステップＳ７０９〜Ｓ７１０に対応する。再配置フェーズに入る時に、基底状態探索の間下げていたスピン用電源線１４１の電源電圧を元に戻す。これは、再配置フェーズではスピンを表現するメモリセルへの読み書きを行うため、通常のメモリと同等の振る舞いをさせるためである。再配置フェーズでは、スピンの値を一旦読出し（データ２２００の読出し）、他のスピン割当てマップに基づいて生成した新しいデータ（データ２４００）を書き込む。
その後、基底状態探索フェーズ２では、基底状態探索フェーズ１と同様の制御で基底状態探索を続ける。この時、スピン用電源線１４１の電圧は基底状態探索フェーズ１終了時の電圧値を引き継いでも良いし、初期の電圧（メモリセルの記憶を保持するために十分な電圧）からやり直しても良い。【００８４】
最後に結果読出フェーズで、基底状態探索完了後のスピンの値を読み出す（ステップＳ７１２に対応する）。以上の動作によって、本発明のイジングチップ１００は与えられたイジングモデル（例えば図１４）の基底状態を探索し、図１４の問題に対して図１５のような答え（基底状態のスピン配列）を得ることができる。
【符号の説明】
【００８５】
１００，１００−１，１００−２  イジングチップ
１１０  スピンアレイ
１２０  Ｉ／Ｏドライバ
１３０  Ｉ／Ｏアドレスデコーダ
１４０  相互作用アドレスデコーダ
１４１  スピン用電源線
１４２  通常電源線
１５０  ＳＲＡＭ互換インタフェース
１６０  相互作用制御インタフェース
１８０  相互作用アドレス
１８１  相互作用クロック
１９０  アドレスバス(ＳＲＡＭ互換インタフェース)
１９１  データバス(ＳＲＡＭ互換インタフェース)
１９２  Ｉ／Ｏクロック(ＳＲＡＭ互換インタフェース)
１９３  Ｒ／Ｗ制御線(ＳＲＡＭ互換インタフェース)
２００  情報処理装置
２１０  ＣＰＵ
２２０  ＲＡＭ
２３０  システムバス
２４０  ＮＩＣ
２５０  イジングチップコントローラ
２６０  ＨＤＤ
２９０  装置間ネットワーク
３００  スピンユニット
４１０，９０２，１９３０  ビット線
４２０，９０１，１９２０  ワード線
１９００  メモリセル
１９５０  パスゲートトランジスタ
１９６０  データ保持部
Ｎ  スピンを表現するメモリセル、及び、スピンの値を出力するインタフェース
ＩＳ０  外部磁場係数が０であるかどうかを示すメモリセル
ＩＳ１  外部磁場係数の＋１／−１を示すメモリセル
ＩＵ０，ＩＬ０，ＩＲ０，ＩＤ０，ＩＦ０  相互作用係数が０であるかどうかを示すメモリセル
ＩＵ１，ＩＬ１，ＩＲ１，ＩＤ１，ＩＦ１  相互作用係数の＋１／−１を示すメモリセル
【図１】
2015132883.tif 000005
【図２】
2015132883.tif 000006
【図３】
2015132883.tif 000007
【図４】
2015132883.tif 000008
【図５】
2015132883.tif 000009
【図６】
2015132883.tif 000010
【図７】
2015132883.tif 000011
【図８】
2015132883.tif 000012
【図９】
2015132883.tif 000013
【図１０】
2015132883.tif 000014
【図１１】
2015132883.tif 000015
【図１２】
2015132883.tif 000016
【図１３】
2015132883.tif 000017
【図１４】
2015132883.tif 000018
【図１５】
2015132883.tif 000019
【図１６】
2015132883.tif 000020
【図１７】
2015132883.tif 000021
【図１８】
2015132883.tif 000022
【図１９】
2015132883.tif 000023
【図２０】
2015132883.tif 000024
【図２１】
2015132883.tif 000025
【図２２】
2015132883.tif 000026
【図２３】
2015132883.tif 000027
【図２４】
2015132883.tif 000028
【図２５】
2015132883.tif 000029
【図２６】
2015132883.tif 000030
【図２７】
2015132883.tif 000031
【図２８】
2015132883.tif 000032
【国際調査報告】
2015132883.tif 000033
2015132883.tif 000034
2015132883.tif 000035
2015132883.tif 000036