量子アニーラではどのような問題を解決できますか?

D-Wave量子アニーラーは汎用コンピュータではなく、エネルギー最小化として構造化できる問題群しか解けません。そして、そうした問題群においてさえ、D-Waveの従業員は、現世代のD-Waveハードウェアは、標準的なコンピュータに実装されたアルゴリズムを上回る性能を発揮できないことを認めています（ただし、次世代のマシンでは状況が変化する可能性があると楽観視しています）。

しかし、同社が明確な優位性を得る前に自社のマシンの時間を販売してきた主な理由は、開発者に量子アニーリングが効果的であることが証明される問題の種類を特定する機会を与えるためです。先週、ArsはD-Waveユーザーグループのミーティングに出席し、これらのシステムで動作するソフトウェアを開発している人々と話す機会を得ました。また、D-Waveのスタッフとも話をしました。そこで浮かび上がったのは、十分に高度な量子アニーリング装置で実行した場合に明確な速度向上が期待されるような種類のものについて、人々がどのような感覚を抱いているかということでした。

量子アニーリング

D-Waveのシステムは、量子アニーリングと呼ばれるプロセスによって動作します。これは、システムの量子ビットを絶対エネルギー最小値に配置することから始まります。そこから、ハードウェアはシステムの構成を緩やかに変更し、エネルギーランドスケープが解決すべき問題を反映するようにします。すべてがうまくいけば、すべての量子ビットは新しいランドスケープにおいて可能な限り低いエネルギーを持つことになります。文字通りに解釈すると、これはランドスケープにおける最低エネルギー状態を特定することになります。しかし、エネルギーランドスケープが別の何か、つまりエネルギー最小化のように見えるように再構成された別の問題を表している場合、最終状態はその問題の解を表すことになります。

少なくとも、それはそのように動作するはずです。エネルギーランドスケープは山と谷の集合体のように見える傾向があり、システムが絶対最小値ではない谷に閉じ込められる可能性があります。システムは量子効果を利用してこれらの谷から抜け出すことができるはずですが、そのプロセスは決定論的ではなく、時には単に閉じ込められたままになることもあります。場合によっては、これはあまり重要ではありません。良い最小値は最良のものとほぼ同等の価値を持つ場合があるからです。それが重要な場合は、同じ問題を複数回実行し、その頻度によって最適な解を特定することができます。

(また、「逆アニーリング」と呼ばれる方法も実行できます。これは、システムを既知の最小値から開始し、その後解放して、より良い値にトンネルできるかどうかを調べる方法です。)

アニーリング自体は非常に高速なプロセスであり、ほんの一瞬で複数回実行して解をサンプリングすることが可能です。しかし、ここで問題となるのはそれだけではありません。まず、問題の設定と、それを従来のコンピュータから量子アニーリングを実行するハードウェアに転送する際に、ある程度のオーバーヘッドが発生します。また、D-Waveの新しいハードウェアについて説明した際に述べたように、解ける問題の複雑さは、量子ビットの数と量子ビット間の接続に依存します。ここでも、これをエネルギーランドスケープとして考えると分かりやすいでしょう。量子ビットの数が多いほど、一度に探索できるエネルギーランドスケープは広くなります。

アニーリングが直面するもう一つの課題は、古典的なアルゴリズムが絶えず改良されていることです。コーネル大学のFengqi You氏は、計算能力とアルゴリズムの改善により、1988年には124年かかっていた計算が、今では1秒で済むと推定しています。また、D-Wave社のCathy McGeoch氏は、D-Waveハードウェアで得られた初期の成果を受けて、古典的なアルゴリズムの一部が再検討され始め、パフォーマンスが大きく向上したと述べています。

何がうまくいくでしょうか?

これらのアルゴリズムの多くが古典コンピュータ上で優れた性能を示していることを踏まえ、量子アニーリングが明らかな性能優位性を発揮する状況を見つけることが、主要な研究分野の一つとなっています。これらの取り組みの中には、非常に単純なものもあります。量子アニーリングはエネルギー最小化を実行するため、エネルギー最小化が求められる他の状況は、このハードウェア上で適切に動作するアルゴリズムに直接マッピングされるはずです。巡回セールスマン問題やワークフロー最適化など、エネルギー最小化に比較的直接的にマッピングされる最適化問題は数多くあります。

