Quantum Computing: Implementing Hitting Time for Coined Quantum Walks on
Regular Graphs

Ellinor Wanzambi, Stina Andersson

Uppsala
August 27, 2024

###### Abstract

In recent years, quantum walks have been widely researched and have shown
exciting properties. One such is a quadratic speed-up in hitting time compared
to its classical counterpart. In this paper, we design a quantum circuit for
the MNRS algorithm, which finds a marked node in a graph with a quantum walk,
and use it to find a hitting time for the marked nodes in the walk. We do this
by implementing the circuit on IBM quantum simulators and show that the
execution on a noise-free simulator results in hitting times that agree with
the theoretical expectations. We also run the algorithm on a mock backend that
simulates the noise of the IBM Melbourne computer. As expected, the noise has
an extensive impact on the output, resulting in outcomes far from the noise-
free simulation.

## Acknowledgments

During the writing of this Master Thesis, we have received much support from
different people. This thesis would not have been possible without their help,
and we would like to offer our gratitude towards them. Firstly, we cannot
begin to express our thanks to Researcher Dr. Dhinakaran Vinayagamurthy and
Research Engineer Dhiraj Madan at IBM Research, who has helped us continuously
throughout the entire process. We are highly grateful for the time you have
spent to help and support us. Both of you have played decisive roles in
deciding the topic for the thesis, and it is thanks to your knowledge and
valuable advice that we have been able to complete it. We would also want to
extend our sincere thanks to Mikael Haglund, CTO at IBM Sweden, for your
guidance and support. Your profound belief in our abilities has encouraged us
greatly during this process. Lastly, we want to give many thanks to Associate
Professor Carl Nettelblad for reviewing our thesis and giving us many
practical suggestions. You have always been willing to give of your time to
help us, which has made the process of writing this thesis considerably
easier.

###### Contents

  1. 1 Introduction
  2. 2 Theory
    1. 2.1 Hilbert space
    2. 2.2 Quantum computing
      1. 2.2.1 Qubits
      2. 2.2.2 Quantum gates
      3. 2.2.3 Phases
    3. 2.3 Quantum oracle
    4. 2.4 Quantum Fourier transform
      1. 2.4.1 Phase estimation
    5. 2.5 Grover’s algorithm
    6. 2.6 Qiskit
      1. 2.6.1 State vector vs measurement output
      2. 2.6.2 IBM Melbourne quantum computer
      3. 2.6.3 Mock backends
    7. 2.7 Quantum computers and noise
    8. 2.8 Hardware-aware circuits
    9. 2.9 Classical Markov chains
    10. 2.10 Quantum walks
      1. 2.10.1 Quantum walk with coins
      2. 2.10.2 Szedgedy’s quantum walk model
      3. 2.10.3 Equivalence of coined and Szegedy’s model
      4. 2.10.4 Hitting time
    11. 2.11 Quantum walk search algorithm
  3. 3 Method
    1. 3.1 Implementation of Grover coin
    2. 3.2 Coined quantum walks
      1. 3.2.1 Hypercube
      2. 3.2.2 2-dimensional lattice with boundary conditions
      3. 3.2.3 Complete bipartite graph
      4. 3.2.4 Complete graph
    3. 3.3 Implementation of quantum walk search algorithm
  4. 4 Result
    1. 4.1 4-dimensional hypercube
    2. 4.2 2-dimensional lattice
    3. 4.3 Complete bipartite graph
    4. 4.4 Complete graph
  5. 5 Discussion
  6. 6 Recommendation
  7. 7 Conclusions
  8. A Quantum gates
    1. A.1 Single qubit gates
      1. A.1.1 NOT gate
      2. A.1.2 Hadamard gate
      3. A.1.3 Z gate
      4. A.1.4 I gate
      5. A.1.5 $R_{Z}$ gate
      6. A.1.6 $\sqrt{X}$ gate
    2. A.2 Multi-qubit gates
      1. A.2.1 CNOT gate
      2. A.2.2 $n$-bit Toffoli gate
      3. A.2.3 SWAP gate
      4. A.2.4 Controlled-Z gate
      5. A.2.5 $\ket{0}$ as control qubit

##  1 Introduction

In October 2019, Google published a report in Nature, announcing that they had
achieved quantum supremacy [2]. In only 200 seconds, the quantum computer
managed to do calculations that would take the best classical computer 10 000
years to complete. This was a major milestone in quantum computing, and there
is much more to come. IBM has revealed that their target for the end of 2023
is a quantum device with more than 1000 qubits [9]. To put this in context:
already with 300 qubits, a quantum computer can do more calculations
simultaneously than there are particles in the universe [20].

Alongside hardware development, progress has also been made in the area of
quantum algorithms. Two of the most famous algorithms are Shore’s algorithm
for integer factorization [26], and Grover’s algorithm for searching an
unsorted database [8]. Both have shown a significant speed-up compared to
their classical counterparts. Something that has turned out to be a key in
many quantum algorithms is quantum walks, which is the quantum equivalence of
a classical Markov chain, i.e., a walk without memory. Quantum walks are
useful in areas such as searching [13, 25], node ranking in networks [17, 18]
and element distinctness [1]. The two most popular models for discrete-time
quantum walks are coined quantum walks and Szegedy’s quantum walk. Coined
quantum walks are walks on the vertices of a graph. Szegedy’s walk, on the
other hand, is a walk on the edges of a bipartite double cover of the original
graph. These two models are equivalent under certain circumstances, namely
when the coin used in the coined walk is a Grover coin [28]. Most research on
quantum walks has been on their theoretical properties, but there has been a
few papers on circuit design and implementation. A 2016 paper by Loke and Wang
[12] shows circuits for implementing Szegedy’s walk for a few different graphs
and a paper by Douglas and Wang [7] presents some circuits for coined quantum
walks.

The MNRS algorithm [13] is a quantum search algorithm that finds a marked
element in a graph with a quantum walk. In this paper, we design a quantum
circuit for the MNRS algorithm, and use it to find the walk’s hitting time.
The hitting time for a (quantum or classical) random walk is the minimum
number of steps required to reach a marked vertex in a graph. We also give
quantum circuits for walks with Grover coin on a hypercube, 2-dimensional
lattice, complete bipartite graph, and complete graph, which are the graphs
that we use in the quantum walk search algorithm. Finally, we implement the
search algorithm with all four graphs on IBM quantum simulators and compare
the resulting hitting times to what has been derived from theory. This paper
is structured as follows. Section 2 provides an introduction to quantum
computing, quantum walks and the quantum walk search algorithm. In section 3,
we present the quantum circuits for the graphs and the quantum walk search
algorithm. The results are given and discussed in sections 4 and 5
respectively. Section 6 gives some recommendations for future work and the
conclusions are found in section 7.

##  2 Theory

###  2.1 Hilbert space

The state of a quantum system can be described by a vector in its associated
Hilbert space, which we also refer to as the state space. A Hilbert space is a
complex vector space with an inner product [19].

###  2.2 Quantum computing

Computers make use of bits and Boolean logic gates to store and manipulate
information. In a classical computer, bits are binary and can be either 0 or
1. Quantum computers have logic gates that are based on the principles of
quantum mechanics. Instead of acting on regular binary bits, these gates
operate on so-called quantum bits, or qubits. Qubits have the property that
they cannot only be in one of the two binary states; they can also be in
combinations of both states simultaneously, called a superposition. As a
consequence, this allows us to develop new, faster algorithms that outperform
their classical counterparts. In quantum computing, we start with a set of
qubits, all in state $\ket{0}$, and apply a sequence of gates to manipulate
the qubits, before we do a measurement to obtain the result [14].

####  2.2.1 Qubits

In the same way that bits are crucial in classical computers, qubits are
fundamental in quantum computing. A classical bit is always in a single state,
$\ket{0}$ or $\ket{1}$, while a qubit can also be in a so-called mixed state:

$\ket{\psi}=\alpha\ket{0}+\beta\ket{1},$ (1)

i.e. a linear combination of the computational basis states $\ket{0}$ and
$\ket{1}$. This is called superposition. The coefficients $\alpha$ and $\beta$
are complex numbers and are called the amplitudes of state. It is impossible
to directly observe the state of a qubit in superposition. Instead, we need to
apply a measure gate. When we measure a qubit, we will not get a mixed state
as in equation (1); the resulting state will be either $\ket{0}$ or $\ket{1}$
and we will not know the state of the qubit before the measurement. At the
time of measurement, we say that the qubit collapses to state $\ket{0}$ or
$\ket{1}$, and the probabilities for each state are given by the square of the
coefficients in (1). That is, the qubit collapses to $\ket{0}$ with
probability $|\alpha|^{2}$ and to $\ket{1}$ with probability $|\beta|^{2}$
[15]. From this follows that the coefficients in (1) must satisfy

$|\alpha|^{2}+|\beta|^{2}=1.$ (2)

The states $\ket{0}$ and $\ket{1}$ can also be expressed by unit vectors in a
2-dimensional Hilbert space, $\mathcal{H}^{2}$,

$\ket{0}=\begin{bmatrix}1\\\ 0\end{bmatrix},\;\ket{1}=\begin{bmatrix}0\\\
1\end{bmatrix}.$ (3)

If we have two qubits, the computational basis is the four states $\ket{00}$,
$\ket{01}$, $\ket{10}$, $\ket{11}$. In general, the computational basis
consist of the possible distinct states a qubit, or a set of qubits, can
collapse to in the measurement. Similarly as in the one qubit case, two qubits
can exist in superposition of the computational basis,

