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^{\prime }=(H-E)/\lambda$ for some $E\in \mathbb{R}$, the goal is to implement an $\epsilon$-approximation to $e^{-itH}$ when the initial state is confined to the subspace corresponding to eigenvalues $[-1,-1+\Delta /\lambda ]$ of $H^{\prime }$. We present a quantum algorithm that uses $O(t\sqrt{\lambda \Gamma }+\sqrt{\lambda /\Gamma }\log (1/\epsilon ))$ queries to the block-encoding for any $\Gamma$ such that $\Delta \le \Gamma \le \lambda$. When $\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. Using standard access models for $H$, we show that the ability to efficiently block-encode $H^{\prime }$ 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$, $\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 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.

58 pages. Abstract shortened to fit within the arXiv limit

References in corpus (8)

• Simulated Quantum Computation of Molecular Energies
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Spatial search by quantum walk
• The computational difficulty of finding MPS ground states
• Fast quantum computation at arbitrarily low energy
• Hamiltonian Simulation by Uniform Spectral Amplification
• Complexity of Digital Quantum Simulation in the Low-Energy Subspace: Applications and a Lower Bound
• Tight Bounds for Quantum Phase Estimation and Related Problems

Cited by in corpus (6)

• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Fast quantum simulation of electronic structure by spectrum amplification
• Trotterization is substantially efficient for low-energy states
• Exponential distillation of dominant eigenproperties
• Discrete Superconvergence Analysis for Quantum Magnus Algorithms of Unbounded Hamiltonian Simulation
• Comprehensive Study on Heisenberg-limited Quantum Algorithms for Multiple Observables Estimation