[技術解説]

2022年1月11日(火)日川 佳三（IT Leaders編集部）

リスト

　早稲田大学の研究グループは、量子アニーリングマシンで大規模な問題を解法するための技術を開発した。早稲田大学グリーン・コンピューティング・システム研究機構の客員次席研究員である跡部悠太氏、同機構の研究院講師である多和田雅師氏、同大学理工学術院の戸川望教授らの研究グループが発表した。

まず、最適性を失わずに大規模な問題を小さな問題に分割する条件を解明した。これに基づき、小さな問題を繰り返し解法することで、量子アニーリングマシン（イジングマシン）で大規模な問題を解法する技術を開発した。

　「イジングマシンは従来、ハードウェア上の制約から、利用可能なビット数に制限があった。このため、規模の大きな問題を解くことが困難だった。これに対し、今回開発した手法を使うと、規模の大きな問題をイジングマシンで計算できるようになる」（早稲田大学）。

　研究グループは、実際のイジングマシンで解法可能な問題規模に対して8倍～32倍の大きな問題について、新手法と従来手法（ランダム手法とqbsolv手法）を比較。その結果、新手法で得られる答えのほうが精度が高いことが判明したという（図1）。

図1：実際のイジングマシンで解法可能な問題規模に対して8倍～32倍の大きな問題について、新手法と従来手法（ランダム手法とqbsolv手法）を比べた。この結果、新手法で得られる答えのほうが精度が高いことが分かった（出典：早稲田大学）
拡大画像表示

元の大規模な問題の答えと一致するように、小さな問題に分割

　早稲田大学は次のように述べている。「既存の研究では、おそらく良さそうと考えられる手続きを組み合わせる発見的な手法によって、大規模な問題を小さな問題に分割し、イジングマシンで解法していた。しかし、この手法では、分割した問題の答えが元の大規模な問題の答えと一致しているかは分からなかった」。

　今回の研究で同大学は、イジングマシンに入力できる問題規模の制限を解決することを目指した。まず、最適性を失わずに大規模な組み合わせ最適化問題を小さな問題に分割する条件を解明。条件を満足した小さな問題を解法すれば、元の大規模な問題の答えと一致することを証明した。

　また、大規模な問題からうまくこのような条件を抽出し、元の大規模な問題をイジングマシンで解法可能な問題規模まで小さくして、繰り返し解法する新たなアルゴリズムを提案した。「理論的な裏付けの下、大規模な問題を小さな問題に分割して解法するため、従来技術と比べて、精度よく元の大規模な問題を解法できる」（同大学）。

●Next：早稲田大学が新たに開発した手法のポイント