2026年10月19日（月）13:30- (13:30-, October 19, 2026)

理学部1号館206教室 (Room No. 206, Science Bldg. 1) 

Speaker: Jun Takahashi (ISSP, Univ. of Tokyo )
Title: Efficient quantum algorithms via Lee-Yang theorems for spin and fermionic systems 

Abstract: 

Computing the ground state energy for general quantum many-body systems is known to be QMA-hard, i.e. a computationally hard problem even for quantum computers in the worst case. Despite this complexity theoretic obstacle, physicists have made substantial progress in understanding many-body systems in various ways, which suggests that restricted to an appropriate physically motivated class, many of the problems should actually be computationally feasible in some sense. 

In this talk, I will explain several recent works showing that indeed, there is a natural yet broad class of many-body Hamiltonians, which we dub “Lee-Yang”, that we can prove to be efficiently solvable (in terms of the ground state energy problem) by quantum computers (i.e. contained in the complexity class BQP). The key concept for our work dates back to the theorem proven by Lee and Yang in 1952 [1] which states that all zeros of the partition function lie on the imaginary axis for ferromagnetic Ising models, regardless of the interaction structure (e.g. in any dimension, with any coefficients). I will explain how this theorem, originally viewed as a way to rigorously prove statements on phase transitions, has recently gained attention in theoretical computer science for its deeper connections to classical algorithmic efficiency, and most recently, resulted in our quantum algorithm efficiency [2].

For the technical part of the talk, I will first go through the proof sketch of [2], where we show, via imaginary-time correlation decay, that the quantum extensions of the Lee-Yang theorem [3] imply a spectral gap of the corresponding hamiltonian that is lower bounded by h/4 when the system is under uniform magnetic field of strength h. This result then implies that an adiabatic quantum algorithm can compute the ground state energy of Lee-Yang Hamiltonians up to inverse polynomial precision in polynomial time. Then, if time permits, I will explain that we can obtain Lee-Yang-type theorems for interacting fermionic systems as well [4], providing a quantum algorithm for the ground state energy problem for this class of interacting fermion models at arbitrary interaction strengths, going beyond previously studied perturbative regimes.

[1] T. D. Lee and C. N. Yang, Phys. Rev., 87 (3) 410 (1952)
[2] C. Rayudu and J. Takahashi, arXiv:2607.10765
[3] T. Asano, J. Phys. Soc. Jpn., 29 (2) 350 (1970); M. Suzuki and M. E. Fisher, J. Math. Phys., 12 (2) 235 (1971)
[4] C. Rayudu, T. Misawa, A. Zhao, and J. Takahashi, arXiv:2609.23942