Title: The average search probability in a quantum walk with an oracle
| Speaker: | Harmony Zhan |
| Affiliation: | York University |
| Zoom: | Contact Soffia Arnadottir |
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.