author: Beatrice Nash

Abstract

In this blog post, we give a broad overview of quantum walks and some quantum walks-based algorithms, including traversal of the glued trees graph, search, and element distinctness [3; 7; 1]. Quantum walks can be viewed as a model for quantum computation, providing an advantage over classical and other non-quantum walks based algorithms for certain applications.

Continuous time quantum walks

We begin our discussion of quantum walks by introducing the quantum analog of the continuous random walk. First, we review the behavior of the classical continuous random walk in order to develop the definition of the continuous quantum walk.

Take a graph $G$ with vertices $V$ and edges $E$ . The adjacency matrix $A$ of $G$ is defined as follows:

$A_{i,j} = \begin{cases} 1 \quad &\text{if } (i,j) \in E \\ 0 \quad &\text{otherwise}. \end{cases}$

And the Laplacian $L$ is given by:

$L_{i,j} = \begin{cases} -\text{degree}(i) \quad &\text{if } i = j \\ 1 \quad &\text{if } (i,j) \in E \\ 0 \quad &\text{otherwise}. \end{cases}$

The Laplacian determines the behavior of the classical continuous random walk, which is described by a length $|V|$ vector of probabilities, p(t). The $i$ th entry of p(t) represents the probability of being at vertex $i$ at time $t$ . p(t) is given by the following differential equation:

$\begin{aligned} \frac{\text{d}}{\text{dt}} \text{p}_{i}(\text{t}) = \underset{(i,j) \in E}{\sum} L_{i,j} \text{p}_{j}(\text{t}),\end{aligned}$

which gives the solution $\textbf{p}(t) = e^{Lt}\textbf{p}(0)$ .

Recalling the Schrödinger equation $i \frac{\text{d}}{\text{dt}} \left|\psi\right>= H \left|\psi\right>$ , one can see that by inserting a factor of $i$ on the left hand side of the equation for p(t) above, the Laplacian can be treated as a Hamiltonian. One can see that the Laplacian preserves the normalization of the state of the system. Then, the solution to the differential equation:

$\begin{aligned} i \frac{\text{d}}{\text{dt}} \psi_{i}(\text{t}) = \underset{(i,j) \in E}{\sum} L_{i,j} \psi_{j}(\text{t})\end{aligned}$ ,

which is $\left|\psi(t)\right> = e^{-iLt} \left|\psi(0)\right>$ , determines the behavior of the quantum analog of the continuous random walk defined previously. A general quantum walk does not necessarily have to be defined by the Laplacian; it can be defined by any operator which “respects the structure of the graph,” that is, only allows transitions to between neighboring vertices in the graph or remain stationary [7]. To get a sense of how the behavior of the quantum walk differs from the classical one, we first discuss the example of the continuous time quantum walk on the line, before moving on to the discrete case.

Continuous time quantum walk on the line

An important example of the continuous time quantum walk is that defined on the infinite line. The eigenstates of the Laplacian operator for the graph representing the infinite line are the momentum states with eigenvalues $2(\text{cos}(p) - 1)$ , for $p$ in range $[-\pi,\pi]$ . This can be seen by representing the momentum states in terms of the position states and applying the Laplacian operator:

$\begin{aligned} \left|p\right> &= \underset{x}{\sum} e^{ipx} \left|x\right> \\ L\left|p\right> &= \underset{x}{\sum} e^{ipx} \left|x+1\right>+ e^{ipx} \left|x-1\right> - 2e^{ipx} \left|x\right> \\ &= \underset{x}{\sum} (e^{ip} + e^{-ip} - 2) e^{ipx} \left|x\right> \\ &= 2(\text{cos}(p) - 1) \left|p\right>.\end{aligned}$

Hence the probability distribution at time $t$ , $p(x,t) = |\left< x\right| e^{-iLt} \left|\psi(0)\right> | ^{2}$ , with initial position $\left|\psi(0)\right> = \left|0\right>$ is given by:

