量子コンピュータ関連のアプリケーション開発を行っている研究者や企業の方の負担を減らすために、積極的にベンチマークを取り、結果を共有しております。今回は、500量子ビットのQAOAと呼ばれる組合せ最適化問題を解くための問題のベンチマークです。MAXCUT問題を解いています。
今回実装したのは、
MAXCUT問題
500量子ビット
QAOA
random-3-regularという構造
量子断熱ステップ p=2
実装の際に利用したソフトウェアは、
quimb
cotengra
jax
となっています。ソフトウェアが最適化されていない可能性もありますので、今後の量子ゲート型量子コンピュータのソフトウェア開発の参考にしてもらえればと思います。
今回計算を実行したのは、
GPU
での実装となります。QAOAは量子古典ハイブリッド計算の一つで、組合せ最適化問題を解くために量子コンピュータ向けに開発されたアルゴリズムです。今回は全部計算すると膨大な時間になるので、1サイクルの計算を計測しました。
QAOAは1サイクルで一回の量子回路の計算をします。そして、期待値いう値を求めます。実際の量子コンピュータで期待値を求めようとすると、1サイクルでは済まないのですが、今回はGPUを使ってショートカットをしているため、一回で期待値を求めます。このサイクルを収束するまで続けることでいい結果へと導いていくのがQAOAです。最適化アルゴリズムにはベイズ最適化を利用しました。こちらは普通のコンピュータを利用して行います。
今回の実行結果は約4分でした。1サイクルで4分ですので、例えば100サイクルの最適化を行う場合には400分=6時間40分のように推定ができます。基本的には期待値を求めるための1サイクルの時間はステップごとで変わりません。下記はベイズ最適化された期待値で20ステップを記録しています。今回のベイズ最適は微分をつかわないため、バレンプラトー問題の一部を回避しています。期待値は最適化されて落ちていくのが確認できます。
参考に今回の量子回路をTN表示で確認します。
以上です。