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:1109.1866 · IEICE Transactions on Information and Systems

Quantum Walks on the Line with Phase Parameters

Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita, Yasuhiko Nakashima

Published Jan 1, 2012• 4 citations
arXivHTMLPDF

Abstract

In this paper, a study on discrete-time coined quantum walks on the line is presented. Clear mathematical foundations are still lacking for this quantum walk model. As a step toward this objective, the following question is being addressed: Given a graph, what is the probability that a quantum walk arrives at a given vertex after some number of steps? This is a very natural question, and for random walks it can be answered by several different combinatorial arguments. For quantum walks this is a highly non-trivial task. Furthermore, this was only achieved before for one specific coin operator (Hadamard operator) for walks on the line. Even considering only walks on lines, generalizing these computations to a general SU(2) coin operator is a complex task. The main contribution is a closed-form formula for the amplitudes of the state of the walk (which includes the question above) for a general symmetric SU(2) operator for walks on the line. To this end, a coin operator with parameters that alters the phase of the state of the walk is defined. Then, closed-form solutions are computed by means of Fourier analysis and asymptotic approximation methods. We also present some basic properties of the walk which can be deducted using weak convergence theorems for quantum walks. In particular, the support of the induced probability distribution of the walk is calculated. Then, it is shown how changing the parameters in the coin operator affects the resulting probability distribution.

DOI
10.1587/transinf.e95.d.722

Related papers

Alternating Quantum Walks

Jenia Rousseva

Quantum walks are a powerful tool for developing efficient algorithms in quantum computing. This research explores two discrete-time one-dimensional quantum walks where the coin operator varies along even and odd positions on the line. We find closed-form expressions for the coefficients of the wave function for both walks and also arrive at a formula for the probability distribution for one of the walks. A significant discovery is a way to model the well-known Hadamard walk using two alternating coins.

•Jan 1, 2016•0 citations

Revisiting one-dimensional discrete-time quantum walks with general coin

Mahesh N. Jayakody, Chandrakala Meena, Priodyuti Pradhan

Quantum walk (QW) is the quantum analog of the random walk. QW is an integral part of the development of numerous quantum algorithms. Hence, an in-depth understanding of QW helps us to grasp the quantum algorithms. We revisit the one-dimensional discrete-time QW and discuss basic steps in detail by incorporating the most general coin operator, constant in both space and time, and a localized initial state using numerical modeling. We investigate the impact of each parameter of the general coin operator on the probability distribution of the quantum walker. We show that by tuning the parameters of the general coin, one can regulate the probability distribution of the walker. We provide an algorithm for the one-dimensional quantum walk driven by the general coin operator. The study on general coin operators also includes the popular coins – Hadamard, Grover, and Fourier.

arXiv:2102.07207•Physics Open•Nov 10, 2023•15 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

QUANTUM RANDOM WALK ON FRACTALS

Kai Zhao

Quantum walks are the quantum mechanical analogue of classical random walks. Discrete-time quantum walks have been introduced and studied mostly on the line Z or higher dimensional space Z d but rarely defined on graphs with fractal dimensions because the coin operator depends on the position and the Fourier transform on the fractals is not defined. Inspired by its nature of classical walks, different quantum walks will be defined by choosing different shift and coin operators. When the coin operator is uniform, the results of classical walks will be obtained upon measurement at each step. Moreover, with measurement at each step, our results reveal more information about the classical random walks. In this dissertation, two graphs with fractal dimensions will be considered. The first one is Sierpinski gasket, a degree-4 regular graph with Hausdorff di- mension of df = ln 3/ ln 2. The second is the Cantor graph derived like Cantor set, with Hausdorff dimension of df = ln 2/ ln 3. The definitions and amplitude functions of the quantum walks will be introduced. The main part of this dissertation is to derive a recursive formula to compute the amplitude Green function. The exiting probability will be computed and compared with the classical results. When the generation of graphs goes to infinity, the recursion of the walks will be investigated and the convergence rates will be obtained and compared with the classical counterparts.

•Jan 1, 2018•0 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

Invariance in quantum walks with time-dependent coin operators

Miquel Montero

