quantum walk

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.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, {{arxiv|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}}. Quantum walks also give polynomial speedups over classical algorithms for many practical problems, such as the element distinctness problem,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. the triangle finding problem,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. and evaluating NAND trees.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 The well-known Grover search algorithm can also be viewed as a quantum walk algorithm.

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. There is also no randomness in quantum walks. Due to the laws of quantum mechanics, the evolution of an isolated quantum system is deterministic. This means that by using current conditions, you can exactly predict the future behaviors of the system. Randomness only occurs in quantum walks when the system is measured and classical information is gathered. Also, instead of the "coin flip" used in classical systems, quantum walks enlarge the space of the physical system to create more data.{{Cite journal |last=Kemp |first=J. |date=February 1, 2008 |title=Quantum random walks - an introductory overview |journal=Contemporary Physics|volume=44 |issue=4 |pages=307–327 |doi=10.1080/00107151031000110776 |arxiv=quant-ph/0303081 |bibcode=2003ConPh..44..307K }}

{{Main|Continuous-time quantum walk}}

Continuous-time quantum walks arise when one replaces the continuum spatial domain in the Schrödinger equation with a discrete set. That is, instead of having a quantum particle propagate in a continuum, one restricts the set of possible position states to the vertex set $V$ of some graph $G\; =\; (V,E)$ which can be either finite or countably infinite. Under particular conditions, continuous-time quantum walks can provide a model for universal quantum computation.Andrew M. Childs, [https://arxiv.org/abs/0806.1972 "Universal Computation by Quantum Walk"].

Consider the dynamics of a non-relativistic, spin-less free quantum particle with mass $m$ propagating on an infinite one-dimensional spatial domain. The particle's motion is completely described by its wave function $\backslash psi\; :\; \backslash mathbb\{R\}\backslash times\; \backslash mathbb\{R\}\_\{\backslash geq\; 0\}\backslash to\backslash mathbb\{C\}$ which satisfies the one-dimensional, free particle Schrödinger equation

: $\backslash textbf\{i\}\backslash hbar\backslash frac\{\backslash partial\backslash psi\}\{\backslash partial\; t\}\; =\; -\backslash frac\{\backslash hbar^2\}\{2m\}\backslash frac\{\backslash partial^2\backslash psi\}\{\backslash partial\; x^2\}$

where $\backslash textbf\{i\}\; =\; \backslash sqrt\{-1\}$ and $\backslash hbar$ is the reduced Planck constant. Now suppose that only the spatial part of the domain is discretized, $\backslash mathbb\{R\}$ being replaced with $\backslash mathbb\{Z\}\_\{\backslash Delta\; x\}\; \backslash equiv\; \backslash \{\backslash ldots,-2\backslash ,\backslash Delta\; x,-\backslash Delta\; x,0,\backslash Delta\; x,\; 2\backslash ,\backslash Delta\; x,\backslash ldots\backslash \}$ where $\backslash Delta\; x$ is the separation between the spatial sites the particle can occupy. The wave function becomes the map $\backslash psi\; :\; \backslash mathbb\{Z\}\_\{\backslash Delta\; x\}\backslash times\backslash mathbb\{R\}\_\{\backslash geq\; 0\}\backslash to\backslash mathbb\{C\}$ and the second spatial partial derivative becomes the discrete laplacian

: $\backslash frac\{\backslash partial^2\backslash psi\}\{\backslash partial\; x^2\}\; \backslash to\; \backslash frac\{L\_\{\backslash mathbb\{Z\}\}\backslash psi(j\backslash ,\backslash Delta\; x,t)\}\{\backslash Delta\; x^2\}\; \backslash equiv\; \backslash frac\{\backslash psi\backslash left((j+1)\backslash ,\backslash Delta\; x,t\backslash right)-2\backslash psi\backslash left(j\backslash ,\backslash Delta\; x,t\backslash right)+\backslash psi\backslash left((j-1)\backslash ,\backslash Delta\; x,t\backslash right)\}\{\backslash Delta\; x^2\}$

The evolution equation for a continuous time quantum walk on $\backslash mathbb\{Z\}\_\{\backslash Delta\; x\}$ is thus

: $\backslash textbf\{i\}\backslash frac\{\backslash partial\backslash psi\}\{\backslash partial\; t\}\; =\; -\backslash omega\_\{\backslash Delta\; x\}\; L\_\{\backslash mathbb\{Z\}\}\backslash psi$

where $\backslash omega\_\{\backslash Delta\; x\}\; \backslash equiv\; \backslash hbar/2m\backslash ,\backslash Delta\; x^2$ is a characteristic frequency. This construction naturally generalizes to the case that the discretized spatial domain is an arbitrary graph $G\; =\; (V,E)$ and the discrete laplacian $L\_\backslash mathbb\{Z\}$ is replaced by the graph Laplacian $L\_G\; \backslash equiv\; D\_G\; -\; A\_G$ where $D\_G$ and $A\_G$ are the degree matrix and the adjacency matrix, respectively. Common choices of graphs that show up in the study of continuous time quantum walks are the d-dimensional lattices $\backslash mathbb\{Z\}^d$, cycle graphs $\backslash mathbb\{Z\}/N\backslash mathbb\{Z\}$, d-dimensional discrete tori $(\backslash mathbb\{Z\}/N\backslash mathbb\{Z\})^d$, the d-dimensional hypercube $\backslash mathbb\{Q\}^d$ and random graphs.

{{Expand section|date=December 2009}}

File:One dimensional quantum random walk.svg is plotted ({{color|orange|orange}}) vs a classical walk ({{color|blue|blue}}) after 50 time steps.]]

