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)/\lambda$, for some $\lambda \gt 0$ and $E \in \mathbb R$, the goal is to implement an $\epsilon$-approximation to the evolution operator $e^{-itH}$ when the initial state is confined to the subspace corresponding to eigenvalues $[-1, -1+\Delta/\lambda]$ of $H'$, for $\Delta \leq \lambda$. We present a quantum algorithm that requires $\mathcal{O}(t\sqrt{\lambda\Gamma} + \sqrt{\lambda/\Gamma}\log(1/\epsilon))$ queries to the block-encoding for any choice of $\Gamma$ such that $\Delta \leq \Gamma \leq \lambda$. When the parameters satisfy $\log(1/\epsilon) = o(t\lambda)$ and $\Delta/\lambda = o(1)$, this result improves over generic methods with query complexity $\Omega(t\lambda)$. Our quantum algorithm leverages spectral gap amplification and the quantum singular value transform. For a given $H$, the block-encoding of its $H'$ must be prepared efficiently to achieve an asymptotic speedup in simulating the low-energy subspace; we refer to these Hamiltonians as $gap-amplifiable$. We show necessary and sufficient conditions for gap amplifiability in terms of an operationally useful decomposition of $H$ into a sum of squares. Gap-amplifiable Hamiltonians include physically relevant examples such as frustration-free systems, and it encompasses all previously considered settings of low energy simulation algorithms. Any Hamiltonian can be expressed as a gap-amplifiable Hamiltonian after simple transformations, and our algorithm retains the asymptotic improvement over generic methods as long as the conditions on the parameters are met. We also provide lower bounds for simulating dynamics of low-energy states. In the worst case, we show that the low-energy condition cannot be used to improve the runtime of Hamiltonian simulation methods. For gap-amplifiable Hamiltonians, we prove that our algorithm is tight in the query model with respect to $t$, $\Delta$, and $\lambda$. In the practically relevant regime where $\log (1/\epsilon) = o(t\Delta)$ and $\Delta/\lambda = o(1)$, we also prove a matching lower bound in gate complexity (up to logarithmic factors). To establish the query lower bounds, we consider oracular problems including search and $\mathrm{PARITY}\circ\mathrm{OR}$, and also bounds on the degrees of trigonometric polynomials. To establish the lower bound on gate complexity, we use a circuit-to-Hamiltonian reduction, where a “clock Hamiltonian'' acting on a low-energy state can simulate any quantum circuit.