$\ket{\psi}=\alpha_{00}\ket{00}+\alpha_{01}\ket{01}+\alpha_{10}\ket{10}+\alpha_{11}\ket{11},$
(4)

where $|\alpha_{ij}|^{2}$ denotes the probability that the qubit collapse in
state $\ket{ij}$ [15]. Also here the squares of the amplitudes must sum to 1.
We can generalize this idea to $n$ qubits; an $n$ qubit system has $2^{n}$
computational basis states, which can be represented by unit vectors in the
$2^{n}$-dimensional Hilbert space. For the state to be a valid quantum state
the amplitudes must satisfy $\sum\limits_{i\in x}|a_{i}|^{2}=1$, where $x$ is
the set of all $2^{n}$ computational basis states.

The state of a quantum system of $n$ qubits can be expressed as follows: let
$\ket{\psi_{1}}$,…, $\ket{\psi_{n}}$ be the states of each of the $n$ qubits.
Then, the state of the quantum system is the tensor product of the individual
states, i.e., $\ket{\psi_{1}}\otimes\cdot\cdot\cdot\otimes\ket{\psi_{n}}$
[19].

Now consider the state

$\ket{\psi}=\frac{\ket{00}+\ket{11}}{\sqrt{2}},$ (5)

which collapses to $\ket{00}$ or $\ket{11}$ with equal probability $1/2$. Even
though the qubits are in superposition, we will know the state of the second
qubit by only measure the first since the only possible states are that the
two qubits collapse to the same state. That is, if we measure the first qubit
and get $\ket{1}$ we know, without applying a measure gate to the second
qubit, that it also will collapse to $\ket{1}$. Similarly, we can obtain the
state of the first qubit by measuring only the second. We say that the two
qubits are entangled, or that they are in entangled states [3]. On the
contrary, the state

$\ket{\psi}=\frac{\ket{00}+\ket{01}}{\sqrt{2}}.$ (6)

is not entangled since we do not know the state of the second qubit by only
measure the first; it can be both $\ket{0}$ and $\ket{1}$. Entangled qubits
cannot be written as the tensor product of the individual states. Thus, in a
quantum state of $n$ qubits, if $m$ qubits can be represented by
$\ket{\psi_{1}}\otimes\cdot\cdot\cdot\otimes\ket{\psi_{m}}$, $m\leq n$, the
$m$ qubits are not entangled [10].

####  2.2.2 Quantum gates

Operations on quantum states are called gates. Let $\ket{\psi}$ be a quantum
state. We can transform it into state $\ket{\psi^{\prime}}$ by applying the
gate $U$ as follows,

$\ket{\psi^{\prime}}=U\ket{\psi}.$ (7)

A gate is represented by a unitary matrix, which means that the norm, and
thereby the probabilities, of the state vector is unaffected by the operation.
This is required for the quantum state after the transformation to be valid
since the probabilities must sum to 1 both before and after the operation. It
is also necessary that all gate matrices are unitary since one requirement on
the gates is that they are reversible; combining a gate immediately followed
by its conjugate transpose should return the original quantum state before the
gates were used. A quantum gate operating on $n$ qubits has degree $2^{n}$.

One of the most simple gates is the NOT or (Pauli-) X gate. It inverts a
qubit, so $\ket{0}$ becomes $\ket{1}$ and $\ket{1}$ converts to $\ket{0}$. The
matrix representation of the NOT gate is

$U_{\text{NOT}}=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}.$ (8)

Using the vector notation of the computational basis states for two qubits
introduced in (3) we can see that the NOT gate inverts the qubits as expected
[21]:

$\displaystyle U_{\text{NOT}}\ket{0}$ $\displaystyle=\begin{bmatrix}0&1\\\
1&0\end{bmatrix}\begin{bmatrix}1\\\ 0\end{bmatrix}=\begin{bmatrix}0\\\
1\end{bmatrix}=\ket{1}$ (9) $\displaystyle U_{\text{NOT}}\ket{1}$
$\displaystyle=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}\begin{bmatrix}0\\\
1\end{bmatrix}=\begin{bmatrix}1\\\ 0\end{bmatrix}=\ket{0}.$ (10)

To put a qubit into superposition we can apply the Hadamard gate, H for short,
which puts the qubit into an equal superposition of the computational basis.
It puts $\ket{0}$ into the state $\frac{\ket{0}+\ket{1}}{\sqrt{2}}$ and
$\ket{1}$ in $\frac{\ket{0}-\ket{1}}{\sqrt{2}}$. The matrix is given by

$U_{H}=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\\ 1&-1\end{bmatrix}.$ (11)

The $-1$ in the matrix makes the gate reversible. Both the NOT gate and the
Hadamard gate act on one qubit but there are gates that operate on multiple
qubits. One such gate is the controlled-NOT, or CNOT, gate. The CNOT gate acts
on two qubits - the control qubit and the target qubit. If the control qubit
is $\ket{1}$, it flips the state of the target. In other words, it applies the
NOT gate to the target qubit if the control is in state $\ket{1}$. This can be
written in terms of the XOR operator:

$\ket{\psi_{1},\psi_{2}}\mapsto\ket{\psi_{1},\psi_{2}\oplus\psi_{1}},$ (12)

and in matrix notation [21]:

$U_{\text{CNOT}}=\begin{bmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&0&1\\\
0&0&1&0\end{bmatrix}.$ (13)

We can extend this idea and use more control qubits. A Toffoli gate has two
control qubits and one target. Similarly to the CNOT gate, we can express it
with the XOR operator:

$\ket{\psi_{1},\psi_{2},\psi_{3}}\mapsto\ket{\psi_{1},\psi_{2},\psi_{3}\oplus\psi_{1}\psi_{2}}.$
(14)

It is also possible to implement an $n$-qubit Toffoli gate with the same idea
as above. We then have $n-1$ control qubits and one target.

We can implement multiple gates in sequence; this is called a quantum circuit.
Assume that we have a unitary operator $U$ that consists of two other unitary
operators $U_{1}$ and $U_{2}$, $U=U_{1}U_{2}$. If we apply $U$ to some state
$\ket{\psi}$ we get the following expression:

$U\ket{\psi}=U_{1}U_{2}\ket{\psi}.$ (15)

As we see in the equation, we first apply $U_{2}$ on $\ket{\psi}$ followed by
$U_{1}$. When we implement this circuit, we must place the gates in the order
of application. That is, $U_{2}$ before $U_{1}$. This applies to all quantum
circuits. Figure 1 shows the correct implementation for $U$.

Figure 1: Implementation of $U=U_{1}U_{2}$.

####  2.2.3 Phases

One thing that distinguishes quantum computers from their classical
counterparts is phases. In quantum computing, we work with both global phase
and relative phase. Let us consider the states $e^{i\theta}\ket{\psi}$ and
$\ket{\psi}$. They differ by $e^{i\theta}$, which is the global phase factor,
and $\theta$ is defined as the phase. The global phase does not have any
physical meaning and does not change the measurement probabilities. That is,
in terms of measurement, they are equivalent. The relative phase of a system
has a different meaning. Consider the matrix for the Hadamard gate given in
equation (11). If we apply it to a $\ket{0}$ state, we get the mixed state

$\frac{\ket{0}+\ket{1}}{\sqrt{2}},$ (16)

and if we apply it to state $\ket{1}$ we obtain

$\frac{\ket{0}-\ket{1}}{\sqrt{2}}.$ (17)

We can see that the amplitude for state $\ket{0}$ is the same in both (16) and
(17) but the amplitude for $\ket{1}$ differs; in (16) it is
$\frac{1}{\sqrt{2}}$ and in (17) it is $-\frac{1}{\sqrt{2}}$. We say that the
states differ in relative phase with relative phase factor $-1$. If we have
two arbitrary amplitudes $a_{1}$ and $a_{2}$ we say that they differ in
relative phase if there exists a $\theta\in\mathbb{R}$ such that
$a_{1}=e^{i\theta}a_{2}$ [15]. Now, let us apply another Hadamard gate on the
states (16) and (17). We start with the state in (16) and obtain the
following:

$\displaystyle H\Big{(}\frac{\ket{0}+\ket{1}}{\sqrt{2}}\Big{)}$
$\displaystyle=\frac{1}{\sqrt{2}}H(\ket{0})+H(\ket{1})$ (18)
$\displaystyle=\frac{1}{\sqrt{2}}\Big{(}\frac{\ket{0}+\ket{1}}{\sqrt{2}}+\frac{\ket{0}-\ket{1}}{\sqrt{2}}\Big{)}$
(19) $\displaystyle=\frac{1}{2}\cdot 2\ket{0}$ (20) $\displaystyle=\ket{0}.$
(21)

Following the same logic when we apply the Hadamard gate on the state (17) we
get

$H\Big{(}\frac{\ket{0}-\ket{1}}{\sqrt{2}}\Big{)}=\ket{1}.$ (22)

We can see that terms are canceling out because of difference in the relative
phases. This property, called interference, makes it possible to “force” the
outcome of a qubit towards a wanted state, something that is widely used in
many quantum algorithms [14].

###  2.3 Quantum oracle

In quantum algorithms we sometimes want to give an input $x$ and receive an
output $f(x)$ for some function $f$. In the algorithms, we usually assume that
there exists some black box implementation of this function, referred to as an
oracle. We know that quantum gates must be reversible, i.e., given an output
$f(x)$ we are able to uniquely identify the input $x$. This is not true in
general; it only works when every input $x$ gives a unique output $f(x)$.
However, we can make the transformation reversible by having a copy of the
input in the output. One of the most common form of oracles is Boolean
oracles, which we define by the unitary evolution

$U_{f}\ket{x,\bar{0}}=\ket{x,f(x)}.$ (23)

As we see in equation (23), the first register keeps track of the input state
$\ket{x}$ and does not change throughout the transformation. This register
consists of the number of qubits required to represent $\ket{x}$. The second
register encodes the output. The input $\ket{\bar{0}}$ denotes the state in
which all qubits are $\ket{0}$ and $\ket{f(x)}$ is the binary representation
of the output. The second register must have as many qubits as needed to
represent $\ket{f(x)}$.

Another form of oracles is the phase oracle, where $f(x)$ is a bit value,
either 0 or 1. A phase oracle shifts the relative phase of $\ket{x}$ by $-1$
if $f(x)=1$. We define a phase oracle as [3]

$P_{f}\ket{x}=(-1)^{f(x)}\ket{x}.$ (24)

###  2.4 Quantum Fourier transform

The discrete Fourier transform takes a vector in $\mathcal{C}^{N}$ and maps it
to a vector in $\mathcal{C}^{N}$. If we let the input vector consist of the
elements $x_{0},...,x_{N-1}$ we can define the elements of the output, i.e.
the transformed data, as

$y_{k}\equiv\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_{j}e^{2\pi
ijk/N},\;k=0,...,N-1.$ (25)

The quantum Fourier transform is similar to the discrete one but acts on a
quantum state $\ket{x}=\sum_{i=0}^{N-1}x_{i}\ket{i}$ and converts it into
another quantum state $\ket{y}=\sum_{k=0}^{N-1}y_{k}\ket{k}$:

$\sum_{i=0}^{N-1}x_{i}\ket{i}\mapsto\sum_{k=0}^{N-1}y_{k}\ket{k},$ (26)

where $x_{j}$ are the amplitudes of the non-transformed data and $y_{k}$ are
the amplitudes after the Fourier transform. We can define the quantum Fourier
transform as a linear operator as follows,

$\ket{j}\mapsto\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}e^{2\pi
ijk/N}\ket{k},\;k=0,...,N-1.$ (27)

