Random walks have been discussed in the quantum regime in two very different ways. The continuous time quantum walk is over a vertex space the same size as the original graph, whereas the discrete walk requires two copies of the original vertex space. In the discrete case, this necessity arises due to reflections in Hilbert space.

Quantum searching, Markov chain quantization and fermion Monte Carlo all share similar structures. In this talk, I will use projection operators to demonstrate how the discrete time quantum walk can be reduced to a single vertex space, thereby providing a new connection between discrete and continuous time quantum walks.

Speaker:
J. D. Whitfield
NEC Labs America, Quantum Information Technology Columbia University, Physics Department

web: www.nec-labs.com/~whitfield