Mixing Times in Quantum Walks on the Hypercube

Abstract

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). We show that the mean probability distribution of a discrete-time quantum walk on a hypercube mixes to a (generally non-uniform) distribution pi(x) in time O(n) and the stationary distribution is determined by the initial state of the walk. An explicit expression for 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\approx 0.1$. A similar effect was previously reported for the QW on the N-cycle with decoherence from repeated measurements of position. A controlled amount of decoherence helps to obtain--and preserve--a uniform distribution over the $2^n$ sites of the hypercube in the shortest possible time.

REVTeX, 9 pages, with small corrections

References in corpus (14)

• Quantum random walks - an introductory overview
• Quantum Computation and Decision Trees
• A Quantum Random Walk Search Algorithm
• Spatial search by quantum walk
• Decoherence can be useful in quantum walks
• Connecting the discrete and continuous-time quantum walks
• Quantum random walks with decoherent coins
• Hitting time for quantum walks on the hypercube
• Decoherence in the quantum walk on the line
• Quantum Random Walks Hit Exponentially Faster
• One dimensional quantum walk with unitary noise
• Decoherence vs entanglement in coined quantum walks
• Decoherence in Quantum Walks on the Hypercube
• Decoherent quantum walks driven by a generic coin operation

Cited by in corpus (29)

• Decoherence in one-dimensional Quantum Walk
• Review on Quantum Walk Computing: Theory, Implementation, and Application
• Asymptotic entanglement in a two-dimensional quantum walk
• Group Velocity of Discrete-Time Quantum Walks
• Equivalence of Szegedy's and Coined Quantum Walks
• How fast do quantum walks mix?
• Mixing Times in Quantum Walks on Two-Dimensional Grids
• Analog quantum algorithms for the mixing of Markov chains
• Discrete time quantum walks on percolation graphs
• Simulation of Quantum Walks and Fast Mixing with Classical Processes
• Quantum walk transport on carbon nanotube structures
• Reexamination of decoherence in quantum walks on the hypercube
• Percolated quantum walks with a general shift operator: From trapping to transport
• Efficient tests for equivalence of hidden Markov processes and quantum random walks
• Understanding and controlling N-dimensional quantum walks via dispersion relations. Application to the 2D and 3D Grover walks: Diabolical points and more
• High-dimensional quantum state transfer in a noisy network environment
• The uniform measure for quantum walk on hypercube: a quantum Bernoulli noises approach
• A spectral analysis of discrete-time quantum walks related to the birth and death chains
• Study of Quantum Walk over a Square Lattice
• Quantum Walks on Sierpinski Gaskets
• Decoherence in Search Algorithms
• Transient temperature and mixing times of quantum walks on cycles
• Tunneling effects in a one-dimensional quantum walk
• The switching effect of the side chain on quantum walks on triple graphs
• Analytical solutions for quantum walks on 1D chain with different shift operators
• Quantum Ultra-Walks: Walks on a Line with Hierarchical Spatial Heterogeneity
• Improving quantum walk metrology with split-step quantum walk
• Exact solutions and symmetry analysis for the limiting probability distribution of quantum walks
• Strong dispersion property for the quantum walk on the hypercube