The quantum Fourier transform is a unitary transformation and, hence, it can
be implemented in a quantum computer. Let $R_{k}$ denote the gate

$R_{k}\equiv\begin{bmatrix}1&0\\\ 0&e^{2\pi i/2^{k}}\end{bmatrix}.$ (28)

Then the quantum circuit for the quantum Fourier transform is given in Figure
2 [15].

Figure 2: Circuit implementation of the quantum Fourier transform.  Source:
[15]

####  2.4.1 Phase estimation

One important property of the quantum Fourier transform is that it enables
phase estimation, an approximation of the eigenvalues of a unitary operator.
Phase estimation is a general procedure that turns out to be a key ingredient
in many quantum algorithms. Assume that $U$ is a unitary operator that has an
eigenvector $\ket{u}$ with corresponding eigenvalue $e^{2\pi i\theta}$. Given
that $\theta$ is unknown, the goal of the phase estimation is to find the
value of $\theta$. To do this, we have two registers. The first one has $t$
qubits, all starting in state $\ket{0}$, and we choose $t$ depending on how
many digits of accuracy we want to have and with what probability we want to
succeed with the estimation. The other register starts in state $\ket{u}$, and
has as many qubits as required to store $\ket{u}$. The phase estimation is
done in two steps. We start by applying Hadamard gates on the first register,
along with a sequence of controlled-$U$ gates raised to successive powers of
two on the second register. After this, we apply the inverse quantum Fourier
transform on the first register. We get the phase estimation by measuring the
first register. To obtain the inverse transform, we reverse the circuit of the
original quantum Fourier transform given in Figure 2 [15]. The full
implementation of the phase estimation is presented in figure 3.

Figure 3: Quantum circuit for the phase estimation. The ’/’ denotes $m$
qubits.

###  2.5 Grover’s algorithm

Consider the problem of searching for an element in an unstructured dataset.
Given that the set contains $N$ elements, this can be done in $O(N)$ in a
classical computer. With a quantum computer, we can solve the same problem
using only $O(\sqrt{N})$ operations. The algorithm that enables this is called
Grover’s search algorithm or just Grover’s algorithm. The algorithm makes use
of an oracle function $f(x)$, such that $f(x)=1$ if and only if $x$ is a
solution to the search problem. Otherwise, $f(x)=0$. Let $x_{0}$ be the
element we are searching for. The oracle is represented by a unitary operator
$U_{f}$ such that

$\displaystyle U_{f}=-\ket{x}\>$ $\displaystyle\text{if}\>x=x_{0},$
$\displaystyle U_{f}=\ket{x}\>$ $\displaystyle\text{if}\>x\neq x_{0}.$ (29)

Looking at equation (24) we see that the unitary operator above represents a
phase oracle, i.e., it marks the solutions by shifting the phase of $\ket{x}$.
The algorithm begins with applying a uniform superposition to all qubits,
$\ket{s}=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\ket{x}$. After this initial step
the circuit has equal probability to collapse to each state in the
computational basis. Now we define the diffusion operator, $U_{d}$, as
$2\ket{s}\bra{s}-I$. Then the evolution operator for one step of the Grover
algorithm is $U=U_{d}U_{f}$. After the initial condition, we apply $U$. If we
do so $\lfloor\frac{\pi}{4}\sqrt{N}\rfloor$ times before measuring the result
will be $x_{0}$ with probability $1-\frac{1}{N}$ [19]. The one-step circuit
for Grover’s algorithm is presented in Figure 4.

Figure 4: Quantum circuit for one step of Grover’s algorithm.

###  2.6 Qiskit

Qiskit is an open-source framework for quantum computing provided by IBM.
Qiskit makes it possible to write quantum programs using Python and running it
on simulators or actual quantum prototypes. Qiskit can be used both on a local
computer and in IBM Quantum Experience, a cloud-based quantum computing
service [3].

The quantum simulator provided by IBM allows running circuits with ideal
quantum states without noise. This is something that is not possible on real
quantum computers, which in general suffers from much noise. However, we can
also simulate this noise in a quantum simulator, making it possible to achieve
results closer to those of an actual quantum device. Simulators also provide
other features that are not possible on today’s hardware, such as up to 5000
qubits and the ability to run larger circuits [5].

As we have mentioned, there is no way to know the state of a quantum system.
All we can do is a measurement that outputs the states the qubits collapsed
to, but we will never know the state of the system before the measurement.
However, in a quantum simulator, we can do just this by looking at the state
vector. The state vector is a vector that summarizes the state of the system
at a defined time point. With a real quantum computer, we will not have this
information since the qubits operate in a closed system that we cannot
observe. Having access to the state vector means that we can inspect the
system’s state and thereby know the probabilities of collapsing to all
possible states at any point in time. This is something that will be useful
for us when we run the quantum walk search algorithm [3].

####  2.6.1 State vector vs measurement output

Two plots that can easily be confused are the state vector plot and the
measurement output plot. As mentioned above, the state vector summarizes the
state of the quantum system at a certain time point and is something that we
can observe when we run a circuit on a quantum simulator. A state vector plot
is a histogram that shows the probabilities that the circuit collapses to each
state in the computational basis at that time point. When we run a full
quantum circuit (on either a simulator or a quantum prototype), the program
executes multiple times. The number of execution times is called shots, and
one common value is $2^{10}$. In each execution, the full program runs,
including the measurement. The measurement plot shows the frequency of the
output states after all shots. So, the bars in a measurement plot show
$\frac{\text{number of times circuit collapses to }x_{i}}{\text{total number
of shots}}$ for each state $x_{i}$ in the computational basis.

####  2.6.2 IBM Melbourne quantum computer

Melbourne is a quantum device provided by IBM. It is accessible to the public
via IBM Quantum Experience and has 15 qubits, more than any of the other
publicly accessible quantum computers on the platform. It has five basis
gates, CNOT, I, $R_{Z}$, SX, and NOT gate. This means that the circuit will be
transpiled to an equivalent sequence of these gates in during compilation,
since these are the only gates that are executable in the physical quantum
device. Figure 5 shows the architecture of the Melbourne computer [22]. How
the qubits are physically connected in the quantum device affects the
compilation of the circuit. Operations between qubits that are not physically
connected in general require more gates than operations between physically
linked qubits.

Figure 5: Qubit architecture in the Melbourne quantum computer.

####  2.6.3 Mock backends

As we have previously mentioned, it is possible to run quantum simulators with
simulated noise. If we use so-called mock backends, we can simulate the noise
model of a specific quantum device. By doing so, we get an approximation of
the results that we would get if the program was executed on the actual
quantum computer. These models build on a finite set of input parameters
linked to the gates average error rates. Hence, we can only approximate the
errors on the real device. These mock backends are also referred to as fake
backends [6]. If we, for instance, write fake Melbourne, we refer to a mock
backend with a noise model associated with the Melbourne computer.

###  2.7 Quantum computers and noise

As mentioned in section 2.6, Qiskit offers the possibility to run circuits on
quantum simulators as well as actual quantum computers. In Figures 7 and 7, we
see the outputs after running the same simple circuit on a noise-free quantum
simulator and a quantum computer. The circuit applies a NOT gate to a
$\ket{0}$ qubit. As we see in Figure 7, the simulator always outputs
$\ket{1}$, which is the expected output state. However, in Figure 7 the qubit
collapses to state $\ket{0}$ roughly $7\%$ of the times. This due to noise in
the quantum computer.

