Quantum Walk

In the field of quantum information technology , the quantum walk is the analogue of the classic random walk . While in the classic random walk a state is described by a probability distribution of the possible positions, in the quantum walk it is described as a superposition of positions.

Similar to the classic random walk, there are two types of quantum walks: the discrete and the continuous.

motivation

Quantum Walks are motivated by the widespread use of classic random walks in the design of randomized algorithms. They are part of several quantum algorithms . For some oracle problems, quantum walks are exponentially faster than any classic algorithm. For many practical problems, Quantum Walks also provide polynomial accelerations compared to classical algorithms, for example for the element distinction problem (the problem of determining whether a list contains duplicates), the problem of determining whether a graph is triangle-free and during evaluation of NAND trees. The well-known Grover algorithm can also be viewed as a quantum walk.

Relationship to the classic random walk

Quantum walks differ significantly in their behavior from classic random walks. In particular, they do not converge to a probability distribution . Due to the influence of quantum interference , they can spread out significantly faster or slower.

Continuous walk

In certain circumstances, continuous quantum walks can provide a model for universal quantum computations. This does not necessarily imply uniformity.

Discreet walk

Probability distributions of one-dimensional discrete random walks after 50 time steps. The Quantum Walk, created with the Hadamard coin , is shown in blue, the classic Walk in red.

A discrete quantum walk is specified by a coin and a shift operator that are repeatedly applied. The following example is intended to illustrate this. Imagine a particle with a spin degree of freedom of a spin particle on a line (a one-dimensional model). Its state can be described as the product of a spin state (eigenstates of the z component of the spin operator with eigenvalue (“spin up”) and (“spin down”)) and a spin position. The product of these states is the Kronecker product , which separates the two degrees of freedom. The space of the spin states is called the coin space. A conditional jump of the particle on the line is described by the following: operator . The particle jumps to the right on spin up and to the left on spin down. For example, if you apply the conditional jump operation to an initial state, this leads to the state . If you first rotate the spin using a unitary transformation in , and then apply , you get a random movement on the line. As a transformation as the Hadamard coin can be selected: . If the spin is measured at this point in time, you get either a spin up at position 1 or a spin down at position -1. Repeated use of the procedure would correspond to a classic walk, for example a Galton board . The idea of the Quantum Walk, however, is not to measure between the repetitions of the spin rotation and the conditional jump (so that there is no collapse of the wave function ). In this way, the quantum entanglement (i.e. the uncollapsed wave functions) is preserved and different positions can interfere with each other. This leads to a drastically different probability distribution compared to the classic walk ( Gaussian distribution ), as can be seen in the figure on the right. In particular, it can be seen that the distribution is not symmetrical: although the Hadamard coin delivers spin up and spin down with the same probability, the distribution tends to the right when there is initially a spin high. Roughly speaking, this effect can be explained by the fact that the Hadamard coin provides more destructive interference for positions on paths to the left than to the right. A symmetrical distribution is possible with the help of a suitable coin or an initial state such as , since the Hadamard coin does not introduce complex numbers, so that spin up and spin down do not entangle here. ${\ displaystyle {\ frac {1} {2}}}$ ${\ displaystyle | s \ rangle \ in {\ mathcal {H}} _ {C} = \ {\ left | {\ mathord {\ uparrow}} \ right \ rangle, \ left | {\ mathord {\ downarrow}} \ right \ rangle \}}$ ${\ displaystyle {\ frac {1} {2}}}$ ${\ displaystyle - {\ frac {1} {2}}}$ ${\ displaystyle | i \ rangle \ in {\ mathcal {H}} _ {P} = \ {| n \ rangle: n \ in \ mathbb {Z} \}}$ ${\ displaystyle S = \ left | {\ mathord {\ uparrow}} \ right \ rangle \ left \ langle {\ mathord {\ uparrow}} \ right | \ otimes \ sum \ limits _ {i} | i + 1 \ rangle \ langle i | + \ left | {\ mathord {\ downarrow}} \ right \ rangle \ left \ langle {\ mathord {\ downarrow}} \ right | \ otimes \ sum \ limits _ {i} | i-1 \ rangle \ langle i |}$ ${\ displaystyle \ left | {\ mathord {\ uparrow}} \ right \ rangle \ otimes | 0 \ rangle}$ ${\ displaystyle \ left | {\ mathord {\ uparrow}} \ right \ rangle \ otimes | 1 \ rangle}$ ${\ displaystyle C}$ ${\ displaystyle {\ mathcal {H}} _ {C}}$ ${\ displaystyle S}$ ${\ displaystyle \ left | {\ mathord {\ uparrow}} \ right \ rangle \ otimes | 0 \ rangle \; \, {\ overset {H} {\ longrightarrow}} \; \, {\ frac {1} { \ sqrt {2}}} (\ left | {\ mathord {\ uparrow}} \ right \ rangle + \ left | {\ mathord {\ downarrow}} \ right \ rangle) \ otimes | 0 \ rangle \; \, {\ overset {S} {\ longrightarrow}} \; \, {\ frac {1} {\ sqrt {2}}} (\ left | {\ mathord {\ uparrow}} \ right \ rangle \ otimes | 1 \ rangle + \ left | {\ mathord {\ downarrow}} \ right \ rangle \ otimes | -1 \ rangle)}$ ${\ displaystyle {\ frac {1} {\ sqrt {2}}} (\ left | {\ mathord {\ uparrow}} \ right \ rangle + \ mathrm {i} \ left | {\ mathord {\ downarrow}} \ right \ rangle) \ otimes | 0 \ rangle}$

