Hamiltonian simulation with nearly optimal dependence on spectral norm

Abstract

We present a quantum algorithm for approximating the real time evolution $e^{-iHt}$ of an arbitrary $d$-sparse Hamiltonian to error $\epsilon$, given black-box access to the positions and $b$-bit values of its non-zero matrix entries. The complexity of our algorithm is $\mathcal{O}((t\sqrt{d}\Vert H{\Vert }_{1\to 2}{)}^{1+o(1)}/{\epsilon }^{o(1)})$ queries and a factor $\mathcal{O}(b)$ more gates, which is shown to be optimal up to subpolynomial factors through a matching query lower bound. This provides a polynomial speedup in sparsity for the common case where the spectral norm $\Vert H\Vert \ge \Vert H{\Vert }_{1\to 2}$ is known, and generalizes previous approaches which achieve optimal scaling, but with respect to more restrictive parameters. By exploiting knowledge of the spectral norm, our algorithm solves the black-box unitary implementation problem -- $\mathcal{O}(d^{1/2+o(1)})$ queries suffice to approximate any $d$-sparse unitary in the black-box setting, which matches the quantum search lower bound of $\Omega (\sqrt{d})$ queries and improves upon prior art [Berry and Childs, QIP 2010] of $\tilde{\mathcal{O}}(d^{2/3})$ queries. Combined with known techniques, we also solve systems of sparse linear equations with condition number $\kappa$ using $\mathcal{O}((\kappa \sqrt{d}{)}^{1+o(1)}/{\epsilon }^{o(1)})$ queries, which is a quadratic improvement in sparsity.

arXiv comment26 pages, 2 figures

References in corpus (15)

• Quantum algorithm for solving linear systems of equations
• Perfect state transfer in quantum spin networks
• Quantum random access memory
• Exponential algorithmic speedup by quantum walk
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Toward the first quantum simulation with quantum speedup
• On the relationship between continuous- and discrete-time quantum walk
• Hamiltonian complexity
• Black-box quantum state preparation without arithmetic
• Simulating sparse Hamiltonians with star decompositions
• Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
• Efficient quantum circuits for arbitrary sparse unitaries

Cited by in corpus (20)

• Quantum computational chemistry
• Quantum Chemistry in the Age of Quantum Computing
• Hamiltonian Simulation by Qubitization
• Quantum algorithms for quantum chemistry and quantum materials science
• A Theory of Trotter Error
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Provably accurate simulation of gauge theories and bosonic systems
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• Time-marching based quantum solvers for time-dependent linear differential equations
• Towards quantum advantage via topological data analysis
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Faster quantum and classical SDP approximations for quadratic binary optimization
• A quantum hamiltonian simulation benchmark
• Quantum differential equation solvers: limitations and fast-forwarding
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Hamiltonian simulation for low-energy states with optimal time dependence
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Selection and improvement of product formulae for best performance of quantum simulation
• Perturbational Decomposition Analysis for Quantum Ising Model with Weak Transverse Fields