Figure 6: Qiskit simulator output after applying a NOT gate to a qubit in
state $\ket{0}$.

Figure 7: Qiskit quantum prototype output after applying a NOT gate to a qubit
in state $\ket{0}$.

Ideally, qubits operate in a closed environment without interaction with the
surroundings, until we measure them. Today there is no way to fully accomplish
this. Another problem is that qubits are not stable enough to always hold
their quantum effects; they sometimes accidentally lose their quantum states,
and we have not yet found a way to achieve complete control of this. Because
of this, there is a noise associated with each qubit [24]. Altogether, this
means that the more qubits we have in our circuit, the larger the noise.

###  2.8 Hardware-aware circuits

The qubits in a quantum computer are usually not fully connected, as is the
case with the previously mentioned IBM Melbourne quantum computer. The
compiler does not only transpile a circuit to consist of basis gates entirely;
it also transpiles the circuit to fit the qubit architecture in the physical
hardware. This is achieved with swap operators, which swaps qubits such that
qubits that interact with each other are directly connected. The reason is
that we can only apply a multi-qubit operation to qubits that are directly
connected. So, if we apply a multi-qubit gate to qubits that are not connected
in the physical hardware, the transpiler must swap the qubits to use the gate.

All these swap operators required for multi-qubit gates may lead to a
transpiled circuit that is much deeper than the original circuit. Since the
noise increases with the number of gates, relatively small circuits might be
transpiled into much larger circuits that suffer heavily from noise. Since the
noise from just one gate is quite large, the noise in a sequence of gates will
quickly become such an issue that the output from the circuit is worthless.
Not only does the noise increase, the execution time for these transpiled
circuits also increases [16].

We can decrease the depth of a transpiled circuit by making it hardware-aware.
One way to do this is by constructing the circuit such that we minimize the
number of swaps in the transpiled circuit. We can do this by letting qubits
that often interact with each other be qubits closely connected in the
physical hardware architecture. For example, if the same two qubits have many
two-qubit gates acting on them, we arrange these two qubits to be right next
to each other.

###  2.9 Classical Markov chains

A Markov chain is a stochastic process often used to model real-life
processes. It consists of a set of states and associated transition
probabilities, which describe the probabilities to move between the states in
each time step. This report considers discrete-time walks, implying that there
are discrete, enumerable, time steps. Markov chains satisfy the Markov
property, meaning that the conditional probability distribution of future
states only depends on the present state. If $X$ is a Markov chain, we can
mathematically describe the Markov property as

$P(X_{t}=x_{t}|X_{t-1}=x_{t-1},...,X_{0}=x_{0})=P(X_{t}=x_{t}|X_{t-1}=x_{t-1}).$
(30)

An example of a Markov chain is given in Figure 8. As we see in the graph, the
probability to move to another state depends only on the current state. The
sum of all edges going out from a state has to be equal to 1.

Figure 8: A directed graph showing a Markov chain with three states
represented by nodes. The probabilities of moving between the different states
are shown as the directed edges between the states.

The transition matrix for the Markov chain in Figure 8 is

$P=\begin{pmatrix}0.1&0.3&0.3\\\ 0.1&0.1&0.2\\\ 0.8&0.6&0.5\end{pmatrix}.$
(31)

The transition matrix shows how likely an entity is to move between states in
one time step. We can obtain the probabilities for multiple time steps by
multiplying the transition matrix with itself, i.e., $P^{t}$. Let vector
$v_{0}$ represent the initial state distribution. $v_{0}=(1,0,0)^{T}$ means
that it starts at state A with probability 1,
$v_{0}=(\frac{1}{3},\frac{1}{3},\frac{1}{3})^{T}$ means that it starts in
state A, B, or C with equal probability. Given an initial probability vector
$v_{0}$ and a transition matrix $P$, the state probabilities after $t$ time
steps can be expressed as:

$v_{t}=P^{t}v_{0}.$ (32)

We say that a Markov chain is ergodic if it, for all pair of states $i,j$,
exists a $T$ such that there is a positive probability of being in state $j$
for all $t>T$ given that we start in state $i$. An ergodic Markov chain will,
regardless of the initial state, converge to a stationary distribution. That
is, for an ergodic Markov chain there exists a probability distribution
$v_{c}$ such that

$v_{c}=Pv_{c}.$ (33)

If we select the initial distribution $v_{0}$ such that $v_{0}=v_{c}$, walking
a time step on the graph would not change the probability distribution of the
walker being at a certain state. Mixing time is the time it takes to get close
to this stationary distribution. Let the distance between two distributions
$p$ and $q$ on the finite state space $\Omega$ be

$D(p,q)=\frac{1}{2}\sum_{x\in\Omega}|p_{x}-q_{x}|,$ (34)

where

$\sum_{x\in\Omega}p_{x}=\sum_{x\in\Omega}q_{x}=1.$ (35)

Let the stationary distribution on $\Omega$ be $\pi$ and the transition matrix
of the Markov chain on $\Omega$ be P. Also let

$d(t)=\underset{x\in\Omega}{max}[D(P^{t}(x,\cdot),\pi)].$ (36)

Then the mixing time $t_{mix}$ for some threshold value $\epsilon$ can be
defined as [11] [19]:

$t_{mix}(\epsilon)=min\\{t:d(t)\leq\epsilon\\}.$ (37)

The hitting time of a Markov chain is the expected number of time steps needed
to reach a certain state given an initial state. Let $p_{xx^{\prime}}$ be the
likelihood that state $x^{\prime}$ is reached for the first time after time
$t$ after starting in state $x$. Then hitting time $H_{xx^{\prime}}$ from
state $x$ to state $x^{\prime}$ can be found with [19]:

$H_{xx^{\prime}}=\sum_{t=0}^{\inf}p_{xx^{\prime}}(t).$ (38)

###  2.10 Quantum walks

Quantum walks are the quantum computing equivalent of a Markov chain. As
described previously, quantum computers have the property that they can be in
multiple quantum states at the same time. For quantum walks, this means that,
as long as one does not measure the qubits during the walk, the walker will
take all possible paths simultaneously until it is measured. This leads to
quantum walks having different properties compared to classical Markov chains.
One such is that quantum walks do not converge to a stationary distribution
[19].

There are multiple ways to quantize a classical Markov chain. In this thesis,
we will use two of the most common models, quantum walk with coins and
Szedgedy’s quantum walk.

####  2.10.1 Quantum walk with coins

This model, also called the coin model, consists of two quantum states and two
operators. The states are the position state, which represents the position of
the walker, and the coin state, which represents how the walker should move in
the next time step. The position state can be represented as a vector in
Hilbert space $\mathcal{H}_{P}$, while the coin state can be expressed as a
vector in the Hilbert space $\mathcal{H}_{C}$. Given this, the quantum space
representing the entire walker is
$\mathcal{H}=\mathcal{H}_{C}\otimes\mathcal{H}_{P}$. One simple quantum walk
is the walk on the infinite integer line. The computational basis for the
position state is then $\\{\ket{j}:j\in\mathbb{Z}\\}$, and the computational
basis for the coin state is $\\{\ket{0},\ket{1}\\}$, depending on whether the
walker goes to the right or to the left on the integer line [19].

The two operators in the model are the coin operator, $C$, and the shift
operator, $S$. The coin operator acts on $\mathcal{H}_{C}$ during each time
step and puts the walker in superposition. For the quantum walk on the integer
line this means that it will walk both to the left and to the right at the
same time. There are several different coin operators but a common one is the
Hadamard coin. The Hadamard coin is the most common choice for simple one-
dimensional quantum walks

$H=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\\ 1&-1\end{bmatrix}.$ (39)

Another common coin is the Grover coin. If the Hilbert space of the coin is
defined as $\mathcal{H}^{n}$, then the Grover coin matrix is defined as [19]:

$G=\begin{bmatrix}\frac{2}{n}-1&\frac{2}{n}&\ldots&\frac{2}{n}\\\
\frac{2}{n}&\frac{2}{n}-1&\ldots&\frac{2}{n}\\\ \vdots&\vdots&\ddots&\vdots\\\
\frac{2}{n}&\frac{2}{n}&\ldots&\frac{2}{n}-1\end{bmatrix}.$ (40)

The shift operator, $S$, will act on $\mathcal{H}_{P}$ and can also act on
$\mathcal{H}_{C}$. The shift operator will move the walker to the next
position, for the walk on a line the shift operator will act in the following
way:

$S\ket{0}\ket{j}=\ket{0}\ket{j+1},$ (41)

$S\ket{1}\ket{j}=\ket{1}\ket{j-1}.$ (42)

With the shift operator and the Hadamard coin operator defined as above, we
can represent one step of the quantum walk on the integer line as the unitary
operator $U$ given by

$U=SH.$ (43)

The same evolution operator $U$ can be represented with any coin $C$ as

$U=SC.$ (44)

We can also express the quantum state $\ket{\psi}$ after $t$ time steps can be
represented as

$\ket{\psi(t)}=U^{t}\ket{\psi(0)},$ (45)

where $\ket{\psi(0)}$ is the initial state [19].

