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

International Journal of Modern Physics B

Mixing times of three-state quantum walks on cycles

Qi Han, Ning Bai, Huan Wang, Yaxin Kou

Published Oct 19, 2022• 2 citations
Publisher

Abstract

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.

DOI
10.1142/s0217979223500935

Related papers

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

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

arXiv:0908.1524•Physical Review E•Mar 15, 2010•20 citations

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

Three-state quantum walks on cycles

Qi Han, Ning Bai, Yaxin Kou +1 more

In this paper, on the basis of constructing a new shift operator [Formula: see text] and choosing the Grover coin [Formula: see text] as coin operator [Formula: see text], we get the standard evolution operator [Formula: see text] on cycles. Using [Formula: see text], we not only got the analytical expression of wavefunction [Formula: see text], but also obtained the conclusion that the limit distribution [Formula: see text] of [Formula: see text], which is not uniform distribution, regardless of [Formula: see text] is odd or even.

International Journal of Modern Physics B•Apr 18, 2022•4 citations

Bounds of Quantum Mixing Processes via Controlled Walks

Li, Shang

Quantum mixing is a category of processes of reaching a stationary state when starting from a single initial vertex via quantum walks. In this thesis, we introduce the quantum mixing processes based on the framework of controlled quantum walks in [DH17a]. We first discuss why Szegedy's walks are not well-suited for the quantum mixing processes. We then show that the controlled quantum walk is a suitable framework for achieving a quadratic speed-up in the quantum mixing processes, because of its relationship with interpolated walks [KMOR16] and the phase estimation algorithm [CEMM98]. Accordingly, we give two definitions of quantum mixing times via controlled quantum walks: instant quantum mixing time and average quantum mixing time. We later prove the bounds of these two quantum mixing times on complete graphs. We also prove the upper bound of the average quantum mixing times on cycle graphs. To have clearer views on the bounds of instant and average quantum mixing times, we then discuss and present the simulations of quantum mixing processes, with four types of graphs (complete graphs, cycle graphs, 2-dimensional tori and dumbbell graphs) as examples. The simulations include the quantum mixing processes with the same ~θ (an important parameter in the controlled quantum walk operator) as in [DH17a], and the suitable range of ~θ that achieves the quadratic speed-up for different types of graphs. Inspired by the quantum search algorithm via controlled quantum walks in [DH17a], we adapt this algorithm to a new algorithm of quantum mixing, which generates samples from the stationary distribution of the Markov chain, with its runtime upper bounded by the quantum hitting time, which is quadratically faster than the classical hitting process.

•Apr 29, 2020•0 citations

Quantum walks on N-cycles with an absorbing wall

Qi Han, Ning Bai, Huan Wang +2 more

In this paper, we analyze quantum walks on cycles with an absorbing wall. We set the absorbing wall on cycles with N vertices (where N is an even number), and divide [Formula: see text] into two parts, [Formula: see text] and [Formula: see text]. Due to the periodicity of the cycles, the condition [Formula: see text] (or [Formula: see text]) is applied to [Formula: see text] and [Formula: see text], then the transmission probability [Formula: see text] and reflection probability [Formula: see text] at the absorbing wall [Formula: see text] at time t are obtained. Furthermore, we show that over time, the absorbing wall absorbs less and less.

Modern Physics Letters B•Jul 5, 2023•0 citations

Quantum Walks on the Hypercube

Cristopher Moore, Alexander C. Russell

Recently, it has been shown that one-dimensional quantum walks can mix more quickly than classical random walks, suggesting that quantum Monte Carlo algorithms can outperform their classical counterparts. We study two quantum walks on the n-dimensional hypercube, one in discrete time and one in continuous time. In both cases we show that the quantum walk mixes in (π/4)n steps, faster than the O(n log n) steps required by the classical walk. In the continuous-time case, the probability distribution is {\em exactly} uniform at this time. More importantly, these walks expose several subtleties in the definition of mixing time for quantum walks. Even though the continuous-time walk has an O(n) instantaneous mixing time at which it is precisely uniform, it never approaches the uniform distribution when the stopping time is chosen randomly as in [AharonovAKV2001]. Our analysis treats interference between terms of different phase more carefully than is necessary for the walk on the cycle; previous general bounds predict an exponential, rather than linear, mixing time for the hypercube.

