Mark Hillery, The City University of New York
Abstract
A quantum walk is a quantum version of a classical random walk. It can take place on a line or on a more general graph. There are a number of different kinds of quantum walks, and a brief introduction to them will be given. Quantum walks can serve as the basis for quantum searches; one vertex has different properties than the others, and the object of the search is to find it. One way to approach quantum walks is by the use of scattering theory. A particle enters a graph and can either be reflected from it or transmitted through it. The functions describing the transmission and reflection contain a great deal of information about the walk. This approach is useful when combining graphs; it allows one to find the scattering properties of the combined graph from those of its parts. It also allows one to perform searches whose object is to find a structural anomaly in the graph rather than just find a distinguished vertex.