2006/10/31 by Viv Kendon, Olivier Maloyer
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum and electron transport phenomena #quant-ph
paper · pdf · doi:10.1016/j.tcs.2007.12.011
published as Theoretical Computer Science 394(3) pp187-196 2008 · 16 pages, 3 eps figures, ELsevier style; v2 clarification added to start of Sec. 4, typos fixed & refs updated; v3 error fixed in qubit counts on p. 9, refs updated, to appear (in 2008) in TCS-A postproceedings volume of CiE 2006
arxiv created 2007/09/18 · openalex publication_date 2008/02/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/02
Quantum versions of random walks on the line and the cycle show a quadratic improvement over classical random walks in their spreading rates and mixing times respectively. Non-unitary quantum walks can provide a useful optimisation of these properties, producing a more uniform distribution on the line, and faster mixing times on the cycle. We investigate the interplay between quantum and random dynamics by comparing the resources required, and examining numerically how the level of quantum correlations varies during the walk. We show numerically that the optimal non-unitary quantum walk proceeds such that the quantum correlations are nearly all removed at the point of the final measurement. This requires only O(log T) random bits for a quantum walk of T steps