A method for exact simulation of quantum dynamics

摘要

We propose a method to simulate exactly quantum dynamics for finite-dimensional quantum systems and analyze its complexity. We apply this method to the exact simulation of any unitary using the dynamics of a time-varying discrete quantum walk on a graph. For this example, in the special case where the graph is a cycle, we show that the complexity grows like NlogN, N being the number of vertices of the graph.