We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The average search probabilities of discrete-time quantum walks.
- Authors
Zhan, Hanmeng
- Abstract
We study the average probability that a discrete-time quantum walk finds a marked vertex on a graph. We first show that, for a regular graph, the spectrum of the transition matrix is determined by the weighted adjacency matrix of an augmented graph. We then consider the average search probability on a distance regular graph, and find a formula in terms of the adjacency matrix of its vertex-deleted subgraph. In particular, for any family of Complete graphs, or Strongly regular graphs, or Distance regular graphs of a fixed parameter d, varying valency k and varying size n, such that k d - 1 / n vanishes as k increases, the average search probability approaches 1/4 as the valency goes to infinity. We also present a more relaxed criterion, in terms of the intersection array, for this limit to be approached by distance regular graphs.
- Subjects
RANDOM walks; REGULAR graphs; COMPLETE graphs; PROBABILITY theory; VALENCE (Chemistry)
- Publication
Quantum Information Processing, 2022, Vol 21, Issue 9, p1
- ISSN
1570-0755
- Publication type
Article
- DOI
10.1007/s11128-022-03681-9