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.
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.
For a discrete time quantum walk (QW) on the N-cycle, allowing for decoherence on the coin, we derive a number of new results, including an explicit formula for the position probability distribution. For a QW of this type, we show that the mixing behavior tends, in the long-run, to a uniform distribution, regardless of the initial state of the system and irrespective of the parity of the number of nodes N. These results confirm the findings of previous authors who arrived at similar conclusions through extensive numerical simulations. In particular, we infer that the mixing time M(ϵ)ˉ for the time-everaged probability distribution is of order no greater than O(N2/ϵ).
For a discrete time quantum walk (QW) on the N-cycle, allowing for decoherence on the coin, we derive a number of results, including an explicit formula for the position probability distribution. For a QW of this type, we show that the mixing behavior tends, in the long run, to a uniform distribution regardless of the initial state of the system and irrespective of the parity of the number of nodes N. These results confirm the findings of previous authors who arrived at similar conclusions through extensive numerical simulations. In particular, we infer that the mixing time M(epsilon) for the time-averaged probability distribution is of order no greater than O(N2/).
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 At present, decoherence continuous-time quantum walks are only based on measurement decoherence, but a new broken-line noise model for continuous-time quantum walks on the cycle is proposed. In this scheme, we first construct the Hamiltonian H according to four cases including no broken links, the link to the left of the node is broken, the link to the right of the node is broken, and both links are broken, and then the probability of a walker is reconstructed. The analysis shows that with the increase of the probability of disconnection, the oscillation of the walk gradually weakens and becomes a peak distribution, and with the continuous increase of the walk time, the probability distribution of each vertex tends to be uniform. In addition, we also analyze the mixing time of this walk model and find that a small amount of broken chain decoherence can help reduce the mixing time, thereby improving the performance of quantum walks.
We prove analytical results showing that decoherence can be useful for mixing time in a continuous-time quantum walk on finite cycles. This complements the numerical observations by Kendon and Tregenna (Physical Review A 67 (2003), 042315) of a similar phenomenon for discrete-time quantum walks. Our analytical treatment of continuous-time quantum walks includes a continuous monitoring of all vertices that induces the decoherence process. We identify the dynamics of the probability distribution and observe how mixing times undergo the transition from quantum to classical behavior as our decoherence parameter grows from zero to infinity. Our results show that, for small rates of decoherence, the mixing time improves linearly with decoherence, whereas for large rates of decoherence, the mixing time deteriorates linearly towards the classical limit. In the middle region of decoherence rates, our numerical data confirms the existence of a unique optimal rate for which the mixing time is minimized.
Disorder in coined quantum walks generally leads to localization. We investigate the influence of the localization on the entanglement properties of coined quantum walks. Specifically, we consider quantum walks on the line and explore the effects of quenched disorder in the coin operations. After confirming that our choice of disorder localizes the walker, we study how the localization affects the properties of the coined quantum walk. We find that the mixing properties of the walk are altered nontrivially with mixing being improved at short time scales. Special focus is given to the influence of coin disorder on the properties of the quantum state and the coin-walker entanglement. We find that disorder alters the quantum state significantly even when the walker probability distribution is still close to the nondisordered case. We observe that, generically, coin disorder decreases the coin-walker entanglement and that the localization leaves distinct traces in the entanglement entropy and the entanglement negativity of the coined quantum walk.