Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-10T08:26:03.184Z Has data issue: false hasContentIssue false
  • English
  • Français

Decoherence in quantum walks – a review

Published online by Cambridge University Press:  01 December 2007

VIV KENDON
VIV KENDON*
Affiliation:
School of Physics and Astronomy, University of Leeds, Leeds, LS2 9JT, U.K. Email: v.kendon@leeds.ac.uk
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 17 , Issue 6 , December 2007 , pp. 1169 - 1220
Copyright
Copyright © Cambridge University Press 2007

References

Adamczak, W., Andrew, K., Hernberg, P. and Tamon, C. (2003) A note on graphs resistant to quantum uniform mixing. ArXiv: quant-ph/0308073.Google Scholar
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.Google Scholar
Aharonov, D., Ambainis, A., Kempe, J. and Vazirani, U. (2001) Quantum walks on graphs. In: Proc. 33rd Annual ACM STOC., ACM 50–59.CrossRefGoogle Scholar
Aharonov, Y., Davidovich, L. and Zagury, N. (1992) Quantum random walks. Phys. Rev. A 48 (2)1687–1690.CrossRefGoogle Scholar
Ahmadi, A., Belk, R., Tamon, C. and Wendler, C. (2003) On mixing in continuous-time quantum walks on some circulant graphs. Quantum Information and Computation 3 (6)611–618.CrossRefGoogle Scholar
Alagić, G. and Russell, A. (2005) Decoherence in quantum walks on the hypercube. Phys. Rev. A 72 0062304.CrossRefGoogle Scholar
Ambainis, A. (2003) Quantum walks and their algorithmic applications. Intl. J. Quantum Information 1 (4)507–518.CrossRefGoogle Scholar
Ambainis, A. (2004) Quantum walk algorithms for element distinctness. In: 45th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press 22–31.CrossRefGoogle Scholar
Ambainis, A., Bach, E., Nayak, A., Vishwanath, A. and Watrous, J. (2001) One-dimensional quantum walks. In: Proc. 33rd Annual ACM STOC., ACM 60–69.CrossRefGoogle Scholar
Anderson, P. W. (1958) Absence of diffusion in certain random lattices. Phys. Rev. 109 (5)1492–1505.CrossRefGoogle Scholar
Bach, E., Coppersmith, S., Goldschen, M. P., Joynt, R. and Watrous, J. (2004) One-dimensional quantum walks with absorbing boundaries. J. Comput. Syst. Sci. 69 (4)562–592.CrossRefGoogle Scholar
Bednarska, M., Grudka, A., Kurzyński, P., Łuczak, T. and Wójcik, A. (2003) Quantum walks on cycles. Phys. Lett. A 317 (1–2)21–25.CrossRefGoogle Scholar
Bennett, C. H., Bernstein, E., Brassard, G. and Vazirani, U. (1997) Strengths and weaknesses of quantum computing. SIAM J. Comput. 26 (5)151–152.CrossRefGoogle Scholar
Bouwmeester, D., Marzoli, I., Karman, G. P., Schleich, W. and Woerdman, J. P. (1999) Optical Galton board. Phys. Rev. A 61 013410.CrossRefGoogle Scholar
Brun, T. A., Carteret, H. A. and Ambainis, A. (2003a) Quantum random walks with decoherent coins. Phys. Rev. A 67 032304.CrossRefGoogle Scholar
Brun, T. A., Carteret, H. A. and Ambainis, A. (2003b) The quantum to classical transition for random walks. Phys. Rev. Lett. 91 (13)130602.CrossRefGoogle ScholarPubMed
Brun, T. A., Carteret, H. A. and Ambainis, A. (2003c) Quantum walks driven by many coins. Phys. Rev. A 67 052317.CrossRefGoogle Scholar
Carlson, W., Ford, A., Harris, E., Rosen, J., Tamon, C. and Wrobel, K. (2006) Universal mixing of quantum walk on graphs. quant-ph/0608044.Google Scholar
Carneiro, I., Loo, M., Xu, X., Girerd, M., Kendon, V. M. and Knight, P. L. (2005) Entanglement in coined quantum walks on regular graphs. New J. Phys. 7 56.CrossRefGoogle Scholar
Carteret, H. A., Ismail, M. A. and Richmond, B. (2003) Three routes to the exact asymptotics for the one-dimensional quantum walk. J. Phys. A 36 (33)8775–8795.CrossRefGoogle Scholar
Childs, A. and Eisenberg, J. M. (2005) Quantum algorithms for subset finding. Quantum Information and Computation 5 593–604.CrossRefGoogle Scholar
Childs, A. and Goldstone, J. (2004a) Spatial search by quantum walk. Phys. Rev. A 70 022314.CrossRefGoogle Scholar
Childs, A. M. and Goldstone, J. (2004b) Spatial search and the Dirac equation. Phys. Rev. A 70 042312.CrossRefGoogle Scholar
Childs, A. M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S. and Spielman, D. A., (2003) Exponential algorithmic speedup by a quantum walk. In: Proc. 35th Annual ACM STOC., ACM 59–68.CrossRefGoogle Scholar
Dür, W., Raussendorf, R., Kendon, V. M. and Briegel, H.-J. (2002) Quantum random walks in optical lattices. Phys. Rev. A 66 052319.CrossRefGoogle Scholar
Dyer, M., Frieze, A. and Kannan, R. (1991) A random polynomial-time algorithm for approximating the volume of convex bodies. J. of the ACM 38 (1)1–17.CrossRefGoogle Scholar
Ermann, L., Paz, J. P. and Sraceno, M. (2006) Decoherence induced by a chaotic environment: a quantum walker with a complex coin. Phys. Rev. A 73 (1)012302.CrossRefGoogle Scholar
Farhi, E. and Gutmann, S. (1998) Quantum computation and decison trees. Phys. Rev. A 58 915–928.CrossRefGoogle Scholar
Fedichkin, L., Solenov, D. and Tamon, C. (2006) Mixing and decoherence in continuous time quantum walks on cycles. Quantum Information and Computation 6 (3)263–276.CrossRefGoogle Scholar
Feldman, E. and Hillery, M. (2004) Scattering theory and discrete-time quantum walks. Phys. Lett. A 324 (3)277.CrossRefGoogle Scholar
Feynman, R. P. (1986) Quantum mechanical computers. Found. Phys. 16 507.CrossRefGoogle Scholar
Feynman, R. P., Leighton, R. B. and Sands, M. (1964) Feynman Lectures on Physics, Addison Wesley.CrossRefGoogle Scholar
Flitney, A. P., Abott, D. and Johnson, N. F. (2004) Quantum random walks with history dependence. J. Phys. A 37 7581–7591.CrossRefGoogle Scholar
Gottlieb, A. D. (2004) Two examples of discrete-time quantum walks taking continuous steps. Phys. Rev. E 72 (4)047102.CrossRefGoogle Scholar
Gottlieb, A. D., Janson, S. and Scudo, P. F. (2005) Convergence of coined quantum walks in $\mathbb{R}^d$. Inf. Dimen. Anal. Quantum Probab. Rel. Topics 8 (1)129–140.CrossRefGoogle Scholar
Grimmett, G., Janson, S. and Scudo, P. (2004) Weak limits for quantum random walks. Phys. Rev. E 69 026119.CrossRefGoogle ScholarPubMed
Grossing, G. and Zeilinger, A. (1988) Quantum cellular automata. Complex Systems 2 197–208.Google Scholar
Grover, L. K. (1996) A fast quantum mechanical algorithm for database search. In: Proc. 28th Annual ACM STOC., ACM 212.CrossRefGoogle Scholar
Gudder, S. (1988) Quantum Probability, Academic Press.Google Scholar
Gurvitz, S. A. (1997) Measurements with a noninvasive detector and dephasing mechanism. Phys. Rev. B 56 15215.CrossRefGoogle Scholar
Gurvitz, S. A., Fedichkin, L., Mozyrsky, D. and Berman, G. P. (2003) Relaxation and Zeno effects in qubit measurements. Phys. Rev. Lett. 91 066801.CrossRefGoogle ScholarPubMed
Inui, N., Konishi, Y. and Konno, N. (2004) Localization of two-dimensional quantum walks. Phys. Rev. A 69 052323.CrossRefGoogle Scholar
Jerrum, M., Sinclair, A. and Vigoda, E. (2001) A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. In: Proc. 33rd Annual ACM STOC., ACM 712–721.CrossRefGoogle Scholar
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.Google Scholar
Kempe, J. (2003a) Quantum random walk algorithms. Contemp. Phys. 44 (3)302–327.CrossRefGoogle Scholar
Kempe, J. (2003b) Quantum random walks hit exponentially faster. In: Proc. 7th Intl. Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM '03). Springer-Verlag Lecture Notes in Computer Science 354–369.CrossRefGoogle Scholar
Kempe, J. (2005) Quantum random walks hit exponentially faster. Probability Th. and Related Fields 133 (2)215–235.CrossRefGoogle Scholar
Kendon, V. (2006a) Quantum walks on general graphs. Int. J. Quantum Inf. 4 (5)791–805. See also quant-ph/0306140.CrossRefGoogle Scholar
Kendon, V. (2006b) A random walk approach to quantum algorithms. Phil. Trans. Roy. Soc. A 364 3407–3422.CrossRefGoogle ScholarPubMed
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.Google Scholar
Kendon, V. and Tregenna, B. (2002) Decoherence in a quantum walk on a line. In: Shapiro, J. H. and Hirota, O. (eds.) Quantum Communication, Measurement and Computing (QCMC'02), Rinton Press 463.Google Scholar
Kendon, V. and Tregenna, B. (2003) Decoherence can be useful in quantum walks. Phys. Rev. A 67 042315.CrossRefGoogle Scholar
Kendon, V. M. and Sanders, B. C. (2004) Complementarity and quantum walks. Phys. Rev. A 71 022307.CrossRefGoogle Scholar
Knight, P. L., Roldán, E. and Sipe, J. E. (2003) Quantum walk on the line as an interference phenomenon. Phys. Rev. A 68 020301(R).CrossRefGoogle Scholar
Knight, P. L., Roldán, E. and Sipe, J. E. (2004) Propagating quantum walks: the origin of interference structures. J. Mod. Opt. 51 1761–1777.CrossRefGoogle Scholar
Konno, N. (2002) Quantum random walks in one dimension. Quantum Information Processing 1 (5)345–354.CrossRefGoogle Scholar
Konno, N. (2005a) A new type of limit theorems for the one-dimensional quantum random walk. Journal of the Mathematical Society of Japan 57 (4)1179–1195.CrossRefGoogle Scholar
Konno, N. (2005b) A path integral approach for disordered quantum walks in one dimension. Fluctuation and Noise Letters 5 (4)529–537.CrossRefGoogle Scholar
Konno, N., Namiki, T. and Soshi, T. (2004) Symmetricity of distribution for the one-dimentional Hadamard walk. Interdisciplinary Infor. Sci. 10 (1)11–22.Google Scholar
Kottos, T. and Smilansky, U. (1997) Quantum chaos on graphs. Phys. Rev. Lett. 79 4794–4797.CrossRefGoogle Scholar
Košík, J., Bužek, V. and Hillery, M. (2006) Quantum walks with random phase shifts. Phys. Rev. A 74 (2)022310.CrossRefGoogle Scholar
Kraus, B., Gisin, N. and Renner, R. (2005) Lower and upper bounds on the secret key rate for QKD protocols using one-way classical communication. Phys. Rev. Lett. 95 080501.CrossRefGoogle ScholarPubMed
Krovi, H. and Brun, T. A. (2006a) Hitting time for quantum walks on the hypercube. Phys. Rev. A 73 (3)032341.CrossRefGoogle Scholar
Krovi, H. and Brun, T. A. (2006b) Quantum walks with infinite hitting times. Phys. Rev. A 74 (4)042334.CrossRefGoogle Scholar
Lo, P., Rajaram, S., Schepens, D., Sullivan, D., Tamon, C. and Ward, J. (2006) Mixing of quantum walk on circulant bunkbeds. Quantum Information and Computation 6 (4–5)370–381.CrossRefGoogle Scholar
Lomont, C. (2004) The hidden subgroup problem – review and open problems. ArXiv: quant-ph/0411037.Google Scholar
Lopéz, C. C. and Paz, J. P. (2003) Decoherence in quantum walks: Existence of a quantum-classical transition. Phys. Rev. A 68 052305.Google Scholar
Mackay, T. D., Bartlett, S. D., Stephenson, L. T. and Sanders, B. C. (2002) Quantum walks in higher dimensions. J. Phys. A: Math. Gen. 35 2745.CrossRefGoogle Scholar
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–1117.Google Scholar
Maloyer, O. and Kendon, V. (2007) Decoherence vs entanglement in coined quantum walks. New J. Phys. 9 87.CrossRefGoogle Scholar
Meyer, D. A. (1996a) From quantum cellular automata to quantum lattice gases. J. Stat. Phys. 85 551–574.CrossRefGoogle Scholar
Meyer, D. A. (1996b) On the absence of homogeneous scalar unitary cellular automata. Phys. Lett. A 223 (5)337–340.CrossRefGoogle Scholar
Misra, B. and Sudarshan, E. C. G. (1977) The Zeno's paradox in quantum theory. J. Math. Phys. 18 756.CrossRefGoogle Scholar
Montanaro, A. (2007) Quantum walks on directed graphs. Quantum Information and Computation 7 (1–2)93–102.CrossRefGoogle Scholar
Moore, C. and Russell, A. (2002) Quantum walks on the hypercube. In: Rolim, J. D. P. and Vadhan, S. (eds.) Proc. 6th Intl. Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM '02), Springer 164–178.CrossRefGoogle Scholar
Motwani, R. and Raghavan, P. (1995) Randomized Algorithms, Cambridge University Press.CrossRefGoogle Scholar
Nayak, A. and Vishwanath, A. (2000) Quantum walk on the line. quant-ph/0010117.Google Scholar
Pakoński, P., Tanner, G. and Życzkowski, K. (2003) Families of line-graphs and their quantization. J. Stat. Phys 111 (5/6)1331–1352.CrossRefGoogle Scholar
Renner, R., Gisin, N. and Kraus, B. (2005) An information-theoretic security proof for QKD protocols. Phys. Rev. A 72 012332.CrossRefGoogle Scholar
Ribeiro, P., Milman, P. and Mosseri, R. (2004) Aperiodic quantum random walks. Phys. Rev. Lett. 93 (19)190503.CrossRefGoogle ScholarPubMed
Richter, P. (2007a) Almost uniform sampling in quantum walks. New J. Phys. 9 72. See also ArXiv: quant-ph/0606202.CrossRefGoogle Scholar
Richter, P. (2007b) Quantum speedup of classical mixing processes. Phys. Rev. A 76 042306. See also ArXiv: quant-ph/0609204.CrossRefGoogle Scholar
Romanelli, A., Sicardi-Schifino, A. C., Siri, R., Abal, G., Auyuanet, A. and Donangelo, R. (2004) Quantum random walk on the line as a Markovian process. Physica A 338 395–405.CrossRefGoogle Scholar
Romanelli, A., Siri, R., Abal, G., Auyuanet, A. and Donangelo, R. (2003) Decoherence in the quantum walk on the line. Physica A 347 137–152.CrossRefGoogle Scholar
Ryan, C. A., Laforest, M., Boileau, J. C. and Laflamme, R. (2005) Experimental implementation of discrete time quantum random walk on an NMR quantum information processor. Phys. Rev. A 72 062317.CrossRefGoogle Scholar
Sachdev, S. (1999) Quantum Phase Transitions, Cambridge University Press.Google Scholar
Sanders, B. C., Bartlett, S. D., Tregenna, B. and Knight, P. L. (2003) Quantum quincunx in cavity QED. Phys. Rev. A 67 042305.CrossRefGoogle Scholar
Schöning, U. (1999) A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: 40th Annual Symposium on FOCS, IEEE Computer Society Press 17–19.Google Scholar
Severini, S. (2003) On the digraph of a unitary matrix. SIAM J. Matrix Anal. Appl. 25 (1)295–300.CrossRefGoogle Scholar
Severini, S. (2006) Graphs of a unitary matrix. math.CO/0303084.Google Scholar
Shapira, D., Biham, O., Bracken, A. J. and Hackett, M. (2003) One dimensional quantum walk with unitary noise. Phys. Rev. A 68 (6)062315.CrossRefGoogle Scholar
Shenvi, N., Kempe, J. and Birgitta Whaley, K. (2003) A quantum random walk search algorithm. Phys. Rev. A 67 052307.CrossRefGoogle Scholar
Shor, P. W. (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Sci Statist. Comput. 26 1484.Google Scholar
Solenov, D. and Fedichkin, L. (2006a) Continuous-time quantum walks on a cycle graph. Phys. Rev. A 73 012313.CrossRefGoogle Scholar
Solenov, D. and Fedichkin, L. (2006b) Non-unitary quantum walks on hyper-cycles. Phys. Rev. A 73 012308.CrossRefGoogle Scholar
Strauch, F. W. (2006a) Connecting the discrete and continuous-time quantum walks. Phys. Rev. A 74 (3)030301.CrossRefGoogle Scholar
Strauch, F. W. (2006b) Relativistic quantum walks. Phys. Rev. A 73 (6)054302.CrossRefGoogle Scholar
Szegedy, M. (2004a) Quantum speed-up of Markov chain based algorithms. In: 45th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press 32–41.CrossRefGoogle Scholar
Szegedy, M. (2004b) Spectra of quantized walks and a $\sqrt{\delta\epsilon}$ rule. ArXiv: quant-ph/0401053.Google Scholar
Tadej, W. and Życzkowski, K. (2006) A concise guide to complex Hadamard matrices. Open Syst. Inf. Dyn. 13 133–177.CrossRefGoogle Scholar
Travaglione, B. C. and Milburn, G. J. (2002) Implementing the quantum random walk. Phys. Rev. A 65 032310.CrossRefGoogle Scholar
Tregenna, B., Flanagan, W., Maile, R. and Kendon, V. (2003) Controlling discrete quantum walks: coins and initial states. New J. Phys. 5 83.CrossRefGoogle Scholar
Watrous, J. (2001) Quantum simulations of classical random walks and undirected graph connectivity. J. Comp. System Sciences 62 (2)376–391.CrossRefGoogle Scholar
Watrous, J. (2002) Private communication.Google Scholar
Weiss, G. H. (1994) Aspects and Applications of the Random Walk, North-Holland.Google Scholar
Yamasaki, T., Kobayashi, H. and Imai, H. (2002) An analysis of absorbing times of quantum walks. In: Calude, C., Dinneen, M. J. and Peper, F. (eds.) Proceedings: Unconventional Models of Computation, Third Intl. Conf., UMC 2002. Springer-Verlag Lecture Notes in Computer Science 2509 315–330.CrossRefGoogle Scholar