$\begin{aligned} |\left< x\right| e^{-iLt} \left|0\right> | ^{2} &= \bigg| \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{-2it(\text{cos}p - 1)} \left< x|p\right> \text{d}p \bigg|^{2} \\ &= \bigg| \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{-2it(\text{cos}p - 1)} e^{ipx} \text{d}p \bigg|^{2} \\ &= | J_{x}(2t) |^{2}.\end{aligned}$

Figure 1.a) Probability distribution for continuous time quantum walk on the infinite line at time $t = 80$ .

Figure 1.a) Probability distribution for continuous time quantum walk on the infinite line at time $t = 80$ .

Figure 1.b) Approximate probability
distribution of the continuous time random walk on the infinite line at
time $t=30$ .

Figure 1.b) Approximate probability
distribution of the continuous time random walk on the infinite line at
time $t=30$ .

While the probability distribution for the classical continuous time
random walk on the same graph approaches, for large $t$ , $\frac{1}{\sqrt{4\pi t}} e^{\frac{-x^{2}}{4t}}$ , or a Gaussian of width $2\sqrt{t}$ . One can see that the quantum walk has its largest peaks at the extrema, with oscillations in between that decrease in amplitude as one approaches the starting position at $x=0$ . This is due to the destructive interference between states of different phases that does not occur in the classical case. The probability distribution of the classical walk, on the other hand, has no oscillations and instead a single peak centered at $x=0$ , which widens and flattens as $t$ increases.

Walk on the glued trees graph

A glued tree is a graph obtained by taking two binary trees of equal height and connecting each of the leaves of one of the trees to exactly two leaves of the other tree so that each node that was a leaf in one of the original trees now has degree exactly $3$ . An example of such a graph is shown in Figure 2.

Figure 2: An example of a glued tree graph, from [2].

The time for the quantum walk on this graph to reach the right root from the left one is exponentially faster than in the classical case. Consider the classical random walk on this graph. While in the left tree, the probability of transitioning to a node in the level one to the right is twice that of transitioning to a node in the level one to the left. However, while in the right tree, the opposite is true. Therefore, one can see that in the middle of the graph, the walk will get lost, as, locally, there is no way to determine which node is part of which tree. It will instead get stuck in the cycles of identical nodes and will have exponentially small probability of reaching the right node.

To construct a continuous time quantum walk on this graph, we consider the graph in terms of columns. One can visualize the columns of Figure 2 as consisting of all the nodes equidistant from the entrance and exit nodes. If each tree is height $n$ , then we label the columns $0,1,\text{...},2n,2n+1$ , where column $i$ contains the nodes with shortest path of length $i$ from the leftmost root node. We describe the state of each column as a superposition of the states of each node in that column. The number of nodes in column $i$ , $N_{i}$ , will be $2^{i}$ for $i \in [0,n]$ and $2^{2n+1-i}$ for $i \in [n+1,2n+1]$ . Then, we can define the state $\left|\text{col} \; i\right>$ as:

$\begin{aligned} \left|\text{col} \; i\right> = \frac{1}{\sqrt{N_{i}}} \underset{j \in \text{col} \; i}{\sum} \left|j\right>.\end{aligned}$

The factor of $\frac{1}{\sqrt{N_{i}}}$ latex ensures that the state is normalized. Since the adjacency matrix $A$ of the glued tree is Hermitian, then we can treat $A$ as the Hamiltonian of the system determining the behavior of the quantum walk. By acting on this state with the adjacency matrix operator $A$ , we get the result (for $i \in [1,n-1]$ ):

$\begin{aligned} A\left|\text{col} \; i\right> &= 2\frac{\sqrt{N_{i-1}}}{\sqrt{N_{i}}} \left|\text{col} \; i-1\right> + \frac{\sqrt{N_{i+1}}}{\sqrt{N_{i}}} \left|\text{col} \; i+1\right> \\ &= \sqrt{2} \left|\text{col} \; i-1\right> + \sqrt{2} \left|\text{col} \; i+1\right>.\end{aligned}$

