Interpolating walk between discrete-time quantum walk and its intrinsic random walk on graph
Abstract
We consider an interpolation with the parameter p∈ [0,1] between the discrete-time quantum (p=0) and its intrinsic random (p=1) walks on a finite connected graph. Its time evolution is defined by the convex combination of the Kraus (CPTP) maps of the quantum and random walks. The Kraus map of the random walk is represented by taking a kind of projection of that of the quantum walk. The time evolution of the interpolation is interpreted as the combination of the following two dynamics of $2$ walkers on the same graph correlated with each other: $2$ walkers move independently of each other (no-correlation) with probability 1−p, while $2$ walkers always move into the same position (the maximal correlation) with probability p at each time step. In this paper, we generalize the random walk to a new walk, namely, the correlated walk, which preserves the intrinsic property and relaxes the maximal correlation of the random walk. This correlation is determined by a partition of the arc sets in the underlying graph. We show that the eigenvalues of the interpolating walk between the correlated and quantum walks live in { z∈ ℂ | 1−p≤ |z|≤ 1 } and that the absorption state coincides with that of the correlated walk, which is characterized by the underlying graph structures.
Related
- Intrinsic Finite-Step Characterizations of Discrete General Helices
- Generalized Discrete Fractal Dimensions of Graph Families
- Pairwise Distortion Distribution with Graph-Based Importance Sampling for Quantization Error and Intrinsic Dimension Estimation
- Quadratic differentials and random walks on the dual graph of a pants decomposition
- Majorization, Entropy and Concentration Inequalities for Discrete α-Concave Random Variables
BibTeX
@misc{higuchi2026interpolating,
title = {{Interpolating walk between discrete-time quantum walk and its intrinsic random walk on graph}},
author = {Yusuke Higuchi and Etsuo Segawa and Honoka Shiratori and Saori Yoshino},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30931},
eprint = {2609.30931},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30931},
}
RIS
TY - UNPB
TI - Interpolating walk between discrete-time quantum walk and its intrinsic random walk on graph
AU - Yusuke Higuchi
AU - Etsuo Segawa
AU - Honoka Shiratori
AU - Saori Yoshino
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.30931
UR - https://arxiv.org/abs/2609.30931
AB - We consider an interpolation with the parameter p∈ [0,1] between the discrete-time quantum (p=0) and its intrinsic random (p=1) walks on a finite connected graph. Its time evolution is defined by the convex combination of the Kraus (CPTP) maps of the quantum and random walks. The Kraus map of the random walk is represented by taking a kind of projection of that of the quantum walk. The time evolution of the interpolation is interpreted as the combination of the following two dynamics of $2$ walkers on the same graph correlated with each other: $2$ walkers move independently of each other (no-correlation) with probability 1−p, while $2$ walkers always move into the same position (the maximal correlation) with probability p at each time step. In this paper, we generalize the random walk to a new walk, namely, the correlated walk, which preserves the intrinsic property and relaxes the maximal correlation of the random walk. This correlation is determined by a partition of the arc sets in the underlying graph. We show that the eigenvalues of the interpolating walk between the correlated and quantum walks live in { z∈ ℂ | 1−p≤ |z|≤ 1 } and that the absorption state coincides with that of the correlated walk, which is characterized by the underlying graph structures.
ER -