Individual evidence

↑ AM Childs, R. Cleve , E. Deotto, E. Farhi , S. Gutmann, and DA Spielman , Exponential algorithmic speedup by quantum walk, Proc. 35th ACM Symposium on Theory of Computing, pp. 59-68, 2003, quant-ph / 0209131.
↑ AM Childs, LJ Schulman, and UV 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, arxiv : quant-ph / 0310134 .
↑ Andrew M. Childs: Universal Computation by Quantum Walk . arxiv : 0806.1972
↑ Julia Kempe: Quantum random walks - an introductory overview . In: Contemporary Physics . 44, No. 4, July 1, 2003, ISSN 0010-7514 , pp. 307-327. arxiv : quant-ph / 0303081 . doi : 10.1080 / 00107151031000110776 .

literature

Julia Kempe: Quantum random walks - an introductory overview . In: Contemporary Physics . 44, No. 4, 2003, pp. 307-327. arxiv : quant-ph / 0303081 . bibcode : 2003ConPh..44..307K . doi : 10.1080 / 00107151031000110776 .
Andris Ambainis : Quantum walks and their algorithmic applications . In: International Journal of Quantum Information . 1, No. 4, 2003, pp. 507-518. arxiv : quant-ph / 0403120 . doi : 10.1142 / S0219749903000383 .
Miklos Santha: Quantum walk based search algorithms . In: Theory and Applications of Models of Computation (TAMC), Xian, LNCS 4978 . 5, No. 8, April 2008, pp. 31-46. arxiv : 0808.0059 . bibcode : 2008arXiv0808.0059S .
Salvador E. Venegas-Andraca: Quantum walks: a comprehensive review . In: Quantum Information Processing . 11, No. 5, 2012, pp. 1015-1106. arxiv : 1201.4780v2 . doi : 10.1007 / s11128-012-0432-5 .
Salvador E. Venegas-Andraca: Quantum Walks for Computer Scientists . Retrieved October 16, 2008.

Web links

[1] AM Childs, R. Cleve , E. Deotto, E. Farhi , S. Gutmann, and DA Spielman , Exponential algorithmic speedup by quantum walk, Proc. 35th ACM Symposium on Theory of Computing, pp. 59-68, 2003, quant-ph / 0209131.

[2] AM Childs, LJ Schulman, and UV 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, arxiv : quant-ph / 0310134 .

[5] Andrew M. Childs: Universal Computation by Quantum Walk . arxiv : 0806.1972

[6] Julia Kempe: Quantum random walks - an introductory overview . In: Contemporary Physics . 44, No. 4, July 1, 2003, ISSN 0010-7514 , pp. 307-327. arxiv : quant-ph / 0303081 . doi : 10.1080 / 00107151031000110776 .