[市場動向]

早稲田大学、量子アニーリングマシンで大規模な問題を解法する技術を開発

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

早稲田大学は2022年1月11日、量子アニーリングマシンで大規模な問題を解法するための技術を開発したと発表した。まず、最適性を失わずに大規模な問題を小さな問題に分割する条件を解明した。さらに、これにもとづき、小さな問題を繰り返し解法することで、量子アニーリングマシンで大規模な問題を解法する技術を開発した。量子アニーリングマシン(イジングマシン)は従来、ハードウェア上の制約から、入力できる問題の規模に制限があった。これを解消する。

 早稲田大学の研究グループは、量子アニーリングマシンで大規模な問題を解法するための技術を開発した。まず、最適性を失わずに大規模な問題を小さな問題に分割する条件を解明した。さらに、これにもとづき、小さな問題を繰り返し解法することで、量子アニーリングマシン(イジングマシン)で大規模な問題を解法する技術を開発した。

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

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

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

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

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

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

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

●Next:開発した手法のポイント

この記事の続きをお読みいただくには、
会員登録(無料)が必要です
  • 1
  • 2
関連キーワード

早稲田大学 / 量子アニーリング / イジングマシン

関連記事

Special

-PR-

早稲田大学、量子アニーリングマシンで大規模な問題を解法する技術を開発早稲田大学は2022年1月11日、量子アニーリングマシンで大規模な問題を解法するための技術を開発したと発表した。まず、最適性を失わずに大規模な問題を小さな問題に分割する条件を解明した。さらに、これにもとづき、小さな問題を繰り返し解法することで、量子アニーリングマシンで大規模な問題を解法する技術を開発した。量子アニーリングマシン(イジングマシン)は従来、ハードウェア上の制約から、入力できる問題の規模に制限があった。これを解消する。

PAGE TOP