The evolution of a quantum walk in discrete time is specified by the product of two unitary operators: (1) a "coin flip" operator and (2) a conditional shift operator, which are applied repeatedly. The following example is instructive here.{{Cite journal|last=Kempe|first=Julia|author-link=Julia Kempe|date=2003-07-01|title=Quantum random walks – an introductory overview|journal=Contemporary Physics|volume=44|issue=4|pages=307–327|doi=10.1080/00107151031000110776|issn=0010-7514|arxiv=quant-ph/0303081|bibcode=2003ConPh..44..307K|s2cid=17300331}} Imagine a particle with a spin-1/2-degree of freedom propagating on a linear array of discrete sites. If the number of such sites is countably infinite, we identify the state space with $\backslash mathbb\{Z\}$. The particle's state can then be described by a product state

: $|\backslash Psi\backslash rangle\; =\; |s\backslash rangle\; \backslash otimes\; |\backslash psi\; \backslash rangle$

consisting of an internal spin state

: $|s\backslash rangle\; \backslash in\; \backslash mathcal\{H\}\_C=\backslash left\backslash \{a\_\{\backslash uparrow\}|\{\backslash uparrow\}\backslash rangle\; +\; a\_\{\backslash downarrow\}|\{\backslash downarrow\}\backslash rangle:\; a\_\{\backslash uparrow/\backslash downarrow\}\; \backslash in\; \backslash mathbb\{C\}\; \backslash right\backslash \}$

and a position state

:

where $\backslash mathcal\{H\}\_C\; =\; \backslash mathbb\{C\}^2$ is the "coin space" and $\backslash mathcal\{H\}\_P\; =\; \backslash ell^2(\backslash mathbb\{Z\})$ is the space of physical quantum position states. The product $\backslash otimes$ in this setting is the Kronecker (tensor) product. The conditional shift operator for the quantum walk on the line is given by

: $S\; =\; |\{\backslash uparrow\}\backslash rangle\; \backslash langle\{\backslash uparrow\}|\; \backslash otimes\; \backslash sum\backslash limits\_i\; |i+1\backslash rangle\backslash langle\; i|\; +\; |\{\backslash downarrow\}\backslash rangle\; \backslash langle\{\backslash downarrow\}|\; \backslash otimes\; \backslash sum\backslash limits\_i\; |i-1\backslash rangle\; \backslash langle\; i|,$

i.e. the particle jumps right if it has spin up and left if it has spin down. Explicitly, the conditional shift operator acts on product states according to

: $S(|\{\backslash uparrow\}\backslash rangle\; \backslash otimes\; |i\backslash rangle)\; =\; |\{\backslash uparrow\}\backslash rangle\; \backslash otimes\; |i+1\backslash rangle$

