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:quant-ph/0304204 · New Journal of Physics

Controlling discrete quantum walks: coins and initial states

Ben Tregenna, W. Flanagan, Rik Maile, Viv M. Kendon

Published Jul 2, 2003• 264 citations
arXivHTMLPDF

Abstract

In discrete time, coined quantum walks, the coin degrees of freedom offer the potential for a wider range of controls over the evolution of the walk than are available in the continuous time quantum walk. This paper explores some of the possibilities on regular graphs, and also reports periodic behaviour on small cyclic graphs.
DOI
10.1088/1367-2630/5/1/383

Related papers

Controllability of Quantum Walks on Graphs

Francesca Albertini, Domenico D’Alessandro

In this paper, we consider discrete time quantum walks on graphs with coin focusing on the decentralized model, where the coin operation is allowed to change with the vertex of the graph. When the coin operations can be modified at every time step, these systems can be looked at as control systems and techniques of geometric control theory can be applied. In particular, the set of states that one can achieve can be described by studying controllability. Extending previous results, we give a characterization of the set of reachable states in terms of an appropriate Lie algebra. We then prove general results and criteria relating controllability to the algebraic and topological properties of the walk. As a consequence of these results, we prove that if the degree of the underlying graph is larger than $\frac{N}{2}$, where $N$ is the number of nodes, the quantum walk is always completely controllable, i.e., it is possible to having it to evolve according to an arbitrary unitary evolution. Another result is that controllability for decentralized models only depends on the graph and not on the particular quantum walk defined on it. We also provide explicit algorithms for control and quantify the number of steps needed for an arbitrary state transfer. The results of the paper are of interest in quantum information theory where quantum walks are used and analyzed in the development of quantum algorithms.

arXiv:1006.2405•Jun 11, 2010•3 citations

Perfect State Transfer in Quantum Walks on Graphs

Viv M. Kendon, Christino Tamon

We provide a brief survey of perfect state transfer in quantum walks on finite graphs. The ability to transfer a quantum state from one part of a quantum computer to another is a key ingredient of scalable architectures. Transfer through structures that do not require locally varying dynamic control simplifies the design and hence reduces the opportunities for errors to arise. Continuous time walks quantum walks on highly structured graphs exhibit perfect state transfer for the complete graph of size 2, the path of length 3, and the cycle of size 4. From these, larger graphs can be constructed, and the use of edge weights widens this set considerably. Discrete-time quantum walks have more flexibility through exploiting the coin degrees of freedom, but with the disadvantage that local control of the coin is required if the degree of the vertices varies. The closely related property of periodicity (exact return to the starting state) is also mentioned.

Journal of Computational and Theoretical Nanoscience•Mar 1, 2011•109 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•147 citations

Generic quantum walk using a coin-embedded shift operator

C. M. Chandrashekar

The study of quantum walk processes has been widely divided into two standard variants, the discrete-time quantum walk (DTQW) and the continuous-time quantum walk (CTQW). The connection between the two variants has been established by considering the limiting value of the coin operation parameter in the DTQW, and the coin degree of freedom was shown to be unnecessary [F. W. Strauch, Phys. Rev. A 74, 030301(R) (2006)]. But the coin degree of freedom is an additional resource which can be exploited to control the dynamics of the QW process. In this paper we present a generic quantum walk model using a quantum coin-embedded unitary shift operation ${U}_{C}$. The standard version of the DTQW and the CTQW can be conveniently retrieved from this generic model, retaining the features of the coin degree of freedom in both variants.

arXiv:0810.1556•Physical Review A•Nov 5, 2008•10 citations

Continuous limit of discrete quantum walks

M N Dheeraj, Todd A. Brun

Quantum walks can be defined in two quite distinct ways: discrete-time and continuous-time quantum walks (DTQWs and CTQWs). For classical random walks, there is a natural sense in which continuous-time walks are a limit of discrete-time walks. Quantum mechanically, in the discrete-time case, an additional ``coin space'' must be appended for the walk to have nontrivial time evolution. Continuous-time quantum walks, however, have no such constraints. This means that there is no completely straightforward way to treat a CTQW as a limit of a DTQW, as can be done in the classical case. Various approaches to this problem have been taken in the past. We give a construction for walks on $d$-regular, $d$-colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time $O(\sqrt{N}logN)$, but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the $O(\sqrt{N}logN)$ scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).

arXiv:1501.06950•Physical Review A•Jun 5, 2015•17 citations

