Algebraic Graph Theory Seminar - Harmony Zhan

Monday, August 2, 2021 11:30 am - 11:30 am EDT (GMT -04:00)

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

Speaker: Harmony Zhan
Affiliation: York University
Zoom: Contact Soffia Arnadottir


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.