Then for $i \in [n+2,2n]$ , we get the same result, because of symmetry.

For $i = n$ :

$\begin{aligned} A\left|\text{col} \; n\right> = \sqrt{2} \left|\text{col} \;n-1\right> + 2 \left|\text{col} \; n\right>.\end{aligned}$

The case of $i = n+1$ is symmetric. One can see that the walk on this graph is equivalent to the quantum walk on the finite line with nodes corresponding to the columns. All of the edges, excluding that between columns $n$ and $n+1$ , have weight $\sqrt{2}$ . The edge between column $n$ and $n+1$ has weight $2$ .

The probability distribution of the quantum walk on this line can be roughly approximated using the infinite line. In the case of the infinite line, the probability distribution can be seen as a wave propagating with speed linear in the time $t$ . Thus, in time linear in $n$ , the probability that the state is measured at distance $2n+1$ from the starting state is $\frac{1}{\text{poly} \; n}$ . In [3] it is shown that the fact that the line is finite and has a single differently weighted edge from the others (that between $n$ and $n+1$ ) does not change the fact that in polynomial time, the quantum walk will travel from the left root node to the right one, although in this case there is no limiting distribution as the peaks oscillate. This was the first result that gives an exponential speed up over the classical case using quantum walks.

Figure 3: Although the quantum walk on the glued trees graph does not have a limiting distribution, this is an example of the resulting probability distribution at time $t=30$ for a $n=4$ column glued tree graph. The x-axis corresponds to the columns. One can see that the probability of being at the columns at either extremes is significantly larger than that of being in the middle of the graph. In contrast, the classical random walk takes exponential time to ever reach the exit root node.

Figure 3: Although the quantum walk on the glued trees graph does not have a limiting distribution, this is an example of the resulting probability distribution at time $t=30$ for a $n=4$ column glued tree graph. The x-axis corresponds to the columns. One can see that the probability of being at the columns at either extremes is significantly larger than that of being in the middle of the graph. In contrast, the classical random walk takes exponential time to ever reach the exit root node.

Discrete time quantum walks

In this section, we will first give an introduction to the discrete quantum walk, including the discrete quantum walk on the line and the Markov chain quantum walk, as defined in [7]. Next, we discuss how Grover search can be viewed as a quantum walk algorithm, which leads us into Ambainis’s quantum-walks based algorithm from [1] for the element distinctness problem, which gives a speed up over classical and other quantum non-walks based algorithms.

The discrete time quantum walk is defined by two operators: the coin flip operator, and the shift operator. The coin flip operator $C$ determines the direction of the walk, while the shift operator $S$ makes the transition to the new state conditioned on the result of the coin flip. The Hilbert space governing the walk is $\mathcal{H} = \mathcal{H}{C} \otimes \mathcal{H}{S}$ , where $\mathcal{H}{C}$ corresponds to the space associated with the result of the coin flip operator, and $\mathcal{H}{S}$ corresponds to the locations in the graph on which the walk is defined.

For example, consider the discrete time walk on the infinite line. Since there are two possible directions (left or right), then the Hilbert space associated with the coin flip operator is two dimensional. In the unbiased case, the coin flip is the Hadamard operator,

$\begin{aligned} H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix},\end{aligned}$

and shift operator that produces the transition from state $\left|j\right>$ to $\left|j+1\right>$ or $\left|j-1\right>$ ,
conditioned on the result of the coin flip, is $S = \left|0\right>\left< 0\right| \otimes \underset{j}{\sum} \left|j+1\right> \left< j\right| + \left|1\right>\left< 1\right| \otimes \underset{j}{\sum} \left|j - 1\right> \left< j\right|$ .

