(57)【特許請求の範囲】
【請求項１】
情報処理装置であって、
メモリと、１つ又は複数のプロセッサとを含み、
前記１つ又は複数のプロセッサが、
グラフに含まれる複数の頂点を複数のスピンに対応させ、前記グラフに含まれる複数のエッジの重みを前記複数のスピン間の相互作用に対応させるように、前記複数のスピンのハミルトニアンをアニーリングマシンに設定し、
前記アニーリングマシンにより算出された、前記ハミルトニアンの固有状態となる前記複数のスピンの配列を取得し、
前記配列が棄却条件を満たす場合、前記配列を棄却し、
前記配列が前記棄却条件を満たさない場合、前記配列に基づいて、前記グラフの最小カットを算出し、
前記棄却条件は、前記配列が自明解に対応する基底状態であることである、
情報処理装置。
【請求項２】
前記棄却条件は、前記配列が全て同じ値であることを含む、
請求項１に記載の情報処理装置。
【請求項３】
前記配列が前記棄却条件を満たさない場合、前記配列の固有エネルギーに基づいて、前記グラフの最小カット数を算出する、
請求項１又は２に記載の情報処理装置。
【請求項４】
前記アニーリングマシンにより、前記ハミルトニアンの前記基底状態又は第１励起状態となる前記配列を算出させる、
請求項１から３のいずれか一項に記載の情報処理装置。
【請求項５】
メモリと、１つ又は複数のプロセッサとを含む情報処理装置が実行する情報処理方法であって、
前記１つ又は複数のプロセッサが、
グラフに含まれる複数の頂点を複数のスピンに対応させ、前記グラフに含まれる複数のエッジの重みを前記複数のスピン間の相互作用に対応させるように、前記複数のスピンのハミルトニアンをアニーリングマシンに設定し、
前記アニーリングマシンにより算出された、前記ハミルトニアンの固有状態となる前記複数のスピンの配列を取得し、
前記配列が自明解に対応する基底状態であることである棄却条件を、前記配列が満たす場合、前記配列を棄却し、
前記配列が前記棄却条件を満たさない場合、前記配列に基づいて、前記グラフの最小カットを算出する、
情報処理方法。
【請求項６】
メモリと、１つ又は複数のプロセッサとを含む情報処理装置の前記１つ又は複数のプロセッサに、
グラフに含まれる複数の頂点を複数のスピンに対応させ、前記グラフに含まれる複数のエッジの重みを前記複数のスピン間の相互作用に対応させるように、前記複数のスピンのハミルトニアンをアニーリングマシンに設定し、
前記アニーリングマシンにより算出された、前記ハミルトニアンの固有状態となる前記複数のスピンの配列を取得し、
前記配列が自明解に対応する基底状態であることである棄却条件を、前記配列が満たす場合、前記配列を棄却し、
前記配列が前記棄却条件を満たさない場合、前記配列に基づいて、前記グラフの最小カットを算出する、
処理を実行させる、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、情報処理装置、情報処理方法及びプログラムに関する。
【背景技術】
【０００２】
従来、ネットワークの堅牢性を確認したり、最大フローを確認したりするために、ネットワークのグラフの最小カットを求めることがある。グラフの最小カットを求めるアルゴリズムは複数知られている。
【０００３】
例えば、下記非特許文献１には、解の精度が保証されないが、Ｏ（｜Ｖ｜＋｜Ｅ｜）の計算量で最小カットに近いグラフの二分割を求めるアルゴリズムが記載されている。ここで、｜Ｖ｜はグラフに含まれる頂点の数であり、｜Ｅ｜はグラフに含まれるエッジの数である。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】M. Henzinger, A. Noe, C. Schulz, and D. Strash, “Practicalminimum cut algorithms," Journal of Experimental Algorithmics (JEA), vol.23, no.1, pp.1-8, 2018.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
既存のアルゴリズムによってグラフの最小カットを求めることができるが、グラフの規模が大きくなるほど計算時間が長くなる。
【０００６】
近年、量子アニーリングマシン等のアニーリングマシンが用いられ始めており、最小カット問題を含む組み合わせ最適化問題の求解に応用されている。
【０００７】
本開示は、アニーリングマシンによって、グラフの最小カットをより高速に求めることができる情報処理装置、情報処理方法及びプログラムを提供することを目的の一つとする。
【課題を解決するための手段】
【０００８】
本開示の一実施形態に係る情報処理装置は、メモリと、１つ又は複数のプロセッサとを含み、１つ又は複数のプロセッサが、グラフに含まれる複数の頂点を複数のスピンに対応させ、グラフに含まれる複数のエッジの重みを複数のスピン間の相互作用に対応させるように、複数のスピンのハミルトニアンをアニーリングマシンに設定し、アニーリングマシンにより算出された、ハミルトニアンの固有状態となる複数のスピンの配列を取得し、配列が棄却条件を満たす場合、配列を棄却し、配列が棄却条件を満たさない場合、配列に基づいて、グラフの最小カットを算出する。
【発明の効果】
【０００９】
開示の技術によれば、アニーリングマシンによって、グラフの最小カットをより高速に求めることができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施形態に係る情報処理装置のハードウェア構成の一例を示す図である。
【図２】本実施形態に係る情報処理装置に記憶されるグラフ情報の一例を示す図である。
【図３】本実施形態に係る情報処理装置により実行される処理のフローチャートである。
【図４】本実施形態に係る情報処理装置による計算時間と、従来技術による計算時間とを示す図である。
【発明を実施するための形態】
【００１１】
以下、本開示の実施形態について図面を参照しつつ詳細に説明する。なお、同一の要素には同一の符号を付し、重複する説明を省略する。
【００１２】
本発明の実施形態では、複数の頂点と複数のエッジを含むグラフを２分割する場合に、カットするエッジの重みの合計を最小とするカット（最小カット）を、アニーリングマシンによって求める情報処理装置について説明する。
【００１３】
＜システムの適用例＞
図１は、本発明の実施形態に係る情報処理装置のハードウェア構成の一例を示す図である。本例では、情報処理装置の例として、第１ユーザが用いる第１情報処理装置５００Ａと、第２ユーザが用いる第２情報処理装置５００Ｂと、第３ユーザが用いる第３情報処理装置５００Ｃとを図示している。また、同図では、アニーリングマシン７００を図示している。本明細書では、第１情報処理装置５００Ａ、第２情報処理装置５００Ｂ及び第３情報処理装置５００Ｃ等のユーザが用いる情報処理装置を、クライアントコンピュータ５００と総称する。
【００１４】
＜構成の一例＞
クライアントコンピュータ５００は典型的には、１つ又は複数の処理装置（ＣＰＵ）５０２、１つ又は複数のネットワーク又は他の通信インタフェース５０６、メモリ５０４、及びこれらの構成要素を相互接続するための１つ又は複数の通信バス５１４を含む。
【００１５】
クライアントコンピュータ５００はまた、ディスプレイ装置５１０及び入力装置（キーボード及び／又はマウス、又は他の何らかのポインティングデバイス）５１２を備えるユーザインタフェース５０８も含み得る。入力装置５１２は、タッチパネルでもよい。
【００１６】
メモリ５０４は、例えば、ＤＲＡＭ、ＳＲＡＭ、ＤＤＲ ＲＡＭ又は他のランダムアクセス固体記憶装置などの高速ランダムアクセスメモリであり、また、１つ又は複数の磁気ディスク記憶装置、光ディスク記憶装置、フラッシュメモリデバイス、又は他の不揮発性固体記憶装置などの不揮発性メモリでもよい。
【００１７】
また、メモリ５０４の他の例として、ＣＰＵ５０２から遠隔に設置される１つ又は複数の記憶装置でもよい。ある実施形態において、メモリ５０４は次のプログラム、モジュール及びデータ構造、又はそれらのサブセットを格納する。
【００１８】
オペレーティングシステム５１６は、例えば、様々な基本的なシステムサービスを処理するとともにハードウェアを用いてタスクを実行するためのプロシージャを含む。
【００１９】
ネットワーク通信モジュール５１８は、例えば、クライアントコンピュータ５００を他のコンピュータに、１つ又は複数のネットワーク通信インタフェース５０６及び、インターネット、他の広域ネットワーク、ローカルエリアネットワーク、メトロポリタンエリアネットワークなどの１つ又は複数の通信ネットワーク１３０を介して接続するために使用される。
【００２０】
設定モジュール５２０は、グラフに含まれる複数の頂点を複数のスピンに対応させ、グラフに含まれる複数のエッジの重みを複数のスピン間の相互作用に対応させるように、複数のスピンのハミルトニアンをアニーリングマシン７００に設定する。設定モジュール５２０は、アニーリングマシンのハードウェア構成では設定不可能なグラフについて、設定不可能であることをユーザに通知してよい。
【００２１】
Ｎ個の頂点を（１〜Ｎ）と表し、対応してＮ個のスピンをｓi（ｉ＝１〜Ｎ）と表すとき、設定モジュール５２０は、ハミルトニアンＨ＝−（Σ(i,j)∈Eｗijｓiｓj）をアニーリングマシン７００に設定する。ここで、ｗijは頂点ｉ，頂点ｊの間の辺重みであり、Ｅは、グラフに含まれるエッジの集合である。
【００２２】
制御モジュール５２２は、アニーリングマシン７００を制御し、アニーリングマシン７００により算出された、設定したハミルトニアンの固有状態となる複数のスピンの配列を取得する。そして、制御モジュール５２２は、算出された配列が棄却条件を満たす場合、配列を棄却し、算出された配列が棄却条件を満たさない場合、その配列に基づいて、グラフの最小カットを算出する。
【００２３】
ここで、棄却条件は、配列が全て同じ値であることであってよい。例えば、ハミルトニアンがＨ＝−（Σ(i,j)∈Eｗijｓiｓj）であり、複数のスピンが＋１又は−１のいずれかの値を取る場合、棄却条件は、複数のスピンが全て＋１であることであってよい。複数のスピンが全て＋１である配列は、グラフを、グラフ全体と空グラフとに二分割することに対応しており、最小カットの自明解である。
【００２４】
従来、最小カットの自明解を排除するため、ハミルトニアンに制約項を加えることがあった。制約項は、例えば、Ｈ1＝−α（Σ(i,j)∈Eｗijｓiｓj）＋β（Σi<jｓiｓj）というハミルトニアンの二項目のように設定される。ここで、αとβはパラメータである。ここで、制約項に表れる相互作用の数は、Ｏ（｜Ｖ｜２）である。このような相互作用は、全てのスピンの間に相互作用を設定することを意味しており、現在の量子アニーリングマシンのように設定できるグラフ構造が限定される場合、最小カットを求めることができるグラフの大きさを著しく制限する要因となる。
【００２５】
この点、本実施形態に係るクライアントコンピュータ５００は、Ｈ＝−（Σ(i,j)∈Eｗijｓiｓj）というハミルトニアンをアニーリングマシン７００に設定することで、相互作用の数をＯ（｜Ｅ｜）に抑えることができる。これにより、アニーリングマシン７００のハードウェア構成に起因する制限を受けづらくなり、最小カットを求めることができるグラフの大きさの上限を大幅に増やすことができる。
【００２６】
グラフ情報５２４は、グラフに含まれる複数の頂点と、複数のエッジとに関する情報であり、複数のエッジの重みに関する情報を含んでもよい。
【００２７】
クライアントアプリケーション５２６は、例えば、ウェブブラウザなどを含む。
【００２８】
１つ又は複数の処理装置（ＣＰＵ）５０２は、メモリ５０４から、必要に応じて各モジュールを読み出して実行する。例えば、１つ又は複数の処理装置（ＣＰＵ）５０２は、メモリ５０４に格納されているネットワーク通信モジュールを実行することで、通信部を構成してもよい。また、１つ又は複数の処理装置（ＣＰＵ）５０２は、メモリ５０４に格納されている接続モジュールを実行することで、接続部を構成してもよい。また、１つ又は複数の処理装置（ＣＰＵ）５０２内に接続部を構成してもよい。
【００２９】
上記に示した要素の各々は、先述の記憶装置の１つ又は複数に格納され得る。上記に示したモジュールの各々は、上述される機能を実行するための命令のセットに対応する。上記に示したモジュール又はプログラム（すなわち、命令のセット）は別個のソフトウェアプログラム、プロシージャ又はモジュールとして実装される必要はないとともに、従ってこれらのモジュールの様々なサブセットは様々な実施形態で組み合わされるか、或いは再構成されてもよい。ある実施形態において、メモリ５０４は上記に示されるモジュール及びデータ構造のサブセットを格納し得る。さらには、メモリ５０４は上述されない追加的なモジュール及びデータ構造を格納し得る。
【００３０】
アニーリングマシン７００は、複数のスピンに関して設定されたハミルトニアンの低エネルギー状態を求める専用計算機である。ここで、低エネルギー状態は、少なくとも基底状態と第１励起状態とを含む。アニーリングマシン７００は、ジョセフソン接合等の超電導素子で構成される量子アニーリングマシンであってよいが、半導体素子で構成されるデジタルアニーリングマシンであってもよい。
【００３１】
図２は、本実施形態に係る情報処理装置（クライアントコンピュータ５００）に記憶されるグラフ情報５２４の一例を示す図である。本例のグラフ情報５２４は、５つの頂点と、８つのエッジとを含むグラフに関する情報である。
【００３２】
クライアントコンピュータ５００は、グラフに含まれる複数の頂点を複数のスピンｓ1，ｓ2，ｓ3，ｓ4，ｓ5に対応させ、グラフに含まれる複数のエッジの重みを複数のスピン間の相互作用ｗ12，ｗ13，ｗ14，ｗ23，ｗ24，ｗ34，ｗ35，ｗ45に対応させるように、複数のスピンのハミルトニアンＨ＝−（Σ(i,j)∈Eｗijｓiｓj）をアニーリングマシン７００に設定する。以下では、簡単のため、スピン間の相互作用は、全て＋１であるとする。すなわち、ｗ12＝ｗ13＝ｗ14＝ｗ23＝ｗ24＝ｗ34＝ｗ35＝ｗ45＝１であるとする。この場合、ハミルトニアンは、Ｈ＝−（ｓ1ｓ2＋ｓ1ｓ3＋ｓ1ｓ4＋ｓ2ｓ3＋ｓ2ｓ4＋ｓ3ｓ4＋ｓ3ｓ5＋ｓ4ｓ5）である。
【００３３】
クライアントコンピュータ５００は、アニーリングマシン７００により算出された、ハミルトニアンの固有状態となる複数のスピンの配列を取得する。上記ハミルトニアンの基底状態（最小エネルギー状態）は、ｓ1＝ｓ2＝ｓ3＝ｓ4＝ｓ5＝１であり、その固有エネルギーは、＜Ｈ＞＝−８である。
【００３４】
クライアントコンピュータ５００は、算出されたスピンの配列が棄却条件を満たす場合、その配列を棄却する。ここで、棄却条件は、スピンの配列が全て同じ値であることである。言い換えると、棄却条件は、算出されたスピンの配列が基底状態であることである。基底状態は、グラフの最小カットに関する自明解に対応する。
【００３５】
クライアントコンピュータ５００は、アニーリングマシン７００により算出された、ハミルトニアンの基底状態又は第１励起状態となるスピンの配列を取得する。アニーリングマシン７００は、ハミルトニアンの低エネルギー状態を求めるが、必ずしも基底状態が得られるとは限らず、第１励起状態が得られる場合もある。クライアントコンピュータ５００は、棄却条件によって、基底状態の配列を棄却し、第１励起状態の配列が得られた場合に、その配列を採用する。
【００３６】
クライアントコンピュータ５００は、配列が棄却条件を満たさない場合、その配列に基づいて、グラフの最小カットを算出する。本例のハミルトニアンの場合、第１励起状態は、ｓ1＝ｓ2＝ｓ3＝ｓ4＝１、ｓ5＝−１であり、その固有エネルギーは、＜Ｈ＞＝−４である。このような配列は、ｓ＝１である頂点のクラスタと、ｓ＝−１である頂点のクラスタとにグラフを二分割する場合が最小カットＣであることを表している。
【００３７】
クライアントコンピュータ５００は、配列が棄却条件を満たさない場合、配列の固有エネルギーに基づいて、グラフの最小カット数を算出する。より具体的には、クライアントコンピュータ５００は、（｜Ｅ｜＋＜Ｈ＞）／２によって最小カット数を算出する。本例の場合、グラフに含まれるエッジの数は｜Ｅ｜＝８であり、固有エネルギーは＜Ｈ＞＝−４であるから、最小カット数は（８−４）／２＝２と算出される。
【００３８】
＜動作説明＞
続いて、本実施形態に係るクライアントコンピュータ５００の動作について説明する。図３は、本実施形態に係る情報処理装置（クライアントコンピュータ５００）により実行される処理のフローチャートである。
【００３９】
（ステップＳ１０）
はじめに、クライアントコンピュータ５００は、複数の頂点を複数のスピンに対応させ、複数のエッジの重みを複数のスピン間の相互作用に対応させるように、複数のスピンのハミルトニアンをアニーリングマシン７００に設定する。
【００４０】
（ステップＳ１１）
次に、クライアントコンピュータ５００は、アニーリングマシン７００により算出された、ハミルトニアンの固有状態となる複数のスピンの配列を取得する。
【００４１】
（ステップＳ１２）
クライアントコンピュータ５００は、算出されたスピンの配列が全て同じ値であるか否かを判定する。
【００４２】
（ステップＳ１３）
算出されたスピンの配列が全て同じ値である場合（Ｓ１２：ＹＥＳ）、クライアントコンピュータ５００は、その配列を棄却する。そして、クライアントコンピュータ５００は、ステップＳ１１及びＳ１２を再び実行する。
【００４３】
（ステップＳ１４）
一方、算出されたスピンの配列が同じ値ではない場合、クライアントコンピュータ５００は、その配列に基づいて、グラフの最小カットを算出する。
【００４４】
（ステップＳ１５）
また、クライアントコンピュータ５００は、配列の固有エネルギーに基づいて、グラフの最小カット数を算出する。
【００４５】
図４は、本実施形態に係る情報処理装置（クライアントコンピュータ５００）による計算時間と、従来技術による計算時間とを示す図である。同図では、本実施形態による計算時間Ｇ１を実線で示し、従来技術による計算時間Ｇ２を破線で示している。同図では、C. Seshadhri, T.G. Kolda, and A. Pinar, “Community structure and scale-free collections of erdos-renyi graphs,” Physical Review E, vol.85, no.5, p.056109, 2012.に記載された方法でグラフのデータセットを生成し、本実施形態に係るクライアントコンピュータ５００と、非特許文献１の方法による計算時間とを算出した結果を示している。
【００４６】
グラフの生成は、元とするグラフ、密度パラメータｄと、カットサイズパラメータｃとを指定して行われる。はじめに、元とするグラフの複数の頂点を二分割し、異なる集合に属する辺を削除する処理を行う。その後、残っている辺の中から頂点の次元数がともにｃ＋１より大きい辺をランダムに削除し、辺の数が当初のｄ％になるまで削除を繰り返す。最後に、端点が異なる頂点集合に属する辺の中からランダムにｃ個を選んで、辺を再形成する。このような方法でグラフを生成することで、グラフの最小カット数は、ほとんどの場合ｃとなる。本例では、元とするグラフを現在の量子アニーリングマシンのハードウェア構成、ｃ＝２として、ｄを変化させた場合の計算時間を示す。
【００４７】
図４の横軸は、グラフの生成に用いた密度パラメータｄを示し、左側の縦軸は、アニーリングマシン７００として量子アニーリングマシンを用いた場合の計算時間（Time To Solution）をμｓの単位で示している。ここで、量子アニーリングのアニーリング時間は１μｓに設定し、９９％の確率で解が得られるまでの時間の平均値を計算時間としている。また、右側の縦軸は、非特許文献１に記載のアルゴリズム（VieCut）を汎用のコンピュータで１万回実行した場合の平均演算時間をμｓの単位で示している。全てのパラメータ領域について、本実施形態に係るクライアントコンピュータ５００による計算時間は、従来技術による計算時間よりも短い。
【００４８】
密度パラメータｄを６０から９０に増加させていった場合、本実施形態に係るクライアントコンピュータ５００による計算時間Ｇ１と、従来技術による計算時間Ｇ２とは、おおよそ同じ振る舞いをしているが、密度パラメータｄが９０から１００に増加する場合に、従来技術では計算時間が上昇しているのに対して、本実施形態に係るクライアントコンピュータ５００によれば、計算時間が減少する。このように、本実施形態に係るクライアントコンピュータ５００によれば、アニーリングマシン７００を用いてグラフの最小カットをより高速に求めることができ、従来技術では計算時間が増大するようなグラフについて、計算時間を一定に抑えたり、減少させたりすることができる。
【００４９】
なお、開示技術は、上述した各実施形態に限定されるものではなく、開示技術の要旨を逸脱しない範囲内において、他の様々な形で実施することができる。このため、上記各実施形態はあらゆる点で単なる例示にすぎず、限定的に解釈されるものではない。例えば、上述した各処理ステップは処理内容に矛盾を生じない範囲で任意に順番を変更し、または並列に実行することができる。
【００５０】
本開示の各実施形態のプログラムは、コンピュータに読み取り可能な記憶媒体に記憶された状態で提供されてもよい。記憶媒体は、「一時的でない有形の媒体」に、プログラムを記憶可能である。プログラムは、限定でなく例として、ソフトウェアプログラムやコンピュータプログラムを含む。
【符号の説明】
【００５１】
１３０…通信ネットワーク、５００…クライアントコンピュータ、５０２…ＣＰＵ、５０４…メモリ、５０６…通信インタフェース、５０６…ネットワーク通信インタフェース、５０８…ユーザインタフェース、５１０…ディスプレイ、５１２…キーボード／マウス、５１４…通信バス、５１６…オペレーティングシステム、５１８…ネットワーク通信モジュール、５２０…設定モジュール、５２２…制御モジュール、５２４…グラフ情報、５２６…クライアントアプリケーション、７００…アニーリングマシン
【図１】
0006889230.tif 000002
【図２】
0006889230.tif 000003
【図３】
0006889230.tif 000004
【図４】
0006889230.tif 000005