: $S(|\{\backslash downarrow\}\backslash rangle\; \backslash otimes\; |i\backslash rangle)\; =\; |\{\backslash downarrow\}\backslash rangle\; \backslash otimes\; |i-1\backslash rangle$

If we first rotate the spin with some unitary transformation $C:\; \backslash mathcal\{H\}\_C\; \backslash to\; \backslash mathcal\{H\}\_C$ and then apply $S$, we get a non-trivial quantum motion on $\backslash mathbb\{Z\}$. A popular choice for such a transformation is the Hadamard gate $C\; =\; H$, which, with respect to the standard z-component spin basis, has matrix representation

:

When this choice is made for the coin flip operator, the operator itself is called the "Hadamard coin" and the resulting quantum walk is called the "Hadamard walk". If the walker is initialized at the origin and in the spin-up state, a single time step of the Hadamard walk on $\backslash mathbb\{Z\}$ is

: $|\{\backslash uparrow\}\backslash rangle\; \backslash otimes\; |0\backslash rangle\; \backslash ;\backslash ,\backslash overset\{H\}\{\backslash longrightarrow\}\backslash ;\backslash ,\; \backslash frac\{1\}\{\backslash sqrt\{2\}\}\; (|\{\backslash uparrow\}\backslash rangle\; +\; |\{\backslash downarrow\}\backslash rangle)\; \backslash otimes\; |0\backslash rangle\; \backslash ;\backslash ,\backslash overset\{S\}\{\backslash longrightarrow\}\backslash ;\backslash ,\; \backslash frac\{1\}\{\backslash sqrt\{2\}\}\; (|\{\backslash uparrow\}\backslash rangle\; \backslash otimes\; |1\backslash rangle\; +\; |\{\backslash downarrow\}\backslash rangle\; \backslash otimes\; |\{-1\}\backslash rangle).$

Measurement of the system's state at this point would reveal an up spin at position 1 or a down spin at position −1, both with probability 1/2. Repeating the procedure would correspond to a classical simple random walk on $\backslash mathbb\{Z\}$. In order to observe non-classical motion, no measurement is performed on the state at this point (and therefore do not force a collapse of the wave function). Instead, repeat the procedure of rotating the spin with the coin flip operator and conditionally jumping with $S$. This way, quantum correlations are preserved and different position states can interfere with one another. This gives a drastically different probability distribution than the classical random walk (Gaussian distribution) as seen in the figure to the right. Spatially one sees that the distribution is not symmetric: even though the Hadamard coin gives both up and down spin with equal probability, the distribution tends to drift to the right when the initial spin is $|\{\backslash uparrow\}\backslash rangle$. This asymmetry is entirely due to the fact that the Hadamard coin treats the $|\{\backslash uparrow\}\backslash rangle$ and $|\{\backslash downarrow\}\backslash rangle$ state asymmetrically. A symmetric probability distribution arises if the initial state is chosen to be

: $|\backslash Psi^\{\backslash text\{symm\}\}\_0\backslash rangle\; =\; \backslash frac\{1\}\{\backslash sqrt\{2\}\}\; (|\{\backslash uparrow\}\backslash rangle\; -\; \backslash textbf\{i\}\; |\{\backslash downarrow\}\backslash rangle)\; \backslash otimes\; |0\backslash rangle$

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.{{Clarify|What are the movers, & where do they come from?|date=September 2011}} 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,{{clarify|date=December 2014}} and

(3) exponentially decay in the classically hidden region.T. Sunada and T. Tate, Asymptotic behavior of quantum walks on the line, Journal of Functional Analysis 262 (2012) 2608–2645

