Quantum walk

In quantum computing, quantum walks are the quantum analogue of classical random walks. Analogous to 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

Probability distribution resulting from one-dimensional discrete time random walks. The quantum walk created using the Hadamard coin is plotted (blue) vs a classical walk (red) after 50 time steps.

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. 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 Richard Feynman's model of an electron in 1 (one) spatial and 1 (one) 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.

The transition probability for a 1-dimensional quantum walk behaves like the Hermite functions which (1) asymptotically oscillate in the classically allowed region, (2) is approximated by the Airy function around the wall of the potential, and (3) exponentially decay in the classically hidden region.[7]

See also

References

  1. ↑ 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.
  2. ↑ 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.
  3. ↑ 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.
  4. ↑ 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.
  5. ↑ 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
  6. ↑ Andrew M. Childs, "Universal Computation by Quantum Walk".
  7. ↑ T. Sunada and T. Tate, Asymptotic behavior of quantum walks on the line, Journal of Functional Analysis 262 (2012) 2608-2645

Further reading

External links

This article is issued from Wikipedia - version of the 3/25/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.