Each step of the walk is determined by an application of the unitary
operator $U = S \cdot (H \otimes I)$ . If the walk starts at position
$\left|x\right>$ , then measuring the state after one application of $U$ gives $\left|x+1\right>$ with probability $\frac{1}{2}$ and $\left|x-1\right>$ with probability $\frac{1}{2}$ . This is exactly the same as the case of the classical random walk on the infinite line; the difference between the two walks becomes apparent after a few steps.

For example, the result of the walk starting at state $\left|\psi(0)\right> = \left|0\right>\left|0\right>$ after 4 steps gives:

$\begin{aligned} \left|\psi(1)\right> &= \frac{1}{\sqrt{2}}\left( \left|0\right>\left|1\right> + \left|1\right>\left|-1\right> \right) \\ \left|\psi(2)\right> &= \frac{1}{2}\left( \left|0\right>\left|2\right> + \left|1\right>\left|0\right> + \left|0\right>\left|0\right> - \left|1\right>\left|-2\right> \right) \\ \left|\psi(3)\right> &= \frac{1}{2\sqrt{2}}\left(\left|0\right>\left|3\right> + \left|1\right>\left|1\right> + 2\left|0\right>\left|1\right> -\left|0\right>\left|-1\right> + \left|1\right>\left|-3\right> \right) \\ \left|\psi(4)\right> &= \frac{1}{4} (\left|0\right>\left|4\right> + \left|1\right>\left|2\right> + 3\left|0\right>\left|2\right> + \left|1\right>\left|0\right> -\left|0\right>\left|0\right> -\left|1\right>\left|-2\right> +\left|0\right>\left|-2\right>-\left|1\right>\left|-4\right>).\end{aligned}$

One can see that the distribution is becoming increasingly skewed
towards the right, while in the classical case the distribution will be
symmetric around the starting position. This is due to the destructive
interference discussed earlier. The distribution after $t = 20$ time
steps is shown in Figure 4.

Figure 4: Distribution at time $t = 20$ , with $20$ on the x-axis corresponding to position $0$ .

Figure 4: Distribution at time $t = 20$ , with $20$ on the x-axis corresponding to position $0$ .

Now, consider the walk starting at state $\left|\psi(0)\right> = -\left|1\right>\left|0\right>$ :

$\begin{aligned}\left|\psi(1)\right> &= \frac{1}{\sqrt{2}}\left( -\left|0\right>\left|1\right> + \left|1\right>\left|-1\right> \right) \\ \left|\psi(2)\right> &= \frac{1}{2}\left( -\left|0\right>\left|2\right> - \left|1\right>\left|0\right> + \left|0\right>\left|0\right> - \left|1\right>\left|-2\right> \right) \\ \left|\psi(3)\right> &= \frac{1}{2\sqrt{2}}\left(-\left|0\right>\left|3\right> - \left|1\right>\left|1\right> + 2\left|1\right>\left|-1\right> - \left|0\right>\left|-1\right> + \left|1\right>\left|-3\right> \right) \\ \left|\psi(4)\right> &= \frac{1}{4} (-\left|0\right>\left|4\right> -\left|1\right>\left|2\right> - \left|0\right>\left|2\right> + \left|1\right>\left|0\right> + \left|0\right>\left|0\right> -3\left|1\right>\left|-2\right> + \left|0\right>\left|-2\right> - \left|1\right>\left|-4\right>).\end{aligned}$

This distribution given by this walk is the mirror image of the first.
To generate a symmetric distribution, consider the start state $\left|\psi(0)\right> = \frac{1}{\sqrt{2}}(\left|0\right> -i\left|1\right>)\left|0\right>$ . The resulting distribution after $t$ steps will be $p(x,t) = \frac{1}{2} p_{0}(x,t) + \frac{1}{2} p_{1}(x,t)$ , where $p_{0}(x,t)$ is the probability distribution after $t$ steps resulting from the start state $\psi(0) = \left|0\right>\left|0\right>$ and $p_{1}(x,t)$ is the probability distribution after $t$ steps resulting from the start state $\psi(0) = -\left|1\right>\left|0\right>$ . The result will be symmetric, with peaks near the extrema, as we saw in the continuous case.

