Continuous-time quantum walk

A Continuous-time quantum walk (CTQW) is a walk on a given connected graph that is dictated by a time-varying unitary matrix that relies on the Hamiltonian of the quantum system and the adjacency matrix. CTQW belongs to what is known as 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.^[1] 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 factorization algorithm, which is exponentially faster than known classical factoring algorithms, and 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.

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" (or simply "quantum walk") could be proposed. One such model of a quantum walk is the Continuous-time quantum walk (CTQW) proposed by E. Farhi et al.^[1] 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:
Let A be the |V| $\times$ |V| adjacency matrix of G with elements

$A_{u,v} = \left\{ \begin{matrix} 1 & \text{if } \textrm{\{u,v\}} \text{ } \epsilon\text{ } E\\ 0 & \text{otherwise} \end{matrix}\right.$

and D be the |V| $\times$ |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

$\,U(t) = e^{-itL}$

where $i$ is the imaginary unit and $t\,\, \epsilon \text{ }\mathbb{R}$. The probability of a walk starting at vertex $u$ ending up at vertex $v$ at time $t$ is given by $\left| \langle v| U(t) | u \rangle \right|^2$. Consequently starting from the quantum state $|\psi_0\rangle$ and performing a quantum walk for time $t$ will result in the new state $|\psi_t\rangle = U(t)|\psi_0\rangle$ and measuring will thus localize the walk in vertex $v$ with the probability $\left| \langle v| U(t)|\psi_0\rangle \right|^2$. ^[2]

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 Markov process model.

Classical Random Walk (CRW)

Here, a graph is traversed in an order that predicts the probability of being at a node $v$ in time $t$ given that the walk starts from a node $u$ 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 $d$ after $N$ steps can be shown to be

$P_N(d) = \frac{1}{2^N}\begin{pmatrix}N\\ \frac{d+N}{2}\end{pmatrix}$

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 $\sqrt{N}$.^[3] 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 $|\downarrow\rangle$ and $|\uparrow\rangle$ different from the $|0\rangle$, $|1\rangle$ 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

$H|\uparrow\rangle = \frac{1}{\sqrt{2}}|\uparrow\rangle + \frac{1}{\sqrt{2}}|\downarrow\rangle$

and

$H=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$

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

$U=e^{i\hat{p}\sigma_z}H$

where $\sigma_z$ is the Pauli-Z operator and $\hat{p}$ 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 $\frac{1}{\sqrt{2}}|\uparrow\rangle + \frac{1}{\sqrt{2}}|\downarrow\rangle$, the standard deviation is shown to be approximately $\frac{3}{5}N$ ^[3] 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 evolves the state of the system at any given time.

Difference between CTQW and CRW^[4]

Farhi et al. showed^[4] that on a symmetric graph known as $G_{4}$, 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.

G4 graph

It could be deduced that the probability of reaching the EXIT node from the ENTRANCE node of a $G_{n}$ is less than $2^{-n}$, but in the quantum case, the limiting distribution probability is at least ${(2n+1)}^{-1}$. 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 ^[5] 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.^[6] 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

1. Quantum search algorithm^[7]
2. Graph Traversal problem^[5]
3. 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 $O(\sqrt{N})$.

References

1. E. Farhi and S. Gutmann, Quantum computation and decision trees, Phys. Rev. A 58, 915 (1998)
2. H. Gerhardt and J. Watrous, Continuous-time quantum walks on the symmetric group, quant-ph/0305182
3. B.C. Travaglione and G.J. Milburn, Implementing the quantum random walk, quant-ph/0109076
4. A.M. Childs, E. Farhi, and S. Gutmann, An example of the difference between quantum and classical random walks, quant-ph/0103020
5. 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
6. J. Kempe, Quantum random walks - an introductory overview, quant-ph/0303081
7. N. Shenvi, J. Kempe, and K.B. Whaley, A quantum random walk search algorithm, quant-ph/0210064

External links

• Quantum Walk on arxiv.org
• CTQW on Wolfram Demonstrations
• Quantum walk