Hamiltonian Simulation by Uniform Spectral Amplification

Abstract

The exponential speedups promised by Hamiltonian simulation on a quantum computer depends crucially on structure in both the Hamiltonian $\hat{H}$, and the quantum circuit $\hat{U}$ that encodes its description. In the quest to better approximate time-evolution $e^{-i\hat{H}t}$ with error $\epsilon$, we motivate a systematic approach to understanding and exploiting structure, in a setting where Hamiltonians are encoded as measurement operators of unitary circuits $\hat{U}$ for generalized measurement. This allows us to define a \emph{uniform spectral amplification} problem on this framework for expanding the spectrum of encoded Hamiltonian with exponentially small distortion. We present general solutions to uniform spectral amplification in a hierarchy where factoring $\hat{U}$ into $n=1,2,3$ unitary oracles represents increasing structural knowledge of the encoding. Combined with structural knowledge of the Hamiltonian, specializing these results allow us simulate time-evolution by $d$-sparse Hamiltonians using $\mathcal{O}\left(t(d\Vert \hat{H}{\Vert }_{\text{max}}\Vert \hat{H}{\Vert }_1{)}^{1/2}\log (t\Vert \hat{H}\Vert /\epsilon )\right)$ queries, where $\Vert \hat{H}\Vert \le \Vert \hat{H}{\Vert }_1\le d\Vert \hat{H}{\Vert }_{\text{max}}$. Up to logarithmic factors, this is a polynomial improvement upon prior art using $\mathcal{O}\left(td\Vert \hat{H}{\Vert }_{\text{max}}+\frac{\log (1/\epsilon )}{\log \log (1/\epsilon )}\right)$ or $\mathcal{O}(t^{3/2}(d\Vert \hat{H}{\Vert }_{\text{max}}\Vert \hat{H}{\Vert }_1\Vert \hat{H}\Vert /\epsilon {)}^{1/2})$ queries. In the process, we also prove a matching lower bound of $\Omega (t(d\Vert \hat{H}{\Vert }_{\text{max}}\Vert \hat{H}{\Vert }_1{)}^{1/2})$ queries, present a distortion-free generalization of spectral gap amplification, and an amplitude amplification algorithm that performs multiplication on unknown state amplitudes.

32 pages, 4 figures

References in corpus (8)

• Quantum algorithm for solving linear systems of equations
• Quantum principal component analysis
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• On the relationship between continuous- and discrete-time quantum walk
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Fixed-point quantum search with an optimal number of queries
• Hamiltonian Simulation with Optimal Sample Complexity

Cited by in corpus (26)

• Emerging quantum computing algorithms for quantum chemistry
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• A randomized quantum algorithm for statistical phase estimation
• Hamiltonian simulation in the low-energy subspace
• Time-marching based quantum solvers for time-dependent linear differential equations
• Quantum linear systems algorithms: a primer
• Quantum Algorithms for Estimating Physical Quantities using Block-Encodings
• On applications of quantum computing to plasma simulations
• Thermal State Preparation via Rounding Promises
• Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms
• Finding Angles for Quantum Signal Processing with Machine Precision
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Scalable Benchmarks for Gate-Based Quantum Computers
• Continuous-variable gate decomposition for the Bose-Hubbard model
• Quantum Regularized Least Squares
• Perturbation theory with quantum signal processing
• Efficient algorithms for quantum information bottleneck
• Well-conditioned multiproduct Hamiltonian simulation
• Hamiltonian simulation for low-energy states with optimal time dependence
• A quantum algorithm for simulating non-sparse Hamiltonians
• Nonlinear transformation of complex amplitudes via quantum singular value transformation
• Nearly-frustration-free ground state preparation
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Quantum linear system algorithm with optimal queries to initial state preparation
• Quantum Machine Learning For Classical Data
• Improving quantum linear system solvers via a gradient descent perspective