Quantum walk
For some oracular problems, quantum walks provide an exponential speedup over any classical algorithm.
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.
Randomness only occurs in quantum walks when the system is measured and classical information is gathered.
[6] Continuous-time quantum walks arise when one replaces the continuum spatial domain in the Schrödinger equation with a discrete set.
[7] Consider the dynamics of a non-relativistic, spin-less free quantum particle with mass
and the second spatial partial derivative becomes the discrete laplacian The evolution equation for a continuous time quantum walk on
This construction naturally generalizes to the case that the discretized spatial domain is an arbitrary graph
Common choices of graphs that show up in the study of continuous time quantum walks are the d-dimensional lattices
[8] Imagine a particle with a spin-1/2-degree of freedom propagating on a linear array of discrete sites.
Explicitly, the conditional shift operator acts on product states according to If we first rotate the spin with some unitary transformation
, 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
Repeating the procedure would correspond to a classical simple random walk on
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
A symmetric probability distribution arises if the initial state is chosen to be Consider what happens when we discretize a massive Dirac operator over one spatial dimension.
[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.
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,[clarification needed] 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.
The transition rate between neighboring vertices serves as the probability factor, replacing the need for a coin flip.
[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.
[11] 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.