Markov chain quantum walk

A reversible, ergodic Markov chain with $n$ states can be represented by a $n \times n$ transition matrix $P$ with $P_{j,i}$ equal to the probability of transitioning from state $i$ to state $j$ and $P = P^{*}$ . Then, $p_{0}P$ , where $p_{0}$ is an initial probability distribution over the states, gives the distribution after one step.
Since $\sum_{j} P_{i,j} = 1$ for all $i$ , $P$ is stochastic and thus preserves normalization.

There are multiple ways to define a discrete quantum walk, depending on the properties of the transition matrix and the graph on which it is defined (overview provided in [4]). Here we look at the quantum walk on a Markov chain as given in [2]. For the quantum walk on this graph, we define state $\left|i\right>\left|j\right>$ as the state that represents currently being at position $j$ and facing in the direction of $i$ . Then, we define the state $\left|\psi_{j}\right>$ as a superposition of the states associated with position $j$ :

$\begin{aligned} \left|\psi_{i}\right> = \underset{j}{\sum} \sqrt{P_{j,i}} \left|i\right>\left|j\right>.\end{aligned}$

The unitary operator,

$D = 2 \underset{i}{\sum} \left|\psi_{i}\right>\left< \psi_{i}\right| - I$ ,

acts as a coin flip for the walk on this graph. Since $P$ is reversible, we can let the shift operator be the unitary $SWAP$ operator:

$SWAP = \underset{i,j}{\sum} \left|i,j\right>\left< j,i\right|$ .

A quantum walk can also be defined for a non-reversible Markov chain using a pair of reflection operators (the coin flip operator is an example of a reflection operator). This corresponds to the construction given in [7].

Search as a quantum walk algorithm

Given a black box function $f$ and a set of inputs $S$ with $|S| = N$ , say we want to find whether an input $x \in S$ exists for which $f(x)$ equals some output value. We refer to the set of inputs $M$ for which this is true as marked. Classically, this requires $O(N/|M|)$ queries, for nonempty $M$ . Using the Grover search algorithm, this problem requires $O(\sqrt{N/|M|})$ quantum queries. In this section, we give a quantum walks based algorithm that also solves this problem in $O(\sqrt{N/|M|})$ time. If we define a doubly stochastic matrix $P$ with uniform transitions, then we can construct a new transition matrix $P'$ from $P$ as:

$P_{i,j}' = \begin{cases} \frac{1}{N-1} \quad &\text{if } i \neq j \text{ and } i \notin M \\0 \quad &\text{if } i = j \text{ and } i \notin M \\ 1 \quad &\text{if } i = j \text{ and } i \in M \\ 0 \quad &\text{if } i \neq j \text{ and } i \in M. \end{cases}$

Then, when the state of the first register is unmarked, the operator $D$ defined in the previous section acts as a diffusion over its neighbors. When the state in the first register is marked, then $D$ will act as the operator $-I$ , and the walk stops, as a marked state has been reached. This requires two queries to the black box function: one to check whether the input is marked, and then another to uncompute. By rearranging the order of the columns in $P$ so that the columns corresponding to the non-marked elements come before the columns corresponding to the marked elements, we get:

$\begin{aligned} P' = \begin{pmatrix} P_{0} & 0 \\ P_{1} & I \end{pmatrix},\end{aligned}$

where $P_{0}$ gives the transitions between non-marked elements and $P_{1}$ gives the transitions from non-marked to marked elements.