The quantum space for any finite regular graph where it is possible to color
the edges of the graph using $d$ different colors can be generalized to
$\mathcal{H}=\mathcal{H}^{d}\otimes\mathcal{H}^{N}$. $\mathcal{H}^{N}$ is the
Hilbert space representing a graph with N states and $\mathcal{H}^{d}$
represents the coin space where d is the degree of each state node. The
computational basis will then be [19]

$\\{\ket{a,v},0\leq a\leq d-1,0\leq v\leq N-1\\}.$ (46)

The downside of using the quantum walk with coins is that it is most suitable
for regular graphs and can be quite difficult to generalize to other types of
graphs [10]. An alternative quantum walk model more convenient to use on other
types of graphs is reviewed in the following section.

####  2.10.2 Szedgedy’s quantum walk model

While a coined walk is a walk on the graph’s nodes, Szegedy’s walk is a walk
on the edges on a double-cover of the original graph. As described in section
2.9, a classical discrete-time random walk is represented by a transition
matrix $P$. For any $N$-vertex graph with $N\times N$ transition matrix $P$,
we can define the corresponding discrete-time quantum walk as a unitary
operation on the Hilbert space $\mathcal{H}^{N}\otimes\mathcal{H}^{N}$. Let
$P_{jk}$ define the probability of making a transition from state $j$ to $k$.
Before we define the walk, we define the normalized states

$\ket{\psi_{j}}:=\sum_{k=1}^{N}\sqrt{P_{kj}}\ket{j,k},\;j=1,...,N$ (47)

and the projection onto ${\ket{\psi_{j}}}:j=1,...,N$

$\Pi:=\sum_{j=1}^{N}\ket{\psi_{j}}\bra{\psi_{j}}.$ (48)

We also introduce the shift operator S:

$S:=\sum_{j,k=1}^{N}\ket{j,k}\bra{k,j}.$ (49)

With $S$ and $\Pi$ defined as above we can introduce one step of the discrete-
time quantum walk:

$U:=S(2\Pi-1),$ (50)

where $(2\Pi-1)$ is the reflection operator. We also define $t$ steps of the
walk as $U^{t}$ [10].

####  2.10.3 Equivalence of coined and Szegedy’s model

It is known that a coined walk with Grover coin is equivalent to Szegedy’s
quantum walk. For more details we refer to this article [28] by Thomas G.
Wong, where he also shows the equivalence between the operators in the two
models.

####  2.10.4 Hitting time

A hitting time for a (classical or quantum) random walk is the minimum number
of steps required to reach one or a set of marked states in the state space.
We define the quantum walk hitting time as the number of steps needed to
maximize the probability to collapse to one of the marked states. For hitting
time, quantum walks provide a quadratic speed-up compared to its classical
counterpart [4].

###  2.11 Quantum walk search algorithm

The quantum walk search algorithm solves the problem of finding marked
vertices in a graph by a quantum walk. That is, we mark some set of vertices
$|M|$, start at an arbitrary node in the graph and move according to the walk
until we find the marked nodes. This explanation of the algorithm is based on
de Wolf’s lecture notes [27], which builds on Santa’s paper [23] that presents
a slightly simplified version of the MNRS algorithm [13]. The basis states in
the quantum walk search algorithm have two registers, one corresponding to the
current node and the other corresponding to the previous node. That is, the
basis states corresponds to the edges in the graph. We denote the quantum walk
based on the classical Markov chain with transition matrix $P$ by the unitary
operation $W(P)$ on $\mathcal{H}$. We also define
$\ket{p_{x}}=\sum_{y}\sqrt{P_{xy}}\ket{y}$ as the uniform superposition over
the node $x$’s neighbors. Let $\ket{x}\ket{y}$ be a basis state. We define the
basis state $\ket{x}\ket{y}$ as “good” if $x$ is a marked node. Otherwise, we
refer to it as “bad”. We now introduce “good” and “bad” states:

$\ket{G}=\frac{1}{\sqrt{|M|}}\sum_{x\in
M}\ket{x}\ket{p_{x}},\;\ket{B}=\frac{1}{\sqrt{N-|M|}}\sum_{x\notin
M}\ket{x}\ket{p_{x}},$ (51)

which are the superpositions over good and bad basis states. Next, let us
define $\epsilon=|M|/N$ and $\theta=\arcsin(\sqrt{\epsilon})$.

In short, the algorithm consists of three steps:

[enumerate] Set up the initial state
$\ket{U}=\frac{1}{\sqrt{N}}\sum_{x}\ket{x}\ket{p_{x}}=\sin{\theta}\ket{G}+\cos{\theta}\ket{B}$,
a uniform superposition over all edges Repeat $O(1/\sqrt{\epsilon})$ times:
Reflect through $\ket{B}$ Reflect through $\ket{U}$ Perform a measurement in
the computational basis

Step $1$ is easily implemented with Hadamard gates. The reflection through
$\ket{B}$ can be implemented with a phase oracle that shifts the phase of $x$
if $x$ is in the first register, and leaves the circuit unchanged otherwise.

Step 2(b) is equivalent to finding a unitary $R(P)$ that performs the
following mapping:

$\displaystyle\ket{U}$ $\displaystyle\mapsto\ket{U},\>\text{and}$ (52)
$\displaystyle\ket{\psi}$
$\displaystyle\mapsto-\ket{\psi},\>\forall\ket{\psi}\text{in the span of
eigenvectors of $W(P)$ that are orthogonal to $\ket{U}$}$ (53)

To find this operator we apply phase estimation on $W(P)$. Above we defined
$W(P)$ as the evolution operator for the random walk. As we saw in section
2.10.1, this is a unitary operator. From this follows that the eigenvalues of
$W(P)$ have norm $1$. Because of this, we can write the eigenvalues of $W(P)$
on the form $e^{\pm 2i\theta_{j}}$. The unitary $W(P)$ has one eigenvector
with corresponding eigenvalue $1$, which is $\ket{U}$. This is given by
$\theta_{1}=0$. $R(P)$ will find this vector $\ket{U}$ by adding a register
with ancilla qubits and perform phase estimation with precision
$O(1/\sqrt{\delta})$, where $\delta$ is the spectral gap of $P$. To do this,
we need to apply $W(P)$ $O(1/\sqrt{\delta})$ times. Let $\ket{w}$ be an
eigenvector of $W(P)$ with eigenvalue $e^{\pm 2i\theta_{j}}$ and assume that
$\tilde{\theta_{j}}$ is the best approximation to $\theta_{j}$ given by the
phase estimation. The operation $R(P)$ that performs the mappings in (52) and
(53) for $\ket{w}$ is given by [27]

$\ket{w}\ket{0}\mapsto\ket{w}\ket{\tilde{\theta_{j}}}\mapsto(-1)^{|\tilde{\theta_{j}}\neq
0|}\ket{w}\ket{\tilde{\theta_{j}}}\mapsto(-1)^{|\tilde{\theta_{j}}\neq
0|}\ket{w}\ket{0}.$ (54)

The hitting time is the number of iterations of step 2 required to maximize
the probability that the circuit collapses to one of the marked states, and is
a central part in this project. We will compare this theoretical value,
$O(1/\sqrt{\epsilon})$, to the results we get when we run the algorithm for a
few different graphs.

##  3 Method

###  3.1 Implementation of Grover coin

The Grover coin is a crucial part of many of the walks we present below. The
implementation consists of Hadamard- and NOT gates along with a controlled-Z
gate. Figure 9 shows the implementation of a Grover coin of an arbitrary size
$n$. When we henceforth discuss the Grover coin implementation, this is what
we refer to.

Figure 9: Implementation an of $n$-qubit Grover coin.

###  3.2 Coined quantum walks

####  3.2.1 Hypercube

A hypercube is the $n$-dimensional counterpart of the $3$-dimensional cube.
All nodes have degree $n$, and the hypercube has a total of $N=2^{n}$ nodes. A
$4$-dimensional hypercube is shown in Figure 10.

Figure 10: A 4-dimensional hypercube graph with 16 nodes.

We can represent the nodes in a hypercube graph by $n$-tuples of binary
numbers. The binary representation of the neighbors of a node will differ by
only one binary number. For example, in the 4-dimensional hypercube, the
neighbors to $0000$ are $0001$, $0010$, $0100$, and $1000$. Thus a node is
connected to all nodes to which the Hamming distance is 1 [19]. The edges are
also labeled. Two neighboring nodes that differ in the a:th bit are connected
by the edge labeled $a$.

The Hilbert space representing a coined quantum walk on the hypercube is
$\mathcal{H}=\mathcal{H}^{n}\otimes\mathcal{H}^{2^{n}}$, where
$\mathcal{H}^{n}$ denotes the coin space and $\mathcal{H}^{2^{n}}$ the
walker’s position. The computational basis is

$\big{\\{}\ket{a,\vec{v}},0\leq a\leq
n-1,\vec{v}\in\\{(00...00),(00...01),.....,(11...11)\\}\big{\\}}.$ (55)

The value of the coin computational basis $a$, which is associated with edge
$a$, decides the direction to move. If the $a=0$, the walker will go to the
node where the first binary value differs from the current node. If $a=1$, the
walker will move to the node in which the second value differs from the
current, et cetera. Let $\vec{e}_{a}$ be an n-tuple where all binary values,
except the value with index $a$, are $0$. Then the shift operator $S$ moves
the walker from the state $\ket{a}\ket{\vec{v}}$ to
$\ket{a}\ket{\vec{v}\oplus\vec{e}_{a}}$ [19]:

