Decoherence in Discrete Quantum Walks

Abstract

We present an introduction to coined quantum walks on regular graphs, which have been developed in the past few years as an alternative to quantum Fourier transforms for underpinning algorithms for quantum computation. We then describe our results on the effects of decoherence on these quantum walks on a line, cycle and hypercube. We find high sensitivity to decoherence, increasing with the number of steps in the walk, as the particle is becoming more delocalised with each step. However, the effect of a small amount of decoherence can be to enhance the properties of the quantum walk that are desirable for the development of quantum algorithms, such as fast mixing times to uniform distributions.

15 pages, Springer LNP latex style, submitted to Proceedings of DICE 2002

References in corpus (8)

• A Quantum Random Walk Search Algorithm
• Exponential algorithmic speedup by quantum walk
• Controlling discrete quantum walks: coins and intitial states
• Quantum random walks in optical lattices
• The quantum to classical transition for random walks
• Quantum random walks with decoherent coins
• Quantum Random Walks Hit Exponentially Faster
• Decoherence in a quantum walk on the line

Cited by in corpus (13)

• Quantum walks: a comprehensive review
• One dimensional quantum walk with unitary noise
• Decoherence in Quantum Walks on the Hypercube
• Hitting time for the continuous quantum walk
• Decoherence in one-dimensional Quantum Walk
• Quantum Edge Detection for Image Segmentation in Optical Environments
• Optimal Estimation of States in Quantum Image Processing
• Analytical expression for variance of homogeneous-position quantum walk with decoherent position
• Quantum image processing?
• A Path Integral Approach for Disordered Quantum Walks in One Dimension
• A proposal for the optimal estimation of states in Quantum Information Processing
• Quantum Boolean Image Denoising
• On the von Neumann entropy of certain quantum walks subject to decoherence