東京工業大学(東工大)と東北大学の両者は10月4日、複雑な構造を持つ「連続変数関数の最適化問題」に量子アニーリングを適用してさまざまな古典アルゴリズムと比較し、理想的な環境下における量子アニーリングの高度な有効性を実証したことを共同で発表した。

同成果は、東工大 国際先駆研究機構 量子コンピューティング研究拠点の荒井俊太助教、同・西森秀稔特任教授、東北大の押山広樹特任助教らの共同研究チームによるもの。詳細は、米国物理学会が刊行する原子・分子・光学・量子などを扱う学術誌「Physical Review A」に掲載された。

連続変数関数の最適化問題とは、0、1、2、3などの離散値を取る変数の関数の値を最小あるいは最大にする「組み合わせ最適化問題」に対し、任意の実数値を取れる連続変数の関数の値を最小あるいは最大にする問題のことをいう。この問題は、一定量の原材料から多種類の商品を生産して利益を最大化するように原材料の配分を決める場合など、現実に数多く存在している。

「巡回セールスマン問題」に代表される組み合わせ最適化問題自体も、最適な経路選択など、実際に数多くの場面で重要な役割を担っており、古典コンピュータや量子コンピュータ上でのアルゴリズムの研究開発が活発に行われている。中でも、組み合わせ最適化問題の解決に量子力学を利用する量子アニーリングの重要性の認識が広がっており、その適用範囲の拡大が望まれていた。そこで、連続変数を近似的に離散変数で表す方法が開拓されていたが、それを量子アニーリングに適用した時の有効性に関する系統的な研究はなされていなかったという。

今回の研究では、複雑な構造を持つ連続変数関数の最適化の例として、「1次元のRastrigin関数」の最小値を求める問題に取り組んだとする。この関数は原点での最小値に加えて多数の極小値を持ち、単純なやり方では極小解に陥ってしまう。

  • 多くの極小を持つ複雑な1次元のRastrigin関数。

    多くの極小を持つ複雑な1次元のRastrigin関数。(出所:東工大プレスリリースPDF)

まず、連続変数関数の最適化のために開発された各種の強力な古典アルゴリズムと、量子アニーリングマシンを商用化しているカナダ・D-Waveのデバイスに変数の離散化の手法を適用した結果の比較が行われた。その結果、限られた計算時間の範囲では、D-Wave製デバイスは古典アルゴリズムと同程度の性能を持つものの、この時間範囲を超えると、デバイス上のノイズのために古典アルゴリズムの方が優れた性能を持つことが確認された。つまり、量子アニーリングは連続変数の最適化にも応用できるが、実デバイスではノイズの影響が強く、本来の実力が発揮できているのかどうかが不明という結果になったとする。

  • 量子アニーリングの実デバイスD-Wave 2000QのQPU(Media courtesy of D-Wave)。

    量子アニーリングの実デバイスD-Wave 2000QのQPU(Media courtesy of D-Wave)。(出所:東工大プレスリリースPDF)

そこで、ノイズの影響を排した量子アニーリングの本来の性能を調べるため、組み合わせ最適化に絞り、量子アニーリングを古典コンピュータで直接的にシミュレート可能な手法「TEBD」を適用。連続変数を近似的に離散変数で表す「ドメイン壁符号化」が適用され、TEBDや離散変数関数の最適化用に開発された各種の古典アルゴリズムと、D-Wave製デバイスとの比較を行った。すると、ノイズのない理想的な量子アニーリングが、ほかの古典アルゴリズムやD-Wave製デバイスなどを大幅に上回る性能を示すことが確かめられたとのことだ。

  • ノイズのない量子アニーリング(左)と古典シミュレーテッド・アニーリング(右)で正解が得られる確率(縦軸)と計算時間(横軸)の関係。

    ノイズのない量子アニーリング(左)と古典シミュレーテッド・アニーリング(右)で正解が得られる確率(縦軸)と計算時間(横軸)の関係。色で区別されたh0は画像1の山の高さが表されている。山がより高い方が困難な問題。左の量子アニーリングの方が右のシミュレーテッド・アニーリングより山の高さによらず常に高い正解率が示されている。特に、量子アニーリングでは正解率が山の高さによらないが、シミュレーテッド・アニーリングは山が高くなると山を越えての探索が難しくなり、正解率が低下している。(出所:東工大プレスリリースPDF)

今回の研究により、連続変数関数の最適化においても、ノイズの影響さえなければ量子アニーリングが古典アルゴリズムをしのぐ優れた性能を持つことが示唆された。現在のD-Wave製デバイスではノイズの影響が大きく、量子アニーリング本来の性能を発揮するに至っていないが、東工大 量子コンピューティング研究拠点の研究者も参加した超短時間の量子シミュレーション実験では、ノイズの影響を排した理想的なデータが得られるなど、大幅な改善の兆しが見えてきている。研究チームは、ノイズの影響を排した運用が一般のエンドユーザーにもアクセス可能な形で実現すれば、遠くない将来、量子アニーリングが有効に適用できる範囲が大幅に拡大し、さまざまな実社会の課題の解決につながることが期待されるとしている。