$S\ket{a}\ket{\vec{v}}=\ket{a}\ket{\vec{v}\oplus\vec{e}_{a}}.$ (56)

We use the Grover coin, $G$, for this walk, and thus the evolution operator is

$U=SG.$ (57)

The implementation of the quantum walk on an $n$-dimensional hypercube is
shown in Figure 11.

Figure 11: Implementation of one step of the quantum walk with Grover coin on
an $n$-dimensional hypercube. $2^{n}$ nodes.

####  3.2.2 2-dimensional lattice with boundary conditions

A 2-dimensional lattice graph with periodic boundary conditions has the form
of a torus as we see in Figure 12.

Figure 12: 2-dimensional lattice with periodic boundary conditions. $8\times
8$ nodes.

The 2-dimensional lattice graph has a total of $\sqrt{N}\times\sqrt{N}$ nodes,
and the walker can move in either the $x$-direction or the $y$-direction. By
taking $\sqrt{N}$ steps in $x-$ or $y$-direction, the walker ends up in its
initial position. We define the coin space by $\ket{d,s}$, where $d$ decides
in what direction, $x$ or $y$, the walker should move, and $s$ decides whether
it should increase or decrease. The position space is represented by
$\ket{x,y}$ [19]. The computational basis for the entire quantum walk is

$\\{\ket{d,s,x,y},d,s\in\\{0,1\\},0\leq x,y\leq\sqrt{N}-1\\}.$ (58)

There is also a shift operator, $S$, that operates as follows:

$S\ket{d,s}\ket{x,y}=\ket{d,s\oplus
1}\ket{x+(-1)^{s}\delta_{d0},y+(-1)^{s}\delta_{d1}}.$ (59)

If $d=0$ and $s=0$, $y$ is left unchanged and $x$ is increased by one after
the application of $S$. If $x$ is changed, $y$ is left unchanged, and vice
versa. We can also see that the shift operator changes the coin state so that
$s$ gets inverted: $\ket{d,s\oplus 1}$. This increases the speed for searching
algorithms for this graph [19]. We implement the walk with a Grover coin, so
the evolution operator is

$U=SG.$ (60)

Figure 13 shows the implementation of a quantum walk on a 2-dimensional
$\sqrt{N}\times\sqrt{N}$ graph.

Figure 13: 2-dimensional lattice implementation for one step with Grover coin.
$\sqrt{N}\times\sqrt{N}$ nodes.

####  3.2.3 Complete bipartite graph

Figure 14 shows a complete bipartite graph with a total of 8 nodes, 4 in each
set. We implement the quantum walk on bipartite graphs with the same number of
nodes in both sets. There is a total of $N$ nodes, and each node is connected
to $\frac{N}{2}$ neighbors. The computational basis for this walk is

$\\{\ket{c,j},0\leq c\leq\frac{N}{2}-1,0\leq j\leq N-1\\}.$ (61)

Figure 14: Complete bipartite graph with 8 nodes.

The nodes in the graph are numbered such that all nodes belonging to the same
set will start with the same binary number. For example, in the complete
bipartite graph in Figure 14, the nodes on the left will have the binary
representations $000$, $001$, $010$, $011$ and belong to the same set.
Similarly, the nodes to the right belong to the same set and have the labels
$100$, $101$, $110$, $111$. If $2^{n}=N$ and $j_{0}j_{1}....j_{n-1}$ is the
binary representation of $j$, where
$j=2^{n-1}j_{0}+2^{n-2}j_{1}+....+2^{0}j_{n}$, and similarly
$c_{0}c_{1}..c_{n-2}$ is the binary representation of $c$, then the shift
operator will act in the following way:

$S\ket{c}\ket{j}=\ket{j_{1}j_{2}....j_{n-1}}\ket{(j_{0}\oplus
1)c_{0}c_{1}...c_{n-2}}.$ (62)

The shift operator swaps the coin space with the position space for all qubits
except for the position qubit $j_{0}$, which flips. Figure 15 shows an
implementation of the quantum walk on a complete bipartite graph with $N$
nodes. We implement the walk with a Grover coin, so the evolution operator is
$U=SG$.

Figure 15: Implementation of quantum walk on complete bipartite graph with $N$
nodes.

####  3.2.4 Complete graph

Here we present the implementation of a coined quantum walk on a complete
graph with self loops. Figure 16 shows a complete graph with 8 nodes. In a
complete graph with $N$ nodes, every node has $N$ neighbors, itself included.
The computational basis for the walk is

$\\{\ket{c,j},0\leq c\leq N-1,0\leq j\leq N-1\\}.$ (63)

The shift operator swaps the coin qubit values with the position qubit values,
so it acts in the following way:

$S\ket{c}\ket{j}=\ket{j}\ket{c}.$ (64)

Figure 16: Complete graph with 8 nodes.

Figure 17 shows an implementation of the walk on a complete graph with $N$
nodes using a Grover coin. The evolution operator for the walk is $U=SG$.

Figure 17: Implementation of quantum walk on complete graph with $N$ nodes.

###  3.3 Implementation of quantum walk search algorithm

This quantum walk search algorithm, which we introduced in section 2.11, makes
it possible to find a marked set of nodes in $O(1/\sqrt{\epsilon})$ steps,
$\epsilon=|M|/N$, where $M$ is the set of marked nodes and $N$ is the total
number of nodes. This algorithm is originally used with Szegedy’s quantum
walk, where two node registers are used to represent the quantum state.
However, a coined walk with Grover coin is equivalent to Szegedy’s quantum
walk, and its implementation is usually less complicated. Therefore, we chose
to implement the algorithm with coined walks.

We achieve step 1, a uniform superposition over all edges, by applying
Hadamard gates to the node qubits and the coin qubits. For step 2(a), we
implement a phase oracle. The implementation of step 2(b) is shown in Figure
18. This step consists of a phase estimation followed by marking all quantum
states where $\theta\neq 0$. We do this by rotating an ancilla qubit. In the
last part of this step, we reverse the phase estimation. The QWALK gate in
this implementation is one step of a quantum walk, which is described in the
previous sections (3.2.1, 3.2.2, 3.2.3, 3.2.4). The number of theta qubits
depends on the precision of $\theta$. Figure 19 shows the complete quantum
walk search algorithm.

Figure 18: Step 2(b) of the quantum walk search algorithm. A phase estimation
followed by marking an ancilla qubit if $\theta\neq 0$ and a reversed phase
estimation. Figure 19: Complete implementation of quantum walk search
algorithm.

##  4 Result

This section presents the experimental results of the quantum hitting times
for 4-dimensional hypercube, 2-dimensional lattice, complete bipartite graph,
and complete graph. We have implemented the quantum walk search algorithm as
we showed in section 3.3 in Qiskit on a noise-free simulator and a simulator
with the noise model of the Melbourne computer. The state vector plots show
the state vectors in iterations 1-4 in the noise-free simulator. We also show
the measurement outputs for both the noise-free and the noisy simulator and
compare their results.

###  4.1 4-dimensional hypercube

Figure 20 below shows the state vector simulations for the 4-dimensional
hypercube with 16 nodes in the first four iterations on a noise-free simulator
in Qiskit. Initially, the states are in superposition, and we have marked
state $1011$. We see that the probability that the circuit collapses to state
$1011$ increases until the third iteration, where it reaches the maximum
probability before it starts to decrease again. Thus, the hitting time for the
graph is $3$. Figure 21 shows the result from running the full algorithm on a
noise-free simulator, followed by a measurement after 3 iterations. As we see
in the figure, the circuit collapses to the marked state a significant
majority of the times, over $93\%$.

Figure 20: State vectors for the quantum walk search algorithm on a
4-dimensional hypercube implemented on a noise-free simulator. 1011 is marked.
Figure 21: Measurement of quantum walk search algorithm implemented on a
noise-free simulator for a 4-dimensional hypercube after 3 iterations with
node 1011 marked. The circuit collapses to the marked node $93.2\%$ of the
times.

Figure 22 shows the measurement output after running the same program on a
noisy quantum simulator. Again, we have marked node 1011. As we see in the
figure, the circuit does not collapse to the marked node most of the time; it
is not even the node with the highest output probability. In the noisy
simulation, the marked node is the output only $3.2\%$ of the times, compared
to the noise-free circuit where the circuit collapsed to the marked node
$93.2\%$ of the times. These results illustrate the extent to which noise
influences the behavior of the algorithm.

Figure 22: Measurement of quantum walk search algorithm for a 4-dimensional
hypercube graph with 16 nodes after 3 iterations with node 1011 marked. The
circuit is implemented on the fake Melbourne simulator that simulates the
noise of the real Melbourne quantum computer. The circuit collapses to the
marked node $3.2\%$ of the times.

###  4.2 2-dimensional lattice

For the 2-dimensional lattice with 16 nodes and one marked node ($1011$), the
hitting time is 3. We can see this in the state vector plots from the noise-
free simulator presented in Figure 23, where the maximum probability that the
circuit collapse to $1011$ occurs in the third iteration. Figure 24 shows the
distribution of the result after 3 iterations of the algorithm for 1024
executions without noise. In $93.1\%$ of the runs, the circuit collapses to
the marked state.

Figure 23: Noise-free state vectors for the 2-dimensional lattice. 1011 is
marked.  Figure 24: Measurement of quantum walk search algorithm for a
2-dimensional lattice after three iterations with node 1011 marked. The
circuit collapses to the marked node $93.1\%$ of the times and the program was
executed on a simulator without noise.