This paper unveils some features of a discrete-time quantum walk on the line whose coin depends on the temporal variable. After considering the most general form of the unitary coin operator, it focuses on the role played by the two phase factors that one can incorporate there, and shows how both terms influence the evolution of the system. A closer analysis reveals that the probabilistic properties of the motion of the walker remain unaltered when the update rule of these phases is chosen adequately. This invariance is based on a symmetry with consequences not yet fully explored.

arXiv:1410.0550•Physical Review A•Dec 5, 2014•11 citations
In this paper, a study on discrete-time coined quantum walks on the line is presented. Clear mathematical foundations are still lacking for this quantum walk model. As a step toward this objective, the following question is being addressed: Given a graph, what is the probability that a quantum walk arrives at a given vertex after some number of steps? This is a very natural question, and for random walks it can be answered by several different combinatorial arguments. For quantum walks this is a highly non-trivial task. Furthermore, this was only achieved before for one specific coin operator (Hadamard operator) for walks on the line. Even considering only walks on lines, generalizing these computations to a general SU(2) coin operator is a complex task. The main contribution is a closed-form formula for the amplitudes of the state of the walk (which includes the question above) for a general symmetric SU(2) operator for walks on the line. To this end, a coin operator with parameters that alters the phase of the state of the walk is defined. Then, closed-form solutions are computed by means of Fourier analysis and asymptotic approximation methods. We also present some basic properties of the walk which can be deducted using weak convergence theorems for quantum walks. In particular, the support of the induced probability distribution of the walk is calculated. Then, it is shown how changing the parameters in the coin operator affects the resulting probability distribution.
Quantum walks are a powerful tool for developing efficient algorithms in quantum computing. This research explores two discrete-time one-dimensional quantum walks where the coin operator varies along even and odd positions on the line. We find closed-form expressions for the coefficients of the wave function for both walks and also arrive at a formula for the probability distribution for one of the walks. A significant discovery is a way to model the well-known Hadamard walk using two alternating coins.
Quantum walk (QW) is the quantum analog of the random walk. QW is an integral part of the development of numerous quantum algorithms. Hence, an in-depth understanding of QW helps us to grasp the quantum algorithms. We revisit the one-dimensional discrete-time QW and discuss basic steps in detail by incorporating the most general coin operator, constant in both space and time, and a localized initial state using numerical modeling. We investigate the impact of each parameter of the general coin operator on the probability distribution of the quantum walker. We show that by tuning the parameters of the general coin, one can regulate the probability distribution of the walker. We provide an algorithm for the one-dimensional quantum walk driven by the general coin operator. The study on general coin operators also includes the popular coins – Hadamard, Grover, and Fourier.
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.
Quantum walks are the quantum mechanical analogue of classical random walks. Discrete-time quantum walks have been introduced and studied mostly on the line Z or higher dimensional space Z d but rarely defined on graphs with fractal dimensions because the coin operator depends on the position and the Fourier transform on the fractals is not defined. Inspired by its nature of classical walks, different quantum walks will be defined by choosing different shift and coin operators. When the coin operator is uniform, the results of classical walks will be obtained upon measurement at each step. Moreover, with measurement at each step, our results reveal more information about the classical random walks. In this dissertation, two graphs with fractal dimensions will be considered. The first one is Sierpinski gasket, a degree-4 regular graph with Hausdorff di- mension of df = ln 3/ ln 2. The second is the Cantor graph derived like Cantor set, with Hausdorff dimension of df = ln 2/ ln 3. The definitions and amplitude functions of the quantum walks will be introduced. The main part of this dissertation is to derive a recursive formula to compute the amplitude Green function. The exiting probability will be computed and compared with the classical results. When the generation of graphs goes to infinity, the recursion of the walks will be investigated and the convergence rates will be obtained and compared with the classical counterparts.
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
This paper unveils some features of a discrete-time quantum walk on the line whose coin depends on the temporal variable. After considering the most general form of the unitary coin operator, it focuses on the role played by the two phase factors that one can incorporate there, and shows how both terms influence the evolution of the system. A closer analysis reveals that the probabilistic properties of the motion of the walker remain unaltered when the update rule of these phases is chosen adequately. This invariance is based on a symmetry with consequences not yet fully explored.