arXiv:quant-ph/0104137•Apr 29, 2001•9 citations
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.
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/ϵ).
In this paper, on the basis of constructing a new shift operator [Formula: see text] and choosing the Grover coin [Formula: see text] as coin operator [Formula: see text], we get the standard evolution operator [Formula: see text] on cycles. Using [Formula: see text], we not only got the analytical expression of wavefunction [Formula: see text], but also obtained the conclusion that the limit distribution [Formula: see text] of [Formula: see text], which is not uniform distribution, regardless of [Formula: see text] is odd or even.
Quantum mixing is a category of processes of reaching a stationary state when starting from a single initial vertex via quantum walks. In this thesis, we introduce the quantum mixing processes based on the framework of controlled quantum walks in [DH17a]. We first discuss why Szegedy's walks are not well-suited for the quantum mixing processes. We then show that the controlled quantum walk is a suitable framework for achieving a quadratic speed-up in the quantum mixing processes, because of its relationship with interpolated walks [KMOR16] and the phase estimation algorithm [CEMM98]. Accordingly, we give two definitions of quantum mixing times via controlled quantum walks: instant quantum mixing time and average quantum mixing time. We later prove the bounds of these two quantum mixing times on complete graphs. We also prove the upper bound of the average quantum mixing times on cycle graphs. To have clearer views on the bounds of instant and average quantum mixing times, we then discuss and present the simulations of quantum mixing processes, with four types of graphs (complete graphs, cycle graphs, 2-dimensional tori and dumbbell graphs) as examples. The simulations include the quantum mixing processes with the same ~θ (an important parameter in the controlled quantum walk operator) as in [DH17a], and the suitable range of ~θ that achieves the quadratic speed-up for different types of graphs. Inspired by the quantum search algorithm via controlled quantum walks in [DH17a], we adapt this algorithm to a new algorithm of quantum mixing, which generates samples from the stationary distribution of the Markov chain, with its runtime upper bounded by the quantum hitting time, which is quadratically faster than the classical hitting process.
In this paper, we analyze quantum walks on cycles with an absorbing wall. We set the absorbing wall on cycles with N vertices (where N is an even number), and divide [Formula: see text] into two parts, [Formula: see text] and [Formula: see text]. Due to the periodicity of the cycles, the condition [Formula: see text] (or [Formula: see text]) is applied to [Formula: see text] and [Formula: see text], then the transmission probability [Formula: see text] and reflection probability [Formula: see text] at the absorbing wall [Formula: see text] at time t are obtained. Furthermore, we show that over time, the absorbing wall absorbs less and less.
Recently, it has been shown that one-dimensional quantum walks can mix more quickly than classical random walks, suggesting that quantum Monte Carlo algorithms can outperform their classical counterparts. We study two quantum walks on the n-dimensional hypercube, one in discrete time and one in continuous time. In both cases we show that the quantum walk mixes in (π/4)n steps, faster than the O(n log n) steps required by the classical walk. In the continuous-time case, the probability distribution is {\em exactly} uniform at this time. More importantly, these walks expose several subtleties in the definition of mixing time for quantum walks. Even though the continuous-time walk has an O(n) instantaneous mixing time at which it is precisely uniform, it never approaches the uniform distribution when the stopping time is chosen randomly as in [AharonovAKV2001]. Our analysis treats interference between terms of different phase more carefully than is necessary for the walk on the cycle; previous general bounds predict an exponential, rather than linear, mixing time for the hypercube.