Quantum walks and graph operations
Abstract
Let UX(t) be the transition matrix of a quantum walk on a graph X relative to its adjacency matrix A or the Laplacian matrix L. This paper investigates the behavior of quantum walks under Cartesian products, joins, and graph complements. We have two main goals. First, we characterize the conditions such that peak state transfer and pretty good state transfer are preserved under these operations, allowing us to construct new families of graphs admitting these properties. Our second goal is to analyze the relationship between the quantum walks on a graph and its complement. We provide bounds for fu,v(t)=|UXc(t)u,v−eitδUX(−t)u,v| and gu,v(t)=||UX(t)u,v|−|UXc(t)u,v||, where δ=−1 when dealing with A and δ=n otherwise. Note that fu,v(t) and gu,v(t) both measure the difference between the behavior of quantum state transfer between vertices u and v in a graph and its complement. If X is regular or M=L, then fu,v(t) is bounded above by 2/|V(X)|. If X is non-regular and M=A, then we utilize the main eigenvalues of a graph to obtain an upper bound for fu,v(t) which depends only on A. We also use the bounding matrix of the graph to give bounds for the Nordhaus-Gaddum type relations |UX(t)u,v|+|UXc(t)u,v| and |UX(t)u,v|· |UXc(t)u,v|. Finally, we demonstrate that most of our bounds are sharp for certain families of graphs.
Related
- Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
- Quadratic differentials and random walks on the dual graph of a pants decomposition
- Spectral characterization of the uniform theta graph Θ(t,2) and classification of 6-periodic Grover walks
- Paths maximize the expected range of graph-indexed random walks
- Transfer of Weisfeiler-Leman equivalence under graph operations
BibTeX
@misc{cooper2026quantum,
title = {{Quantum walks and graph operations}},
author = {Joy Cooper and Homer De Vera and Hermie Monterde and S. A. Talebpour and Xuzhu and Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07673},
eprint = {2610.07673},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07673},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum walks and graph operations
AU - Joy Cooper
AU - Homer De Vera
AU - Hermie Monterde
AU - S. A. Talebpour
AU - Xuzhu
AU - Wang
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.07673
UR - https://arxiv.org/abs/2610.07673
AB - Let U_X(t) be the transition matrix of a quantum walk on a graph X relative to its adjacency matrix A or the Laplacian matrix L. This paper investigates the behavior of quantum walks under Cartesian products, joins, and graph complements. We have two main goals. First, we characterize the conditions such that peak state transfer and pretty good state transfer are preserved under these operations, allowing us to construct new families of graphs admitting these properties. Our second goal is to analyze the relationship between the quantum walks on a graph and its complement. We provide bounds for f_u,v(t)=|U_X^c(t)_u,v−e^itδU_X(−t)_u,v| and g_u,v(t)=||U_X(t)_u,v|−|U_X^c(t)_u,v||, where δ=−1 when dealing with A and δ=n otherwise. Note that f_u,v(t) and g_u,v(t) both measure the difference between the behavior of quantum state transfer between vertices u and v in a graph and its complement. If X is regular or M=L, then f_u,v(t) is bounded above by 2/|V(X)|. If X is non-regular and M=A, then we utilize the main eigenvalues of a graph to obtain an upper bound for f_u,v(t) which depends only on A. We also use the bounding matrix of the graph to give bounds for the Nordhaus-Gaddum type relations |U_X(t)_u,v|+|U_X^c(t)_u,v| and |U_X(t)_u,v|· |U_X^c(t)_u,v|. Finally, we demonstrate that most of our bounds are sharp for certain families of graphs.
ER -