We now look at the hitting time of the classical random walk. Assume
that there is zero probability of starting at a marked vertex. Then, we
can write the starting distribution $p$ , where the last $|M|$ elements of $p$ , corresponding to the marked elements, are zero, as
$p = \underset{\lambda}{\sum} \alpha_{\lambda} \left|\lambda\right>$ , where $\lambda$ are the eigenvalues of $P_{0}$ , and $\left|\lambda\right>$ are the corresponding eigenvectors, with the last $|M|$ entries zero. Let $\lambda^{}$ be the principal (largest) eigenvalue. Then, the probability that, after $t$ steps, a marked element has not yet been reached will be $\sum (P_{0}^{t}p)_{i} \leq \lambda^{*t}$ . Then, the
probability that a marked element has been reached in that time will be
$\geq 1 - \lambda^{t} \geq 1 - t \lambda^{*}$ . Setting
$t = \frac{1}{1-\lambda^{*}}$ gives probability $\Omega(1)$ that a marked element will be reached in that time.

The eigenvalues of $P_{0}$ will be $\frac{N-|M|-1}{N-1}$ and
$\frac{-1}{N-|M|-1}$ . Then, the classical hitting time will be:

$\begin{aligned} t &= \frac{1}{1-\lambda^{*}} \\ &= \frac{1}{1-\frac{N-|M|-1}{N-1}} \\ &= O\left(\frac{N}{|M|}\right).\end{aligned}$

It can be showed that for a walk defined by a Markov chain, the
classical hitting time will be $O(\frac{1}{\delta \epsilon})$ , where $\delta = 1 - \lambda^{*}$ , the spectral gap, and $\epsilon \leq \frac{|M|}{N}$ [2].

Magniez et al proved in [6] that for a reversible, ergodic
Markov chain, the quantum hitting time for a walk on this chain is
within a factor of the square root of the classical hitting time. Since
the walk on this input acts as a walk on a reversible Markov chain until
a marked element is reached, then this is also true for a walk defined
by our transition matrix $P'$ . This arises from the fact that the
spectral gap of the matrix describing the quantum walk corresponding to
stochastic matrix $P$ is quadratically larger than the spectral gap of
the matrix describing the classical random walk corresponding to $P$ , the proof of which is given in [2]. Thus, the quantum hitting time
is $O(\sqrt{N/|M|})$ , which exactly matches the quantum query complexity of Grover search.

Element distinctness problem

Now, we describe Ambainis’s algorithm given in [1] for solving
the element distinctness problem in $O(N^{\frac{2}{3}})$ time, which
produces a speed up over the classical algorithm, which requires $O(N)$ queries, and also over other known quantum algorithms that do not make use of quantum walks, which require $O(N^{\frac{3}{4}})$ queries. The element distinctness problem is defined as follows: given a function $f$ on a size $N$ set of inputs

$S=\{x_{1}$ ,…, $x_{N}\}$ ,

determine whether there exists a pair $x_{1},\; x_{2} \in S$ for which $f(x_{1}) = f(x_{2})$ . As in the search problem defined in the previous section, this is a decision problem; we are not concerned with finding the values of these pairs, only whether at least one exists.

The algorithm is similar to the search algorithm described in the previous section, except we define the walk on a Hamming graph. A Hamming graph $H(N,m)$ is defined as follows: each vertex $i$ corresponds to an $m$ -tuple, ( $i_{1}$ ,…, $i_{m}$ ), where $i_{k} \in S$ for all $k$ and repetition is allowed (that is, $i_{k}$ may equal $i_{j}$ for $k \neq j$ ), and $m$ is a parameter we will choose. Edges will exist between vertices that differ in exactly one coordinate (order matters in this graph). We describe the state of each vertex as:

$\left|i \right>=| i_{1},i_{2}$ ,…, $i_{m},f(i_{1})$ ,…, $f(i_{m})>$

Then, moving along each edge that replaces the $j$ th coordinate with $x_{k}$ such that $i_{j} \neq x_{k}$ requires two queries to the black box function to erase $f(i_{j})$ and compute $f(x_{k})$ . In the case, the marked vertices will be those that contain some $f(i_{k}) = f(i_{j})$ for $i_{j} \neq i_{k}$ . Since the function values are stored in the description of the state, then no additional queries to the black box are required to check if in a marked state.

