134.75.87.66: /* Definition */ corrected definition. Previous definition mistook a the parts of a partition for the partition itself.

2014-07-31T07:38:22Z

Definition: corrected definition. Previous definition mistook a the parts of a partition for the partition itself.

140.209.125.53: /* References */

2012-04-19T15:58:01Z

References

New page

{{Use dmy dates|date=July 2013}}
{{Essay-like|date=December 2007}}

A '''Continuous-time quantum walk (CTQW)''' is a walk on a given [[Connectivity (graph theory)|connected]] [[Graph (mathematics)|graph]] that is dictated by a time-varying unitary matrix that relies on the [[Hamiltonian (quantum mechanics)|Hamiltonian]] of the quantum system and the [[adjacency matrix]]. CTQW belongs to what is known as [[Quantum random walk|''Quantum walks'']], which also consists of the Discrete-time quantum walk. The concept of Continuous-time quantum walk is believed to have been first considered for quantum computation by Edward Farhi and Sam Gutmann.<ref name="Farhi:1998">E. Farhi and S. Gutmann, ''Quantum computation and decision trees'', Phys. Rev. A '''58''', 915 (1998)</ref> Though, it may be possible to consider CTQW for directed graphs, we focus on this area as it applies to undirected graphs unless stated otherwise.

==Introduction==
Ever since the advent of quantum mechanics and the discovery by Shor of how to achieve factorization of large semi-primes efficiently (polynomial time) using quantum computation, scientists have been intrigued by the realm of possibilities. In many cases where the quantum algorithms are derived for problems, the complexity of the algorithms are faster than their classical counterpart. Some of these include [[Shor's algorithm|Shor's factorization algorithm]], which is exponentially faster than known classical factoring algorithms, and [[Grover's algorithm|Grover's searching algorithms]], which is polynomially faster than any possible black-box classical algorithm. Many of these algorithms use (or can be modified to use) the concept of [[Quantum Fourier transform|''quantum fourier transform'']].

In recent times, some scientists have decided to propose a new form of looking at quantum computation algorithms. The reason is that many classical algorithms are based on (classical) random walks. This led to the intuitive question of whether a "quantum random walk" could be proposed. Though named "quantum random walk" by many research articles, the more appropriate name will be "quantum walk" given the sense of the randomness used. One such model of a quantum walk is the Continuous-time quantum walk (CTQW) proposed by E. Farhi et al.<ref name="Farhi:1998"/> There are a number of variations to representing a CTQW, but we follow the definition below.

