 |
Center for Nonlinear Studies |
Quantum walk is one of the main tools for quantum algorithms. Defined by analogy to classical random walk, a quantum walk is a time-homogeneous quantum process on a graph. Both random and quantum walks can be defined either in continuous or discrete time. However, whereas a continuous-time random walk can be obtained as the limit of a sequence of discrete-time random walks, the two types of quantum walk appear fundamentally different, owing to the need for extra degrees of freedom in the discrete-time case. In this talk, I will describe a precise correspondence between continuous- and discrete-time quantum walks on arbitrary graphs. This provides a description of continuous-time quantum walk as a certain limit of discrete-time quantum walks, and also leads to improved methods for simulating Hamiltonian dynamics. In particular, there is a simulation whose complexity grows linearly with the total evolution time and that does not necessarily require the Hamiltonian to be sparse.
Host: Michael Forbes