Hamiltonian simulation for low-energy states with optimal time dependence

Abstract

We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. Assuming access to a block-encoding of $H'=(H-E)/λ$ for some $E \in \mathbb R$, the goal is to implement an $ε$-approximation to $e^{-itH}$ when the initial state is confined to the subspace corresponding to eigenvalues $[-1, -1+Δ/λ]$ of $H'$. We present a quantum algorithm that uses $O(t\sqrt{λΓ} + \sqrt{λ/Γ}\log(1/ε))$ queries to the block-encoding for any $Γ$ such that $Δ\leq Γ\leq λ$. When $\log(1/ε) = o(tλ)$ and $Δ/λ= o(1)$, this result improves over generic methods with query complexity $Ω(tλ)$. Our quantum algorithm leverages spectral gap amplification and the quantum singular value transform. Using standard access models for $H$, we show that the ability to efficiently block-encode $H'$ is equivalent to $H$ being what we refer to as a "gap-amplifiable" Hamiltonian. This includes physically relevant examples such as frustration-free systems, and it encompasses all previously considered settings of low-energy simulation algorithms. We also provide lower bounds for low-energy simulation. In the worst case, we show that the low-energy condition cannot be used to improve the runtime of Hamiltonian simulation. For gap-amplifiable Hamiltonians, we prove that our algorithm is tight in the query model with respect to $t$, $Δ$, and $λ$. In the practically relevant regime where $\log (1/ε) = o(tΔ)$ and $Δ/λ= o(1)$, we also prove a matching lower bound in gate complexity (up to log factors). To establish the query lower bounds, we consider $\mathrm{PARITY}\circ\mathrm{OR}$ and degree bounds on trigonometric polynomials. To establish the lower bound on gate complexity, we use a circuit-to-Hamiltonian reduction acting on a low-energy state.