Quantum Institute: Visitor Schedule

The Quantum Lunch is regularly held on Thursdays in the Theoretical Division Conference Room, TA-3, Building 123, Room 121.
For more information, contact Diego Dalvit.
To add your name to the Quantum Lunch email list, contact Charlotte Carter

Thursday, September 10, 2009
12:30 PM - 2:00 PM

Speaker: Andrew Childs, University of Waterloo

Technical Host: Michael Forbes

TOPIC: The relationship between continuous- and discrete-time quantum walk

Abstract
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..