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:0908.1524 · Physical Review E

Quantum walks on the N -cycle subject to decoherence on the coin degree of freedom

Chaobin Liu, Nelson Petulante

Published Mar 15, 2010• 20 citations
arXivHTMLPDF

Abstract

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/).

DOI
10.1103/physreve.81.031113

Related papers

Coin-decohered quantum random walks on the NNN-cycle

Chaobin Liu, Nelson Petulante

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 $\bar{M(\epsilon)}$ for the time-everaged probability distribution is of order no greater than $O(N^2/\epsilon)$.

•Aug 11, 2009•0 citations

Asymptotic evolution of quantum walks on the N -cycle subject to decoherence on both the coin and position degrees of freedom

Chaobin Liu, Nelson Petulante

Consider a discrete-time quantum walk on the $N$-cycle subject to decoherence both on the coin and the position degrees of freedom. By examining the evolution of the density matrix of the system, we derive some conclusions about the asymptotic behavior of the system. When $N$ is odd, the density matrix of the system tends, in the long run, to the maximally mixed state, independent of the initial state. When $N$ is even, although the behavior of the system is not necessarily asymptotically stationary, in this case too an explicit formulation is obtained of the asymptotic dynamics of the system. Moreover, this approach enables us to specify the limiting behavior of the mutual information, viewed as a measure of quantum entanglement between subsystems (coin and walker). In particular, our results provide efficient theoretical confirmation of the findings of previous authors, who have arrived at their results through extensive numerical simulations. Our results can be attributed to an important theorem which, for a generalized random unitary operation, explicitly identifies the structure of all of its eigenspaces corresponding to eigenvalues of unit modulus.

arXiv:1104.2653•Physical Review A•Jul 18, 2011•21 citations

Mixing times in quantum walks on the hypercube

Franklin de Lima Marquezino, Renato Portugal, Gonzalo Abal +1 more

The mixing time of a discrete-time quantum walk on the hypercube is considered. The mean probability distribution of a Markov chain on a hypercube is known to mix to a uniform distribution in time $O(n\text{ }\text{log}\text{ }n)$. We show that the mean probability distribution of a discrete-time quantum walk on a hypercube mixes to a (generally nonuniform) distribution $\ensuremath{\pi}(x)$ in time $O(n)$, and the stationary distribution is determined by the initial state of the walk. An explicit expression for $\ensuremath{\pi}(x)$ is derived for the particular case of a symmetric walk. These results are consistent with those obtained previously for a continuous-time quantum walk. The effect of decoherence due to randomly breaking links between connected sites in the hypercube is also considered. We find that the probability distribution mixes to the uniform distribution as expected. However, the mixing time has a minimum at a critical decoherence rate $p\ensuremath{\approx}0.1$. A similar effect was previously reported for a quantum walk on an $N$-cycle with decoherence from repeated measurements of position. A controlled amount of decoherence helps in obtaining---and preserving---a uniform distribution over the ${2}^{n}$ sites of the hypercube in the shortest possible time.

arXiv:0712.0625•Physical Review A•Apr 16, 2008•45 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/0612229•New Journal of Physics•Apr 11, 2007•67 citations

Mixing and decoherence in quantum walks on cycles

Leonid Evgenevich Fedichkin, Dmitry Solenov, Christino Tamon

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.

Quantum Information and Computation•May 1, 2006•40 citations

Mixing times of three-state quantum walks on cycles

Qi Han, Ning Bai, Huan Wang +1 more

In this paper, we successfully obtain an explicit expression of the limit distribution [Formula: see text] of three-state quantum walks on cycles, the total variation distance between [Formula: see text] and the average probability [Formula: see text], and lower bound on the difference between two eigenvalues, among others. Based on the above conclusions, we finally get the mixing time [Formula: see text] of the quantum walk of Grover coin on the N-cycle. [Formula: see text] is the time required to characterize [Formula: see text] approaching [Formula: see text]. Our results show that the average probability of a three-state quantum walk on a cycle can approach its limit distribution faster than that of a two-state quantum walk, which might be of significance to quantum computation.

International Journal of Modern Physics B•Oct 19, 2022•2 citations
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/).
For a discrete time quantum walk (QW) on the NNN-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 NNN. 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(ϵ)ˉ\bar{M(\epsilon)}M(ϵ)ˉ​ for the time-everaged probability distribution is of order no greater than O(N2/ϵ)O(N^2/\epsilon)O(N2/ϵ).
Consider a discrete-time quantum walk on the NNN-cycle subject to decoherence both on the coin and the position degrees of freedom. By examining the evolution of the density matrix of the system, we derive some conclusions about the asymptotic behavior of the system. When NNN is odd, the density matrix of the system tends, in the long run, to the maximally mixed state, independent of the initial state. When NNN is even, although the behavior of the system is not necessarily asymptotically stationary, in this case too an explicit formulation is obtained of the asymptotic dynamics of the system. Moreover, this approach enables us to specify the limiting behavior of the mutual information, viewed as a measure of quantum entanglement between subsystems (coin and walker). In particular, our results provide efficient theoretical confirmation of the findings of previous authors, who have arrived at their results through extensive numerical simulations. Our results can be attributed to an important theorem which, for a generalized random unitary operation, explicitly identifies the structure of all of its eigenspaces corresponding to eigenvalues of unit modulus.
The mixing time of a discrete-time quantum walk on the hypercube is considered. The mean probability distribution of a Markov chain on a hypercube is known to mix to a uniform distribution in time O(n log n)O(n\text{ }\text{log}\text{ }n)O(n log n). We show that the mean probability distribution of a discrete-time quantum walk on a hypercube mixes to a (generally nonuniform) distribution $\ensuremath{\pi}(x)$ in time O(n)O(n)O(n), and the stationary distribution is determined by the initial state of the walk. An explicit expression for $\ensuremath{\pi}(x)$ is derived for the particular case of a symmetric walk. These results are consistent with those obtained previously for a continuous-time quantum walk. The effect of decoherence due to randomly breaking links between connected sites in the hypercube is also considered. We find that the probability distribution mixes to the uniform distribution as expected. However, the mixing time has a minimum at a critical decoherence rate $p\ensuremath{\approx}0.1$. A similar effect was previously reported for a quantum walk on an NNN-cycle with decoherence from repeated measurements of position. A controlled amount of decoherence helps in obtaining---and preserving---a uniform distribution over the 2n{2}^{n}2n sites of the hypercube in the shortest possible time.
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.
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.
In this paper, we successfully obtain an explicit expression of the limit distribution [Formula: see text] of three-state quantum walks on cycles, the total variation distance between [Formula: see text] and the average probability [Formula: see text], and lower bound on the difference between two eigenvalues, among others. Based on the above conclusions, we finally get the mixing time [Formula: see text] of the quantum walk of Grover coin on the N-cycle. [Formula: see text] is the time required to characterize [Formula: see text] approaching [Formula: see text]. Our results show that the average probability of a three-state quantum walk on a cycle can approach its limit distribution faster than that of a two-state quantum walk, which might be of significance to quantum computation.