Another approach to quantizing classical random walks is through continuous-time Markov chains. Unlike the coin-based mechanism used in discrete-time random walks, Markov chains do not rely on a coin flip to determine the direction of movement.{{Cite web |title=Markov Chains explained visually |url=https://setosa.io/ev/markov-chains/ |access-date=2024-11-20 |website=Explained Visually}} In this framework, time is treated as a continuous variable, allowing the walker to transition between adjacent vertices at any point in time. As time progresses, the probability of finding the walker at a neighboring vertex increases, while the likelihood of remaining at the current vertex decreases. The transition rate between neighboring vertices serves as the probability factor, replacing the need for a coin flip.{{Cite book |last=Portugal |first=R. |title=Quantum Walks and Search Algorithms |date=2018 |publisher=Springer Cham |isbn=978-3-319-97812-3 |edition=2nd |location=Switzerland |publication-date=2018}}

Quantum walks on infinite graphs represent a distinctive area of study, characterized by the walk's unbounded spread over time.{{Cite journal |last1=Krovi |first1=Hari |last2=Brun |first2=Todd A. |date=2006-10-27 |title=Quantum walks with infinite hitting times |journal=Physical Review A |volume=74 |issue=4 |pages=042334 |doi=10.1103/PhysRevA.74.042334 |arxiv=quant-ph/0606094 |issn=1050-2947}} In this context, the expected distance from the origin can be quantified by the standard deviation of the probability distribution. This measurement has been explored on both one-dimensional and two-dimensional lattices, where the standard deviation grows in direct proportion to the evolution time. Classically, the standard deviation of the random walk would be proportional to the square root of the evolution time.

Atomic lattice is the leading quantum platform in terms of scalability. Coined and coinless discrete-time quantum-walk could be realized in the atomic lattice via a distance-selective spin-exchange interaction.{{Cite journal |last=Khazali |first=Mohammadsadegh |date=2022-03-03 |title=Discrete-Time Quantum-Walk & Floquet Topological Insulators via Distance-Selective Rydberg-Interaction |url=https://quantum-journal.org/papers/q-2022-03-03-664/ |journal=Quantum |language=en |volume=6 |pages=664 |doi=10.22331/q-2022-03-03-664 |arxiv=2101.11412 |bibcode=2022Quant...6..664K |s2cid=246635019 |issn=2521-327X|doi-access=free }} Remarkably the platform preserves the coherence over couple of hundred sites and steps in 1, 2 or 3 dimensions in the spatial space. The long-range dipolar interaction allows designing periodic boundary conditions, facilitating the QW over topological surfaces.

• Path integral formulation
• Quantum walk search

{{reflist}}

{{refbegin}}

• {{cite journal | author=Julia Kempe | title=Quantum random walks – an introductory overview | journal=Contemporary Physics | year=2003 | volume=44 | pages=307–327 | arxiv=quant-ph/0303081 | doi=10.1080/00107151031000110776|bibcode = 2003ConPh..44..307K | issue=4 | s2cid=17300331 }}
• {{cite journal | author=Andris Ambainis | author-link=Andris Ambainis | title=Quantum walks and their algorithmic applications | journal=International Journal of Quantum Information | year=2003 | volume=1 | pages=507–518 | arxiv=quant-ph/0403120 | doi=10.1142/S0219749903000383 | issue=4| s2cid=10324299 }}
• {{cite book |arxiv=0808.0059|doi=10.1007/978-3-540-79228-4_3 |chapter=Quantum Walk Based Search Algorithms |title=Theory and Applications of Models of Computation |series=Lecture Notes in Computer Science |date=2008 |last1=Santha |first1=Miklos |volume=4978 |pages=31–46 |isbn=978-3-540-79227-7 }}
• {{cite journal | author=Salvador E. Venegas-Andraca | title=Quantum walks: a comprehensive review | journal=Quantum Information Processing | year=2012 | volume = 11 | issue = 5 | pages=1015–1106 | arxiv=1201.4780 | doi=10.1007/s11128-012-0432-5| s2cid=27676690 }}
• {{cite book | author=Salvador E. Venegas-Andraca |title= Quantum Walks for Computer Scientists |year = 2008|publisher= Morgan & Claypool Publishers |isbn = 978-1598296563}}
• {{cite book | author=Kia Manouchehri, Jingbo Wang |title= Physical Implementation of Quantum Walks |year = 2014|publisher= Springer |isbn = 978-3-642-36014-5}}

{{refend}}

• [http://www.th.phys.titech.ac.jp/~shikano/dtqw/ International Workshop on Mathematical and Physical Foundations of Discrete Time Quantum Walk]
• [https://soulstreet.web.fc2.com/quantumwalk/english Quantum walk]
• [https://short.classiq.io/discrete_quantum_walk Implementations of Discrete Quantum Walks with Classiq]

Category:Quantum algorithms