Discrete-time quantum walk approach to state transfer

Paweł Kurzyński, Antoni Wójcik

We show that a quantum-state transfer, previously studied as a continuous-time process in networks of interacting spins, can be achieved within the model of discrete-time quantum walks with a position-dependent coin. We argue that, due to additional degrees of freedom, discrete-time quantum walks allow one to observe effects which cannot be observed in the corresponding continuous-time case. First, we study a discrete-time version of the engineered coupling protocol due to Christandl et al. [Phys. Rev. Lett. 92, 187902 (2004)] and then we discuss the general idea of conversion between continuous-time quantum walks and discrete-time quantum walks.

arXiv:1103.4185•Physical Review A•Jun 13, 2011•76 citations
In this paper, we consider discrete time quantum walks on graphs with coin focusing on the decentralized model, where the coin operation is allowed to change with the vertex of the graph. When the coin operations can be modified at every time step, these systems can be looked at as control systems and techniques of geometric control theory can be applied. In particular, the set of states that one can achieve can be described by studying controllability. Extending previous results, we give a characterization of the set of reachable states in terms of an appropriate Lie algebra. We then prove general results and criteria relating controllability to the algebraic and topological properties of the walk. As a consequence of these results, we prove that if the degree of the underlying graph is larger than N2\frac{N}{2}2N​, where NNN is the number of nodes, the quantum walk is always completely controllable, i.e., it is possible to having it to evolve according to an arbitrary unitary evolution. Another result is that controllability for decentralized models only depends on the graph and not on the particular quantum walk defined on it. We also provide explicit algorithms for control and quantify the number of steps needed for an arbitrary state transfer. The results of the paper are of interest in quantum information theory where quantum walks are used and analyzed in the development of quantum algorithms.
We provide a brief survey of perfect state transfer in quantum walks on finite graphs. The ability to transfer a quantum state from one part of a quantum computer to another is a key ingredient of scalable architectures. Transfer through structures that do not require locally varying dynamic control simplifies the design and hence reduces the opportunities for errors to arise. Continuous time walks quantum walks on highly structured graphs exhibit perfect state transfer for the complete graph of size 2, the path of length 3, and the cycle of size 4. From these, larger graphs can be constructed, and the use of edge weights widens this set considerably. Discrete-time quantum walks have more flexibility through exploiting the coin degrees of freedom, but with the disadvantage that local control of the coin is required if the degree of the vertices varies. The closely related property of periodicity (exact return to the starting state) is also mentioned.
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.
The study of quantum walk processes has been widely divided into two standard variants, the discrete-time quantum walk (DTQW) and the continuous-time quantum walk (CTQW). The connection between the two variants has been established by considering the limiting value of the coin operation parameter in the DTQW, and the coin degree of freedom was shown to be unnecessary [F. W. Strauch, Phys. Rev. A 74, 030301(R) (2006)]. But the coin degree of freedom is an additional resource which can be exploited to control the dynamics of the QW process. In this paper we present a generic quantum walk model using a quantum coin-embedded unitary shift operation UC{U}_{C}UC​. The standard version of the DTQW and the CTQW can be conveniently retrieved from this generic model, retaining the features of the coin degree of freedom in both variants.
Quantum walks can be defined in two quite distinct ways: discrete-time and continuous-time quantum walks (DTQWs and CTQWs). For classical random walks, there is a natural sense in which continuous-time walks are a limit of discrete-time walks. Quantum mechanically, in the discrete-time case, an additional ``coin space'' must be appended for the walk to have nontrivial time evolution. Continuous-time quantum walks, however, have no such constraints. This means that there is no completely straightforward way to treat a CTQW as a limit of a DTQW, as can be done in the classical case. Various approaches to this problem have been taken in the past. We give a construction for walks on ddd-regular, ddd-colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time O(NlogN)O(\sqrt{N}logN)O(N​logN), but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the O(NlogN)O(\sqrt{N}logN)O(N​logN) scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).
We show that a quantum-state transfer, previously studied as a continuous-time process in networks of interacting spins, can be achieved within the model of discrete-time quantum walks with a position-dependent coin. We argue that, due to additional degrees of freedom, discrete-time quantum walks allow one to observe effects which cannot be observed in the corresponding continuous-time case. First, we study a discrete-time version of the engineered coupling protocol due to Christandl et al. [Phys. Rev. Lett. 92, 187902 (2004)] and then we discuss the general idea of conversion between continuous-time quantum walks and discrete-time quantum walks.