東芝、“疑似量子トンネル効果”で組合せ最適化計算を高速・高精度化　「世界最速・最大規模」うたう独自の量子コンピュータ発アルゴリズムを開発

　東芝は2月4日、一部の量子コンピュータが得意とする「組合せ最適化問題」を、従来のコンピュータでより高速に計算するアルゴリズムの改良版を発表した。現状の量子コンピュータを含む他の計算方式よりも速度で上回り、より大規模な問題も解けるとして「世界最速・最大規模」（同社）をうたう。2021年中に、同アルゴリズムを搭載したハードウェアやクラウドサービスの提供を目指す。

　2019年に発表した、同社が研究中の独自の量子コンピュータから着想を得た「シミュレーテッド分岐アルゴリズム」（SB）を改良したもの。“疑似量子トンネル効果”を取り入れたことで、大規模な問題でも最適解を経験的に計算できるようになったという。

　GPUやFPGAへの実装が可能で、GPU16台を接続した環境では100万変数という大きな問題でも約30分で事実上の最適解に到達できたという。同様の問題を解く一般的な手法として知られる「シミュレーテッド・アニーリング」（SA）と16台のGPUを使って解いた場合に比べ、約100倍高速だとしている。

　東芝は、コロナ禍で求められる治療薬の開発や医療従事者の勤務シフトの作成といった、組合せ最適化問題で解ける社会課題への応用が期待できるとしている。

　研究結果は、米オンライン科学雑誌「Science Advances」に2月3日付で掲載された。

どんな工夫で高速化・高精度化したか

　SB自体は、東芝の研究主幹である後藤隼人さんらが研究開発している量子コンピュータ「量子分岐マシン」の計算を古典力学に変換したもの。組合せ最適化問題の変数は1、0（もしくは1、－1）の離散的な値を取るが、SBではあえて変数を連続にすることで計算の並列化と高速化を実現した。

　しかし、従来のSBは問題サイズが大きい場合に最適解の計算が難しく、良解（最適解ではないがある程度いい解）で止まってしまう問題があった。これを解消するため、後藤さんらは改良した2つのアルゴリズムを作った。

　従来のSBで最適解が出なかった理由の一つは、変数が連続的であるためぴったりと1にとどまらず、1.1のような微妙にずれた値で落ち着いてしまうため。そこで後藤さんらは「弾道的シミュレーテッド分岐アルゴリズム」（ballistic SB, bSB）を開発。

　変数の取る範囲を1～－1に区切った上、計算の時間経過とともに動く変数の値が端に近づいた際には端に吸い付くように工夫することで、値を1や－1にぴったりと落ち着かせるようにした。これにより、従来のSBと同程度の良解を約10倍高速に計算できるようになった上、計算を進めればより最適解に近い良解も得られるという。

　新たに開発したアルゴリズムのもう一つが「離散的シミュレーテッド分岐アルゴリズム」（discrete SB, dSB）。従来のSBが最適解を得られなかった理由のもう一つは“山”を乗り越えられず、「局所最適解」（最適解ほど小さくないが局所的には最適に見える解）に落ち着いてしまうからだった。この性質はSAなど他の古典力学に基づくアルゴリズムでも見られる。

　「量子アニーリング」という計算方式の量子コンピュータが組合せ最適化問題に向くとされるのは、量子特有の性質である「量子トンネル効果」で良解同士の間にある“山”を乗り越えず、トンネルのようにくぐることでエネルギーのより小さい最適解にたどり着けるといわれるからだ。

　dSBはbSBの式の中にある変数を再び離散化。「これにより、量子トンネル効果と似た壁抜け効果が生まれることが分かった」と後藤さんは話す。

　従来のSBは問題サイズが大きい場合、いくら計算ステップ数をかけても最適解にはたどり着かなかった。しかしdSBでは計算ステップを十分に踏めば、推定値ながら最適解に到達することが分かった。

　後藤さんらは、組合せ最適化問題に特化した他のマシン（量子アニーラ、デジタルアニーラ、コヒーレントイジングマシン、シミュレーテッドCIM、制限ボルツマンマシン）とも最適解に到達するまでの計算速度を比較。100変数までの問題サイズではdSBとほぼ同等の計算速度のマシンもあったが、各マシンが解ける問題サイズの制限から、それ以上の大きさの問題ではdSBが最速だった。

　dSBとbSBを比べると、ある程度精度の高い良解を得るならbSBの方が高速だが、bSBで最適解に到達するのは難しい。「瞬時に良解を得たいか、時間をかけて極めて精度の高い解が欲しいかといった使い分けが想定できる」（後藤さん）

この記事の著者

関連記事

• 

  「量子理論の副産物に過ぎなかった」──東芝の「量子コンピュータより速いアルゴリズム」誕生秘話

• 

  中国科技大、光量子コンピュータで「量子超越性」を実証　スパコン富岳で6億年かかる計算を200秒で

• 

  「世界最速・最大規模」──東芝、量子コンピュータより高速に組み合わせ最適化問題を計算するアルゴリズムを開発

• 

  「海外は量子アニーリングに見切り」──ハードもソフトも開発する量子ベンチャー「MDR」に聞いた「量子コンピュータの今」