Figure 25 shows the output of same implementation executed on the fake
Melbourne simulator. Here, the circuit collapses to the marked node the least
number of times.

Figure 25: Measurement of quantum walk search algorithm for a 2-dimensional
lattice graph with 16 nodes after three iterations with node 1011 marked. This
simulation was done on the fake Melbourne simulator to simulate a real quantum
computer’s noise when running this circuit. The circuit collapses to the
marked node $2.4\%$ of the times.

###  4.3 Complete bipartite graph

When running the quantum walk search algorithm for the complete bipartite
graph, we marked state $011$. Figure 26 shows the noise-free state vectors for
the first four iterations. As we see in the figure, the circuit collapses to
the marked state with the highest probability after the second iteration, and
we conclude that the hitting time is 2. In Figure 26, we have run the
algorithm on the same simulator with two iterations 1024 times, and it
collapses to state $011$ $94.5\%$ of the times.

Figure 26: Quantum walk search algorithm state vector for a complete bipartite
graph with node 011 marked. Executed on noise-free simulator. Figure 27:
Measurement of quantum walk search algorithm for a complete bipartite graph
with 8 nodes after 2 iterations on noise-free simulator with node 011 marked.
The circuit collapses to the marked node $94.5\%$ of the times.

We also implement the algorithm on a simulator with the fake Melbourne
backend. The measurement output after 2 iterations after marking node 011 is
shown in Figure 28. Compared to the noise-free simulator, where the circuit
collapsed to the marked node $94.5\%$ of the times, the same percentage is
only $10.4\%$ on the noisy device.

Figure 28: Measurement of quantum walk search algorithm for a complete
bipartite graph with 8 nodes after 2 iterations with node 011 marked on fake
Melbourne simulator. The circuit collapses to the marked node $10.4\%$ of the
times.

###  4.4 Complete graph

In Figure 29 we see the state vectors for the complete graph with 8 nodes and
two marked nodes, $1011$ and $1111$. With the same logic as above, we conclude
that the hitting time is 2.

Figure 29: Noise-free state vector simulations for a complete graph with 16
nodes. 1011 and 1111 is marked.

We see the final, noise-free output of the algorithm after two iterations in
Figure 30. The circuit collapses to state $1011$ $49.2\%$ of the times and to
state $1111$ $45.3\%$ of the times. That means that we end up in a marked
state in $94.5\%$ of the executions. Figure 31 shows the output from a noisy
simulation. Here, the circuit collapses to one of the marked nodes $6.5\%$ of
the times in total.

Figure 30: Measurement of quantum walk search algorithm for a complete graph
with 16 nodes after 2 iterations with two nodes, 1011 and 1111, marked. The
circuit collapses to a marked node $94.5\%$ of the times.  Figure 31:
Measurement of the quantum walk search algorithm for a complete graph with 16
nodes after 2 iterations with nodes 1011 and 1111 marked. This simulation was
done on the fake Melbourne simulator to simulate the noise a real quantum
computer would have when running this circuit. The circuit collapses to 1011
and 1111 $4.4\%$ and $2.1\%$ of the times respectively.

##  5 Discussion

The number of iterations we needed to find the marked nodes for both the state
vector simulations and the noise-free quantum computer simulations matches the
theoretical values, which, for all of the graphs, is $O(1/\sqrt{\epsilon})$.
$\epsilon$ is defined as $\epsilon=|M|/N$, where $M$ is the set of marked
nodes and $N$ the size of the graph. For the simulations of complete- and
complete bipartite graphs, this theoretical number was
$O(1/\sqrt{\epsilon})\approx O(2.8)$. In the simulations without noise, we
could see that we needed two iterations to maximize the probability of
returning the marked nodes for both of these graphs. This coincides well with
the theoretical number. For the 4-dimensional hypercube and the 2-dimensional
lattice, the theoretical number was $O(1/\sqrt{\epsilon})=O(4)$, and both of
these graphs needed three iterations to find the marked nodes. As expected,
the complete graph with two marked nodes and the complete bipartite graph with
half the total nodes compared to all the other graphs needed a smaller number
of iterations than the two other graphs, which had one marked node and a total
of 16 nodes. When increasing the number of marked nodes or decreasing the
number of total nodes, we expected the number of iterations to decrease, which
our result showed. However, these results are from a noise-free simulator,
which does not reflect the result we would get on an actual quantum device.

To understand how the quantum walk algorithm implementation would run on
actual quantum computers, we also used simulations with noise. These results
differed vastly from both the theoretical number of iterations and the results
from the ideal, noise-free quantum computer. The output from simulating with
noise did not have a high probability of returning the marked nodes; for most
of the graphs, the percentage of times it found the marked nodes were much
smaller than in the simulation without noise. Not only was it smaller than in
the noise-free simulation, but it would also find an unmarked node most of the
time. As discussed in section 2.7, the error rate from just using a single
gate is quite large. When using as many gates as required in the quantum walk
search algorithm, this error will be so immense that the output is essentially
worthless. The large number of gates is not only due to the size of the
algorithm, but also because the circuit will be transpiled to only basis
gates, resulting in an even larger circuit. Combined, this makes it impossible
to get a usable output when running this algorithm on a real quantum computer.

We attempted to run these implementations on the real IBM Melbourne quantum
computer. However, there is a limit for the circuit’s execution time, and our
transpiled circuit became too deep. This resulted in an exceeded time limit,
and we could therefore not run the algorithm on the quantum device.

We also made some attempts to make the algorithm implementation hardware
aware. The goal was to decrease the size of the transpiled circuit. We mainly
focused on the hardware-aware implementation on the complete bipartite graph
implementation since this graph had the smallest amount of qubits in the
circuit and contained the least number of gates of the four implementations.
The controlled QWALK gate was the main reason why the transpiled circuit was
too deep; it was the sequence that used most multi-qubit gates. Most of these
were a result of making the QWALK gate controlled.

As mentioned previously, two qubits can only interact with each other if they
are directly connected. Since the Melbourne architecture allows a qubit to be
directly connected to at most three other qubits, we cannot place all qubit
that interacts via multi-qubit gates alongside each other. Therefore, we set
the qubits that had the most interactions close, which reduced the number of
swap gates in the transpiled circuit. In total, we succeeded in decreasing the
QWALK gate by $12\%$. However, this was not enough to make it executable on
IBM’s Melbourne computer. The main issue with the transpiled circuit was not
the use of swap gates to position the qubits in the correct position; it was
to transpile the circuit into basis gates. Too many basis gates were needed to
represent the original circuit, and this is something that we cannot solve by
adapting the circuit to the qubit architecture.

##  6 Recommendation

Since quantum computing is very far from ideal and suffers from much noise,
one of the main improvements is to improve the hardware. As we have seen when
running the implementation on a noisy simulator, the results would have been
useless even if we managed to implement the algorithm on an actual quantum
device. For quantum computers to be usable in practice, the noise must
decrease drastically. One other crucial thing is to increase the number of
qubits in the quantum computer to allow for even more extensive computations.
There are also future improvements to the implementation of the quantum walk
search algorithm, such as continuing to make it hardware-aware. We tried to
make a subset of the implementation hardware-aware, but the next step is to do
this with the complete implementation. As mentioned previously, the main issue
was how the circuit was transpiled into the basis gates. One way of improving
this might be to improve the algorithm that creates the transpiled circuit
from the implemented circuits. One other way might be to manually implement
the quantum walk search algorithm using these basis gates only. However, the
most significant limitation of quantum computing today is the hardware, so
continuing to work on these quantum devices and improving them is crucial for
the future of quantum computing.

Another extension is to implement the quantum walk search algorithm with new
types of graphs. This would require creating circuits for the new quantum
walks. Also, the algorithm could be implemented with Szegedy’s quantum walks,
something that would also allow for irregular graphs.

##  7 Conclusions

In this paper, we implemented the quantum walk search algorithm. The
implementation was done with four different regular graphs; a 4-dimensional
hypercube graph, a 2-dimensional lattice graph, a complete bipartite graph,
and a complete graph. We implemented the walks with a Grover coin, something
that is equivalent to Szegedy’s quantum walk. We executed the quantum walk
search algorithm on both a quantum simulator without noise and a quantum
simulator with noise. The result from running it on the simulator without
noise matched the theoretical result, but when running it on the simulator
with noise, this was not the case. This was caused by the error from using the
gates, which increases when we increase the number of gates in the circuit.
There were attempts to run the implementation on a real quantum computer;
however, this was not possible since the transpiled circuits were too deep and
required too long execution time. Although it is possible to implement the
quantum search algorithm, which for an ideal quantum computer without noise
will return the expected result, it is today impossible to run it on a real
quantum computer and get a proper output. The error in the output will be too
large, which makes the output unusable. The usefulness of implementing the
quantum walk search algorithm will come first when quantum computers with less
noise exist.

##  Appendix A Quantum gates

###  A.1 Single qubit gates

In this section, we present gates that operate on one qubit.

####  A.1.1 NOT gate

The NOT gate, or X gate, inverts a qubit; $\ket{0}$ becomes $\ket{1}$ and
$\ket{1}$ becomes $\ket{0}$.

Gate and matrix:

$U_{\text{NOT}}=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$ (65)

####  A.1.2 Hadamard gate

The Hadamard gate puts a qubit into equal superposition, i.e., after the gate
has been applied, the probability that the qubit collapses to $\ket{0}$ or
$\ket{1}$ are $50\%$ each.

Gate and matrix:

