とにかく毎日頑張っています。量子アニーリングから量子ゲートの最新動向まで、離散数理最適化問題として組合せ最適化問題の最新を追ってみます。2020年12月です。
１、量子アニーリングからスタート
量子計算をつかってイジングモデルを使うことで組合せ最適化問題を解くのは有名です。アナログマシンとして有名なのがカナダのD-Wave社です。イジング定式化をすることで離散最適化を解くことができます。ドライバーハミルトニアンと呼ばれる探索を司る部分については、D-Waveで実装されているのは、横磁場と呼ばれるタイプに限定されています。
２、量子ゲートでのNISQ変分アルゴリズムQAOA
上記量子アニーリングと同時期のアイデアで、別方面の見方をしている量子断熱計算をつかって、広義の量子アニーリングをGoogleやIBMなどのマシン向けに理論開発されたのがQAOAです。量子変分原理と呼ばれる原理をつかったVQEを改造して、量子アニーリングをデジタルでステップ分解したようなアルゴリズムのパラメータを最適化するものです。
途中で、Quantum Alternating Operator Ansatzと呼ばれる理論が開発され、ドライバーハミルトニアンが横磁場以外が利用できるようになり、主に最近はXYmixerが使われています。これを使うと特定の制約条件を量子もつれを使うことで、正答率が大幅に上がることがわかりました。こちらのドライバーハミルトニアンはD-Waveではハードウェア的にはかけることができないので、量子ゲートの将来的な大きなアドバンテージになります。
QAOAは量子回路が長いのと相互作用が多いので、実機の量子コンピュータで実行されることはほぼありませんでした。QAOAは日の目を見ることなく廃れていくのか、もう少し実機が出たら実行されるのかは、次の汎用量子コンピュータの流れと合わせて今後の注目ポイントです。
３、汎用量子コンピュータ
NISQでのQAOAが厳しかったので、次は誤り訂正汎用量子コンピュータの出番です。上記のQAOAではなく、より理論に忠実な形での実装が進みます。時間発展と呼ばれる手法で、ステップ数に応じて回路を分解して汎用計算します。もちろん実行は厳しいのですが、どうせQAOAもうまく行かないなら、最初からこっちでいい気もします。
４、グローバー
とりあえずグローバーのアルゴリズムもあまり組合せ最適化に対して開発が進んでいないので、速度はあまり出ないのですが、研究は多少はやる人もいるのではないでしょうか。期待です。
まとめ
量子アニーリングからスタートした離散最適化の流れですが、個人的な見解としてはQAOAはNISQアルゴリズムとして実行していい面は、Quantum Alternating Operator Ansatzの発見で一定の成果を収めた以外は実装していいことは速度面でもあまりないのかなという印象を受けます。今後は量子断熱計算をスケジュールを含めて、汎用量子コンピュータで突き詰めていく段階に突入するのではないかと思っています。量子アニーリングからQAOAから汎用量子計算（量子断熱orグローバー）へ移行です。以上です。