Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1612.02448 · Interdisciplinary Information Sciences

Connecting Coined Quantum Walks with Szegedy's Model

Renato Portugal, Etsuo Segawa

Published Jan 1, 2017• 13 citations
arXivHTMLPDF

Abstract

We analyze the equivalence between discrete-time coined quantum walks and Szegedy's quantum walks. We characterize a class of flip-flop coined models with generalized Grover coin on a graph Γ that can be directly converted into Szegedy's model on the subdivision graph of Γ and we describe a method to convert one model into the other. This method improves previous results in literature that need to use the staggered model and the concept of line graph, which are avoided here.

DOI
10.4036/iis.2017.a.15

Related papers

Staggered quantum walks on graphs

Renato Portugal

The staggered quantum-walk model makes it possible to establish an unprecedented connection between discrete-time quantum walks and graph theory. We call attention to the fact that a large subclass of the coined model is included in Szegedy's model, which in its turn is entirely included in the staggered model. In order to compare those three quantum-walk models, we put them in the staggered formalism and show that the Szegedy and coined models are defined on a special subclass of graphs. This inclusion scheme is also true when the searching framework is added. We use graph theory to characterize which staggered quantum walks can be reduced to the Szegedy or coined quantum-walk model. We analyze a staggered-based search that cannot be included in Szegedy's model and show numerically that this search is more efficient than a random-walk-based search.

arXiv:1603.02210•Physical Review A•Jun 27, 2016•46 citations

Coined quantum walks on weighted graphs

Thomas G. Wong

Abstract We define a discrete-time, coined quantum walk on weighted graphs that is inspired by Szegedy’s quantum walk. Using this, we prove that many lackadaisical quantum walks, where each vertex has l integer self-loops, can be generalized to a quantum walk where each vertex has a single self-loop of real-valued weight l . We apply this real-valued lackadaisical quantum walk to two problems. First, we analyze it on the line or one-dimensional lattice, showing that it is exactly equivalent to a continuous deformation of the three-state Grover walk with faster ballistic dispersion. Second, we generalize Grover’s algorithm, or search on the complete graph, to have a weighted self-loop at each vertex, yielding an improved success probability when l < 3 + 2 2 ≈ 5.828 .

arXiv:1703.10134•Journal of Physics A Mathematical and Theoretical•Sep 13, 2017•39 citations

Staggered quantum walks with Hamiltonians

Renato Portugal, M. C. de Oliveira, Jalil Khatibi Moqadam

Quantum walks are recognizably useful for the development of new quantum algorithms, as well as for the investigation of several physical phenomena in quantum systems. Actual implementations of quantum walks face technological difficulties similar to the ones for quantum computers, though. Therefore, there is a strong motivation to develop new quantum-walk models which might be easier to implement. In this work we present an extension of the staggered quantum walk model that is fitted for physical implementations in terms of time-independent Hamiltonians. We demonstrate that this class of quantum walk includes the entire class of staggered quantum walk model, Szegedy's model, and an important subset of the coined model.

arXiv:1605.02774•Physical Review A•Jan 26, 2017•27 citations

Establishing the equivalence between Szegedy’s and coined quantum walks using the staggered model

Renato Portugal

arXiv:1509.08852•Quantum Information Processing•Jan 12, 2016•39 citations

Entanglement in coined quantum walks on regular graphs

Ivens Carneiro, Meng Loo, Xibai Xu +3 more

Quantum walks, both discrete (coined) and continuous time, form the basis of several recent quantum algorithms. Here we use numerical simulations to study the properties of discrete, coined quantum walks. We investigate the variation in the entanglement between the coin and the position of the particle by calculating the entropy of the reduced density matrix of the coin. We consider both dynamical evolution and asymptotic limits for coins of dimensions from two to eight on regular graphs. For low coin dimensions, quantum walks which spread faster (as measured by the mean square deviation of their distribution from uniform) also exhibit faster convergence towards the asymptotic value of the entanglement between the coin and particle's position. For high-dimensional coins, the DFT coin operator is more efficient at spreading than the Grover coin. We study the entanglement of the coin on regular finite graphs such as cycles, and also show that on complete bipartite graphs, a quantum walk with a Grover coin is always periodic with period four. We generalize the 'glued trees' graph used by Childs et al (2003 Proc. STOC , pp 59–68) to higher branching rate (fan out) and verify that the scaling with branching rate and with tree depth is polynomial.

arXiv:quant-ph/0504042•New Journal of Physics•Jul 12, 2005•140 citations

Classification of coined quantum walks on the line and comparison to correlated classical random walks

Lukas Hantzko, Lennart Binkowski

