arXiv:quant-ph/0504042 · New Journal of Physics

Entanglement in coined quantum walks on regular graphs

Ivens Carneiro, Meng Loo, Xibai Xu, Mathieu Girerd, Viv M. Kendon, P. L. Knight

Published Jul 12, 2005• 147 citations

Abstract

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.

DOI: 10.1088/1367-2630/7/1/156

Related papers

Coined quantum walks on percolation graphs

Godfrey Leung, Paul Knott, Joe Bailey +1 more

Quantum walks, both discrete (coined) and continuous time, form the basis of several quantum algorithms and have been used to model processes such as transport in spin chains and quantum chemistry. The enhanced spreading and mixing properties of quantum walks compared with their classical counterparts have been well studied on regular structures and also shown to be sensitive to defects and imperfections in the lattice. As a simple example of a disordered system, we consider percolation lattices, in which edges or sites are randomly missing, interrupting the progress of the quantum walk. We use numerical simulation to study the properties of coined quantum walks on these percolation lattices in one and two dimensions. In one dimension (the line), we introduce a simple notion of quantum tunnelling and determine how this affects the properties of the quantum walk as it spreads. On two-dimensional percolation lattices, we show how the spreading rate varies from linear in the number of steps down to zero as the percolation probability decreases towards the critical point. This provides an example of fractional scaling in quantum-walk dynamics.

arXiv:1006.1283New Journal of PhysicsDec 9, 201052 citations

A hybrid quantum walk model unifying discrete and continuous quantum walks

Tianen Chen, Yun Shang

Quantum walks, both discrete and continuous, serve as fundamental tools in quantum information processing with diverse applications. This work introduces a hybrid quantum walk model that integrates the coin mechanism of discrete walks with the Hamiltonian-driven time evolution of continuous walks. Through systematic analysis of probability distributions, standard deviations, and entanglement entropy on fundamental graph structures, we reveal distinctive dynamical characteristics that differentiate our model from conventional quantum walk paradigms. The proposed framework demonstrates unifying capabilities by naturally encompassing existing quantum walk models as special cases. Two significant applications emerge from this hybrid architecture: (1) We develop a novel protocol for perfect state transfer(PST) in general connected graphs, overcoming the limitations of previous graph-specific approaches. A PST on a tree graph has been implemented on a quantum superconducting processor. (2) We devise a quantum algorithm for multiplying K adjacency matrices of n -vertex regular graphs with time complexity O ( n 2 d 1 ⋯ d K ), outperforming classical matrix multiplication ( O ( n 2.371552 )) when vertex degrees d i are bounded. The algorithm’s efficacy for triangle counting is experimentally validated through the quantum simulation on PennyLane. These results establish the hybrid quantum walk as a versatile framework bridging discrete and continuous paradigms while enabling practical quantum advantage in graph computation tasks.

arXiv:2509.09221npj Quantum InformationDec 30, 20252 citations

Asymptotic entanglement in 2D quantum walks

Mostafa Annabestani, Mohammad Reza Abolhasani, Gonzalo Abal

The evolution operator of a discrete-time quantum walk involves a conditional shift in position space which entangles the 'coin' and position degrees of freedom of the walker. After several steps, the coin-position entanglement (CPE) converges to a well-defined value which depends on the initial state. In this work we provide an analytical method which allows for the exact calculation of the asymptotic reduced density operator and the corresponding CPE for a discrete-time quantum walk on a two-dimensional lattice. We use the von Neumann entropy of the reduced density operator as an entanglement measure. The method is applied to the case of a Hadamard walk for which the dependence of the resulting CPE on initial conditions is obtained. Initial states leading to the maximum or minimum CPE are identified and the relation between the coin or position entanglement present in the initial state of the walker and the final level of CPE is discussed. The CPE obtained from separable initial states satisfies an additivity property in terms of CPE of the corresponding one-dimensional cases. Non-local initial conditions are also considered and we find that the extreme case of an initial uniform position distribution leads to the largest CPE variation.

arXiv:0901.1188Journal of Physics A Mathematical and TheoreticalJan 27, 201045 citations

Discrete-Time Quantum Walk with Phase Disorder: Localization and Entanglement Entropy

Meng Zeng, Ee Hou Yong

Quantum Walk (QW) has very different transport properties to its classical counterpart due to interference effects. Here we study the discrete-time quantum walk (DTQW) with on-site static/dynamic phase disorder following either binary or uniform distribution in both one and two dimensions. For one dimension, we consider the Hadamard coin; for two dimensions, we consider either a 2-level Hadamard coin (Hadamard walk) or a 4-level Grover coin (Grover walk) for the rotation in coin-space. We study the transport properties e.g. inverse participation ratio (IPR) and the standard deviation of the density function (σ) as well as the coin-position entanglement entropy (EE), due to the two types of phase disorders and the two types of coins. Our numerical simulations show that the dimensionality, the type of coins, and whether the disorder is static or dynamic play a pivotal role and lead to interesting behaviors of the DTQW. The distribution of the phase disorder has very minor effects on the quantum walk.

Scientific ReportsSep 14, 201739 citations

Decoherence versus entanglement in coined quantum walks

Olivier Maloyer, Viv M. Kendon

Quantum versions of random walks on the line and cycle show a quadratic improvement in their spreading rate and mixing times respectively. The addition of decoherence to the quantum walk produces a more uniform distribution on the line, and even faster mixing on the cycle by removing the need for time-averaging to obtain a uniform distribution. We calculate numerically the entanglement between the coin and the position of the quantum walker and show that the optimal decoherence rates are such that all the entanglement is just removed by the time the final measurement is made.

arXiv:quant-ph/0612229New Journal of PhysicsApr 11, 200767 citations

Long-time entanglement in the Quantum Walk

Gonzalo Abal, R. Donangelo, Hugo Fort

Abstract. The coin-position entanglement generated by the evolution operator of a discrete–time quantum walk is quantified, using the von Neumann entropy of the reduced density operator (entropy of entanglement). In the case of a single walker, the entropy of entanglement converges, in the long time limit, to a well defined value which depends on the initial state. Exact expressions are obtained for local and non-local initial conditions. We also discuss the asymptotic bi-partite entanglement generated by non-separable coin operations for two coherent quantum walkers. In this case, the entropy of entanglement is observed to increase logarithmically with time. 1.

Nov 21, 20122 citations