{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T17:59:51Z","timestamp":1778695191131,"version":"3.51.4"},"reference-count":106,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2007,12,1]],"date-time":"2007-12-01T00:00:00Z","timestamp":1196467200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2007,12]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1017\/s0960129507006354","type":"journal-article","created":{"date-parts":[[2007,11,23]],"date-time":"2007-11-23T13:42:02Z","timestamp":1195825322000},"page":"1169-1220","source":"Crossref","is-referenced-by-count":240,"title":["Decoherence in quantum walks \u2013 a review"],"prefix":"10.1017","volume":"17","author":[{"given":"VIV","family":"KENDON","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2007,12,1]]},"reference":[{"key":"S0960129507006354_manual_ref-48","doi-asserted-by":"publisher","DOI":"10.1142\/S0219749906002195"},{"key":"S0960129507006354_manual_ref-69","unstructured":"Magniez, F. , Santha, M. and Szegedy, M. (2005) Quantum algorithms for the triangle problem. In: Proceedings of 16th ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia 1109\u20131117."},{"key":"S0960129507006354_manual_ref-84","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2004.08.070"},{"key":"S0960129507006354_manual_ref-29","doi-asserted-by":"publisher","DOI":"10.26421\/QIC6.3-3"},{"key":"S0960129507006354_manual_ref-70","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/9\/4\/087"},{"key":"S0960129507006354_manual_ref-95","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.73.012308"},{"key":"S0960129507006354_manual_ref-15","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.67.032304"},{"key":"S0960129507006354_manual_ref-59","first-page":"11","article-title":"Symmetricity of distribution for the one-dimentional Hadamard walk","volume":"10","author":"Konno","year":"2004","journal-title":"Interdisciplinary Infor. Sci."},{"key":"S0960129507006354_manual_ref-50","unstructured":"Kendon, V. and Maloyer, O. (2006) Optimal computation with non-unitary quantum walks. ArXiv: quant-ph\/0610240. To appear in Theor. Comp. Sci. A (2008) as a postproceedings volume for CiE 2006."},{"key":"S0960129507006354_manual_ref-36","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026119"},{"key":"S0960129507006354_manual_ref-56","doi-asserted-by":"publisher","DOI":"10.1023\/A:1023413713008"},{"key":"S0960129507006354_manual_ref-63","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.73.032341"},{"key":"S0960129507006354_manual_ref-75","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45726-7_14"},{"key":"S0960129507006354_manual_ref-26","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"S0960129507006354_manual_ref-98","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.53"},{"key":"S0960129507006354_manual_ref-18","unstructured":"Carlson, W. , Ford, A. , Harris, E. , Rosen, J. , Tamon, C. and Wrobel, K. (2006) Universal mixing of quantum walk on graphs. quant-ph\/0608044."},{"key":"S0960129507006354_manual_ref-24","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780552"},{"key":"S0960129507006354_manual_ref-5","doi-asserted-by":"publisher","DOI":"10.26421\/QIC3.6-4"},{"key":"S0960129507006354_manual_ref-10","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.109.1492"},{"key":"S0960129507006354_manual_ref-12","doi-asserted-by":"publisher","DOI":"10.1016\/j.physleta.2003.08.023"},{"key":"S0960129507006354_manual_ref-51","first-page":"463","volume-title":"Quantum Communication, Measurement and Computing (QCMC'02)","author":"Kendon","year":"2002"},{"key":"S0960129507006354_manual_ref-30","doi-asserted-by":"publisher","DOI":"10.1016\/j.physleta.2004.03.005"},{"key":"S0960129507006354_manual_ref-32","doi-asserted-by":"publisher","DOI":"10.1063\/1.3051743"},{"key":"S0960129507006354_manual_ref-34","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.047102"},{"key":"S0960129507006354_manual_ref-52","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.67.042315"},{"key":"S0960129507006354_manual_ref-11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.03.005"},{"key":"S0960129507006354_manual_ref-57","doi-asserted-by":"publisher","DOI":"10.2969\/jmsj\/1150287309"},{"key":"S0960129507006354_manual_ref-58","doi-asserted-by":"publisher","DOI":"10.1142\/S0219477505002987"},{"key":"S0960129507006354_manual_ref-99","unstructured":"Szegedy, M. (2004b) Spectra of quantized walks and a $\\sqrt{\\delta\\epsilon}$ rule. ArXiv: quant-ph\/0401053."},{"key":"S0960129507006354_manual_ref-101","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.65.032310"},{"key":"S0960129507006354_manual_ref-83","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2004.02.061"},{"key":"S0960129507006354_manual_ref-92","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.67.052307"},{"key":"S0960129507006354_manual_ref-104","unstructured":"Watrous, J. (2002) Private communication."},{"key":"S0960129507006354_manual_ref-44","doi-asserted-by":"crossref","unstructured":"Keating, J. P. , Linden, N. , Matthews, J. C. F. and Winter, A. (2006) Localization and its consequences for quantum walk algorithms and quantum communication. ArXiv: quant-ph\/0606205.","DOI":"10.1103\/PhysRevA.76.012315"},{"key":"S0960129507006354_manual_ref-49","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2006.1901"},{"key":"S0960129507006354_manual_ref-73","doi-asserted-by":"publisher","DOI":"10.1063\/1.523304"},{"key":"S0960129507006354_manual_ref-81","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/9\/3\/072"},{"key":"S0960129507006354_manual_ref-2","doi-asserted-by":"crossref","unstructured":"Adamczak, W. , Andrew, K. , Bergen, L. , Ethier, D. , Hernberg, P. , Lin, J. and Tamon, C. (2007) Non-uniform mixing of quantum walk on cycles. Intl. J. Quantum Inf. (to appear). See also ArXiv: 0708.2096.","DOI":"10.1142\/S0219749907003195"},{"key":"S0960129507006354_manual_ref-25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.66.052319"},{"key":"S0960129507006354_manual_ref-105","volume-title":"Aspects and Applications of the Random Walk","author":"Weiss","year":"1994"},{"key":"S0960129507006354_manual_ref-47","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-004-0423-2"},{"key":"S0960129507006354_manual_ref-91","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.68.062315"},{"key":"S0960129507006354_manual_ref-90","unstructured":"Severini, S. (2006) Graphs of a unitary matrix. math.CO\/0303084."},{"key":"S0960129507006354_manual_ref-78","doi-asserted-by":"publisher","DOI":"10.1023\/A:1023012502046"},{"key":"S0960129507006354_manual_ref-38","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"S0960129507006354_manual_ref-88","first-page":"17","volume-title":"40th Annual Symposium on FOCS","author":"Sch\u00f6ning","year":"1999"},{"key":"S0960129507006354_manual_ref-60","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.79.4794"},{"key":"S0960129507006354_manual_ref-61","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.74.022310"},{"key":"S0960129507006354_manual_ref-6","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.72.062304"},{"key":"S0960129507006354_manual_ref-71","doi-asserted-by":"publisher","DOI":"10.1007\/BF02199356"},{"key":"S0960129507006354_manual_ref-82","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.76.042306"},{"key":"S0960129507006354_manual_ref-8","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.54"},{"key":"S0960129507006354_manual_ref-66","unstructured":"Lomont, C. (2004) The hidden subgroup problem \u2013 review and open problems. ArXiv: quant-ph\/0411037."},{"key":"S0960129507006354_manual_ref-72","doi-asserted-by":"publisher","DOI":"10.1016\/S0375-9601(96)00745-1"},{"key":"S0960129507006354_manual_ref-87","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.67.042305"},{"key":"S0960129507006354_manual_ref-97","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.73.054302"},{"key":"S0960129507006354_manual_ref-35","doi-asserted-by":"publisher","DOI":"10.1142\/S0219025705001895"},{"key":"S0960129507006354_manual_ref-74","doi-asserted-by":"publisher","DOI":"10.26421\/QIC7.1-2-5"},{"key":"S0960129507006354_manual_ref-106","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45833-6_26"},{"key":"S0960129507006354_manual_ref-42","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.69.052323"},{"key":"S0960129507006354_manual_ref-85","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.72.062317"},{"key":"S0960129507006354_manual_ref-45","doi-asserted-by":"publisher","DOI":"10.1080\/00107151031000110776"},{"key":"S0960129507006354_manual_ref-100","doi-asserted-by":"publisher","DOI":"10.1007\/s11080-006-8220-2"},{"key":"S0960129507006354_manual_ref-1","unstructured":"Adamczak, W. , Andrew, K. , Hernberg, P. and Tamon, C. (2003) A note on graphs resistant to quantum uniform mixing. ArXiv: quant-ph\/0308073."},{"key":"S0960129507006354_manual_ref-13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300933"},{"key":"S0960129507006354_manual_ref-22","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.70.022314"},{"key":"S0960129507006354_manual_ref-37","first-page":"197","article-title":"Quantum cellular automata","volume":"2","author":"Grossing","year":"1988","journal-title":"Complex Systems"},{"key":"S0960129507006354_manual_ref-68","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/35\/12\/304"},{"key":"S0960129507006354_manual_ref-19","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/7\/1\/156"},{"key":"S0960129507006354_manual_ref-9","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380757"},{"key":"S0960129507006354_manual_ref-27","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.73.012302"},{"key":"S0960129507006354_manual_ref-94","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.73.012313"},{"key":"S0960129507006354_manual_ref-7","doi-asserted-by":"publisher","DOI":"10.1142\/S0219749903000383"},{"key":"S0960129507006354_manual_ref-16","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.91.130602"},{"key":"S0960129507006354_manual_ref-46","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45198-3_30"},{"key":"S0960129507006354_manual_ref-67","first-page":"052305","article-title":"Decoherence in quantum walks: Existence of a quantum-classical transition","volume":"68","author":"Lop\u00e9z","year":"2003","journal-title":"Phys. Rev. A"},{"key":"S0960129507006354_manual_ref-77","unstructured":"Nayak, A. and Vishwanath, A. (2000) Quantum walk on the line. quant-ph\/0010117."},{"key":"S0960129507006354_manual_ref-14","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.61.013410"},{"key":"S0960129507006354_manual_ref-53","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.71.022307"},{"key":"S0960129507006354_manual_ref-65","doi-asserted-by":"publisher","DOI":"10.26421\/QIC6.4-5-5"},{"key":"S0960129507006354_manual_ref-86","volume-title":"Quantum Phase Transitions","author":"Sachdev","year":"1999"},{"key":"S0960129507006354_manual_ref-79","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.72.012332"},{"key":"S0960129507006354_manual_ref-96","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.74.030301"},{"key":"S0960129507006354_manual_ref-17","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.67.052317"},{"key":"S0960129507006354_manual_ref-20","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/36\/33\/305"},{"key":"S0960129507006354_manual_ref-62","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.95.080501"},{"key":"S0960129507006354_manual_ref-76","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"S0960129507006354_manual_ref-89","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479802410293"},{"key":"S0960129507006354_manual_ref-55","doi-asserted-by":"publisher","DOI":"10.1080\/09500340408232489"},{"key":"S0960129507006354_manual_ref-3","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380758"},{"key":"S0960129507006354_manual_ref-31","doi-asserted-by":"publisher","DOI":"10.1007\/BF01886518"},{"key":"S0960129507006354_manual_ref-54","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.68.020301"},{"key":"S0960129507006354_manual_ref-43","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380877"},{"key":"S0960129507006354_manual_ref-23","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.70.042312"},{"key":"S0960129507006354_manual_ref-40","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.56.15215"},{"key":"S0960129507006354_manual_ref-64","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.74.042334"},{"key":"S0960129507006354_manual_ref-93","first-page":"1484","article-title":"Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer","volume":"26","author":"Shor","year":"1997","journal-title":"SIAM J. Sci Statist. Comput."},{"key":"S0960129507006354_manual_ref-102","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/5\/1\/383"},{"key":"S0960129507006354_manual_ref-39","volume-title":"Quantum Probability","author":"Gudder","year":"1988"},{"key":"S0960129507006354_manual_ref-28","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.58.915"},{"key":"S0960129507006354_manual_ref-4","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.48.1687"},{"key":"S0960129507006354_manual_ref-33","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/37\/30\/013"},{"key":"S0960129507006354_manual_ref-41","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.91.066801"},{"key":"S0960129507006354_manual_ref-80","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.93.190503"},{"key":"S0960129507006354_manual_ref-103","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1732"},{"key":"S0960129507006354_manual_ref-21","doi-asserted-by":"publisher","DOI":"10.26421\/QIC5.7-7"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129507006354","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T06:01:22Z","timestamp":1750485682000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129507006354\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12]]},"references-count":106,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2007,6]]}},"alternative-id":["S0960129507006354"],"URL":"https:\/\/doi.org\/10.1017\/s0960129507006354","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12]]}}}