===Mathematical Definition===
A continuous-time quantum walk (CTQW) on a graph ''G'' = (''V,E''), where ''V'' is the set of vertices (nodes) and ''E'' is the set of edges connecting the nodes, is defined as follows:<br> Let ''A'' be the ''|V| <math>\times</math> |V|'' [[adjacency matrix]] of ''G'' with elements
:<math>
A_{u,v} = \left\{
\begin{matrix}
1 & \text{if } \textrm{\{u,v\}} \text{ } \epsilon\text{ } E\\
0 & \text{otherwise}
\end{matrix}\right.
</math>
and ''D'' be the ''|V| <math>\times</math> |V|'' [[degree matrix]] of ''G'' (for which the diagonal entry corresponding to vertex ''v'' is degree(''v'')), and let ''L'' = ''D'' - ''A'', be the corresponding [[Laplacian matrix]] which is positive semidefinite. The continuous-time quantum walk on the graph ''G'' is then defined by the unitary matrix

:<math>\,U(t) = e^{-itL}</math>
<br>where <math>i</math> is the [[imaginary unit]] and <math>t\,\, \epsilon \text{ }\mathbb{R}</math>. The probability of a walk starting at vertex <math>u</math> ending up at vertex <math>v</math> at time <math>t</math> is given by <math>\left| \langle v| U(t) | u \rangle \right|^2</math>.
Consequently starting from the quantum state <math>|\psi_0\rangle</math> and performing a quantum walk for time <math>t</math> will result in the new state
<math>|\psi_t\rangle = U(t)|\psi_0\rangle</math> and measuring will thus localize the walk in vertex <math>v</math> with the probability
<math>\left| \langle v| U(t)|\psi_0\rangle \right|^2</math>.
<ref name="Gerhardt:2003">H. Gerhardt and J. Watrous, ''Continuous-time quantum walks on the symmetric group'', quant-ph/0305182</ref>

==Quantum walk==
To discuss the quantum walk, it is useful to define the more familiar topic of (classical) random walk (CRW). The random walk is well-defined in random processes with the [http://mathworld.wolfram.com/MarkovProcess.html Markov process] model.

===Classical Random Walk (CRW)===
Here, a graph is traversed in an order that predicts the probability of being at a node <math>v</math> in time <math>t</math> given that the walk starts from a node <math>u</math> in the graph. To elaborate this concept, consider the case of a classical walk on a line. Assume a person, John, stands at the origin of a straight line and he has a fair coin. John wants to exhibit a random walk in which the probability of moving a step to the left or right is equal (=1/2). John flips his coin and the outcome dictates where he goes next. If the outcome is head (H), he takes one step to the right and if it is tail (T), he takes one step to the left. Following this rule, then the probability of John being at position <math>d</math> after <math>N</math> steps can be shown to be

:<math>P_N(d) = \frac{1}{2^N}\begin{pmatrix}N\\ \frac{d+N}{2}\end{pmatrix}</math>

Since John has a fair coin, the average of his distribution (where he's expected to be on the average) is the origin (position 0), and the standard deviation can be shown to be <math>\sqrt{N}</math>.<ref name="Travaglione:2001">B.C. Travaglione and G.J. Milburn, ''Implementing the quantum random walk'', quant-ph/0109076</ref> A table showing the probability of this distribution for up to the fourth step is shown below:


===Continuous-time quantum walk (CTQW)===
Now, the fair coin in John's possession is replaced with a qubit. This qubit is defined in terms of states <math>|\downarrow\rangle</math> and <math>|\uparrow\rangle</math> different from the <math>|0\rangle</math>, <math>|1\rangle</math> basis. Next, a Hadamard operation is applied to the initial state. A Hadamard on the up state will give a superposition of up and down as follows
:<math>H|\uparrow\rangle = \frac{1}{\sqrt{2}}|\uparrow\rangle + \frac{1}{\sqrt{2}}|\downarrow\rangle</math>
and
:<math>H=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}</math>
After applying the Hadamard operator, the spin-1/2 rotation in the z-direction is applied, thereby stepping left or right based on the resulting state. Overall, the applied operator becomes
:<math>U=e^{i\hat{p}\sigma_z}H</math>
where <math>\sigma_z</math> is the Pauli-Z operator and <math>\hat{p}</math> is the momentum operator of the qubit particle. This evolving operator in the CTQW is applied N times to the resulting qubit states. When the initial state representing the origin of the line is chosen to be <math>\frac{1}{\sqrt{2}}|\uparrow\rangle + \frac{1}{\sqrt{2}}|\downarrow\rangle</math>, the standard deviation is shown to be approximately <math>\frac{3}{5}N</math> <ref name=Travaglione:2001/> which is in quadratic form of the standard deviation from classical algorithm. In this case the probability of being at position ''d'' after ''N'' steps is different from the classical case as depicted below:

Note that the description employs a discrete-time quantum walk, but it provides an intuitive use on the graph problem for the continuous-time quantum walk where the [[Hamiltonian (quantum mechanics)|Hamiltonian]] evolves the state of the system at any given time.

==Difference between CTQW and CRW<ref name=Farhi:2001>A.M. Childs, E. Farhi, and S. Gutmann, ''An example of the difference between quantum and classical random walks'', quant-ph/0103020</ref>==
Farhi et al. showed<ref name=Farhi:2001/> that on a symmetric graph known as <math>G_{4}</math>, which consists of two binary trees of depth four(4) merged at their children nodes, it is possible for the quantum random walk to achieve exponential speed-up over its classical counterpart. [[Image:G4 graph.png||thumb||right||G4 graph]]
It could be deduced that the probability of reaching the EXIT node from the ENTRANCE node of a <math>G_{n}</math> is less than <math>2^{-n}</math>, but in the quantum case, the limiting distribution probability is at least <math>{(2n+1)}^{-1}</math>. This is a tremendous increase, but it only states that the time to reach the EXIT is faster ''as contrasted from'' the algorithmic speedup. However, it was later shown by the same author <ref name="Farhi:2003">A.M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D.A. Spielman, ''Exponential Algorithmic Speedup by a Quantum walk'' quant-ph/0209131</ref> that indeed an exponential algorithmic speedup can be achieved by the quantum walk.

It is also important to note that the quantum walk 'collapses' to a classical random walk with the degree of decoherence.<ref name="Kempe:2003">J. Kempe, ''Quantum random walks - an introductory overview'', quant-ph/0303081</ref> It is possible to obtain the classical if one measures the positions in the quantum work at every step. In other words, the inability to have superposition restricts the classical domain of walks in graph theory.

==Potential Applications==
The area of CTQW as well as discrete-time quantum walk has given additional insight on how to achieve quantum computation. It is an area of research that is still captivating interest and a number of algorithm using CTQW has been proposed. The three main applications to date are
#Quantum search algorithm<ref name="Shenvi:2002">N. Shenvi, J. Kempe, and K.B. Whaley, ''A quantum random walk search algorithm'', quant-ph/0210064</ref>
#Graph Traversal problem<ref name="Farhi:2003"/>
#[http://info.phys.unm.edu/~alandahl/iqiwiki/index.php/Quantum_Scattering_NAND-Tree_Algorithm Quantum scattering NAND-tree]
In each case, the algorithmic speedup is not different from what was expected in existing quantum algorithms like the Grover search algorithm that takes <math>O(\sqrt{N})</math>.

==References==
<references/>

==External links==
*[http://xstructure.inr.ac.ru/x-bin/theme3.py?level=1&index1=151590 Quantum Walk on arxiv.org]
*[http://demonstrations.wolfram.com/ContinuousTimeQuantumWalk/ CTQW on Wolfram Demonstrations]
*[http://machida.stat.t.u-tokyo.ac.jp/pukiwiki/index.php?Quantum%20walk Quantum walk]

{{DEFAULTSORT:Continuous-Time Quantum Walk}}
[[Category:Quantum mechanics]]

Dominance order - Revision history

134.75.87.66: /* Definition */ corrected definition. Previous definition mistook a the parts of a partition for the partition itself.

140.209.125.53: /* References */