Speaker
Description
$N$個のqubitが相互作用するハミルトニアンを与えられて、それの基底エネルギーを計算する問題は一般に${\sf QMA}$完全（${\sf NP}$完全の量子版）であり非常に難しい。この計算論的困難さは例えば物性物理において種々の模型上でスピン液体状態が実現されているかを巡って長年論争が続く一因だとも言える。けれども考慮するハミルトニアンを限定すれば、それなりに簡単な問題になる場合もある。例えば、ハミルトニアンがパウリ$Z$による相互作用のみを持つ場合を考えれば、これは古典的な最適化問題なので、$\sf{QMA}$など量子的な複雑性クラスにはなれず、${\sf NP}$完全にしかならないことが知られている。
このようなハミルトニアンの制限の中でも興味深いクラスが “stoquastic” と呼ばれる部分集合であり、これは$Z$基底で書いたときにハミルトニアンの非対角項が全て非正なハミルトニアンと定義される[1]。D-wave社のアニーリングマシンはstoquasticなハミルトニアンのみ扱っているので、当時「完全な量子ではない」と批判されたのであった。Stoquasticなハミルトニアンの基底エネルギー計算は「最大限に量子的」な${\sf QMA}$完全にはならず、${\sf StoqMA}$完全という${\sf QMA}$と${\sf NP}$の間の謎のクラスになり、しかもlocalなハミルトニアンの計算複雑性はこの三種類のクラスに限られることが証明されている[2]。${\sf NP}$は既に計算困難なクラスなので、${\sf StoqMA}$完全な場合も一般には難しい。けれども、自然に登場するstoquasticなハミルトニアンに関しては、その基底状態などを計算する量子/古典アルゴリズムがあるのか否かについて近年盛んに研究されるようになっている[3]。
本講演では，計算物理の現場で言われる「量子モンテカルロ法（QMC）を用いれば一部のstoquasticなハミルトニアンは素早くシミュレートできる」[4]という経験則を厳密に多項式時間緩和という定式化によって証明した最近の成果[5,6]を解説する。また、時間があればLee-Yangの定理を用いることで量子コンピュータ(アニーリングマシン)によって効率的に解けると新たに証明できたハミルトニアンのクラス[7]についても解説する。
これらの証明は全て、巨大な行列の固有値にギャップが開いていることを示している、という共通点がある。Haldane予想が半世紀近くに渡って未解決であることを踏まえると分かるように、このようなギャップの証明は通常、非常に困難である。QMCの多項式時間証明ではJerrumとSinclairがGödel賞を獲ったcanonical pathという証明手法、量子断熱アルゴリズムの証明ではLee-Yangの定理の(Asano, Suzuki-Fisherによる)量子拡張定理を用いることでそのようなギャップ証明が可能になる概略を説明する。
参考文献
[1] S. Bravyi, A. J. Bessen, and B. M. Terhal, arXiv:quant-ph/0611021 (2006).
[2] T. Cubitt and A. Montanaro, SIAM J. Comput. 45, 268 (2016).
[3] S. Piddock and A. Montanaro, Quan Inf Comput 17:636 (2016); K. Marwaha and J. Sud, arXiv:2604.13026; S. Gharibian, ACM SIGACT News 54, 54 (2024). Open question 3.4
[4] For example: B. Zhao, J. Takahashi, & A. W. Sandvik, PRL 125 (25), 257204 (2020) など
[5] J. Takahashi, S. Slezak, & E. Crosson, arXiv:2411.01452, Talk at QIP 2025.
[6] C. Rayudu and J. Takahashi, arXiv:2509.21683.
[7] C. Rayudu and J. Takahashi, arXiv:2607.10765.