現状の課題は、古典的なアルゴリズムは小規模な最適化問題ではうまく機能する一方で、大規模な問題ではうまく機能しないことが多いことです。量子アニーラはこうした複雑な問題に対して優位性を持つかもしれませんが、現世代のハードウェアには大規模な問題を処理するのに必要な量子ビット数が不足しています。この状況を受けて、多くの人が「ハイブリッドアルゴリズム」の開発に取り組んでいます。これは、一部の処理を従来のコンピュータで実行し、D-Waveハードウェアの恩恵を受けそうな部分をD-Waveで実行するプログラムです。

これは、大規模なエネルギー最小化問題を複数の小さな問題に分割し、それらをD-Waveハードウェアで解くことを意味します。あるいは、古典的な計算を用いて解の集合を求め、量子アニーリングを用いて最適性を検証することも可能です。コーネル大学のYouは、スケジューリング最適化問題において、18個の項目のスケジュール最適化が完全に古典的なシステムでは停止したにもかかわらず、ハイブリッドアプローチでは実行可能であることを実証しました。

ハイブリッドアルゴリズムの場合、古典的アルゴリズムとアニーリングアルゴリズムの世界を行き来するには、D-Waveハードウェアとの定期的な通信が必要になります。これが、同社が通信の遅延を削減しようと試みる動機となりました。さらに同社は、問題をより小さな部分に分割する最適な方法を特定するプロセスを容易にするソフトウェアの開発に取り組んでいます。D-Waveのアラン・バラッツ氏はArsに対し、「D-Waveハイブリッド」フレームワークを開発中であると述べました。

人々が採用しているもう一つのアプローチは、最高の古典的アルゴリズムでさえ、速度が低下したり完全に失敗したりするケースのサブセットが存在するという事実に注目することです。これは、アルゴリズムが非常に大きな問題を逐次的に探索しなければならない場合によく発生し、膨大な時間がかかったり、利用可能なメモリ容量を超えたりすることがあります。カーネギーメロン大学のSridhar Tayur氏は、非線形最適化においてこのようなケースを発見しました。ハイブリッドアルゴリズムではD-Waveマシンを2～3回呼び出すだけで最適化を見つけることができましたが、古典的アルゴリズムでは問題を解くのに約8時間かかりました。

しかし、課題は、問題が従来のアルゴリズムでは処理が追いつかないケースに該当するかどうかを判断することです。その判断にかかる時間は、ハイブリッドアルゴリズムで問題を解くのにかかる時間に追加され、量子アニーリングの利点を打ち消す可能性があります。

量子ビットに近づく

会議に参加した他の人々は、D-Waveハードウェアの性能をさらに引き出すための代替アプローチについて議論し、量子アニーラー上で動作するように問題をどのように構造化するかに焦点を当てました。一つの選択肢として、問題をイジング・ハミルトニアンと呼ばれるものを使って構造化することが挙げられます。メリーランド大学ボルチモア・カウンティ校のラミン・アヤンザデ氏は、単一の問題を複数のイジング・ハミルトニアンを用いて表現することは可能だが、D-Waveハードウェア上でどのハミルトニアンが最も優れた性能を発揮するかは事前に明らかではないと述べました。彼は機械学習を用いて、量子アニーラーに最適な定式化を特定する方法があるかどうかを検討しています。

イジングハミルトニアンは、いわゆる二次制約なし二項最適化問題（QUBO）に変換することもできます。現在ハーバード大学に在籍するジョージ・ハーン氏は、ロスアラモス研究所で行ったQUBOの構造に関する研究について講演しました。ハーン氏は、QUBO内の特定の項を定数に置き換えることができる場合や、2つの項の間に一貫した関係がある場合を特定できることを発見しました。これによりQUBOを簡略化することができ、より大きな問題をD-Waveのハードウェアに収まる可能性が高まります。

リスト画像: D-Wave