Quantum walks are quantum analogs of classical random walks. In contrast to the classical random walk, where the walker occupies definite states and the randomness arises due to stochastic transitions between states, in quantum walks randomness arises through (1) quantum superposition of states, (2) non-random, reversible unitary evolution and (3) collapse of the wave function due to state measurements. Quantum walks are a technique for building quantum algorithms.
As with classical random walks, quantum walks admit formulations in both discrete time and continuous time.
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.
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.[6]
See main article: 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
G=(V,E)
Consider the dynamics of a non-relativistic, spin-less free quantum particle with mass
m
\psi:R x R\geq\toC
|
=-
| \hbar2 | |
| 2m |
| \partial2\psi | |
| \partialx2 |
bf{i}=\sqrt{-1}
\hbar
R
Z\Delta\equiv\{\ldots,-2\Deltax,-\Deltax,0,\Deltax,2\Deltax,\ldots\}
\Deltax
\psi:Z\Delta x R\geq\toC
| \partial2\psi | |
| \partialx2 |
\to
| LZ\psi(j\Deltax,t) | |
| \Deltax2 |
\equiv
| \psi\left((j+1)\Deltax,t\right)-2\psi\left(j\Deltax,t\right)+\psi\left((j-1)\Deltax,t\right) | |
| \Deltax2 |
The evolution equation for a continuous time quantum walk on
Z\Delta
|
=-\omega\DeltaLZ\psi
where
\omega\Delta\equiv\hbar/2m\Deltax2
G=(V,E)
LZ
LG\equivDG-AG
DG
AG
Zd
Z/NZ
(Z/NZ)d
Qd
Z
Z
|\Psi\rangle=|s\rangle ⊗ |\psi\rangle
|s\rangle\inl{H}C=\left\{a\uparrow|{\uparrow}\rangle+a\downarrow|{\downarrow}\rangle:a\uparrow/\downarrow\inC\right\}
|\psi\rangle\inl{H}P=\left\{\sumx\inZ\alphax|x\rangle:\sumx\inZ
| 2 | |
| |\alpha | |
| x| |
<infty\right\}
l{H}C=C2
l{H}P=\ell2(Z)
⊗
S=|{\uparrow}\rangle\langle{\uparrow}| ⊗ \sum\limitsi|i+1\rangle\langlei|+|{\downarrow}\rangle\langle{\downarrow}| ⊗ \sum\limitsi|i-1\rangle\langlei|,
S(|{\uparrow}\rangle ⊗ |i\rangle)=|{\uparrow}\rangle ⊗ |i+1\rangle
S(|{\downarrow}\rangle ⊗ |i\rangle)=|{\downarrow}\rangle ⊗ |i-1\rangle
If we first rotate the spin with some unitary transformation
C:l{H}C\tol{H}C
S
Z
C=H
H=
| 1 | |
| \sqrt{2 |
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
Z
|{\uparrow}\rangle ⊗ |0\rangle \overset{H}{\longrightarrow}
| 1 | |
| \sqrt{2 |
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
Z
S
|{\uparrow}\rangle
|{\uparrow}\rangle
|{\downarrow}\rangle
| symm | |
| |\Psi | |
| 0\rangle |
=
| 1 | |
| \sqrt{2 |
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.[9]
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.[10] 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.[11]
Quantum walks on infinite graphs represent a distinctive area of study, characterized by the walk's unbounded spread over time.[12] 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.[13] 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.