2006/06/30 by Viv Kendon, VIV KENDON · 5 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Physics and Astronomy · #DNA and Biological Computing #Quantum Computing Algorithms and Architecture #Quantum-Dot Cellular Automata #quant-ph
paper · pdf · doi:10.1017/s0960129507006354
published as Math. Struct. in Comp. Sci 17(6) pp 1169-1220 (2006) · 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
arxiv created 2006/11/26 · openalex publication_date 2007/11/23 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/04
The development of quantum walks in the context of quantum computation, as generalisations of random walk techniques, has led rapidly to several new quantum algorithms. These all follow a 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.