世界のスーパーコンピュータとそれを動かす人々


4月 24, 2019

東北大学、D-Waveシステムの能力を改善するアルゴリズムを開発

HPCwire Japan

John Russell

東北大学の研究者と自動車部品メーカーであるデンソーの科学者達は、複雑な問題を処理するために、能力を向上させたD-Waveシステムのアルゴリズムを開発したと報告している。このアルゴリズムは、オリジナルの大きな問題をサブ問題のグループに分割することによって機能する。その後、D-Waveアニーラーは各サブ問題を繰り返し最適化し、最終的に元の大きな問題を解決する。この研究のアカウントは東北大学のウェブサイトに掲載されている。

問題サイズは、量子コンピューティングのすべてのアプローチにとって大きな課題だ。利用可能なキュービット数の少なさ、量子ビットの相互接続性の制限およびコヒーレンス時間の短さのすべてが組み合わさって、現実的に取り組むことができる問題のサイズと複雑さを制限している。ゲートベースのコンピューティングパラダイムではないD-Waveの量子アニーリング(QA)アプローチは、ゲートベースのモデルの多くの問題を回避し、D-Waveが2000キュービットシステムを構築することを可能にしている。

それは、QAマシンが非常に異なって動作するということである。実際のところ、物理的なハードウェアトポロジは、「組み合わせ最適化問題」に取り組むように特別に設計されている。これは、計算上の問題がハードウェアに効率的にマッピングされなければならない、ということを意味する。この最近の技術は、D-Waveマシンのために問題のサイズをより便利なサイズに分割することに役立つのだ。著者の岡田俊太郎博士(東北大学博士号取得候補者)および彼の同僚による、最近の学術雑誌Natureの論文(Improving solutions by embedding larger subproblems in a D-Wave quantum annealer)からの簡単な説明は以下のとおりである。

「量子ビット間の限定された接続性は、現実的な応用のためのD-Wave量子アニーラーの採用に対する制限です。最適化問題を解決する前に、問題グラフをハードウェアグラフのサブグラフにマッピングする必要があります。このプロセスはマイナーエンベディングと呼ばれています。問題グラフは、頂点と辺がそれぞれ論理変数とそれらの間の相互作用を表すグラフとして定義されます。ハードウェアグラフは、頂点と辺がそれぞれキュービットとそれらの間の相互作用を表すグラフとして定義されます。問題グラフとハードウェアグラフの両方が入力の一部である場合にマイナーな埋め込みを見つけ、問題グラフまたはハードウェアグラフが固定されている場合に多項式時間を求めることで、NP困難となることが知られています。」

通常の量子コンピューティングの研究においてそうであるように、論文全文を読むのが一番良い。

「提案されたアルゴリズムは、さらに多くのキュービットを含むD-Wave量子アニーラーの今後のバージョンにも適用可能です。」と、この東北大学の論文の別の著者である大関真之氏は述べています。 「D-Wave量子アニーラーに搭載されているキュービットの数が増えるにつれて、さらに優れた解決策を得ることができるでしょう。」

東北大学の記事へのリンク:http://www.tohoku.ac.jp/en/press/algorithm_quantum_computing.html

学術雑誌Natureへのリンク:https://www.nature.com/articles/s41598-018-38388-4

図出典:学術雑誌Nature