量子コンピュータにおける組合せ最適化問題はどの程度のフェーズか。そして学ぶための３つのステップ。

量子コンピュータと組合せ最適化問題を取り巻く環境は大きく変化しつつあります。これまでの大規模問題を解いて実用化を目指すフェーズから、基礎研究に戻り、より数理最適化を理解しようという試みに各社向いています。

BMW社はhoneywellマシンやawsにおけるコンテストなどを開催しています。VWはIonQを利用した組合せ最適化問題に取り組むなど、実用化から大きく後退はしますが、より高度な技術の習得に進んでいます。

https://crowd-innovation.bmwgroup.com/servlet/hype/IMT?documentTableId=7025714350976785060&userAction=Browse&templateName=&documentId=740c3d47812c470b208a495d85f18206

量子コンピュータにおける組合せ最適化問題を解くための手法は現在二つあります。

一つは量子断熱計算、もう一つは振幅増幅計算です。それぞれは異なるアプローチとなっています。

一般的には前者の量子断熱計算を使います。

理論的な内容、概要は下記のAISpiritsさんの記事をご覧ください。

量子アルゴリズム QAA、イジングモデル、QUBO

https://aispirits.com/2021/05/01/%e9%87%8f%e5%ad%90%e3%82%a2%e3%83%ab%e3%82%b4%e3%83%aa%e3%82%ba%e3%83%a0-qaa%e3%80%81%e3%82%a4%e3%82%b8%e3%83%b3%e3%82%b0%e3%83%a2%e3%83%87%e3%83%ab%e3%80%81qubo/

量子アルゴリズム QAOA

https://aispirits.com/2021/04/26/%e9%87%8f%e5%ad%90%e3%82%a2%e3%83%ab%e3%82%b4%e3%83%aa%e3%82%ba%e3%83%a0-qaoa/

現在は量子コンピュータの性能的にQAOAを理論として利用することが多いです。学ぶのはなかなか骨が折れますが、

１，社会問題のイジングモデル・QUBOへの定式化

２，QAOAアルゴリズムと固有値の理解

３，QAOAアルゴリズムの精度を上げるためのmixerと初期状態の理解

こちらを学ぶことが必要です。

１，社会問題のイジングモデル・QUBOへの定式化

こちらは社会問題をQUBOと呼ばれる01で記述される定式化を行います。量子ゲートではサイズが小さいのでmatrixの形よりは方程式の形式に書きます。QUBOの定式化をイジング定式化と呼ばれる-1と+1を使った形に変換する必要もありますが、そのあたりもふつうはミドルウェアで処理します。

２，QAOAアルゴリズムと固有値の理解

QAOAで理解するのは人によってはこのステップかもしれません。組合せ最適化問題を量子コンピュータで効率的に解くには、QAOAを利用しますが、これは量子断熱計算の仕組みを理解することが必要です。また、問題設定をした上記QUBOハミルトニアンの固有値を求めますので、どのような仕組みで固有値まで導き出されて、問題を解くためにどのような定式化が必要なのかを理解する必要があります。この段階で初期状態や探索方法は極めて一般的な方法を使いますし、ツールも最近は出ていますので理解を後にしてとりあえず使ってみるということもできます。

３，QAOAアルゴリズムの精度を上げるためのmixerと初期状態の理解

さらに応用に行くには、探索方法を変更する必要があります。これは組合せ最適化問題におけるソフト制約とハード制約の考えた方で、量子回路を工夫することでソフト制約をハード制約にして制約をかけることができます。これらにはさらに固有値問題や、探索をつかさどるmixerハミルトニアンに対する理解が必要となります。

このように量子コンピュータはさらに組合せ最適化問題を理解し、解くために日々基礎研究に戻ってきました。大規模社会問題を解く時代から、小規模社会問題をどのように量子コンピュータにプログラミングするのか、量子回路を工夫して効率化するのかが見どころとなります。

以上です。