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.

Małgorzata Bednarska, Andrzej Grudka, Paweł Kurzyński +2 more

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.

Martins Kokainis, Krišjānis Prūsis, Jevgēnijs Vihrovs +2 more

Abstract We show that the discrete time quantum walk on the Boolean hypercube of dimension n has a strong dispersion property: if the walk is started in one vertex, then the probability of the walker being at any particular vertex after O ( n ) steps is of an order O ( 1.4818 − n ) . This improves over the known mixing results for this quantum walk which show that the probability distribution after O ( n ) steps is close to uniform but do not show that the probability is small for every vertex. Our result shows that quantum walk on hypercube is interesting for algorithmic applications which require fast dispersion over the state space.

Peng Xue