実世界の事象をデータ化しながら活用するフィジタルデータセントリックコンピューティング
イジング型計算機による組合せ最適化のためのハイブリッド計算基盤
NTTソフトウェアイノベーションセンタ

新井 淳也(あらい じゅんや)/八木 哲志(やぎ さとし)/内山 寛之(うちやま ひろゆき)/富田 均也(とみた きんや)/宮原 和大(みやはら かずひろ)/巴 徳瑪(ともえ とくま)/堀川 桂太郎(ほりかわ けいたろう)

ムーアの法則の終焉に伴い、計算機の性能を飛躍的に向上させるのは困難になりつつあります。一方で、私たちは今日のデジタル計算機を圧倒するような複雑な問題に依然として直面しています。組合せ最適化問題はそのような問題の1つです。基礎的な組合せ最適化問題としては、指定された複数の都市をもっとも効率的にめぐる訪問順を求める問題(巡回セールスマン問題)や、限られた色数で隣り合う領域が異なる色になるように塗り分ける問題(グラフ彩色問題)が有名です。
これらの応用の一例としては無線通信の品質改善があります。複数の無線アクセスポイントをイベント会場に配置する際、近傍のアクセスポイントが互いに同じ周波数帯を使用していると、電波の干渉により通信が不安定になります。ここでグラフ彩色問題を応用することで、近傍のアクセスポイントがそれぞれ異なる周波数帯となるような割り当て方を求めることができます。このように、組合せ最適化問題は実世界の課題に広く内包されています。
組合せ最適化のさまざまな問題は、イジングモデルの基底状態探索(イジング最適化)問題に変換可能であることが知られています。イジングモデルとはスピンのネットワークを表現した統計力学のモデルです(図1)。スピンσiはアップ(＋1)またはダウン(−1)のいずれかの状態をとります。Jijとhiがそれぞれスピン間相互作用と磁場の強さを表すとすると、基底状態とは次式で定義されるイジングハミルトニアンHが最小化された状態を指します。基底状態を満たすスピンの組合せが、基底状態探索問題の解となります。

イジング最適化問題、ひいては組合せ最適化問題を効率的に解くため、D-Wave Systemsの量子アニーリングマシンや富士通のデジタルアニーラのようにイジング最適化に特化した計算機が開発されています。本稿ではそのような計算機をイジング型計算機と呼称します。NTTもまたNTT物性科学基礎研究所において光を用いたイジング型計算機であるLASOLV®の研究開発を行っています(図2)。これらの計算機の機能は限られた規模のイジング最適化問題を解くことのみですが、イジング型計算機とデジタル計算機を協調的に利用するハイブリッドアルゴリズムの使用により複雑な問題も解くことができます。例えば、大規模なイジング最適化問題を解くため、デジタル計算機上で小規模な部分問題に分解したうえで、個々の部分問題をイジング型計算機で解くという処理を繰り返す発見的手法が存在します。そのため、イジング型計算機は実世界の問題に幅広く適用可能です。
しかし、イジング型計算機の利用にあたってはいくつかの課題があります。例えば、コストや設置場所の問題で多数のイジング型計算機を用意することは困難であるため、複数人で少数のイジング型計算機を共用する仕組みが必要です。そこでいくつかの企業は、クラウドプラットフォーム上のリモートな計算資源としてイジング型計算機を提供しています^(1)、(2)。プラットフォームの利用者は手元のデジタル計算機でプログラムを実行し、そのプログラムからWeb API(Application Programming Interface)リクエストを発行することでイジング最適化をそのプラットフォームに任せる(オフロードする)ことができます。ところが、イジング型計算機は1ミリ秒オーダーの時間で問題を解くため、相対的にインターネット経由の通信はあまりにも低速です。特に、ハイブリッドアルゴリズムはイジング型計算機とデジタル計算機の間で頻繁に情報をやり取りするため、通信コストによる性能低下が顕著になります。このように、イジング型計算機の利用には依然として課題があります。
これらの課題を解決すべく、NTTソフトウェアイノベーションセンタでは、LASOLV®を簡単かつ効率的に利用するためのプラットフォームの研究開発に取り組んでいます。本稿ではまず、イジング計算プラットフォームに求められる設計上のポイントを整理し、さらにそれらの要求に対する回答として私たちのプラットフォームであるLCS(LASOLV® Computing System：LASOLV®計算システム)を紹介します。LCSの大きな特徴は、利用者によって定義されたハイブリッドアルゴリズムをLASOLV®と併置されたデジタル計算機上で実行することです。これによりLASOLV®とデジタル計算機の間で効率的な通信が可能となります。さらに、LCSは幅広いユースケースにおいてイジング最適化問題への変換を容易にするライブラリを備えています。以降ではこれらについて詳しく説明します。
なお、LASOLV®は以前「量子ニューラルネットワーク」と呼ばれていました。紙面の都合でLASOLV®自体については説明しませんので、詳しくは過去の特集記事⁽³⁾を参照ください。

NTTソフトウェアイノベーションセンタでは、LASOLV®のための計算プラットフォームとしてLCSの開発に取り組んでいます。具体的には、LCSは独自のPythonライブラリ、およびジョブスケジューラなどのミドルウェアを備えた計算機クラスタです。前述した設計上の要求を満たすため、LCSは次の3つの特徴を持ちます。

LASOLV®とデジタル計算機の間の効率的な通信を可能にするため、LASOLV®とデジタル計算機はLCSにおいて1つのクラスタに統合されています…

1. (1)https://cloud.dwavesys.com/leap/
2. (2)https://www.fujitsu.com/global/digitalannealer/services/
3. (3)武居・稲垣・稲葉・本庄：“複雑な組合せ最適化問題を解く量子ニューラルネットワーク、”NTT技術ジャーナル、Vol.29, No.5, pp.11-14, 2017。