Tuesday 5 September 2023, 16:00 - 17:00 in HG03.085
Krystal Guo (UvA)
Algebraic graph theory and quantum walks
The interplay between the properties of graphs and the eigenvalues of their adjacency matrices is well-studied. Important graph invariants, such as diameter and chromatic number, can be understood using these eigenvalue techniques. In this talk, we bring these classical techniques in algebraic graph theory to the study of quantum walks.
A system of interacting quantum qubits can be modelled by a quantum process on an underlying graph and is, in some sense, a quantum analogue of random walk. This gives rise to a rich connection between graph theory, linear algebra and quantum computing. In this talk, I will give an overview of applications of algebraic graph theory in quantum walks, as well as various recent results.
In a recent paper with V. Schmeits, we show that the evolution of a general discrete-time quantum walk that consists of two reflections satisfies a Chebyshev recurrence, under a projection. We apply this to a model of discrete-time quantum walk proposed by H. Zhan [J. Algebraic Combin. 53 (4):1187-1213, 2020], whose transition matrix is given by two reflections, using the face and vertex incidence relations of a graph embedded in an orientable surface. For the vertex-face walk, we prove theorems about perfect state transfer and periodicity and give infinite families of examples where these occur.