PhD Seminar • Quantum Computing — A Quantum Algorithm for Simulating Non-sparse Hamiltonians

Chunhao Wang, PhD candidate
David R. Cheriton School of Computer Science

We present a quantum algorithm for simulating the dynamics of Hamiltonians that are not necessarily sparse. Our algorithm is based on the assumption that the entries of the Hamiltonian are stored in a data structure that allows for the efficient preparation of states that encode the rows of the Hamiltonian. We use a linear combination of quantum walks to achieve a poly-logarithmic dependence on the precision. 

The time complexity measured in terms of circuit depth of our algorithm is $O(t\sqrt{N}\norm{H}\polylog(N, t\norm{H}, 1/\epsilon))$, where $t$ is the evolution time, $N$ is the dimension of the system, and $\epsilon$ is the precision. Our algorithm can directly be applied as a subroutine for unitary implementations and solving linear systems, achieving a $\widetilde{O}(\sqrt{N})$ dependence for both applications.