量子アニーリングマシンの活用を広げる入力データ変換手法を開発

発表のポイント

• イジングマシンには入力できるデータの「桁数」制限というハードウェア上の課題があった
• 計算結果出力データの正しさを保証しつつ、入力データ変換時の桁数の削減手法を開発した
•  これまでにない桁数のデータ計算が可能となり、組合せ最適化問題の活用幅拡張が期待される

早稲田大学大学院基幹理工学研究科博士後期課程3年の於久 太祐（おく だいすけ）氏（現学術振興会特別研究員（PD））、同大理工学術院講師の多和田 雅師（たわだ まさし）氏（現同大グリーン・コンピューティング・システム研究機構研究院講師）、同大グリーン・コンピューティング・システム研究機構研究院准教授の田中 宗（たなか しゅう）氏（現慶應義塾大学理工学部准教授 兼 早稲田大学グリーン・コンピューティング・システム研究機構研究院客員准教授）、同大理工学術院教授の戸川 望（とがわ のぞむ）氏らの研究グループは、イジングマシン^※１の計算結果の出力データが正しいことを保証したまま、入力データを変換して桁数を削減する手法を開発しました。

近年、量子アニーリングマシン^※２をはじめとしたイジングマシンと呼ばれる新しいタイプの計算機が、組合せ最適化問題^※３を解決するために注目されています。しかしイジングマシンは入力データの桁数に制限が存在するため、これまでその性能を十分に引き出せませんでした。このたび本研究グループが開発した手法は、補助データを追加することで入力データの桁数を削減し、実装が容易なアルゴリズムとしてまとめ上げています。また、本手法は入力データを変換する前と後のイジングマシンによる計算結果が変化しないことを数学的にも証明することができました。

これにより、今までイジングマシンへ入力できなかった桁数を持つ入力データでも計算することが可能となり、現実世界の組合せ最適化問題への活用を拡張させます。さらに本手法はイジングマシンを使うためのソフトウェア処理手法を発見する手助けになり、技術発展に寄与できると考えられます。

本研究成果は、2020年12月15日にIEEE Computer Societyが発行する『IEEE Transactions on Computers』のオンライン版Early Accessにて公開されました。

【論文情報】
雑誌名：IEEE Transactions on Computers
論文名：How to Reduce the Bit-width of an Ising Model by Adding Auxiliary Spins
掲載URL：https://ieeexplore.ieee.org/document/9294135

（１）これまでの研究で分かっていたこと

現実世界のあらゆるところに存在する組合せ最適化問題は、大規模になるほど従来型のコンピュータで最適解を得ることが困難になるため、様々な解法が研究されています。中でも近年、量子アニーリングマシンをはじめとしたイジングマシンと呼ばれる新しいタイプの計算機が注目されています。イジングマシンは組合せ最適化問題の解を得るのに特化した計算機です。同計算機は国内外で研究開発され、一般のユーザーもクラウド上で使用できる段階になっています（図1）。

しかし、イジングマシンを活用するにはまだ課題が多くあります。特に、イジングマシンへ解きたい問題を入力する際のデータの変換方法には大きな課題があります。それぞれのイジングマシンには、大きく分けて２つのハードウェアの制限があります。１つ目は入力データが特有な形式のみに制限されているという点、２つ目は入力できるデータの「桁数」に制限があるという点です。これらの制限を回避することで、はじめてイジングマシンの潜在性能を引き出す活用ができると考えられています。

既存研究として、１つ目の制限を回避する方法は多く提案されておりソフトウェア化されつつあります。しかし、２つ目の制限を回避する方法、すなわち、入力データの桁数を効果的に減らす手法はこれまで提案されていませんでした。

（２）今回の研究で新たに実現しようとしたこと、明らかになったこと

今回の研究では、量子アニーリングマシンをはじめとするイジングマシンが持つハードウェアの制限を解決するために、計算結果の出力データが正しいことを保証したまま、入力データを変換して桁数を削減する手法を開発しました。

入力データの桁数が大きい場合は、数値に対して右ビットシフト^※４することで桁数を削減できます。例えば、符号付き2進数を用いて4桁で表現できる「5」は、1つ右ビットシフトすると「2」になります。「2」は符号付き2進数を用いて3桁で表現できます。この手法は単純ですが、入力データを変換する前と後でイジングマシンによる計算結果が変化してしまう欠点があります。

