Harmony Zhan

Affiliation: Simon Fraser University, British Columbia, Canada

Title: An introduction to discrete quantum walks

Abstract: A discrete quantum walk is determined by a unitary matrix representation of a graph. In this talk, I will give an overview of different quantum walks, and show how the spectral information of the unitary matrix representation links properties of the walks to properties of the graphs. Part of this talk will be based on the book, Discrete Quantum Walks on Graphs and Digraphs, by Chris and me.

You can watch the talk here, and the slides are available here.

This talk was given on October 17th, 2022

Affiliation: York University, Toronto, Ontario

Title: The average search probability in a quantum walk with an oracle

Abstract: Some quantum search algorithms can be viewed as discrete-time quantum walks on graphs with a marked vertex a. In such a walk, the oracle is part of the transition matrix, the target state is the characteristic vector of the outgoing arcs of a, and the initial state is the all-ones vector.

Given a distance regular graph X and a marked vertex a, we are interested in the “average probability”, over any period of time, that the quantum walk on X finds the marked vertex a. We show a relation between this probability and the average state of the continuous-time quantum walk on the vertex-deleted subgraph X\a. In particular, for any family of strongly regular graphs, this average probability converges to 1/4 as the valency goes to infinity.

You can watch the talk here.

This talk was given on August 2nd, 2021

Title: Factoring discrete quantum walks into continuous quantum walks

Abstract: The Grover walk is a discrete quantum walk inspired by Grover’s search algorithm. It takes place on the arcs of a graph, and alternates between “coin flips” and “arc reversal”. In this talk, I show that for a distance regular graph X with diameter d and invertible A(X), the Grover walk on X can be “decomposed” into at most d “commuting” continuous quantum walks. Moreover, each of them is a continuous quantum walk on some distance digraph of the line digraph of X.

You can watch the talk here and the slides are available here.

This talk was given on August 3rd, 2020