こんにちは、量子アニーリングマシンは登場してから１０年がたとうとしています。まだ実用的な社会課題が本格的には見つかっておらず、苦労している人も多いと思います。
ここでは、組合せ最適化マシンと思われているD-Waveマシンのモードと本当に最適化が向いているのかどうかを見てみたいと思います。
組合せ最適化問題は速くはならない
量子アニーリングにまつわる誤解の一つとして、理論的に組合せ最適化問題が高速に解けるのではないかというのがあります。これは現在はそうではありません。組合せ最適化問題は量子アニーリングマシンを使っても既存計算機と同様に計算量が指数増大することが分かっており、現在のマシンと比較して高速になるという理論はなく、夢のあるマシンくらいでとらえるのがいいと思います。
Finite temperature quantum annealing solving exponentially small gap problem with non-monotonic success probability
https://www.nature.com/articles/s41467-018-05239-9
とはいいつつ、すでに組合せ最適化問題につぎ込んでしまっている人もいると思いますので、現実的な活用方法を見てみたいと思います。
量子であっても、組合せ最適化問題の計算量は指数増大する。
最適化問題を解くかサンプリング問題を解くか
量子アニーラの活用方法として二種類あります。D-Waveのオリジナルマシンでも両方のモードが用意されています。それが最適化モードとサンプリングモードです。これらのモードを選ぶと、出した答えを後処理し、最適化問題を解いているときに出やすい答えに後処理で近づける処理、もしくはサンプリング問題を解いているときに出やすい答えに後処理で近づける処理をしてくれます。
詳しくはD-Wave社の公式日本語ドキュメントをご覧下さい。
https://dwavejapan.com/app/uploads/2020/02/09-1105A-H_J-DeveloperGuidePostProcessing.pdf
最適化モードは最小エネルギーを求める
最適化モードでは、問題をイジングモデルと呼ばれる物理モデルにマッピングし、その式の最小エネルギーをもって最適解と考え、その最小エネルギーを求めます。そのため、一番小さい答えを探すほうに向かいます。D-Waveでも後処理としてより小さい解があるかどうかの方向に向かいます。
サンプリングモードでは分布を近づける
サンプリングモードでは、問題を必ずしも最小化を求めません。イジングマシンで答えが出る確率は、p(x) = exp(-E)という分布を仮定して、それに近づけるように後処理がされます。ボルツマンマシンと呼ばれる確率分布を利用したモードを利用したい人はこちらを利用することでより理想的な分布に近づくでしょう。逆温度パラメータと呼ばれるパラメータを調整することで分布の形状を変更することができます。
最小化問題にも、機械学習にも
量子アニーラで最小値問題を解くのは結構大変です。サンプリング機械学習など総合的にパフォーマンスを評価する必要があります。以上です。