Quantum walk
In quantum computing, quantum walks are the quantum analogue of classical random walks. Like the classical random walk, where the walker's current state is described by a probability distribution over positions, the walker in a quantum walk is in a superposition of positions. Like classical random walks, there are two types of quantum walks, discrete-time quantum walks and continuous-time quantum walks.
Motivation
Quantum walks are motivated by the widespread use of classical random walks in the design of randomized algorithms, and are part of several quantum algorithms. For some oracular problems, quantum walks provide an exponential speedup over any classical algorithm.[1][2] Quantum walks also give polynomial speedups over classical algorithms for many practical problems, such as the element distinctness problem,[3] the triangle finding problem,[4] and evaluating NAND trees.[5] The well-known Grover search algorithm can also be viewed as a quantum walk algorithm.
Relation to classical random walks
Quantum walks exhibit very different features from classical random walks. In particular, they do not converge to limiting distributions and due to the power of quantum interference they may spread significantly faster or slower than their classical equivalents.
Continuous time
Under particular conditions, continuous-time quantum walks can provide a model for universal quantum computation. This does not necessarily imply uniformality. [6]
Discrete time
![[icon]](/wiki/File:Wiki_letter_w_cropped.svg){kind=small} | This section needs expansion. You can help by adding to it. (December 2009) |
A quantum walk in discrete time is specified by a coin and shift operator, which are applied repeatedly.
Consider what happens when we discretize a massive Dirac operator over one spatial dimension. In the absence of a mass term, we have left-movers and right-movers.[clarification needed] They can be characterized by an internal degree of freedom, "spin" or a "coin". When we turn on a mass term, this corresponds to a rotation in this internal "coin" space. A quantum walk corresponds to iterating the shift and coin operators repeatedly.
This is very much like Feynman's model of an electron in 1 spatial and 1 time dimension. He summed up the zigzagging paths, with left-moving segments corresponding to one spin (or coin), and right-moving segments to the other. See Feynman checkerboard for more details.
See also
References
- ^ A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Exponential algorithmic speedup by quantum walk, Proc. 35th ACM Symposium on Theory of Computing, pp. 59–68, 2003, quant-ph/0209131.
- ^ A. M. Childs, L. J. Schulman, and U. V. Vazirani, Quantum algorithms for hidden nonlinear structures, Proc. 48th IEEE Symposium on Foundations of Computer Science, pp. 395–404, 2007, arXiv:0705.2784.
- ^ Andris Ambainis, Quantum walk algorithm for element distinctness, SIAM J. Comput. 37 (2007), no. 1, 210–239, arXiv:quant-ph/0311001, preliminary version in FOCS 2004.
- ^ F. Magniez, M. Santha, and M. Szegedy, Quantum algorithms for the triangle problem, Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 1109–1117, 2005, quant-ph/0310134.
- ^ E. Farhi, J. Goldstone, and S. Gutmann, A quantum algorithm for the Hamiltonian NAND tree, Theory of Computing 4 (2008), no. 1, 169–190, quant-ph/0702144
- ^ Andrew M. Childs, "Universal Computation by Quantum Walk".
Further reading
- Julia Kempe (2003). "Quantum random walks - an introductory overview". Contemporary Physics. 44 (4): 307–327. arXiv:quant-ph/0303081. Bibcode:2003ConPh..44..307K. doi:10.1080/00107151031000110776.
- Andris Ambainis (2003). "Quantum walks and their algorithmic applications". International Journal of Quantum Information. 1 (4): 507–518. arXiv:quant-ph/0403120. doi:10.1142/S0219749903000383.
- Miklos Santha (2008). "Quantum walk based search algorithms". Th Theory and Applications of Models of Computation (TAMC), Xian, April , LNCS 4978. 5 (8): 31–46. arXiv:0808.0059. Bibcode:2008arXiv0808.0059S.
External links