Abstract We present a comprehensive classification of one-dimensional coined quantum walks on the infinite line, focusing on the spatial probability distributions they induce. Building on prior results, we identify all initial coin states that lead to symmetric quantum walks for arbitrary coins and provide a bijective parametrisation of all symmetric quantum walks modulo distributional equivalence. Extending beyond the symmetric case, we also give a surjective parametrisation of all coined quantum walks under the same equivalence relation, as well as a bijective parametrisation modulo equivalence of their limiting distributions. Furthermore, we derive corrected closed-form expressions for the walk amplitudes, resolving inaccuracies in previous literature, and generalise the approach to the correlated classical random walk. This unified framework enables a direct comparison between quantum and classical dynamics. Additionally, we discuss the asymptotic scaling of variances for both models, identifying quadratic spreading as a hallmark of non-trivial quantum walks and contrasting it with the linear behaviour of classical walks, except at the extremal points of maximal correlation. Finally, we compare the limiting distributions arising from quantum walks with those of the classical case. Graphical abstract - compact classification results for symmetric and general quantum walks, as well as classically correlated random walks - quantum walks spread ballistically while classically correlated random walks approach Gaussian limiting distribution - quantum coin parameter directly influence limiting distribution’s skewness

arXiv:2507.23524•The European Physical Journal D•Jul 1, 2026•0 citations
We analyze the equivalence between discrete-time coined quantum walks and Szegedy's quantum walks. We characterize a class of flip-flop coined models with generalized Grover coin on a graph Γ that can be directly converted into Szegedy's model on the subdivision graph of Γ and we describe a method to convert one model into the other. This method improves previous results in literature that need to use the staggered model and the concept of line graph, which are avoided here.
The staggered quantum-walk model makes it possible to establish an unprecedented connection between discrete-time quantum walks and graph theory. We call attention to the fact that a large subclass of the coined model is included in Szegedy's model, which in its turn is entirely included in the staggered model. In order to compare those three quantum-walk models, we put them in the staggered formalism and show that the Szegedy and coined models are defined on a special subclass of graphs. This inclusion scheme is also true when the searching framework is added. We use graph theory to characterize which staggered quantum walks can be reduced to the Szegedy or coined quantum-walk model. We analyze a staggered-based search that cannot be included in Szegedy's model and show numerically that this search is more efficient than a random-walk-based search.
Abstract We define a discrete-time, coined quantum walk on weighted graphs that is inspired by Szegedy’s quantum walk. Using this, we prove that many lackadaisical quantum walks, where each vertex has l integer self-loops, can be generalized to a quantum walk where each vertex has a single self-loop of real-valued weight l . We apply this real-valued lackadaisical quantum walk to two problems. First, we analyze it on the line or one-dimensional lattice, showing that it is exactly equivalent to a continuous deformation of the three-state Grover walk with faster ballistic dispersion. Second, we generalize Grover’s algorithm, or search on the complete graph, to have a weighted self-loop at each vertex, yielding an improved success probability when l < 3 + 2 2 ≈ 5.828 .
Quantum walks are recognizably useful for the development of new quantum algorithms, as well as for the investigation of several physical phenomena in quantum systems. Actual implementations of quantum walks face technological difficulties similar to the ones for quantum computers, though. Therefore, there is a strong motivation to develop new quantum-walk models which might be easier to implement. In this work we present an extension of the staggered quantum walk model that is fitted for physical implementations in terms of time-independent Hamiltonians. We demonstrate that this class of quantum walk includes the entire class of staggered quantum walk model, Szegedy's model, and an important subset of the coined model.
Quantum walks, both discrete (coined) and continuous time, form the basis of several recent quantum algorithms. Here we use numerical simulations to study the properties of discrete, coined quantum walks. We investigate the variation in the entanglement between the coin and the position of the particle by calculating the entropy of the reduced density matrix of the coin. We consider both dynamical evolution and asymptotic limits for coins of dimensions from two to eight on regular graphs. For low coin dimensions, quantum walks which spread faster (as measured by the mean square deviation of their distribution from uniform) also exhibit faster convergence towards the asymptotic value of the entanglement between the coin and particle's position. For high-dimensional coins, the DFT coin operator is more efficient at spreading than the Grover coin. We study the entanglement of the coin on regular finite graphs such as cycles, and also show that on complete bipartite graphs, a quantum walk with a Grover coin is always periodic with period four. We generalize the 'glued trees' graph used by Childs et al (2003 Proc. STOC , pp 59–68) to higher branching rate (fan out) and verify that the scaling with branching rate and with tree depth is polynomial.
Abstract We present a comprehensive classification of one-dimensional coined quantum walks on the infinite line, focusing on the spatial probability distributions they induce. Building on prior results, we identify all initial coin states that lead to symmetric quantum walks for arbitrary coins and provide a bijective parametrisation of all symmetric quantum walks modulo distributional equivalence. Extending beyond the symmetric case, we also give a surjective parametrisation of all coined quantum walks under the same equivalence relation, as well as a bijective parametrisation modulo equivalence of their limiting distributions. Furthermore, we derive corrected closed-form expressions for the walk amplitudes, resolving inaccuracies in previous literature, and generalise the approach to the correlated classical random walk. This unified framework enables a direct comparison between quantum and classical dynamics. Additionally, we discuss the asymptotic scaling of variances for both models, identifying quadratic spreading as a hallmark of non-trivial quantum walks and contrasting it with the linear behaviour of classical walks, except at the extremal points of maximal correlation. Finally, we compare the limiting distributions arising from quantum walks with those of the classical case. Graphical abstract - compact classification results for symmetric and general quantum walks, as well as classically correlated random walks - quantum walks spread ballistically while classically correlated random walks approach Gaussian limiting distribution - quantum coin parameter directly influence limiting distribution’s skewness