The transition matrix is given by $P = \frac{1}{m(n-1)} \underset{i \in [1,m]}{\sum} (J - I)^{(i)}$ . $J$ is the $n \times n$ all one matrix, and the superscript $i$ denotes the operator acting on the $i$ th coordinate. The factor of $\frac{1}{m(n-1)}$ normalizes the degree, since the graph is regular. We can compute the spectral gap of this graph to be $\frac{n}{m(n-1)}$ (for details of this computation, see [2]). Then, noting that that the fraction of marked vertices, $\epsilon$ , is
$\geq \frac{m(m-1)(n-2)^{m-2}}{n^{m}}$ , classically, the query complexity is $m + O(\frac{1}{\delta \epsilon}) = m + O(\frac{n^{2}}{m})$ , where $m$ is the queries required to construct the initial state. Setting the parameters equal to minimize with respect to $m$ gives classical query complexity $O(N)$ , as expected.

Then in the quantum case, $m$ queries are still required to set up the state. $O(\frac{n}{\sqrt{m}})$ queries are required to perform the walk until a marked state is reached, by [6]. Setting parameters equal gives $O(N^{\frac{2}{3}})$ queries, as desired.

[1] Ambainis, A. Quantum walk algorithm for element distinctness, SIAM Journal on Computing 37(1):210-239 (2007). arXiv:quant-ph/0311001

[2] Childs, A. Lecture Notes on Quantum Algorithms (2017). https://www.cs.umd.edu/ amchilds/qa/qa.pdf

[3] Childs, A., Farhi, E. Gutmann, S. An example of the difference between
quantum and classical random walks. Journal of Quantum Information
Processing, 1:35, 2002. Also quant-ph/0103020.

[4] Godsil, C., Hanmeng, Z. Discrete-Time Quantum Walks and Graph Structures
(2018). arXiv:1701.04474

[5] Kempe, J. Quantum random walks: an introductory overview, Contemporary
Physics, Vol. 44 (4) (2003) 307:327. arXiv:quant-ph/0303081

[6] Magniez, F., Nayak, A., Richter, P.C. et al. On the hitting times of
quantum versus random walks, Algorithmica (2012) 63:91.
https://doi.org/10.1007/s00453-011-9521-6

[7] Szegedy, M. Quantum Speed-up of Markov Chain Based Algorithms, 45th
Annual IEEE Symposium on Foundations of Computer Science (2004).
https://ieeexplore.ieee.org/abstract/document/1366222

[8] Portugal, R. Quantum Walks and Search Algorithms. Springer, New York, NY (2013).

3 thoughts on “Introduction to Quantum Walks”

Gil Kalai says:

December 24, 2018 at 1:10 pm

Very nice post as are the other posts. Maybe it would be a good idea to leave a few days between consecutive postings.

Renato Portugal says:

January 2, 2019 at 7:24 am

Dear Dr. Nash, you may find related material in my book “Quantum Walks and Search Algorithms” (https://link.springer.com/book/10.1007/978-3-319-97813-0).

1. beanash says:
  
  January 7, 2019 at 4:52 pm

	James Cross on GPT as an “Intelligence…
	Thoughts on AI safet… on AI will change the world, but…
	Anonymous on An alarming trend in K-12 Math…
	Interview about this… on Men in Computer Science
	Interview about this… on The Swiss Army Knife of C…

Introduction to Quantum Walks

Continuous time quantum walks

Continuous time quantum walk on the line

Walk on the glued trees graph

Discrete time quantum walks

Markov chain quantum walk

Search as a quantum walk algorithm

Element distinctness problem

Published by beanash

3 thoughts on “Introduction to Quantum Walks”

Leave a Reply Cancel reply

Continuous time quantum walks

Continuous time quantum walk on the line

Walk on the glued trees graph

Discrete time quantum walks

Markov chain quantum walk

Search as a quantum walk algorithm

Element distinctness problem

Share this:

Like this:

Related

Published by beanash

3 thoughts on “Introduction to Quantum Walks”

Leave a Reply Cancel reply