BLOG
PITE®️の量子優位性
量子化学計算のためのFTQC量子アルゴリズム
「理想的な誤り耐性のある量子コンピュータ(FTQC)において、量子コンピュータが古典コンピュータに比べて優位か？」という問いに対して、「幾つかの問題に対しては優位であり、更にその中の幾つかの問題においては指数的に優位である」という答えが正しいだろう。
それでは現在応用が期待されている量子化学計算において、この問いはどうであろうか？原子や分子などのハミルトニアンの実時間ダイナミクス（実時間発展）と基底状態計算の2つの問題について考えてみる。これらの問題は、古典コンピュータ上で指数関数的な時間を要する。実時間発展はBQP複雑性クラス（図1）に分類されるため、量子コンピュータでは多項式時間で効率的にシミュレーションすることができる。一方で、ハミルトニアンの基底状態を求める問題はQMA複雑性クラスに分類されるため量子コンピュータを用いてさえも指数関数的な時間を要する。
INTRODUCTION
図1. 計算複雑性クラスの関係。
量子位相推定の計算コスト
ここで基底状態計算は、量子位相推定を用いることにより古典アルゴリズムであるFull-CI計算よりも指数関数的に高速になるのではないかと思う読者もいるかもしれない。これはある条件（良い初期状態を用意することができる）が満たされれば正しい。
量子位相推定の量子回路を図2に示す。量子位相推定では、入力される（ハミルトニアンHの）固有状態|ψj>に対応する固有値|Ej>を補助ビットに読み出す。もし、入力される状態が複数の固有状態の重ね合わせであれば、固有値も対応するように複数の固有値の重ね合わせとなる。この複数の重ね合わせの中から興味のある基底エネルギーのみを取り出す場合に、入力状態に含まれる基底状態の比率に応じた繰り返し回数の測定が必要となる。すべての固有状態に対して一様な比率での重ね合わせとして入力状態を考えた場合、計算コストはO(N)であり古典計算機での総当たりと変わらなくなる（Nは固有状態の総数、またはハミルトニアンの次元）。
PHASE ESTIMATION
ちなみに図2の量子回路は複数の制御実時間発展ゲートのシーケンスから構成され、それぞれの制御実時間発展ゲートは多項式時間で実装可能である。また、制御実時間発展ゲートの数も精度に依存してスケーリングするものの基本的には指数的な時間は必要ないと見做して良いだろう。
図2. 量子位相推定のための量子回路。
詳細は例えば[ニールセン・チャン, 量子コンピュータと量子通信, オーム社 (2004)]を参照。
PITE®️の計算コスト
前回のBlog「PITE®️-量子化学計算の新時代-」において、量子化学計算における基底状態計算手法として我々の開発している手法、確率的虚時間発展法（PITE®️）を紹介した。PITE®️の計算コストはどうであろうか？詳細に解析した論文をPhys. Rev. Res.誌にて発表しているH. Nishi et al, Phys. Rev. Research 5, 043048 (2023).。
ここでは簡単に概要について述べる。PITE®️の量子回路構造は量子位相推定と若干類似している。補助ビットを制御ビットとする制御実時間発展ゲートが入力状態に作用するような構造である。補助ビットが所望の状態(|0>状態)である場合に近似的な虚時間発展演算子が作用する。虚時間発展演算子は決定論的に与えられず、確率的である。すべてのステップにおいて虚時間発展演算子が作用する確率、つまり全成功確率は量子位相推定において基底エネルギーを得る確率と等しくなることが導ける。全成功確率Pは全ステップの虚時間発展演算子が作用した状態の波動関数のノルムの大きさで表されるが、虚時間発展演算子により励起状態はすべて減衰されてしまうために基底状態の係数のみが残るためである。
PITE®️
一方で精度については、PITE®️は量子位相推定よりも優れていることが分かっている。図3に計算結果を示す。量子位相推定（緑）よりもPITE®️（青）の方が必要な計算コストが小さいことが確認できる。直感的には次のように理解できる。量子位相推定は補助ビットに読み出す固有値の最小桁数を再現するように高周波の実時間発展が必要となり、それに応じて実時間発展演算子の実装の際に必要なトロッターステップ数も大きくなる。一方で、PITE®️は最小エネルギーと第一励起エネルギー差が区別できる程度の大きさで実時間発展すれば良いため、それに応じてトロッターステップ数を小さくすることができる。
図3. PITE®️と量子位相推定の計算コストの結果。
(左) インフィデリティδと計算コストの関係。
(右) 計算コストと初期状態に含まれる基底状態の係数の絶対値の逆数|c1|-1の関係。
PITE®️も量子位相推定もワーストケースでは古典コンピュータに対して指数関数加速されないことを説明した。これは全成功確率が原因である。しかし、量子コンピュータを使うことにより多項式時間の加速は可能であると期待される。実際に、多項式時間加速は量子振幅増幅（QAA）を組み合わせることで達成される。PITE®️とQAAの併用により、図3の橙線で示されるように計算コストは２乗加速することが可能である。
今回紹介した方法以外にも、量子コンピュータを用いた基底状態計算手法は幾つか存在する。例えば、東京工業大学の西森先生が提唱された量子アニーリングと関連する断熱時間発展E. Farhi et al., arXiv:0001106 (2000).、近年注目を集めるQubitizationに基づくQuantum Eigenvalue Transformation of Unitary matrices with real polynomials (QETU)法であるY. Dong et al., PRX Quantum 3, 040305 (2022).。これらの方法においても同様にワーストケースを考えれば指数関数的な時間を要することが見積もられている。これらの様々な基底状態計算手法を比較・検討することによってどのアルゴリズムがどのような問題に適しているか今後明らかになるかもしれない。
また、古典コンピュータでは指数関数的な計算時間が必要だが、量子コンピュータでは多項式時間で基底状態を得ることができるという仮説、指数量子加速仮説、が成り立つような量子化学の問題はどのようなものか？という問いに対して数値実験により調子した論文も報告されている S. Lee et al., Nature Comm. 14, 1952 (2023).。結果は残念ながら、指数量子加速仮説が成り立つような証拠はまだ見つからなかったという結論であった。しかし今後の研究により指数量子加速仮説が成り立つ問題が見つかるかもしれない。また、多項式時間加速によって基底状態計算における量子コンピュータの実用性が今後更に示されていくことが期待される。
PROSPECTS
