Lab Home  Phone  Search  


Quantum walk is one of the main tools for quantum algorithms. Defined by analogy to classical random walk, a quantum walk is a timehomogeneous quantum process on a graph. Both random and quantum walks can be defined either in continuous or discrete time. However, whereas a continuoustime random walk can be obtained as the limit of a sequence of discretetime random walks, the two types of quantum walk appear fundamentally different, owing to the need for extra degrees of freedom in the discretetime case. In this talk, I will describe a precise correspondence between continuous and discretetime quantum walks on arbitrary graphs. This provides a description of continuoustime quantum walk as a certain limit of discretetime 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 