Graph theory seminar - Gabriel Coutinho

Connections Between Quantum Walks and Some Graph Properties

Abstract: 

Let A be the adjacency matrix of a graph. Then we define a quantum system in the graph whose state at a positive time t is given by the matrix exp(i t A), where i is the imaginary constant. It turns out that properties of this quantum walk matrix are related to other more classical graph properties. I will talk about some of these connections, and I will also explain how a very old result in graph theory was a key piece to show a new result about quantum walks in trees. I will try to keep the talk as elementary as possible and absolutely no background in quantum information theory will be needed.