今日は量子コンピューターを使ってQAOAを好きな人がいますよね。最近でもQAOAを使った研究が続けられていて、組合せ最適か問題が量子コンピューター上で研究されています。今回はそうしたテクニックを使った専用のシュミレーターの話となっています。 論文はこちら、 Fast Simulation of High-Depth QAOA CircuitsDanylo Lykov, Ruslan Shaydulin, Yue Sun, Yuri Alexeev, Marco Pistoia<a href="https://arxiv.org/abs/2309.04841" rel="noopener noreferrer" target="_blank">https://arxiv.org/abs/2309.04841</a> 今回のシミュレータは、QAOAパラメーター最適化の計算コストを削減する目的で設計されており、CPUとGPUの実行の両方をサポートしています。QAOAの量子状態のシミュレーションと最適化すべきQAOAの目的関数の計算の両方の計算コストは、問題をエンコードする対角ハミルトニアンを事前に計算することで削減できるということです。このシミュレータは、cuQuantumの最先端のGPU量子回路シミュレーターと比較して、典型的なQAOAパラメーター最適化の時間をn = 26量子ビットの場合に11倍短縮したということです。 こちらにシミュレータが公開されています。<a href="https://github.com/jpmorganchase/QOKit" rel="noopener noreferrer" target="_blank">https://github.com/jpmorganchase/QOKit</a> なんかちょっと最近サボってる間に色んなQAOA周りの論文が出てたみたいです。 QAOAがランダムな8-SAT問題において、最先端の古典的ソルバーよりも優れたスケーリングを示すことを数値的に実証QAOAでの量子スピードアップがp ≳ 14の場合にのみ観測されることを指摘Solving boolean satisfiability problems with the quantum approximate optimization algorithmSami Boulebnane, Ashley Montanaro<a href="https://arxiv.org/abs/2208.06909" rel="noopener noreferrer" target="_blank">https://arxiv.org/abs/2208.06909</a> よく見たら筆頭著者が知り合いでした。。。 QAOAが3-正規グラフ上のMaxCut問題において古典的ソルバーと競争するためには、p ≥ 12が必要であることを指摘Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm Danylo Lykov, Jonathan Wurtz, Cody Poole, Mark Saffman, Tom Noel &amp; Yuri Alexeev<a href="https://www.nature.com/articles/s41534-023-00718-4" rel="noopener noreferrer" target="_blank">https://www.nature.com/articles/s41534-023-00718-4</a> 本シミュレータは深いQAOAのシミュレーションや、QAOAパラメータの調整に必要なQAOA目的関数の繰り返し評価を最適化するために設計。シミュレーションを加速するために、最初に最適化すべき関数の値を事前計算。事前計算の結果は、パラメータ最適化中に再利用。 この事前計算アルゴリズムは並列化が容易でGPUに最適。事前計算には指数関数的に大きなベクトルを保存する必要があり、シミュレーションのメモリフットプリントを12.5%増加。一般的なテクニックで、横磁場やxyミキサーも実装可能。1,024GPUまでのスケーラビリティ。 なんか、古典ソルバーに対するQAOAの優位性に関する論文は下記のようです。 Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable ProblemRuslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky, Marco Pistoia<a href="https://arxiv.org/abs/2308.02342" rel="noopener noreferrer" target="_blank">https://arxiv.org/abs/2308.02342</a> あんまり深く考えないで論文を見ていきます。本論文では、MaxcutとLABS問題が与えられています。LABSは聞いたことがないので、今度調べますが、コスト関数が与えられています。 おじさんなので、知りませんでしたがコストハミルトニアンのことをフェーズ演算子と表現してました。書き方は難しく書いてありますが普通のQAOAです。その他も全部普通のQAOAの話でした。 ここで、今回のシミュレータの話です。基本的にはフェーズ演算子の構造に着目し、イジングZZやZの構造に着目して状態ベクトルシミュレータへの計算コストを削減するようです。 コストベクトルの事前計算コスト関数については全部が対角行列で描かれるので、事前にこれらを状態ベクトルにかけられるように用意しておき、それを使って状態ベクトルと内積を取れば計算が終わるように事前計算をします。そうすることによって、いちいち毎回量子ゲートを反復的に計算する必要がなく、毎回同じ計算をして、それにQAOAの変分パラメータをかければ終わります。 混合演算子こちらは状態ベクトルの計算については、並列かを使って効率化できないので、地道に計算です。 分散計算GPUが圧倒的に速いので、分散計算にCPUは使わないようです。GPUそれぞれ初期の量子ビットの値によって分割して保持させるようです。フェーズ演算子については、GPU間の計算が不要で、ほとんどは混合演算子に依存するそうです。混合演算子の並列処理は難しそうなので、その際にはcuStateVecをフル活用しているようです。 どうやら、同様の論文が2021年に出ていたようです。 Quantum annealing initialization of the quantum approximate optimization algorithmStefan H. Sack, Maksym Serbyn<a href="https://arxiv.org/abs/2101.05742" rel="noopener noreferrer" target="_blank">https://arxiv.org/abs/2101.05742</a> フェーズ演算子・コストハミルトニアンの計算を対角行列で書かれてることから事前計算を行い、単一のベクトルの形にしておき、コストハミルトニアンの時間発展計算において反復的にゲート計算をしなくても高速にシミュレーションできるという論文の紹介となりました。以上です。

[論文解説]深いQAOA量子回路の高速シミュレーション手法の論文

Yuichiro Minato