Colloquium
Questions or comments?

Posted November 25, 2019

Last modified November 26, 2019

Krystal Guo, Université de Montreal

Applying algebraic graph theory to quantum computing

Abstract: 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 use classical techniques in algebraic graph theory to study quantum walks. A system of interacting quantum qubits can be modelled by a graph. The evolution of the quantum system can be completely encoded as a quantum walk in a graph, which can be seen, in some sense, as a quantum analogue of random walk. This gives rise to a rich connection between algebraic graph theory, linear algebra and quantum computing. In this talk, I will present recent results on the average mixing matrix of a graph; a quantum walk has a transition matrix which is a unitary matrix with complex values and thus will not converge, but we may speak of an average distribution over time, which is modelled by the average mixing matrix.