Decoherence in quantum walks - a review

Abstract

The development of quantum walks in the context of quantum computation, as generalisations of random walk techniques, led rapidly to several new quantum algorithms. These all follow unitary quantum evolution, apart from the final measurement. Since logical qubits in a quantum computer must be protected from decoherence by error correction, there is no need to consider decoherence at the level of algorithms. Nonetheless, enlarging the range of quantum dynamics to include non-unitary evolution provides a wider range of possibilities for tuning the properties of quantum walks. For example, small amounts of decoherence in a quantum walk on the line can produce more uniform spreading (a top-hat distribution), without losing the quantum speed up. This paper reviews the work on decoherence, and more generally on non-unitary evolution, in quantum walks and suggests what future questions might prove interesting to pursue in this area.

52 pages, invited review, v2 & v3 updates to include significant work since first posted and corrections from comments received; some non-trivial typos fixed. Comments now limited to changes that can be applied at proof stage

References in corpus (12)

• Exponential algorithmic speedup by quantum walk
• Spatial search by quantum walk
• Connecting the discrete and continuous-time quantum walks
• Spatial search and the Dirac equation
• A random walk approach to quantum algorithms
• Relaxation and Zeno effect in qubit measurements
• Quantum walks with infinite hitting times
• Continuous-time Quantum Walks on a Cycle Graph
• Quantum walks with random phase shifts
• Decoherence vs entanglement in coined quantum walks
• Almost uniform sampling via quantum walks
• Non-Unitary Quantum Walks on Hyper-Cycles

Cited by in corpus (6)

• Realization of quantum walks with negligible decoherence in waveguide lattices
• Quantum searches on highly symmetric graphs
• Decoherent quantum walks driven by a generic coin operation
• Decoherence in Two-Dimensional Quantum Random Walks with Traps
• Optimal computation with non-unitary quantum walks
• Correlation effects in a discrete quantum random walk