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

Bulletin of the American Physical Society

Decoherence in the hypercube quantum walk

Frederick W. Strauch

Published Mar 19, 2009• 0 citations
OpenAlex

Related papers

Quantum Walks on the Hypercube

Cristopher Moore, Alexander C. Russell

Lecture notes in computer science•Jan 1, 2002•209 citations

Decoherence in quantum walks on the hypercube

Gorjan Alagic, Alexander C. Russell

We study a natural notion of decoherence on quantum random walks over the hypercube. We prove that this model possesses a decoherence threshold beneath which the essential properties of the hypercubic quantum walk, such as linear mixing times, are preserved. Beyond the threshold, we prove that the walks behave like their classical counterparts.

arXiv:quant-ph/0501169•Physical Review A•Dec 5, 2005•64 citations

Decoherence in Discrete Quantum Walks

Viv M. Kendon, Ben Tregenna

arXiv:quant-ph/0301182•Lecture notes in physics•Dec 9, 2003•32 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•46 citations

Decoherence in the Three-State Quantum Walk

Luísa Toledo Tude, M. C. de Oliveira

arXiv:2107.09124•Physica A Statistical Mechanics and its Applications•Jan 1, 2022•6 citations

Complete characterization of mixing time for the continuous quantum walk on the hypercube with Markovian decoherence model

Milosh Drezgich, Andrew P. Hines, Mohan Sarovar +1 more

The n-dimensional hypercube quantum random walk (QRW) is a particularily appealing example of a quantum walk because it has a natural implementation on a register on n qubits. However, any real implementation will encounter decoherence effects due to interactions with uncontrollable degrees of freedom. We present a complete characterization of the mixing properties of the hypercube QRW under a physically relevant Markovian decoherence model. In the local decoherence model considered the non-unitary dynamics are modeled as a sum of projections on individual qubits to an arbitrary direction on the Bloch sphere. We prove that there is always classical (asymptotic) mixing in this model and specify the conditions under which instantaneous mixing always exists. And we show that the latter mixing property, as well as the classical mixing time, depend heavily on the exact environmental interaction and its strength. Therefore, algorithmic applications of the QRW on the hypercube, if they intend to employ mixing properties, need to consider both the walk dynamics and the precise decoherence model.

arXiv:0811.4472•Quantum Information and Computation•Sep 1, 2009•7 citations
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.
The n-dimensional hypercube quantum random walk (QRW) is a particularily appealing example of a quantum walk because it has a natural implementation on a register on n qubits. However, any real implementation will encounter decoherence effects due to interactions with uncontrollable degrees of freedom. We present a complete characterization of the mixing properties of the hypercube QRW under a physically relevant Markovian decoherence model. In the local decoherence model considered the non-unitary dynamics are modeled as a sum of projections on individual qubits to an arbitrary direction on the Bloch sphere. We prove that there is always classical (asymptotic) mixing in this model and specify the conditions under which instantaneous mixing always exists. And we show that the latter mixing property, as well as the classical mixing time, depend heavily on the exact environmental interaction and its strength. Therefore, algorithmic applications of the QRW on the hypercube, if they intend to employ mixing properties, need to consider both the walk dynamics and the precise decoherence model.