# A quantum algorithm for simulating non-sparse Hamiltonians

arXiv: https://arxiv.org/abs/1803.08273 · HTML: https://mlsanity.com/paper/1803.08273/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Mar 2018.

## Built on by (most cited first, 2 of 2)

- [Quantum Machine Learning For Classical Data](https://mlsanity.com/paper/2105.03684/) (2021)
- [An Introduction to Quantum Computing for Statisticians and Data Scientists](https://mlsanity.com/paper/2112.06587/) (2021)

## Abstract (arXiv)

We present a quantum algorithm for simulating the dynamics of Hamiltonians that are not necessarily sparse. Our algorithm is based on the input model where the entries of the Hamiltonian are stored in a data structure in a quantum random access memory (qRAM) which allows for the efficient preparation of states that encode the rows of the Hamiltonian. We use a linear combination of quantum walks to achieve poly-logarithmic dependence on precision. The time complexity of our algorithm, measured in terms of the circuit depth, is O(t√N|H|,polylog(N, t|H|, 1/ε)), where t is the evolution time, N is the dimension of the system, and ε is the error in the final state, which we call precision. Our algorithm can be directly applied as a subroutine for unitary implementation and quantum linear systems solvers, achieving widetildeO(√N) dependence for both applications.