今回の研究の結果、補助データを追加することで入力データの桁数を削減できる手法を開発しました。また、本手法は変換後のイジングマシンによる計算結果の出力データが正しいと保証することを数学的に証明しました。

（３）そのために新しく開発した手法

入力データを右ビットシフトすることで桁数を削減する場合、本来の数値を丸め込むため、入力データを変換する前と後のイジングマシンによる計算結果は必ずしも一致しません。

そこで、イジングマシンが持つ入力データの桁数の制限を解決するために、補助データを追加することで入力データの桁数を削減する手法を開発し、実装が容易なアルゴリズムとしてまとめ上げることに成功しました。本手法は計算結果の出力データが正しいことを保証したまま、入力データの桁数を削減できます（図2）。ランダムに生成した入力データだけでなく、実際の組合せ最適化問題を入力データとしてイジングマシン実機を使った実験から、期待通りの計算結果が得られることを確認しました。

また、本手法は入力データを変換する前と後のイジングマシンによる計算結果が変化しないことを数学的に証明しました。

（４）研究の波及効果や社会的影響

今までイジングマシンへ入力できなかった桁数を持つ入力データでも、本手法を使うことによってイジングマシンで計算することができます。そのため、量子アニーリングマシンを含むイジングマシンを使った、現実世界の組合せ最適化問題への活用事例を広げることができると考えられます。また、本研究はイジングマシンを使うためのソフトウェア処理手法を発見する手助けになり、技術発展に寄与できると考えられます。

（５）今後の課題

本研究では計算結果の出力データが正しいことを保証したまま、入力データを変換して桁数を削減する手法を開発しましたが、本手法は桁数を多く削減すると、補助データが多く増える問題点があります。今後の研究では補助データの増加数を抑えつつ、計算結果の出力データが正しいことを保証する新たな手法を開発する必要があります。

（６）研究者のコメント

本研究ではイジングマシンを活用するために重要なハードウェアの制限を解決する手法を開発しました。イジングマシンを活用した事例は増えつつありますが、本研究で開発した手法を使って、今まで活用できなかった事例が増えることを期待します。

（７）用語解説

※１　イジングマシン
組合せ最適化問題をイジングモデルで表現し、組合せ最適化問題を解決するマシンの総称。量子アニーリングマシンはイジングマシンの一種である。

※２　量子アニーリングマシン
組合せ最適化問題を高速に解決すると期待されるマシン。量子効果により量子重ね合わせ状態を実現させ、それを初期状態として用意し、徐々に量子効果を弱める。同時に組合せ最適化問題を表現するイジングモデルの効果を強めることにより、イジングモデルの安定状態を実現させるという機構で動作する。

※3　組合せ最適化問題
膨大な選択肢の中から､与えられた制約を満たしつつ、関数の最小値(または最大値)をとる選択肢を求める問題の総称。

※4　ビットシフト
数字を2進数で表現した時のビット列を右または左にずらす操作。例えば、5は2進数だと101と表現され、右ビットシフトすると10となり、左ビットシフトすると1010となる。

（８）論文情報

雑誌名：IEEE Transactions on Computers
論文名：How to Reduce the Bit-width of an Ising Model by Adding Auxiliary Spins
執筆者名（所属機関名）：Daisuke Oku（早稲田大学）, Masashi Tawada（早稲田大学）, Shu Tanaka（早稲田大学）, Nozomu Togawa（早稲田大学）※所属は論文投稿時
掲載日：2020年12月15日
掲載URL：https://ieeexplore.ieee.org/document/9294135
DOI：10.1109/TC.2020.3045112

（９）研究助成

研究費名・研究課題名：国立研究開発法人新エネルギー・産業技術総合開発機構（NEDO）
「高効率・高速処理を可能とするＡＩチップ・次世代コンピューティングの技術開発／次世代コンピューティング技術の開発／イジングマシン共通ソフトウェア基盤の研究開発」
研究代表者名（所属機関名）：戸川望（早稲田大学）