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.

arXiv comment58 pages. Abstract shortened to fit within the arXiv limit

References in corpus (37)

• Adiabatic Quantum Computing
• Simulated Quantum Computation of Molecular Energies
• Hamiltonian Simulation by Qubitization
• Towards Quantum Chemistry on a Quantum Computer
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Spatial search by quantum walk
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Computation by Adiabatic Evolution
• Quantum Algorithms for Quantum Field Theories
• A Theory of Trotter Error
• Simulating Physical Phenomena by Quantum Networks
• A random compiler for fast Hamiltonian simulation
• Negative weights make adversaries stronger
• Exponential improvement in precision for simulating sparse Hamiltonians
• Higher Order Decompositions of Ordered Operator Exponentials
• Exponentially more precise quantum simulation of fermions I: Quantum chemistry in second quantization
• Quantum algorithm for simulating real time evolution of lattice Hamiltonians
• Hamiltonian simulation in the low-energy subspace
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• Exponentially More Precise Quantum Simulation of Fermions in the Configuration Interaction Representation
• Faster Digital Quantum Simulation by Symmetry Protection
• Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
• The computational difficulty of finding MPS ground states
• Fast quantum computation at arbitrarily low energy
• Hamiltonian Simulation by Uniform Spectral Amplification
• Spectral Gap Amplification
• A Trotter-Suzuki approximation for Lie groups with applications to Hamiltonian simulation
• Solving frustration-free spin systems
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Quantum simulations of one dimensional quantum systems
• Ground-State Spaces of Frustration-Free Hamiltonians
• Complexity of Digital Quantum Simulation in the Low-Energy Subspace: Applications and a Lower Bound
• Tight Bounds for Quantum Phase Estimation and Related Problems
• Nearly-frustration-free ground state preparation

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