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

東芝が開発した2つの新アルゴリズム（同社説明資料より）

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

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

シミュレーテッド・アニーリングをCPUで計算させたときより2万倍速く、GPU16台を使ったときよりも100倍速いという

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

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

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

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

従来のシミュレーテッド分岐アルゴリズムの計算原理

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

従来のSBの課題

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

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

従来4次関数だったところ、項を削って2次関数（弾道）にし、1と－1に“壁”も設けた

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

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

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

離散的シミュレーテッド分岐アルゴリズムでは変数を離散化することで疑似的な量子トンネル効果が生まれた

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

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