A quantum algorithm for simulating non-sparse hamiltonians

Chunhao Wang, Leonard Wossnig

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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 Õ(√N) dependence for both applications.

Original languageEnglish (US)
Pages (from-to)597-615
Number of pages19
JournalQuantum Information and Computation
Issue number7-8
StatePublished - 2020

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistical and Nonlinear Physics
  • Nuclear and High Energy Physics
  • Mathematical Physics
  • General Physics and Astronomy
  • Computational Theory and Mathematics


Dive into the research topics of 'A quantum algorithm for simulating non-sparse hamiltonians'. Together they form a unique fingerprint.

Cite this