Quantum walks on graphs

Abstract: Quantum walks have been defined and analyzed for about three decades, since the work of Ambainis, Kempe, Aharonov, etc. Interest in this model peaked when they were not only shown to be useful in quantum algorithms, but also to be universal for quantum computation (Childs, 2009, Lovett et al., 2010). Besides being useful in Quantum Computer Science, they are objects deserving mathematical attention in their own right.

In my talk I will introduce necessary concepts and notation (from Physics) as needed, starting with the simple one-dimensional “Hadamard” walk. I will cover two classes of walks in detail: (1) alternating walks and (2) walks with memory (or history). In each case I will point out properties of interest - asymptotic probability distribution, localization, dependencies on the initial state and the Unitary matrix we use for “coin flip”, similarities and dissimilarities with corresponding classical random walks, etc. In the case of (1) I will show how we can use fewer physical resources to walk in higher dimensional lattices, while in (2) I will show how this leads to walking on the line graph of the original graph.

computational biologycomputational and theoretical chemistryartificial intelligencecomputational engineering, finance, and sciencemathematical softwareneural and evolutionary computingother computer sciencequantum computing and informationsymbolic computationcomputer science theorymathematical physicsgeneral mathematicsinformation theorynumerical analysisoptimization and controlprobability

Audience: researchers in the discipline

Comments: On-site: room 1/15, 'Działownia' building, Cracow University of Technology Online: zoom.us/j/94141684360?pwd=PUvxIDr0laMi87Y6kcCEWHnIRRM511.1

---

Mathematics for Computer Science and Applications Seminar

Series comments: All talks will be presented through the zoom platform. Please subscribe in the website below in order to obtain the links. For more information go to ii.pk.edu.pl/~m4csa/

---