$U_{\text{H}}=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\\ 1&-1\end{bmatrix}$ (66)

####  A.1.3 Z gate

A Z gate shifts the phase of a qubit by $\pi$. It does not change state
$\ket{0}$ but maps $\ket{1}$ to -$\ket{1}$.

Gate and matrix:

$U_{\text{Z}}=\begin{bmatrix}1&0\\\ 0&-1\end{bmatrix}$ (67)

####  A.1.4 I gate

An I gate, or identity gate, leaves the qubit unaffected. That is, the qubit
state is the same both before and after the gate.

Gate and matrix:

$U_{\text{I}}=\ \begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$ (68)

####  A.1.5 $R_{Z}$ gate

The $R_{Z}$ gate, also referred to as $R_{\phi}$ gate, shifts the phase of
qubits in state $\ket{1}$. The rotation angle $\phi$ is given as a parameter
in the input and has to be a real number.

Gate and matrix:

$U_{\phi}=\ \begin{bmatrix}1&0\\\ 0&e^{i\phi}\end{bmatrix}$ (69)

####  A.1.6 $\sqrt{X}$ gate

$\sqrt{X}$, or $SX$ gate, is the square root of the NOT gate.

Gate and matrix:

$U_{\sqrt{X}}=\frac{1}{2}\begin{bmatrix}1+i&1-i\\\ 1-i&1+i\end{bmatrix}$ (70)

###  A.2 Multi-qubit gates

Below we introduce gates that act on two or more qubits.

####  A.2.1 CNOT gate

A CNOT gate, or controlled-NOT gate, operates on two qubits; one control qubit
and one target. The gate is conditional; it applies a NOT gate on the target
qubit if the control is $\ket{1}$. Otherwise, both qubits are left unchanged.

Gate and matrix:

$U_{\text{CNOT}}=\ \begin{bmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&0&1\\\
0&0&1&0\end{bmatrix}$ (71)

####  A.2.2 $n$-bit Toffoli gate

We can generalize the idea of the CNOT gate to a gate with multiple control
qubits. We call such a gate an $n$-bit Toffoli gate, and it has $n-1$ control
qubits and one target. A $2$-bit Toffoli gate is normally referred to as just
Toffoli gate, or CCNOT gate.

Gate and matrix:

$U_{\text{$n$-Toffoli}}=\begin{bmatrix}1&0&0&\dots&0&0\\\ 0&1&0&\dots&0&0\\\
0&0&\ddots&\dots&0&0\\\ \vdots&\vdots&\vdots&1&0&0\\\
\vdots&\vdots&\vdots&\dots&0&1\\\ 0&0&0&0&1&0\end{bmatrix}$ (72)

####  A.2.3 SWAP gate

A SWAP gate exchanges the values between two qubits so that the first qubit
gets the state of the second and the other way around.

Gate and matrix:

$U_{\text{SWAP}}=\ \begin{bmatrix}1&0&0&0\\\ 0&0&1&0\\\ 0&1&0&0\\\
0&0&0&1\end{bmatrix}$ (73)

####  A.2.4 Controlled-Z gate

Similarly to a controlled-NOT gate, we can construct a controlled-Z gate with
either one or multiple control qubits and one target. Such a gate applies a
Z-gate to the target if all control qubits are $\ket{1}$. The figures below
show the matrix and gate for a controlled-Z gate with one control qubit, but
we can extend it in the same way as we did with the CNOT gate in section
A.2.2. There are two ways to denote the control-Z gate, and both are shown
below.

Gate and matrix:

$U_{\text{controlled-Z}}=\ \begin{bmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\
0&0&0&-1\end{bmatrix}$ (74)

####  A.2.5 $\ket{0}$ as control qubit

In all control gates we have presented above, we apply a gate to the target
qubit if all control qubits are in state $\ket{1}$. However, we might want to
operate on the target qubits if the control qubits are $\ket{0}$. We denote
this by a white dot on the control qubits. The figure below shows this
notation for a CNOT gate.

Figure 32: Gate that applies a NOT gate on the target if the control is
$\ket{0}$.

## References

  * [1] A. Ambainis  “Quantum walk algorithm for element distinctness”  In _45th Annual IEEE Symposium on Foundations of Computer Science_ , 2004, pp. 22–31  DOI: 10.1109/FOCS.2004.54
  * [2] Frank Arute et al.  “Quantum Supremacy using a Programmable Superconducting Processor”  In _Nature_ 574, 2019, pp. 505–510  URL: https://www.nature.com/articles/s41586-019-1666-5
  * [3] Abraham Asfaw et al.  “Learn Quantum Computation Using Qiskit”, 2020  URL: http://community.qiskit.org/textbook
  * [4] Chen-Fu Chiang and Guillermo Gomez  “Hitting time of quantum walks with perturbation”  In _Quantum Information Processing_ 12.1 Springer ScienceBusiness Media LLC, 2012, pp. 217–228  DOI: 10.1007/s11128-012-0368-9
  * [5] “Circuits with IBM’s Quantum Simulators” Accessed: 2021-04-17, https://www.ibm.com/quantum-computing/simulator/
  * [6] “Device backend noise model simulations” Accessed: 2021-04-26, https://qiskit.org/documentation/tutorials/simulators/2_device_noise_simulation.html
  * [7] B.. Douglas and J.. Wang  “Efficient quantum circuit implementation of quantum walks”  In _Phys. Rev. A_ 79 American Physical Society, 2009, pp. 052335  DOI: 10.1103/PhysRevA.79.052335
  * [8] Lov K. Grover  “A Fast Quantum Mechanical Algorithm for Database Search”  In _Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing_ , STOC ’96  Philadelphia, Pennsylvania, USA: Association for Computing Machinery, 1996, pp. 212–219  DOI: 10.1145/237814.237866
  * [9] “IBM’s Roadmap For Scaling Quantum Technology” Accessed: 2021-04-26, https://www.ibm.com/blogs/research/2020/09/ibm-quantum-roadmap/
  * [10] Markus G. Kuhn  “Some Introductory Notes on Quantum Computing”  Computer Laboratory University of Cambridge, 2000
  * [11] Zhongyang Li  “Mixing Time of Markov Chains for the 1–2 Model”  In _Journal of statistical physics_ 176.6, 2019, pp. 1526–1560
  * [12] T. Loke and J.B. Wang  “Efficient quantum circuits for Szegedy quantum walks”  In _Annals of Physics_ 382, 2017, pp. 64–84  DOI: https://doi.org/10.1016/j.aop.2017.04.006
  * [13] F. Magniez, A. Nayak, J. Roland and M. Santha  “Search via quantum walk”  In _SIAM Journal on Computing_ 40.1, 2011, pp. 142–164
  * [14] Nihal Mehta  “Quantum Computing”  Pragmatic Bookshelf, 2020
  * [15] Michael A. Nielsen and Isaac L. Chuang  “Quantum Computation and Quantum Information”  Cambridge University Press, 2000
  * [16] Siyuan Niu, Adrien Suau, Gabriel Staffelbach and Aida Todri-Sanial  “A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era”  In _IEEE Transactions on Quantum Engineering_ 1 Institute of ElectricalElectronics Engineers (IEEE), 2020, pp. 1–14  DOI: 10.1109/tqe.2020.3026544
  * [17] G. Paparo, M. Mueller, F. Comellas and M. Martin-Delgado  “Quantum Google in a Complex Network”  In _Scientific Reports_ 3, 2013
  * [18] Giuseppe Paparo and M Martin-Delgado  “Google in a Quantum Network”  In _Scientific reports_ 2, 2012, pp. 444  DOI: 10.1038/srep00444
  * [19] Renato Portugal  “Quantum Walks and Search Algorithms”  New York, NY: Springer New York, 2013
  * [20] “Quantum computing” Accessed: 2021-04-26, https://www.chalmers.se/en/centres/wacqt/discover/Pages/Quantum-computing.aspx
  * [21] “Quantum Gates and Circuits”  In _Quantum Computing Explained_ John Wiley & Sons, Ltd, 2007, pp. 173–196  DOI: https://doi.org/10.1002/9780470181386.ch8
  * [22] “Quantum services” Accessed: 2021-04-23, https://quantum-computing.ibm.com/services?skip=0&systems=yours
  * [23] Miklos Santha  “Quantum Walk Based Search Algorithms”, 2008  DOI: 10.1007/978-3-540-79228-4_3
  * [24] Sarah Sheldon  “Quantum Computing with Noisy Qubits”  In _Frontiers of Engineering: Reports on Leading-Edge Engineering from the 2018 Symposium._ Washington, DC: The National Academies Press, 2019  DOI: 10.17226/25333
  * [25] Neil Shenvi, Julia Kempe and K. Whaley  “Quantum random-walk search algorithm”  In _Phys. Rev. A_ 67 American Physical Society, 2003, pp. 052307  DOI: 10.1103/PhysRevA.67.052307
  * [26] Peter W. Shor  “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”  In _SIAM J. Comput._ 26.5 USA: Society for IndustrialApplied Mathematics, 1997, pp. 1484–1509  DOI: 10.1137/S0097539795293172
  * [27] Ronald Wolf  “Quantum Computing: Lecture Notes”, 2021  arXiv:1907.09415 [quant-ph]
  * [28] Thomas G. Wong  “Equivalence of Szegedy’s and coined quantum walks”  In _Quantum Information Processing_ 16.9 Springer ScienceBusiness Media LLC, 2017  DOI: 10.1007/s11128-017-1667-y