Lower bounds for adiabatic quantum algorithms by quantum speed limits, Jyong-Hao Chen [陳炯豪], NCU

Tuesday 26 May 2026, 13:30 → 15:30 Asia/Taipei

Physics/124

Adiabatic quantum computation is often analyzed through spectral gaps, but gap
estimates can be difficult to obtain for many algorithms of interest. In this talk, I will
present a complementary approach based on quantum speed limits. The key idea is to
derive lower bounds on the runtime of adiabatic quantum algorithms from the
distinguishability between the initial state and the target ground state. Remarkably, the
resulting bound can be expressed through a simple quantity: the variance of the final
Hamiltonian with respect to the initial state. I will illustrate how this framework
reproduces known scaling results for standard adiabatic algorithms and how it can be
applied to problems whose quantum speedup is less clear, including the problem of
finding k-cliques in random graphs. I will also discuss its connection with the
conventional spectral-gap approach.