Quantum walk
   HOME

TheInfoList



OR:

Quantum walks are
quantum In physics, a quantum (plural quanta) is the minimum amount of any physical entity (physical property) involved in an interaction. The fundamental notion that a physical property can be "quantized" is referred to as "the hypothesis of quantizati ...
analogues of classical
random walk In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space. An elementary example of a random walk is the random walk on the integer number line \mathbb Z ...
s. In contrast to the classical random walk, where the walker occupies definite states and the randomness arises due to
stochastic Stochastic (, ) refers to the property of being well described by a random probability distribution. Although stochasticity and randomness are distinct in that the former refers to a modeling approach and the latter refers to phenomena themselv ...
transitions between states, in quantum walks randomness arises through: (1)
quantum superposition Quantum superposition is a fundamental principle of quantum mechanics. It states that, much like waves in classical physics, any two (or more) quantum states can be added together ("superposed") and the result will be another valid quantum ...
of states, (2) non-random, reversible unitary evolution and (3) collapse of the
wave function A wave function in quantum physics is a mathematical description of the quantum state of an isolated quantum system. The wave function is a complex-valued probability amplitude, and the probabilities for the possible results of measurements mad ...
due to state measurements. As with classical random walks, quantum walks admit formulations in both
discrete time and continuous time In mathematical dynamics, discrete time and continuous time are two alternative frameworks within which variables that evolve over time are modeled. Discrete time Discrete time views values of variables as occurring at distinct, separate "po ...
.


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 algorithm In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite sequ ...
s. For some oracular problems, quantum walks provide an exponential speedup over any classical algorithm. Quantum walks also give
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
speedups over classical algorithms for many practical problems, such as the
element distinctness problem In computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct. It is a well studied problem in many different models of computation. ...
, the
triangle finding problem In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with g ...
, and evaluating NAND trees. 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 In physics, interference is a phenomenon in which two waves combine by adding their displacement together at every single point in space and time, to form a resultant wave of greater, lower, or the same amplitude. Constructive and destructive ...
they may spread significantly faster or slower than their classical equivalents.


Continuous time

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 Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
.


Relation to non-relativistic Schrödinger dynamics

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 \psi : \mathbb\times \mathbb_\to\mathbb which satisfies the one-dimensional, free particle Schrödinger equation : \textbf\hbar\frac = -\frac\frac where \textbf = \sqrt and \hbar is the reduced Planck's constant. Now suppose that only the spatial part of the domain is discretized, \mathbb being replaced with \mathbb_ \equiv \ where \Delta x is the separation between the spatial sites the particle can occupy. The wave function becomes the map \psi : \mathbb_\times\mathbb_\to\mathbb and the second spatial partial derivative becomes the discrete laplacian : \frac \to \frac \equiv \frac The evolution equation for a continuous time quantum walk on \mathbb_ is thus : \textbf\frac = -\omega_ L_\psi where \omega_ \equiv \hbar/2m\,\Delta x^2is 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_\mathbbis replaced by the graph Laplacian L_G \equiv D_G - A_Gwhere D_G and A_G are the
degree matrix In the mathematical field of algebraic graph theory, the degree matrix of an undirected graph is a diagonal matrix which contains information about the degree of each vertex—that is, the number of edges attached to each vertex.. It is used togeth ...
and the
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...
, respectively. Common choices of graphs that show up in the study of continuous time quantum walks are the ''d''-dimensional lattices \mathbb^d, cycle graphs \mathbb/N\mathbb, ''d''-dimensional discrete tori (\mathbb/N\mathbb)^d, the ''d''-dimensional hypercube \mathbb^dand random graphs.


Discrete time


Discrete-time quantum walks on \mathbb

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. 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 \mathbb. The particle's state can then be described by a product state : , \Psi\rangle = , s\rangle \otimes , \psi \rangle consisting of an internal spin state : , s\rangle \in \mathcal_C=\left\ and a position state : , \psi\rangle \in \mathcal_P=\left\ where \mathcal_C = \mathbb^2 is the "coin space" and \mathcal_P = \ell^2(\mathbb) is the space of physical quantum position states. The product \otimes in this setting is the Kronecker (tensor) product. The conditional shift operator for the quantum walk on the line is given by : S= , \rangle \langle, \otimes \sum\limits_i , i+1\rangle\langle i, + , \rangle \langle, \otimes \sum\limits_i , i-1\rangle \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(, \rangle \otimes , i\rangle) = , \rangle \otimes , i+1\rangle : S(, \rangle \otimes , i\rangle) = , \rangle \otimes , i-1\rangle If we first rotate the spin with some unitary transformation C: \mathcal_C \to \mathcal_C and then apply S, we get a non-trivial quantum motion on \mathbb. 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 : H = \frac\begin1 & \;\;1\\ 1 & -1\end 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 \mathbb is : , \rangle \otimes , 0\rangle \;\,\overset\;\, \frac (, \rangle + , \rangle) \otimes , 0\rangle \;\,\overset\;\, \frac (, \rangle \otimes , 1\rangle + , \rangle \otimes , \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 \mathbb. 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 , \rangle. This asymmetry is entirely due to the fact that the Hadamard coin treats the , \rangle and , \rangle state asymmetrically. A symmetric probability distribution arises if the initial state is chosen to be : , \Psi^_0\rangle = \frac (, \rangle - \textbf , \rangle) \otimes , 0\rangle


Dirac equation

Consider what happens when we discretize a massive
Dirac operator In mathematics and quantum mechanics, a Dirac operator is a differential operator that is a formal square root, or half-iterate, of a second-order operator such as a Laplacian. The original case which concerned Paul Dirac was to factorise formall ...
over one
spatial dimension In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coordin ...
. In the absence of a
mass term Mass is an intrinsic property of a body. It was traditionally believed to be related to the quantity of matter in a physical body, until the discovery of the atom and particle physics. It was found that different atoms and different elementa ...
, we have left-movers and right-movers. They can be characterized by an internal
degree of freedom Degrees of freedom (often abbreviated df or DOF) refers to the number of independent variables or parameters of a thermodynamic system. In various scientific fields, the word "freedom" is used to describe the limits to which physical movement or ...
, "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 Richard Phillips Feynman (; May 11, 1918 – February 15, 1988) was an American theoretical physicist, known for his work in the path integral formulation of quantum mechanics, the theory of quantum electrodynamics, the physics of the superflu ...
'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 The Feynman checkerboard, or relativistic chessboard model, was Richard Feynman’s sum-over-paths formulation of the kernel for a free spin-½ particle moving in one spatial dimension. It provides a representation of solutions of the Dirac equ ...
for more details. The transition probability for a 1-dimensional quantum walk behaves like the Hermite functions which (1)
asymptotically In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related contexts, ...
oscillate in the classically allowed region, (2) is approximated by the
Airy function In the physical sciences, the Airy function (or Airy function of the first kind) is a special function named after the British astronomer George Biddell Airy (1801–1892). The function and the related function , are linearly independent solutio ...
around the wall of the potential, 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


Realization

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. 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.


See also

*
Path integral formulation The path integral formulation is a description in quantum mechanics that generalizes the action principle of classical mechanics. It replaces the classical notion of a single, unique classical trajectory for a system with a sum, or functional in ...


References


Further reading

* * * * * * {{refend


External links


International Workshop on Mathematical and Physical Foundations of Discrete Time Quantum WalkQuantum walk
Quantum algorithms