Quantum Algorithms in Cybernetics
Doctoral Dissertation
Area: 5. Engineering

Professional area: 5.2. Electrical engineering, electronics and automation

Scientific specialty: Application of the principles and methods of cybernetics
in various fields of science

by
Petar Nikolaev Nikolov
At the Faculty of German Engineering and Business Administration
Technical University of Sofia

Advisor: Assoc. prof. Dr. Eng. Vassil Galabov Date of Submission: 28.02.2020

TU-Sofia - Technical University of Sofia www.tu-sofia.bg

Abstract

Quantum information theory and the quantum computing as the biggest part of
this scientific area, is one of the fast growing emerging technologies
nowadays. Quantum computers use the quantum mechanical effects like
superposition, entanglement and coherence to process information. The main
difference with the classical computer is that they process the information
probabilistically, while the classical signal processing is deterministic.
Quantum computers can handle two types of data - classical and quantum,
although the classical data need to be prepared and structured before being
processed. The quantum information finds patterns in the data by presenting
those as certain quantum mechanical states and executes basic quantum
routines.

In general a quantum algorithm can be applied on different hardware platforms
if it could be described as a quantum circuit. The circuit model for quantum
computation applies different quantum logic gates over a quantum register
which maps the initial register state to another desired state as a result.
The quantum computation ends with a measurement operation, which is also a
termination for the computational process.

The development of a new quantum algorithm requires the use of both existing
and newly constructed quantum gates. And it can be generalized into two main
tasks - constructing new quantum gates and procedure for solving the problem.
Having only two possible states, the binary homogeneous (the probability
distribution does not change over time) Markov process, makes it possible the
processing being executed on a quantum computer. The process’s states can be
represented by qubits, where the main challenge being the creation and tuning
of the quantum logic gates connecting these qubits.

A new method for simulation of a binary homogeneous Markov process using a
quantum computer was proposed. This new method allows using the distinguished
properties of the quantum mechanical systems - superposition, entanglement and
probability calculations. Implementation of an algorithm based on this method
requires the creation of a new quantum logic gate, which creates entangled
state between two qubits. This is a two-qubit logic gate and it must perform a
predefined rotation over the X-axis for the qubit that acts as a target, where
the rotation accurately represents the transient probabilities for a given
Markov process. This gate fires only when the control qubit is in state
$\ket{1}$. It is necessary to develop an algorithm, which uses the
distributions for the transient probabilities of the process in a simple and
intuitive way and then transforms those into X-axis offsets. The creation of a
quantum $C\sqrt[n]{X}$ gate using only the existing basic quantum logic gates
at the available cloud platforms is possible, although the hardware devices
are still too noisy, which results in a significant measurement error
increase. The IBM’s Yorktown ”bow-tie” back-end performs quite better than the
5-qubit T-shaped and the 14-qubit Melbourne quantum processors in terms of
quantum fidelity. The simulation of the binary homogeneous Markov process on a
real quantum processor gives best results on the Vigo and Yorktown (both
5-qubit) back-ends with Hellinger fidelity of near 0.82. The choice of the
right quantum circuit, based on the available hardware (topology, size, timing
properties), would be the approach for maximizing the fidelity.

###### Contents

  1. Acronyms
  2. 1 Review of the Problem
    1. 1.1 Solved and Unsolved Problems
      1. 1.1.1 Factorization
      2. 1.1.2 Quantum search
      3. 1.1.3 HHL
      4. 1.1.4 Quantum PCA
      5. 1.1.5 Quantum Boltzmann Machines
      6. 1.1.6 Input and output problem
      7. 1.1.7 Benchmark problem
    2. 1.2 Goals
    3. 1.3 Tasks
  3. 2 Analysis of the Review
    1. 2.1 Motivation
    2. 2.2 Quantum Computing
    3. 2.3 Markov Chains
    4. 2.4 Software Tools and Frameworks for Quantum Computing
    5. 2.5 Problem Description
  4. 3 Method and Algorithms
    1. 3.1 Method for quantum simulation of a binary homogeneous Markov process
    2. 3.2 Algorithm for determining the angle of rotation for a qubit over the X axis
    3. 3.3 Building a quantum logic gate C$\sqrt[n]{X}$
    4. 3.4 Algorithm for finding the complete set of possible paths for a stochastic process described by a binary homogeneous Markov model
  5. 4 Applications
    1. 4.1 Implementation of a quantum logic gate which rotates the qubit with custom angle over the X axis
    2. 4.2 Implementation of a controlled quantum logic gate which rotates the qubit with custom angle over the X axis
    3. 4.3 Development of a quantum circuit allowing modelling on a real quantum processor of any stochastic problem described by a binary homogeneous Markov model.
    4. 4.4 Development of an experimental quantum circuit, which to be implemented on both a high-performance quantum simulator and real quantum processors at IBM’s cloud service through the QISIKT software framework.
    5. 4.5 Conclusion
  6. 5 Experimental Verification
    1. 5.1 Implementation considerations
    2. 5.2 Verification and validation of $C\sqrt[n]{X}$ quantum logic gate
    3. 5.3 Results of quantum simulation of a binary homogeneous Markov process on various hardware back-ends
    4. 5.4 Analysis of the results
  7. 6 Scientific and Scientifically Applied Contributions
  8. A Appendix A
  9. B Appendix B

## Acronyms

AI |  Artificial Intelligence
---|---
IBM |  International Business Machines
CNOT |  Controlled-NOT
PCA |  Principal component analysis
QPE |  Quantum phase estimation
HHL |  Harrow, Hassidim, Lloyd. Quantum algorithm for solving linear systems of equations
QSVM |  Quantum support vector machine
VQE |  Vatiational-quantum-eigensolver
QAOA |  Quantum approximate optimization algorithm

###### List of Figures

  1. 1 Structure of the dissertation.
  2. 2 Graphical representation of the symbols for Hadamard, Pauli-X, CNOT and Phase-shift quantum logic gates in quantum circuits.
  3. 3 Required libraries, packages and modules in Python for building a quantum program.
  4. 4 Quantum experiment simulation on selected back-end and result extraction.
  5. 5 Hierarchical Tree structure showing the full set of possible paths for a binary homogeneous Markov process which is described as a quantum-mechanical system.
  6. 6 A binary homogeneous Markov process visualization using chain of qubits. The red arrow shows the entanglement direction (the beginning of the arrow is the control qubit and the end of the arrow is the target qubit). In every discrete moment of time the process is represented by a single qubit, which is in an entangled state with the next one. For a quantum simulation of a process with N number of discrete time steps, a quantum register with N qubits is required.
  7. 7 Quantum circuit for construction of a two-qubit quantum logic gate that does a controlled phase-shift over the Z axis for the target qubit.
  8. 8 Quantum circuit for construction of a two-qubit quantum logic gate that does a controlled phase-shift over the X axis for the target qubit.
  9. 9 Graphical representation of a quantum logic gate, which shifts the qubit over the X axis with custom angle in QISKIT framework.
  10. 10 Quantum circuit used for verification and validation of the $C\sqrt[n]{X}$ gate, where the gate will always fire.
  11. 11 Quantum circuit example for verification and validation of the $C\sqrt[n]{X}$ gate, where the gate will fire only 50% of the time.
  12. 12 Quantum circuit showing the initialization of the binary homogeneous Markov process.
  13. 13 Quantum circuit showing the repetitive unitary operation for the binary homogeneous Markov process.
  14. 14 Quantum circuit showing the schematic representation of an algorithm for quantum simulation of a binary homogeneous Markov process.
  15. 15 Quantum circuit showing the quantum simulation of a binary homogeneous Markov process with absorbing state in $\ket{0}$.
  16. 16 Configuration maps of quantum processors in the IBM cloud platform that have been subjected to experimental verification and validation. a) T-shape layout of the qubits used in Ourence, Vigo, London, Burlington, Essex processors. b) Diagram with bow-tie type used with the Yorktown processor. c) Directional ladder geometry diagram of Melbourne processor.
  17. 17 Quantum circuits for gate verification and validation.  a) Circuit in which the controlled qubit is $q_{1}$.  b) Circuit with inverted qubit functions: $q_{0}$ is the objective and $q_{1}$ is the control.
  18. 18 Results from the implementation of $C\sqrt[n]{X}$ quantum gate validation and verification circuits on a high-performance quantum simulator.  a) Results of circuit 17a.  b) Outcome of circuit 17b
  19. 19 Results from the implementation of $C\sqrt[n]{X}$ quantum gate validation and verification circuits on a real quantum processor Ourence.  a) Results of circuit 17a.  b) Results of circuit 17b
  20. 20  Results from the implementation of $C\sqrt[n]{X}$ quantum gate validation and verification circuits on a real quantum processor Vigo.  a) Results of circuit 17a.  b) Results of circuit 17b
  21. 21 Results from the implementation of $C\sqrt[n]{X}$ quantum gate validation and verification circuits on a real quantum processor London.  a) Results of circuit 17a.  b) Results of circuit 17b
  22. 22 Results from the implementation of $C\sqrt[n]{X}$ quantum gate validation and verification circuits on a real quantum processor Burlington.  a) Results of circuit 17a.  b) Results of circuit 17b
  23. 23 Results from the implementation of $C\sqrt[n]{X}$ quantum gate validation and verification circuits on a real quantum processor Essex.  a) Results of circuit 17a.  b) Results of circuit 17b
  24. 24 Results from the implementation of $C\sqrt[n]{X}$ quantum gate validation and verification circuits on a real quantum processor Yorktown.  a) Results of circuit 17a.  b) Results of circuit 17b
  25. 25 Results from the implementation of $C\sqrt[n]{X}$ quantum gate validation and verification circuits on a real quantum processor Melbourne.  a) Results of circuit 17a.  b) Results of circuit 17b
  26. 26 Quantum circuit for simulation of a binary homogeneous Markov process with absorbin state in $\ket{0}$ on a high-performance quantum simulator and real quantum processors in IBM cloud platform with CNOT gates directions {CX_21, CX_10} respectively.
  27. 27 Quantum circuit for simulation of a binary homogeneous Markov process with absorbing state in $\ket{0}$ on a high-performance quantum simulator and real quantum processors in IBM cloud platform with CNOT gates directions {CX_01, CX_12} respectively.
  28. 28 Results of the execution of quantum circuits for the simulation of a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a high-performance quantum simulator.  a) Results of circuit 26.  b) Outcome of circuit 27.
  29. 29 Results of the execution of quantum circuits for the simulation of a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a real quantum processor Ourence.  a) Results of circuit 26.  b) Outcome of circuit 27.
  30. 30 Results of the execution of quantum circuits for the simulation of a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a real quantum processor Vigo.  a) Results of circuit 26.  b) Outcome of circuit 27.
  31. 31 Results of the execution of quantum circuits for the simulation of a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a real quantum processor London.  a) Results of circuit 26.  b) Outcome of circuit 27.
  32. 32 Results of the execution of quantum circuits for the simulation of a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a real quantum processor Burlington.  a) Results of circuit 26.  b) Outcome of circuit 27.
  33. 33 Results of the execution of quantum circuits for the simulation of a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a real quantum processor Essex.  a) Results of circuit 26.  b) Outcome of circuit 27.
  34. 34 Results of the execution of quantum circuits for the simulation of a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a real quantum processor Yorktown.  a) Results of circuit 26.  b) Outcome of circuit 27.
  35. 35 Results of the execution of quantum circuits for the simulation of a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a real quantum processor Melbourne.  a) Results of circuit 26.  b) Outcome of circuit 27.
  36. 36 Hellinger fidelity calculated from the distance between the high-performance quantum simulator and various hardware backends in IBM cloud platform for the quantum circuits shown on figures 26 and 27.

###### List of Tables

  1. 1 Hellinger fidelity calculated from the distance between the high-performance quantum simulator and various hardware backends in IBM cloud platform for the quantum circuits shown on figures 26 and 27.

##  1 Review of the Problem

The first proposition for a quantum computer was made by Richard Feynman back
in 1981. He pointed out that simulating quantum-mechanical systems on
classical computers would be inefficient, so new type of computers must be
build - ”built of quantum mechanical elements which obey quantum mechanical
laws” (Feynman,, 1982).

The quantum computing is one of the fastest growing research areas in recent
years. The quantum computers are based on quantum mechanical physics laws and
they use unitary operations for handling quantum information usually described
as quantum logic gates. The quantum logic gates can be single-qubit gates and
multiple-qubit gates. The single-qubit gates execute controlled quantum
transitions from one quantum superposition to another. The multiple-qubit
gates create so-called entangled states, where they create dependencies
between more than one quantum systems (qubits) states, so that the state of
one system can not be described without knowing the state of the others.
Nowadays well-known fact is that classical computers can not fully simulate
the dynamics of a quantum system effectively. Every classical simulation (a
simulation executed on a classical computer) is exponentially slower than the
actual process’s dynamics.

The idea of the constantly growing scale of the problems which solution
requires and is only possible using quantum computers is very scary. The
available classical computer resources (hardware mostly) are not enough for
solving some of the most interesting problems in science today. Here the
quantum computers give hope - some of these problems would be solved
efficiently. However, this brings new problem - the algorithms. Quantum
algorithms as essential part of quantum computing, still not very advanced
scientific field, could be classified as algorithms based on Quantum Fourier
Transformation (based on the Shor’s factorization algorithm) and based on
Grover’s search algorithm. The Quantum Fourier Transform based algorithms are
exponentially faster than their classical equivalents, where the quantum
amplification based algorithms are ”only” quadratically more efficient.

The first applied quantum algorithm has been created by Peter Shor in 1994
(Shor,, 1997). With his algorithm though quantum interference he succeeded to
factorize prime number requiring only polynomial number of steps, while the
classical equivalent would require exponential number of steps.

###  1.1 Solved and Unsolved Problems

Classical computers work with bits, where each bit has a deterministic state -
0 or 1 at any moment of time. The fundamental quantum information-carrying
elements are qubits (physically it can be single atom, electron, photo on
superconducting circuit). 111Classification and analysis of the technological
clusters in quantum information theory has been made in author’s work
(Author’s publication iv).

The huge complexity (compared with the classical systems) of quantum-
mechanical systems comes when there needs to be given a full description of
highly entangled quantum states. One of the hardest challenges is to
distinguish which problems are quantum hard and which classically hard
(Jordan,, 2019; Montanaro,, 2016).

Why would quantum computers outperform the classical ones for high complexity
problems? (Preskill,, 2018)

  * •

Quantum algorithms for classical problems - these are problems known to be
hard to solve using classical computers, but quantum algorithms could perform
significantly more efficient. The best known example is factorization problem
for large integers (Shor,, 1997; Chuang et al.,, 1995).

  * •

Complexity theory arguments -these arguments are based on the fact that
quantum states have super-classical properties. If a quantum register is
measured, this is sampling from a correlated probability distribution, that
can’t be sampled efficiently by classical methods (Lund et al.,, 2017; Harrow
and Montanaro,, 2017)

  * •

Classical computers can not simulate quantum computers efficiently (Feynman,,
1982).

Richard Feynman also said: ”if you want to make a simulation of Nature you
better make it quantum mechanical, and by golly it’s a wonderful problem
because it doesn’t look so easy.” (Feynman,, 1982). Here we could start to
think why really quantum computing is hard, because simulating the Nature
isn’t really something possible nowadays on any classical computer. Building
quantum computers (Chuang and Yamamoto,, 1995) brings the contradiction
problem for the qubits - on one side we want them to be fully isolated from
the environment so there is no decoherence problem (Zeh,, 1970; Bacon,, 2003;
Lidar and Birgitta Whaley,, 2003; Zurek,, 2007; Zwirn,, 2016; Zurek,, 1982),
but on the other side we want to fully control from the outside these qubits
in the quantum systems and also to build highly entangled states.

The principle of quantum error correction could help scaling up the quantum
computers (Steane,, 1996; Gottesman,, 2010). The main idea of this principle
is that in order to protect a quantum system it should be encoded in a very
high entangled state (Preskill,, 2018).

####  1.1.1 Factorization

The problem of prime factorization is a problem in number theory. It is the
decomposition of large integer number to a product of small prime numbers.
Peter Shor introduces his algorithm for quantum factorization in 1994 (Shor,,
1994). Using quantum computers can speed-up dramatically the the task for
prime factorization. The fastest classical algorithm which solves this problem
is nearly exponential, while the quantum one is giving a solution in
polynomial time (Chuang et al.,, 1995).

This problem is a key point in modern cryptography because of its asymmetry
for the difficulty of factorization and how easy it is to verify the result.
Such an application widely used these days is the RSA (Rivest-Shamir-Adleman)
algorithm. It depends on the fact that prime factorization of large numbers
requires long time. The logic behind this algorithm is that there is so-called
public and private keys. The public key is a product of two large numbers and
the private key consists of these two large numbers. The public key is used to
encrypt the information, while the decryption is made by using the private
key. At the time when the algorithm was first introduced, the practicality of
the quantum computers was questionable because of the quantum decoherence
(Chuang et al.,, 1995; Zurek,, 1991).

The quantum algorithm for prime factorization uses one of the fundamental
properties of quantum systems - the coherence. The coherence describes the
correlation between several wave packets.

What is factoring?

The main part of the factoring algorithm is the period finding. If there is a
periodic function f, where f maps some numbers $\\{0,1,...,M-1\\}$ to some set
S, such that $\forall x$ , $f(x)=f(x+r)$. The task is to find the period r.
The number of the repetitions of the period is $M/r$. If this function is
considered on a single period, then f is 1-1: values are never repeated. This
is the first condition to the period finding: that f is 1-1 for each period.
The second condition is that r divides M. In order to solve the factoring
problem, the ${M\over r}>>r$ must be true ($M\gg r^{2}$).

How to find the periodic function and how hard is to solve the periodic
finding?

Let’s assume $M\approx 10^{1000}$ (1000 digits number) and $r\approx\sqrt{M}$
(500 digits number). The classical solution here is to pick random inputs
until the pattern is found. Here another question arises - how the pattern
looks like? There must be different numbers, for example x and y, where
$f(x)=f(y)$. But still this is not enough information, since these numbers
doesn’t contain any other information other that the function has the same
output for different input. At first look the count of the random inputs for
trial as input for the f function must be at least r. Here the birthday
paradox (Naccache et al.,, 2011) says that actually the $\sqrt{r}$ are enough
inputs until there is a collision. Still $\sqrt{r}\approx 250$ digits number,
which makes it impossible to find the collision classically.

What does the quantum algorithm do?

There is a quantum circuit which takes $\ket{x}$ and $\ket{0}$ as input and
outputs $\ket{x}$ and $\ket{f(x)}$. It does this in superposition - an uniform
superposition is set on the $\ket{x}s$ and the output of the circuit is
${1\over\sqrt{M}}\sum_{x=0}^{M-1}{\ket{x}\ket{f(x)}}$. The next step to do is
to measure the second register of the output: $\ket{f(x)}$, so the result will
be some random values which form some period (for example: arithmetic
progression). This superposition is the input for the next step, which is
Fourier sampling, and the multiples of the period can be found as non-zero
amplitudes in the superposition.

The result of Fourier sampling is: $\sqrt{r\over
M}\sum_{j=0}^{M-1}{\ket{jr}}$.

Figuring the $M\over r$ from the result is the greatest common divisor of all
random outputs. This task could be solved even using the Eucledian algorithm
(Stark,, 1970). And when M and $M\over r$ are known it is easy to find the r.

The algorithm could be divided in two parts (Beckman et al.,, 1996)

  1. 1.

The first part is the order finding problem, which could be implemented
classically.

  2. 2.

The second part is a quantum algorithm which solves the order finding problem:

    1. i

Initialize a quantum register of length k into $1\ket{0^{k}}$ state. Then
create an equal superposition of all k qubits using the Walsh-Hadamard
transformation. After this transformation there will be equal probability for
each one of the $2^{k}$ possible states for the register.

    2. ii

Construct the $f(x)$ function as quantum function and apply it to the
register. The result will be a superposition of k+n qubits.

${1\over\sqrt{2^{k}}}\sum_{x=0}^{2^{k}-1}{\ket{x,f(x)}}$

    3. iii

Apply the inverse Quantum Fourier transform to the input register $\ket{x}$:

$U_{QFT}(\ket{x})={1\over\sqrt{2^{k}0}}\sum_{y=0}^{2^{k}-1}{\omega^{xy}\ket{y}}$

this sum must be ordered according to the $f(x)=z$,
$x\in\\{0,1,...,2^{k}-1\\}$

       * •

$\omega=e^{2\pi i\over 2^{k}}$

       * •

r is the period of f

       * •

$x_{0}$ is the smallest

    4. iv

Perform a quantum measurement both on the input register and the output
register. y is the outcome from the input register and z is the outcome from
the output register. The probability of measuring the $\ket{y,z}$ state will
be:

$\mathbb{P}(\ket{y,z})={1\over{2^{2k}}}\left({\sin({{\pi
mry}\over{2^{k}}})\over{\sin({{\pi ry}\over{2^{k}}}})}\right)$

    5. v

Perform continued fraction expansion to find the appropriate period r.

  3. 3.

Check if the found solution for the period is a prime factor. If so, here is
the end.

  4. 4.

Otherwise, obtain more candidates for r.

  5. 5.

If no candidates satisfy the conditions to be the period of the function, then
return to step i.

Up to today, there are many available experimental realizations of this
algorithm (Lanyon et al.,, 2007), including the use of nuclear magnetic
resonance for the N = 15 with prime factors 3 and 5 (Vandersypen et al.,,
2001), N = 15 with Josephson phase qubit quantum processor (Lucero et al.,,
2012), N = 21 using recycling qubit instead of n-qubit control register which
recycles n times (Martín-López et al.,, 2012), N = 15 using photonic qubits
(Lu et al.,, 2007; Politi et al.,, 2009), using qutrits for factoring
(Bocharov et al.,, 2017), N=15,21,35 using the IBM Q (Amico et al.,, 2019), N
= 15 at room temperature (Johansson and Larsson,, 2017), scalable version of
the algorithm (Monz et al.,, 2016).

This is one of the largest research areas in the quantum information theory
and quantum computing with applied research in cryptography and number theory,
including accuracy, implementation research and bottlenecks investigation
(Markov and Saeedi,, 2013; Most et al.,, 2010; Shimoni et al.,, 2005;
Gerjuoy,, 2005; Azuma,, 2017; Lawson,, 2015; Most et al.,, 2010; García-Mata
et al.,, 2008, 2007; Ukena and Shimizu,, 2004; Wei et al.,, 2005; Ekera and
Hastad,, 2017).

####  1.1.2 Quantum search

Grover algorithm is a search algorithm over an unordered set of $N=2^{n}$
items to find a unique element which satisfies some predefined conditions
(Grover,, 1996; Grover, 1997a, ; Grover, 1997b, ; Grover, 1998b, ; Grover,
1998a, ; Grover,, 2000, 2001, 2002; Grover and Radhakrishnan,, 2004). This
algorithm requires only O($\sqrt{N}$) operations to perform the search, which
is quadratic speed-up over its classical opponent. It is one of the most
famous quantum algorithms not only because of its speed-up, but also because
it is a good introduction to quantum algorithms. It demonstrates how the
properties of quantum systems and their fundamental differences with the
classical computing systems can be used to lower the runtime. Grover’s
algorithm is based on the quantum superposition and like many other
algorithms, the first step of it is to initialize the system in equal
superposition. This way an equal amplitude ($1/\sqrt{2^{n}}$) is associated
with every possible state of the system, so there is equal probability of
$1/\sqrt{2^{n}}$ that the system will be in any of the $2^{n}$ possible
states. The next step in Grover’s algorithm is to use the amplitude
amplification to selectively shift the phase of one state of the quantum
system - the one that satisfies the search conditions, at each iteration. The
phase shift of $\pi$ is equivalent to multiplication of the amplitude for this
state by -1. Changing the amplitude doesn’t change the probability for the
state (the probability disregards the sign of the amplitude) (Strubell,,
2011).

How this algorithm works?

The search problem needs to be translated into quantum-mechanical problem. So,
let the system have $N=2^{n}$ states {$S_{1},S_{2},...,S_{n}$}. The
representation of these states are bit strings - $n$ bit strings. A unique
state $S_{v}$ must satisfy the condition $C(S_{v})=1$, and all other states S,
$C(S)=0$. The problem is to identify this $S_{v}$ state (Grover,, 1996). The
algorithm itself consists of three steps:

  1. i

System initialization, so that there is the same amplitude for each possible
state: $\left({1\over\sqrt{N}},{1\over\sqrt{N}},...,{1\over\sqrt{N}}\right)$.
This distribution can be obtained in $O[logN]$ steps and can be achieved by
applying a ”fair coin flip” operation on all the qubits in the quantum system
(Simon,, 1997). This operation is represented by the following matrix:

$M={1\over\sqrt{2}}\begin{bmatrix}1&1\\\ 1&-1\end{bmatrix}$

Applied on a signel qubit, the state 0 is transformed into two states:
$\left({1\over\sqrt{2}},{1\over\sqrt{2}}\right)$. And when applied to every
qubit in a quantum system, the transition matrix representation will be of
size $2^{N}X2^{N}$ and an identical amplitude will be induced for every one of
the $2^{N}$ possible states. This is known as Walsh-Hadamard transformation
(Deutsch and Jozsa,, 1992).

  2. ii

Repetition of the following unitary operations O($\sqrt{N}$) times:

    1. (a)

If $C(S)=1$: rotate phase by $\pi$ radians. Else if $C(S)=0$ leave the system
unaltered.

    2. (b)

Apply diffusion transform D. D=WRW, where W is the Walsh-Hadamard
transformation and R is the rotation matrix.

$R_{ij}=0$ if $i\neq j$

$R_{ii}=1$ if $i=0$; $R_{ii}=-1$ if $i\neq 0$

$W_{ij}=2^{-n/2}(-1)^{\overline{i}.\overline{j}}$, where
${\overline{i}.\overline{j}}$ denotes the dot product.

  3. iii

Sample the resulting states. The final state is $S_{v}$ with probability $\geq
1/2$ if $C(S_{v})=1$

The main part of this algorithm is the step $ii$ where the desired state
amplitude is increased.

Working example:

The quantum system is formed of 8 states: $2^{3}$. This means that 3 qubits
are required to represent these 8 states. And the queried state is
$\ket{010}$.

$\ket{\Psi}=\alpha_{0}\ket{000}+\alpha_{1}\ket{001}+\alpha_{2}\ket{010}+\alpha_{3}\ket{011}+\alpha_{4}\ket{100}+\alpha_{5}\ket{101}+\alpha_{6}\ket{110}+\alpha_{7}\ket{111}$

  1. i

Initialize the system in 0:

Apply the identity gate to every qubit in the system so the result is:
$1\ket{000}$.

Then apply Hadamard transform to every one of the three qubits:

$H^{3}\ket{000}={1\over 2\sqrt{2}}\ket{000}+{1\over
2\sqrt{2}}\ket{001}+{1\over 2\sqrt{2}}\ket{010}+{1\over
2\sqrt{2}}\ket{011}+{1\over 2\sqrt{2}}\ket{100}+{1\over
2\sqrt{2}}\ket{101}+{1\over 2\sqrt{2}}\ket{110}+{1\over
2\sqrt{2}}\ket{111}=\ket{\psi}$

  2. ii

The optimal number of Grover operations is ${\pi\over 4}\sqrt{2^{3}}={\pi\over
2}\sqrt{2}\approx 2.22$.

Each operation consists of:

    1. (a)

Call the quantum oracle $O$.

    2. (b)

Inversion about the average (diffusion transform) - $2\ket{\psi}\bra{\psi}-I$.

$\braket{\psi}{\psi}=1$.

$\braket{\psi}{010}={1\over 2\sqrt{2}}$ ($\ket{010}$ is one of the basis
vectors).

$\left[2\ket{\psi}\bra{\psi}-I\right]\ket{x}=2\ket{\psi}\braket{\psi}{\psi}-\ket{\psi}-{2\over\sqrt{2}}\ket{\psi}\braket{\psi}{010}+{1\over\sqrt{2}}\ket{010}={1\over
2}\ket{\psi}+{1\over\sqrt{2}}\ket{010}$.

Substitution of $\ket{psi}$:

${1\over 2}{1\over 2\sqrt{2}}\ket{000}+{1\over 2\sqrt{2}}\ket{001}+{1\over
2\sqrt{2}}\ket{010}+{1\over 2\sqrt{2}}\ket{011}+{1\over
2\sqrt{2}}\ket{100}+{1\over 2\sqrt{2}}\ket{101}+{1\over
2\sqrt{2}}\ket{110}+{1\over 2\sqrt{2}}\ket{111}+{1\over\sqrt{2}}\ket{010}=\\\
={1\over 4\sqrt{2}}\ket{000}+{1\over 4\sqrt{2}}\ket{001}+{1\over
4\sqrt{2}}\ket{011}+{1\over 4\sqrt{2}}\ket{100}+{1\over
4\sqrt{2}}\ket{101}+{1\over 4\sqrt{2}}\ket{110}+{1\over
4\sqrt{2}}\ket{111}+{5\over 4\sqrt{2}}\ket{010}$

This completes the first iteration. Then the result of the second iteration
is:

$-{1\over 8\sqrt{2}}\ket{000}-{1\over 8\sqrt{2}}\ket{001}-{1\over
8\sqrt{2}}\ket{011}-{1\over 8\sqrt{2}}\ket{100}-{1\over
8\sqrt{2}}\ket{101}-{1\over 8\sqrt{2}}\ket{110}-{1\over
8\sqrt{2}}\ket{111}+{11\over 8\sqrt{2}}\ket{010}$.

  3. iii

Now when this quantum-mechanical system is observed the probability for the
state $\ket{010}$ will be:

$\left|{11\over 8\sqrt{2}}\right|^{2}\approx 95\%$.

####  1.1.3 HHL

Linear algebra is a branch of mathematics which concerns operations with
linear equations, linear functions, matrices. It is an essentially big part of
many machine learning algorithms. Solving systems of linear equations is one
of the most common problems not only in the linear algebra, but in all fields
of science and engineering.

Approximating the solution for N linear equations in N unknown parameters
takes time of order N with classical methods. A quantum algorithm (Harrow et
al.,, 2009) in some cases can approximate the value of a function of the full
solution to these N equations scaling logarithmically in N, and with some
additional conditions and precision it could take polynomial time. This
algorithm can achieve exponential speed-up in some special cases with
additional restrictions applied.

How this algorithm works?

The problem: a Hermitian matrix $A=N\times N$ and a unit vector
$\overrightarrow{b}$ are given.

Find $\overrightarrow{x}$, such that $A\overrightarrow{x}=\overrightarrow{b}$.

The algorithm itself consists of the following steps:

  1. i

Represent $\overrightarrow{b}$ as a quantum state
$\ket{b}=\sum_{i=1}^{N}{b_{i}\ket{i}}$.

  2. ii

Use Hamiltonian simulation techniques to apply $e^{iAt}$ to $\ket{b}$ for a
superposition of different times (Berry et al.,, 2006; Childs,, 2009).

  3. iii

Use phase estimation to decompose $\ket{b}$ (Luis and Peřina,, 1996; Cleve et
al.,, 1998; Buzek et al.,, 1999). The result is:

$\sum_{j=1}^{N}{\beta_{j}\ket{u_{j}}\ket{\lambda_{j}}}$

  4. iv

Use a non-unitary operation to do a linear mapping
$\ket{\lambda_{j}}\rightarrow C\lambda_{j}^{-1}\ket{\lambda_{j}}$. The result
is:

$\sum_{j=1}^{N}{\beta_{j}\lambda_{j}^{-1}\ket{u_{j}}}=A^{-1}\ket{b}=\ket{x}$

The real advantage in this algorithm is that it doesn’t need to write all
$A,\overrightarrow{b},\overrightarrow{x}$ in the quantum registers, and
requires only a register with length of $O(logN)$.

There are many potential applications of this algorithm since the matrix
inversion is a widely spread problem across various science fields. Detailed
explanation of the algorithm is given in part II of (Harrow et al.,, 2009).
This algorithm also had become an important subroutine for many quantum
machine learning algorithms (Buhrman et al.,, 2001; Valiant,, 2011, 2008;
Klappenecker and Rotteler,, 2003; Leyton and Osborne,, 2008; Grover and
Rudolph,, 2002), but it has some limitations (Shao,, 2018), which must be
taken into account when applying in practice.

Some of the problems that arise when applying this algorithm are:

  * •

The preparation of the input state $\ket{b}$ \- Lov Grover and Terry Rudolph
have given an efficient process for generating certain probability
distributions using quantum computers (Grover and Rudolph,, 2002) ( forming a
discrete approximation of any efficiently integrable probability density
function). The quantum representation of a probability distribution is a
superposition of the form:

$\ket{\psi(\\{p_{i}\\})}=\sum_{i}{\sqrt{p_{i}}\ket{i}}$

where i are orthonormal.

The quantum sates in this form can also be useful for Quantum Fourier
Transform, since these can be efficiently fourier transformed (Shor,, 1997).

  * •

The choice of t parameter in the Hamiltonian simulation of $e^{iAt}$. Here the
t must satisfy:

$\left|\lambda t\right|<\pi$, $e^{2\pi i}=1$. And theoretically
$t=\pi/|\lambda_{max}|$, $|\lambda_{max}|$ is the maximal singular value of A.

For $|\lambda_{max}|$ exist several upper bounds and the choice of an upper
bound will affect the complexity of the algorithm:

    * –

$\sqrt{Tr(AA^{\dagger}}$

    * –

$||A||_{1}=max_{j}\sum_{i}{|a_{ij}|}$

    * –

$||A||_{2}=\sqrt{\sum_{i,j}{|a_{ij}|^{2}}}$

    * –

$M||A||_{max}=M_{max_{i,j}}|A_{ij}|$

Some of the potential application of the algorithm are:

  * •

Linear regression (Schuld et al.,, 2016; Wiebe et al.,, 2012; Qin et al.,,
2017)

$F^{\dagger}Fx=F^{\dagger}b$

F is a data matrix and b is a given vector.

  * •

Supervised classification (Lloyd et al.,, 2013) \- this application is based
on the distance comparison of a vector to the means of two clusters. The
authors show a novel technique for a preparation of the desired quantum state.

  * •

Support vector machine - the main technique for the Hamiltonian simulation of
a matrix is well described in (Lloyd et al.,, 2014).

  * •

Hamiltonian simulations - a new method for a low rank non-sparse Hermitian
matrix is proposed in (Rebentrost et al.,, 2018).

####  1.1.4 Quantum PCA

The principal component analysis (PCA) is a bedrock to dimensionality
reduction technique for probability and statistics, commonly used in data
science and machine learning applications, where there is big dataset with
statistical distribution and the low-dimensional patterns must be uncovered.

Let’s have data in form of vectors $\overrightarrow{v_{j}}$ in d-dimensional
vector space, where covariance matrix of this data is:

$C=\sum_{j}{\overrightarrow{v_{j}}\overrightarrow{v_{j}^{T}}}$

where $\overrightarrow{v_{j}^{T}}$ is transposed vector.

This covariance matrix summarizes the correlations between the different
components of the data.

The simplest form of PCA is the diagonalization of the covariance matrix:

$C=\sum_{k}{e_{k}\overrightarrow{c_{k}}\overrightarrow{c_{k}}^{\dagger}}$

$\overrightarrow{c_{k}}$ are eigenvectors of C.

$e_{k}$ are eigenvalues of C.

The eigenvectors $\overrightarrow{c_{k}}$ form an orthonormal set.

If the reminder are small or zero (few large values for $e_{k}$), the
corresponding eigenvectors are called the principal components of C. Where
each principal component represents a correlation in the data. The classical
algorithms to perform PCA have computational complexity of order $O(d^{2})$.

In the quantum way this problem is translated to revealing properties of an
unknown quantum state (Lloyd et al.,, 2014). A quantum coherence can be
created among multiple copies of a randomly generated quantum state to perform
a quantum principal component analysis, which reveals the eigenvectors
corresponding to the large eigenvalues of this quantum state. This requires
$O(d)$ operations in qRAM divided over $O(logd)$ steps, which could be
executed in parallel.

The quantum tomography (Nielsen and Chuang,, 2011; Mohseni et al.,, 2008) is a
widely used tool where a given multiple copies of an unknown quantum state in
d-dimensional Hilbert space are being measured with various techniques in
order to extract useful information showing some features of the state (Gross
et al.,, 2010; Shabani et al., 2011a, ; Shabani et al., 2011b, ). Multiple
copies of the state can play active role in its own measurement and implement
the unitary operator $e^{-i\rho t}$: energy operator or Hamiltonian, which
generates transformations on other states.

  1. i

Exponentiate density matrix - this exponentiates non-sparse matrices in
$O(logn)$, which is exponential speed-up over its classical opponents (Lloyd
et al.,, 2014).

Using Suzuki-Trotter expansion (Lloyd,, 1996; Aharonov and Ta-Shma,, 2003;
Berry et al.,, 2006; Wiebe et al.,, 2010) the $e^{-iXt}$ is constructed for
non-sparse positive matrix X.

$\sum_{k}{e_{k}}=1$ for X

$X=A^{\dagger}A$

$A=\sum_{i}{|\overrightarrow{a_{i}}|\ket{a_{i}}\bra{e_{i}}}$

Density matrix plays role in exploring its own features by decomposition of
semi-definite Hermitian matrix to the eigenvectors of the largest eigenvalues
(Bishop,, 2006; Murphy,, 2012).

  2. ii

Application to quantum phase estimation algorithm to find the eigenvalues and
eigenvectors of the unknown density matrix. The quantum phase estimation
algorithm takes any initial state $\ket{psi}\ket{0}$ to
$\sum_{i}{\psi_{i}\ket{x_{i}}\ket{\tilde{r}_{i}}}$, where the eigenvectors are
$\ket{psi_{i}}$ and the approximated (estimated) eigenvalues are
$\tilde{r}_{i}$. There exists an improved method for phase estimation (Harrow
et al.,, 2009) which requires $O(1/\epsilon^{3})$ copies of the random quantum
state $\rho$.

Advantages and future applications of the quantum self-tomography

  * •

Reveals eigenvectors and eigenvalues in time $O(Rlogd)$ compared to the
compressive tomography ($O(Rdlogd)$) (Gross et al.,, 2010).

  * •

The density matrix exponentiation is time-optimal (Lloyd et al.,, 2014).

  * •

Quantum self-tomography is comparable to group representation methods (Keyl
and Werner,, 2001), but not only the spectrum is approximated - also as a
result, the eigenvectors are found.

  * •

Quantum PCA applications in state discrimination and assignment, where the
task is to assign a new set of states to already known other sets. The
decomposition to eigenvectors and eigenvalues gives the possibility for
assignment and also the magnitude of the measured eigenvalue is the confidence
of the set assignment measurement: larger the magnitude is - the higher the
confidence is (Lloyd et al.,, 2014).

  * •

Speed-up of some machine learning problems in clustering and pattern
recognition (Lloyd et al.,, 2013; Rebentrost et al.,, 2014).

####  1.1.5 Quantum Boltzmann Machines

Boltzmann machines (BMs) are recurrent neural networks which can also be
represented as bidirectionally connected networks of stochastic processing
units ( Markov Random Field - set of random variables, each having the Markov
property) (Ackley et al.,, 1985; Brémaud,, 1999; Koller,, 2009). The usage of
Boltzmann machines in practice is usually simplified by imposing restrictions
on the topology of the network (Fischer and Igel,, 2012; Rumelhart and
McClelland,, 1987). The learning process in Restricted Boltzmann machines
could be summarized as adjusting the parameters of the Boltzmann machine so
that the probability distribution of the network fits the input data. The
constructive parts of the BMs are two layers - visible and hidden. The neurons
in the visible layer correspond to the observed object ( for example: if the
object is an image - then each neuron represents a pixel on this image). The
hidden neurons represent the model of the object - dependencies and patterns
between the components of the object (the neurons in the visible layers)
(Fischer and Igel,, 2012; Hinton, 2007a, ).

Restricted Boltzmann machines are reviewed well in (Bengio, 2009a, ) and they
have received attention in the scientific area after being proposed as
building part of the deep belief networks (DBNs) (Hinton, 2007b, ; Hinton et
al.,, 2006).

The probability of a given visible and hidden layers configuration in
Boltzmann machines is given by the Gibbs distribution (Wiebe et al.,, 2014):

$\mathbb{P}(v,h)=e^{-E(v,h)}/Z$,

where $v$ and $h$ are visible and hidden layers respectively and Z is the
normalizing factor (partition function). The energy of a given configuration
of $v$ and $h$, $E(v,h)$, is:

$E(v,h)=-\sum_{i}{v_{i}b_{i}}-\sum_{j}{h_{j}d_{j}}-\sum_{i,j}{\omega_{i,j}^{vh}v_{i}h_{j}}-\sum_{i,j}{\omega_{i,j}^{v}v_{i}v_{j}}-\sum_{i,j}{\omega_{i,j}^{h}h_{i}h_{j}}$

The $b$ and $d$ vectors are biases (energy penalty for unit value 1) and
$\omega_{ij}^{vh}$, $\omega_{i,j}^{v}$, $\omega_{i,j}^{h}$ are weights.
$n_{v}$ and $n_{h}$ are the numbers of visible and hidden units.

The learning for the Boltzmann machine is adjusting the strengths of the
interactions within the graph to maximize the likelihood of the given
observations to be produced by the method. The training process uses gradient
decent to optimize the maximum-likelihood objective:

$O_{ML}:={1\over N_{train}}\sum_{v\in
X_{train}}{log(\sum_{h=1}^{n_{h}}{P(v,h)})}-{\lambda\over 2}\omega^{T}\omega$

$\lambda$ is the L2-norm. The derivative has the following look:

${\partial O_{ML}\over\partial\omega_{i,j}}=\left\langle
v_{i}h_{j}\right\rangle_{data}-\left\langle
v_{i}h_{j}\right\rangle_{model}-\lambda\omega_{i,j}$

The gradient decent computation is exponentially hard (in $n_{v}$ and $n_{h}$)
problem and the best classical approach is approximation through contrastive
divergence (Bengio, 2009b, ; Hinton,, 2002; Salakhutdinov et al.,, 2007;
Tieleman,, 2008; Salakhutdinov and Hinton,, 2009), which unfortunately does
not provide gradient to any true objective function (Sutskever and Tieleman,,
2010; Tieleman and Hinton,, 2009; Bengio and Delalleau,, 2009; Fischer and
Igel,, 2011)

Efficient alternatives to this classical method are provided in (Wiebe et
al.,, 2014) where two new quantum algorithms are proposed: Gradient Estimation
via Quantum Sampling (GEQS) and Gradient Estimation via Quantum Aplitude
Estimation (GEQAE).

The quantum problem

In Quantum Boltzmann machines the problem could be summarized to learning a
set of Hamiltonian parameters $\omega_{i}$ for a fixed set of $H_{i}$, the
input state $\rho$ is well approximated by
$\sigma=e^{-\sum{\omega_{i}H_{i}}}/Tr(e^{-\sum{\omega_{i}H_{i}}})$ (Biamonte
et al.,, 2017; Kieferova and Wiebe,, 2017; Amin et al.,, 2018). The quality of
the approximation is measured by the quantum relative entropy:

$S(\rho||\sigma)=Tr(\rho log\rho-\rho log\sigma)$

where the upper bound is the distance between the two states. Minimizing the
distance, minimizes the error in the approximated state $\sigma$ (Biamonte et
al.,, 2017).

Since it is hard to learn experimentally (calculating the quantum relative
entropy), it is more practical (and easier) to estimate the gradient of the
relative entropy:

$\sigma_{\omega_{i}}S(\rho||\sigma)=Tr(\sigma H_{i})Tr(\rho H_{i})$

The Stochastic Hamiltonians have all off-diagonal matrix elements to be real
and non-negative (non-positive) to which no classical analogue is known
(Biamonte and Love,, 2008).

The algorithms for quantum state generation, gradient calculation, gradient
estimation and training via quantum amplitude estimation are well described in
the Appendix in (Wiebe et al.,, 2014).

####  1.1.6 Input and output problem

Loading classical data into a quantum computer is a bottleneck for some
algorithms. Most quantum machine learning algorithms require exponential time
procedures to load data into quantum states (Aaronson,, 2015). One solution to
this problem is using quantum Random Access Memory (qRAM), but it is a costly
solution for big datasets (Arunachalam et al.,, 2015).

Similar problem is noticeable when a readout for a quantum system is required.
Also known as the ’output problem’. It is a common problem for all linear
algebra-based quantum machine learning algorithms, since it is exponentially
hard to estimate the classical quantities for the solution vector of the qPCA
algorithm.

The quantum information is very different from its classical counterpart,
because it exists in a superposition and it’s hard to measure it - every
observation made on a quantum register leads to a collapse of this
superposition.

In the Machine learning field the computer algorithms are being developed in
such a way, that they learn from the history of observations. In general
Machine learning algorithms can be classified as supervised and unsupervised
learning algorithms depending on the input dataset. When the input dataset is
labeled - it is supervised learning.

One of the main fundamental differences between classical and quantum
computing is the representation of the information - in classical computing
the smallest unit of information is bit, and it can be either in state 0 or in
state 1. The quantum equivalent of the bit is the qubit (quantum bit) - it can
be simultaneously in two orthonormal states, which means the qubit is in
superposition, and using Dirac notation, the qubit representation is given as:

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

The collapse of the superposition means that, when measured the qubit is in
either $\ket{0}$ or $\ket{1}$ state with probability $\left|\alpha\right|^{2}$
or $\left|\beta\right|^{2}$.

The knowledge about a particular quantum system is represented by the density
matrix, which gives a complete description of what can be observed about the
quantum system.

$\rho=\ket{\psi}\bra{\psi}$

$\bra{\psi}$ is the conjugate transpose of $\ket{\psi}$.

$\rho$ is a pure state when the latter being considered as a column vector in
the Hilbert space.

A mixed state is an ensemble of pure states:

$\\{(\alpha_{1},\ket{\psi_{1}}),...,(\alpha_{n},\ket{\psi_{n}})\\}$

$\sum_{i=1}^{n}{\alpha_{i}}=1$

$\alpha_{i}$ is the probability associated with the pure state
$\ket{\psi_{i}}$.

$\rho=\sum_{i=1}^{n}{\alpha_{i}\ket{\psi_{i}}\bra{\psi_{i}}}$

The fundamental limits on operations with a quantum state are:

  * •

No-cloning theorem (Wootters and Zurek,, 1982) \- no unknown quantum state can
be cloned perfectly, unless it is known to belong to a set of pairwise
orthogonal states (AÃ¯meur et al.,, 2006).

  * •

It is not possible to extract more than n bits of classical information from n
qubits (Holevo’s theorem (Holevo,, 1973)). For n qubits, all possible
amplitudes are $2^{n}$, so only a small amount of the quantum information can
be extracted and classically represented.

As mentioned above, the machine learning algorithms learn from history of
observations (a training dataset). In classical dataset the observations are
implicitly considered to be classical. In quantum machine learning a training
dataset is also required, but this dataset obeys on the laws of quantum
mechanics, and the entire learning process needs to be redesigned.

At the time of writing this dissertation, there exists several types of
learning strategies for quantum datasets:

  * •

Quantum tomography - quantum estimation technique through measurements on some
copies of the quantum states.

  * •

One-time classifier - the copies of the quantum states are used only at the
time of demand.

  * •

Hybrid - a combination between the other two.

####  1.1.7 Benchmark problem

The benchmark problem is a general problem not only for the quantum
algorithms, but also a huge research area in classical computer science. In
the quantum world the benchmark problem is connected not only with need for
probing performance of quantum computers against their classical counterparts
for identical (similar) problems, but also for a comparison between various
quantum hardware backends. In (Blume-Kohout and Young,, 2019) the authors
propose a large number of benchmarks which define a family of rectangular
quantum circuits, allowing the study of the time/space performance trade-offs.

The quantum computing is one of the fastest growing hardware areas and only
for a few years the quantum processors scaled from a two coupled qubits to 49
(Intel), 50 (IBM) and 72 (Google) at 2018. In order to use efficiently quantum
processors there need to be a tool for measuring the performance - a
benchmark.

What is a quantum benchmark?

The quantum benchmark is a set of quantum circuits and instructions, analysis
procedure and interpretation rules (Blume-Kohout and Young,, 2019). There
exists few families of quantum benchmarks, each of them measuring different
metrics:

  * •

Quantum volume - this is a benchmark proposed by IBM (Cross et al.,, 2019),
which measures the size of the accessible state space for a quantum processor.
In the ideal world a quantum processor with n qubits would have $2^{n}$
computational states, but in the practice parts of the state space is not
accessible. This problem could be caused by various reasons: poor control for
the qubits, noise in the quantum system. This benchmark gives the answer to
the question ”What’s the largest number of qubits on which the processor can
reliably produce a random state?” and it requires a ”square” quantum circuit
to be run on the hardware ( number of qubits = number of time steps), which is
a considerable caveat, since not many existing quantum algorithms use ”square”
circuits.

  * •

Randomized benchmark - this is a method for measurement of the accuracy of the
implementation of a coherent quantum transformation (Emerson et al.,, 2005,
2007; Knill et al.,, 2008; Magesan et al.,, 2011, 2012). It estimates the gate
fidelity and it is quite relevant for large-scale Hilbert spaces. It
determines the noise in the quantum system by variation over different
experimental arrangements and error-correction strategies.

  * •

Long-sequence gate set tomography - this technique provides an accurate
complete tomographic description for every gate and is not only applicable on
single qubit gates, but also on high-fidelity two-qubit gates (Blume-Kohout et
al.,, 2017, 2013; Greenbaum,, 2015; Kim et al.,, 2015; Dehollain et al.,,
2016).

  * •

Volumetric benchmarks - this is a framework for large family of benchmarks,
that had been inspired by the IBM’s quantum volume benchmark (Blume-Kohout and
Young,, 2019). It measures the quantum processor’s ability to run an ensemble
of rectangular quantum circuits.

###  1.2 Goals

The fundamental properties of the quantum computers give the quantum
information theory a great advantage handling hard problems. The main goal of
this dissertation is to create new quantum algorithm with as easy as possible
implementation on real hardware platforms, which could be used for analysis of
stochastic processes described by binary homogeneous Markov model. Essential
result from this work is that this algorithm allows the stochastic process to
be simulated, discretely over time, through its representation as a quantum
mechanical system. The simulation of binary homogeneous Markov process with
quantum computer returns as a superposition of the quantum register the full
set of all possible paths for the process. This way the required informational
operations for the calculation of full set of paths are being reduced
exponentially - $2^{n}$ possible paths could be calculated with $n$
operations. The computational complexity of the algorithm is linear to the
number of discrete time steps of the process: $O(n)$, where $n$ is the number
of the discrete time steps in the Markov process.

###  1.3 Tasks

The following tasks must be achieved in order to develop the method and
algorithm for quantum simulation of binary homogeneous Markov model:

  * •

An algorithm for estimation of the of qubit’s rotation angle over the X axis,
depending on the desired probability distribution for the states amplitudes.

  * •

Implementation of a quantum logic gate, which rotates the qubit over the X
axis.

  * •

Implementation of a controlled quantum logic gate, which acts on two qubits
and rotates the target over the X axis depending on the control qubit state.

  * •

Algorithm for quantum simulation of a binary homogeneous Markov process with
application on real hardware platforms.

  * •

Development of quantum circuit representing the time evolution of a stochastic
problem defined by binary homogeneous Markov model.

  * •

Development of an example: experimental quantum circuit, which could be
executed on various hardware platforms including high-performance quantum
simulator and real quantum processors in IBM’s cloud platform ”Quantum
Experience”.

  * •

Application of error correction and error mitigation techniques for the
experimental circuit. Analysis of the results and comparative analysis for the
performance of the different hardware back-ends.

##  2 Analysis of the Review

###  2.1 Motivation

Markov chains are fundamental part in algorithms for problems in various
scientific research areas: chemistry, physics, biology, economics, finance and
many more. Using quantum computers for solving real scientific problems would
cause a huge impact on modern science and technology, including the quantum
computing.

This chapter describes the necessary fundamentals for understanding in-depth
the quantum computing and quantum information theory behind the quantum
simulation of stochastic processes and the necessary software frameworks and
tools for quantum computation. Also attention is paid to the mathematical
foundations of the probability theory, and processes described by Markov
chains (binary homogeneous Markov process), more specifically.

Figure 1: Structure of the dissertation.

The workflow is defined by the structure of this dissertation, shown on figure
1, where the structure could be divided down to 3 parts:

  * •

Survey (Review) of the fundamental ideas and modern techniques of quantum
computing and quantum information. Some mathematics and physics fundamentals
behind quantum computing theory - how quantum mechanics together with computer
science theory lead to quantum computation. Fundamentals of probability theory
and stochastic processes (Markov chains). Review of the required software
framework for model development and experimental verification.

  * •

Definition of the goals, challenges and problems this work is based on. The
connection between quantum computing and quantum information theory with
existing software frameworks and tools, required for solving the defined
problems and challenges, and achieving the goals.

  * •

The methodology and conception for development of new quantum algorithm,
applied objects (software), running experiments and analysis of the results
obtained.

###  2.2 Quantum Computing

Quantum computers are based on the laws of quantum mechanics and offer a
fundamentally different (from the classical computers) computational
mechanism. The main fundamental differences between classical and quantum
computers are three:

  * •

Superposition - this is one of the fundamental parts of quantum mechanics. In
a given moment of time the quantum system is simultaneously in all of its
possible states. In the context of quantum computing, this means that if a
quantum register is in a superposition, its state is a linear combination of
all possible states between 0 and 1 for the qubits in the register. In
classical computers, a register can only be in one state at a given moment of
time. The superposition collapses when a measurement is being performed on the
quantum register. The collapse means that at the moment of measurement, the
register is in one deterministic state. The quantum computations are performed
by setting probabilities for all the possible states for a register.

  * •

Probabilistic - the quantum system is probabilistic and not deterministic.
Every possible state for this system can be observed when a measurement is
performed over the quantum register. The quantum computation is performed by
increasing the probability for the desired state of the register.

  * •

Entanglement - this is a specific property for the quantum systems. A given
quantum system is entangled if it can not be decomposed into more fundamental
parts. And one part of this system can not be described without the knowledge
for states of the others.

Understanding mathematics used to describe quantum mechanical systems (states
of quantum registers and quantum logic gates) requires knowledge of the
fundamental concepts and notations. The Dirac notation (also known as bra-ket
notation) is a way of describing vectors, where column-vector is called ket
vector and row vector - bra vector.

$v=\begin{bmatrix}v_{0}\\\ v_{1}\\\ v_{2}\\\ \vdots\\\ v_{n}\end{bmatrix}$
(2.1)

$v=\overline{v^{T}}=\left[\overline{v_{0}},\overline{v_{1}},\overline{v_{2}},...,\overline{v_{n}}\right]$
(2.2)

Where $\overline{v}$ is the conjugate transpose of $v$. The Dirac notation e a
convenient way of vector description in the Hilbert space. The Hilbert space
is a vector space with a vector product and a norm defined by this product.
The vector product of two vectors in the complex Hilbert space is the scalar
product of the vectors $v$ and $u^{T}$ ( the complex conjugate of $u$):

$\braket{v}{u}=\overline{u^{T}}v=\left[\overline{u_{0}},\overline{u_{1}},\overline{u_{2}},...,\overline{u_{n}}\right]\begin{bmatrix}v_{0}\\\
v_{1}\\\ v_{2}\\\ \vdots\\\
v_{n}\end{bmatrix}=\overline{u_{0}}v_{0}+\overline{u_{1}}v_{1}+\overline{u_{2}}v_{2}+...+\overline{u_{n}}v_{n}$
(2.3)

The vector product must satisfy the following conditions:

  * •

$\braket{v}{v}>=0$ where $\braket{v}{v}=0$ if and only if $\ket{v}=0$.

  * •

$\braket{u}{v}=\overline{\braket{v}{u}}$ for all $\ket{u}$ and $\ket{v}$ in
the vector space.

  * •

$\braket{u}{\alpha_{0}v+\alpha_{1}w}=\alpha_{0}\braket{u}{v}+\alpha_{1}\braket{u}{w}$

The norm of $\ket{v}$ in the Hilbert space is defined as square root of the
vector product of $\ket{v}$ with itself, which geometrically represented would
be the distance from the origin of the coordinate system to the point
$\ket{v}$ (also known as Euclidean distance).

$\lVert\ket{v}\rVert=\sqrt{\braket{v}{v}}$ (2.4)

The tensor product of two vectors (also known as Kronecker product) describes
the linear transformation between two vector spaces and is used for combining
multiple vector spaces into a bigger one. The tensor product of two vector
space describing two quantum mechanical systems gives the linear combination
between all the vectors in the two spaces.

$\ket{v}\bra{u}=\begin{bmatrix}v_{0}\\\ v_{1}\\\ v_{2}\\\ \vdots\\\
v_{n}\end{bmatrix}\left[\overline{u_{0}},\overline{u_{1}},\overline{u_{2}},...,\overline{u_{n}}\right]=\begin{bmatrix}v_{0}\overline{u_{0}}&v_{0}\overline{u_{1}}&...&v_{0}\overline{u_{n}}\\\
v_{1}\overline{u_{0}}&v_{1}\overline{u_{1}}&...&v_{1}\overline{u_{n}}\\\
v_{2}\overline{u_{0}}&v_{2}\overline{u_{1}}&...&v_{2}\overline{u_{n}}\\\
\vdots\\\
v_{n}\overline{u_{0}}&v_{n}\overline{u_{1}}&...&v_{n}\overline{u_{n}}\end{bmatrix}$
(2.5)

Like classical computers and information systems, the quantum computers are
based on the quantum bit (qubit). The main properties of one qubit and a
quantum register are presented bellow. Like in the theory of classical
computing, where the bit represents a physical object, the qubits are also a
representation of real physical objects, but for the purpose of this
dissertation these will be treated as abstract mathematical objects, since
there is no single quantum hardware realization - there are multiple hardware
realizations with different physical properties. This representation of qubits
gives the freedom to use the main theory for quantum computation and quantum
information which does not depend on the hardware.

One qubit pure state could be described by the wave function of its basis
states:

$\ket{\Psi(t)}=e^{-i\zeta_{0}(t)}c_{0}(t)\ket{0}+e^{-i\zeta_{1}(t)}c_{1}(t)\ket{1}$
(2.6)

The $\ket{0}$ and $\ket{1}$ are the two possible states for every qubit, and
these are interpretation of the 0 and 1 states of classical bits. The
difference here is that every qubit exists in the two states simultaneously -
the superposition. This superposition is a linear combination of the two
states:

$\ket{\Psi}=\alpha\ket{0}+\beta\ket{1}$ (2.7)

Here $\alpha$ and $\beta$ are complex numbers. And the qubit’s state is a
vector in the two-dimensional complex vector space. When a measurement is
performed over the qubit its superposition collapses and it goes into one of
the two possible states - $\ket{0}$ or $\ket{1}$. Where the probability for
the qubit to be in state $\ket{0}$ is $|\alpha^{2}|$ and in state $\ket{1}$ \-
$|\beta^{2}|$. The two probabilities must sum up to 1:
$|\alpha^{2}|+|\beta^{2}|=1$. Even if it doesn’t sound intuitive, the
superposition means that the qubit is in a state, which is neither $\ket{0}$
nor $\ket{1}$, but somewhere in between. When a collapse occurs the state can
be deterministic defined as one of the two possibilities. The 2.6 could be
transformed into one of the two equations bellow:

$\ket{\Psi}=e^{i\gamma}\left(\cos{\left(\theta\over{2}\right)}\ket{0}+e^{i\phi}\sin{\left(\theta\over{2}\right)}\ket{1}\right)$
(2.8)

And $e^{i\gamma}$ could be removed, so the 2.8 is simplified to:

$\ket{\Psi}=\cos{\theta over2}\ket{0}+e^{i\phi}\sin{\theta over2}\ket{1}$
(2.9)

The quantum registers are sequences of qubits, where the length of the
register indicates how much information it can store. The superposition of a
quantum register is an analogue of the superposition of a qubit, and when it
is in a superposition, all the qubits in the register are in superposition.
All possible bit configurations in the register’s superposition are the tensor
product of all consisting qubits. The vector space of a $n$-size quantum
register is a linear combination of $n$ basis vectors, where every vector is
with size $2^{n}$:

$\ket{\Psi_{n}}=\sum_{i=0}^{2^{n}-1}{\alpha_{i}\ket{i}}$ (2.10)

The quantum registers could be mathematically expressed as an extension to the
qubits, where the probabilities for every possible state of the register
satisfy the following condition:

$\sum_{i=0}^{2^{n}-1}{\left|\alpha_{i}\right|}=1$ (2.11)

A quantum computation (in the meaning of the computation analogue to the
classical one) is achieved by the evolution of a quantum register (a qubit can
be expressed as a register with length of 1) over time. And the evolution is
achieved by the application of quantum logic gates over the registers. When
applied over a register, the quantum logic gate, maps the superposition of
this register from one to another. The mathematical representation of the
quantum logic gates is transformation matrices and when applied to a quantum
register the result is a tensor product of a transformation matrix with the
matrix representation of a quantum register. All linear operators which
represent quantum logic gates must satisfy the condition to be unitary. The
unitary operations over a single qubit could be graphically represented by
rotations over the $x,y,z$ axis on the Bloch sphere, where all linear
combinations of $\alpha\ket{0}+\beta\ket{1}$ in $\mathbb{C}^{2}$ represent all
the possible points on the surface of the Bloch sphere $(\theta,\Psi)$.

Here is a list of all the elementary and newly generated quantum logic gates
used in this dissertation:

  * •

Hadamard gate - a single qubit quantum logic gate which inducts a
superposition with equal probabilities for the two possible qubit states
($\ket{0}$ and $\ket{1}$). It has the following matrix and graphical
representation in quantum circuits:

$H={1\over{\sqrt{2}}}\begin{bmatrix}1&1\\\ 1&-1\end{bmatrix}$ (2.12)

  * •

Pauli-X gate - a single qubit quantum logic gate which acts on a qubit by a
rotation over the $x$ axis of the Bloch sphere with $\pi$ radians. It does the
following transformation of the qubit’s states: $\ket{0}\rightarrow\ket{1}$
and $\ket{1}\rightarrow\ket{0}$:

$X=\begin{bmatrix}0&0\\\ 1&0\end{bmatrix}$ (2.13)

  * •

CNOT gate - a quantum logic gate which acts on two qubits, where one of the
qubits plays the role of a control and the other one is target. When the
control qubit is in state $\ket{1}$ the target state flips:

$CNOT=\begin{bmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&0&1\\\ 0&0&1&0\end{bmatrix}$
(2.14)

  * •

Phase-shift gate ($R_{\phi}$) - a single qubit quantum logic gate which
doesn’t change the basis state $\ket{0}$ and shifts the phase:
$\ket{1}\rightarrow e^{i\phi}\ket{1}$. This way the probabilities for the
states $\ket{0}$ and $\ket{1}$ when the qubit is measured with the main basis
don’t change, but the phase of the quantum state changes:

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

Figure 2: Graphical representation of the symbols for Hadamard, Pauli-X, CNOT
and Phase-shift quantum logic gates in quantum circuits.

###  2.3 Markov Chains

The term Markov chain is derived from the works of the Russian mathematician
Markov (1856 - 1922) where he studies a series of trials in which the outcome
of each event depends only on the previous event. This is the simplest summary
of a series of independent experiments. Today Markov processes find
application in various fields such as biology, physics, computer and
engineering sciences, economics and are useful in analysing practical
problems. Markov chains are mathematical models for time evolutionary
stochastic processes. These processes are a sequence of random events and have
multiple applications which makes them the most important example of
stochastic processes. The main property of such a process is the fact that the
process retains no memory (Norris,, 1998; HAAR,, 1953; Bochner,, 1949) \- no
information about past states of the process is available. This means that the
state in the next moment of time depends only on the current state. In this
dissertation only discrete over time processes with finite discrete state
space have being reviewed.

A discrete over time Markov process could be defined by the following
definitions and assumptions:

  * •

$I$ is a finite countable set.

  * •

Every $i\in I$ is called a state of the process, and $I$ is a state space.

  * •

$\lambda=(\lambda:i\in I)$ is a measure of $I$ if $0\leq\lambda\leq\infty$.

  * •

If $\sum{\lambda}=1$, where $i\in I$, then $\lambda$ is a distribution.

  * •

A random variable $X$ with values in $I$ is a function.

  * •

$X:\Omega\rightarrow I$

$\lambda_{i}=\mathbb{P}(X=i)=\mathbb{P}(\omega:X(\omega)=i)$ (2.16)

Then $\lambda$ defines the distribution of $X$ and $X$ is a random state with
values $i$ with probability $\lambda$. Markov process is a discrete over time
stochastic process only if for every $i_{0},i_{1},i_{2},...,i_{N}\in I$ the
following statement is satisfied:

$\mathbb{P}(X_{0}=i_{0},X_{1}=i_{1},X_{2}=i_{2},...,X_{N}=i_{N})=\lambda
p_{i_{0}i_{1}}p_{i_{1}i_{2}}...p_{i_{N-1}i_{N}}$ (2.17)

A matrix $P=(p_{ij}:i,j\in I)$ is stochastic if every row in the matrix is a
distribution. There are three main Theorems which are used to define if a
random process is Markov (Norris,, 1998; Stroock,, 2014; HAAR,, 1953):

  1. i

A discrete-time random process $(X_{n})_{0}\leq n\leq N$ is Markov
($\lambda,P$) if and only if $\forall i_{0},i_{1},...,i_{n}\in I$:

$\mathbb{P}(X_{0}=i_{0},X_{1}=i_{1},X_{2}=i_{2},...,X_{N}=i_{N})=\lambda
p_{i_{0}i_{1}}p_{i_{1}i_{2}}...p_{i_{N-1}i_{N}}$

  2. ii

Let $(X_{n})_{n}\geq 0$ be Markov ($\lambda,P$). Then, conditional on
$X_{m}=i,(X_{m+n})_{n}\geq 0$ is Markov ($\delta,P$) and is independent of the
random variables $X_{0},X_{1},...,X_{m}$.

  3. iii

Let $(X_{n})_{n}\geq 0$ be Markov ($\lambda,\mathbb{P}$). Then for all
$n,m\geq 0$:

    1. (a)

$\mathbb{P}(X_{n}=j)={(\lambda P^{n})}_{j}$

    2. (b)

$\mathbb{P}_{i}(X_{n}=j)=\mathbb{P}(X_{n+m}=j|X_{m}=i)={p_{ij}}^{(n)}$

In this dissertation a Binary Markov Process is notated as a process which has
only two possible states at any given moment of time. The term Homogeneous
over time LABEL:ASENS1951 means it is a process with stationary transition
probabilities - these transition probabilities do not change with time. When
these two properties (limitations) are applied to the reviewed stochastic
process, the result is a Binary Homogeneous Markov process which is going to
be simulated with quantum computer.

If the Markov chain is defined as follows:

$\mathbb{P}(X_{n+1}=s_{j}|X_{0}=s_{0},X_{1}=s_{1},...,X_{n}=s_{i})=\\\
\mathbb{P}(X_{n+1}=s_{j}|X_{n}=s_{i})$

Then the Markov chain is homogeneous if:

$\mathbb{P}(X_{n+1}=j|X_{n}=i)=\mathbb{P}(X_{1}=j|X_{0}=i),\forall n,i,j$

The probability $\mathbb{P}(X_{n+1}=j|X_{n}=i)$ is a probability for a
transition from state $i$ to state $j$, and the term homogeneous means that
the transition probabilities do not depend on the moment of time $n$.

$p_{ij}=\mathbb{P}(X_{n+1}=j|X_{n}=i)$

Classification of the Markov chain states (Çinlar,, 1975; Karlin and Taylor,,
1981; Snell,, 1994; Ambrose,, 1940):

  * •

accessible \- the state $j$ is accessible from $i$ if, $\exists n\geq
1:{p_{ij}}^{(n)}>0$. If it is not accessible, then if the chain starts from
$i$ state it will never go into the $j$ state.

  * •

communicate \- if state $j$ is accessible from $i$ and $i$ is accessible from
$j$ than these two states ($i$ and $j$) communicate: $i\\\ leftrightarrowj$.
Where it must be true that every state is accessible by itself and communicate
with itself - ${p_{ii}}^{(0)}=\mathbb{P}(X_{0}=i|X_{0}=i)=1$. The
$\leftrightarrow$ has the following properties:

    * –

reflexivity \- $i\leftrightarrow j$.

    * –

symmetry \- $i\leftrightarrow j$ $\iff$ $j\leftrightarrow i$.

    * –

transitivity \- $i\leftrightarrow k$, $k\leftrightarrow j$ $\Rightarrow$
$i\leftrightarrow j$.

  * •

absorbing \- state $j$ is absorbing if no other state can be accessed by it:
$p_{jj}=1$.

  * •

irreducible \- if every two states in the chain are communicating.

  * •

transient \- state $i$ is transient if
$\sum_{n=1}^{\infty}{p_{ii}^{(0)}}=\infty$.

  * •

recurrent \- $\sum_{n=1}^{\infty}{p_{ii}^{(0)}}<\infty$

Using the communicate class of the Markov chains it is possible to decompose a
Markov process into small pieces, analyse those separately and then together
the whole process is understandable relatively easier.

Important properties of a Markov chain are the hitting times and absorption
probabilities. These quantities can be calculated by the linear equations
associated with the transition matrix P (Norris,, 1998):

  1. i

The hitting probabilities vector $\alpha(h)^{A}=(\alpha(h)_{i}^{A}:i\in I)$is
the minimal non-negative solution to the system of linear equations:

$\begin{cases}k_{i}^{A}=0$ for $i\in A\\\ k_{i}^{A}=1+\sum_{j\notin
A}{p_{ij}k_{j}^{A}}$ for $i\notin A\end{cases}$

The minimality in this case means that $x_{i}\geq h_{i}$ for all $i$ if $x$ is
another solution with $x_{i}\geq 0$ for $\forall i$.

  2. ii

The vector of mean hitting times $k^{A}=(k^{A}:i\in I)$ is the minimal non-
negative solution to the system of linear equations:

$\begin{cases}k_{i}^{A}=0$ for $i\in A\\\ k_{i}^{A}=1+\sum_{j\notin
A}{p_{ij}k_{j}^{A}}$ for $i\notin A\end{cases}$

Strong Markov property The Strong Markov property is based on the concept for
the Markov property of a stochastic process, e.g. the probabilistic behaviour
of the chain of events in the next moment of time depends only on the current
state LABEL:Ray1956. Except that in addition the time T is a random quantity
and has special properties:

$T$ is stopping time, which takes values {1,2,…} such that $T=n$ can be
determined by the chain values $X_{0},X_{1},...,X_{n}$.

If $T$ is a stopping time, for $m\geq 1$:

$\mathbb{P}(X_{T+m}=j|X_{k}=x_{k},0\leq
k<T;X_{T}=i)=\mathbb{P}(X_{T+m}=j|X_{T}=i)$

Applications

Markov chains applications can be found in many scientific fields including
biological modelling, queuing, Markov decision processes, Markov chain Monte
Carlo and many more. Using Markov chains appropriate models for systems with
high complexity could be built. An example of biological interpretation for a
stochastic process described by Markov chains is a well known problem for a
virus mutation (Norris,, 1998).

Imagine a virus can exists in N different strains and each time the virus
either stay at the same strain or with a probability $\alpha$ mutates to
another one chosen at random. What would be the probability that $n^{th}$
generation strain is the same as the starting one ($0^{th}$)?

This process can be modelled as a Markov chain with $NxN$ transition matrix
$P$, where:

$p_{ii}=1-\alpha,p_{ij}={\alpha/(N-1)}$ for $i\neq j$.

The solution of this problem is found in the computation of $p_{11}^{(n)}$. At
any moment of time a transition from initial state with probability $\alpha$
is made, and a transition to the initial state with probability
$\alpha/(N-1)$.

If $\beta$ is put to be ${\alpha/(N-1)}$, the transition matrix has the form:

$P=\begin{pmatrix}1-\alpha&\alpha\\\ \beta&1-\beta\par\end{pmatrix}$

Because of the recurrence relation for $p_{11}^{(n)}$:

$p_{11}^{(n+1)}=(1-\alpha-\beta)p_{11}^{(n)}+\beta$, $p_{11}^{(}0)=1$.

The desired probability is:

${1\over N}+\left(1-{1\over N}\right)\left(1-{\alpha N\over N-1}\right)^{n}$

###  2.4 Software Tools and Frameworks for Quantum Computing

Nowadays three are the most popular open-source quantum computing software
frameworks: QISKIT, D-Wave Ocean and Forest SDK. QISKIT and Forest SDK are
frameworks for gate-based (circuit) modelling in quantum computing and these
are developed by IBM and Rigetti Computing respectively. For the purpose of
this dissertation the IBM’s QISKIT framework has been used. Also IBM has
provided access to their real quantum processor available on the cloud
platform.

What is QISKIT? QISKIT is a python framework that allows the creation and
execution of algorithms for quantum computers. These algorithms are
representation of quantum systems and contain all the information about how
the systems should be created and manipulated.

The QISKIT framework consists of four main parts (Abraham et al.,, 2019):

  * •

Terra - this is the software foundation for the stack, containing tools for
building quantum programs at level of circuits and pulses. It also provides
possibility for optimization depending on the physical quantum processor and
managing the execution of the quantum programs on cloud available backends.
The software stack for Terra includes:

    * –

User Inputs (Quantum Circuits and Pulse schedules).

    * –

Transpiler (Optimization passes).

    * –

Providers (Qiskit Aer. IBM Q, Others).

    * –

Visualization and Quantum Information Tools (Histograms, States,
Entanglement).

  * •

Aer - it provides optimized C++ high-performance quantum simulator backends
for execution of quantum circuits. Also it contains tools for performing
realistic noisy simulations based on configurable noise models. Its software
stack includes:

    * –

Qiskit Terra.

    * –

Noise simulation (Noise models, Quantum errors).

    * –

Backends (QasmSimulator, StatevectorSimulator, NoisySimulator).

    * –

Jobs and Results (Counts, Memory, Statevector, Unitary, Snapshots).

  * •

Aqua - this is library of cross-domain quantum algorithms used to build near-
term quantum applications. It is extensible with possibility for adding new
custom quantum algorithms. The current version allows experiments on
chemistry, AI, finance and optimization applications. The software stack
includes:

    * –

Qiskit Aqua Translations (Chemistry, Optimization, AI, Finance).

    * –

Quantum Algoritms (QPE, Grover, HHL, QSVM, VQE, QAOA).

    * –

Qiskit Terra

    * –

Providers (Qiskit Aer. IBM Q, Others).

  * •

Ignis - this is a framework containing experiments for understanding and
mitigating noise in quantum circuits. The experiments are classified in three
groups:

    * –

Characterization - measure noise parameters.

    * –

Verification - verify gate and small circuits.

    * –

Mitigation - run calibration circuits.

Its software stack includes:

    * –

Qiskit Ignis Experiments (Quantum circuits or pusle schedules).

    * –

Qiskit Terra

    * –

Providers (Qiskit Aer. IBM Q, Others).

    * –

Fitter/Filter (Fit to a model or plot results).

Using QISKIT the quantum processors can be remotely accessed. The main
programming language is Python version at least 3.5. The main process in
quantum software development could be divided in three steps:

  * •

Build: This step includes the design of the quantum circuit representing the
problem’s solution.

  * •

Execute: Executing quantum circuits on various hardware back-ends (real
quantum processors or quantum simulators).

  * •

Analyze: Calculation and visualization (histograms) of generalized results and
analysis.

The process above could be also described in more details:

  * •

Import the necessary libraries and modules in Python. The minimal required
pack of libraries and modules used in this dissertation are the following:

    * –

Numpy \- a fundamental packet in Python used for scientific programming. It
consists of powerful N-size array type objects, complex mathematical
functions, linear algebra solutions, random number generator, Fourier
transform, integration tools for code in C++ and Fortran.

    * –

QuantumCircuit which is part of QISKIT framework and includes all available
quantum operations. It could be also said that this is the ”machine language”
for the quantum systems description.

    * –

Execute is also modul in QISKIT and it executes the quantum circuits on varios
back-ends.

    * –

Aer module which enables the usage of simulation hardware.

    * –

plot_histogram is a method for creating histograms and results visualization.

Figure 3: Required libraries, packages and modules in Python for building a
quantum program.

  * •

Variables initialization.

  * •

Adding quantum logic gates to design the desired quantum circuit.

  * •

Quantum circuit visualization and verification. This could be achieved by
using the circuit.draw() method. Using this method the circuit is visualized
so that the qubit order is ascendant and the $0^{th}$ qubit is visualized on
top of the circuit. The quantum circuits must be read from left to right and
the gates located more to the right are being executed later in time by the
quantum back-end.

  * •

Experiment simulation on the selected back-end.

Figure 4: Quantum experiment simulation on selected back-end and result
extraction.

  * •

Visualization of the results from the experiments. Beside the histogram plot,
there are many other possibilities for result visualization in QISKIT,
including interactive methods.

###  2.5 Problem Description

Quantum computers use the effects of quantum mechanics such as coherence and
entanglement to process information differently from classical computers.
Quantum computers can handle two types of data - classic and quantum. Classic
data must be structured as input before being processed by quantum computers.
Quantum information processing finds patterns (structures) in the data by
presenting them as certain quantum mechanical states and then executing basic
quantum subroutines. With only 2 possible states, the binary homogeneous
Markov process, which transition probabilities does not change over time,
enables these states to be represented by qubits, the main challenge being the
creation and tuning of quantum logic gates.

##  3 Method and Algorithms

###  3.1 Method for quantum simulation of a binary homogeneous Markov process

The simulation of a binary homogeneous Markov process using quantum computer
requires the simulated process to be described as a quantum-mechanical system.
In every moment of time the process is represented by a single qubit, where
its two possible states are the two qubit states - $\ket{0}$ and $\ket{1}$.
The starting point for the simulation is a qubit in a superposition of the
desired probability distribution for the stochastic process ( 2.7, 2.11).

This system updates its states by 2x1 transition matrix and for every discrete
moment of time it goes from state $i$ to state $i+1$, where the system
representation is a single qubit for every $i^{th}$ moment. The current state
depends only on the state in the previous moment of time and the process
retains no memory. This means no history must be remembered and the only
required connections between states are those from current to the next state.
The quantum representation of this connections is done by one of the
fundamental properties of the quantum systems - entanglement. The quantum
entangled states represent the connection between 2 or more qubits where the
state of one qubit can not be described without the knowledge of the states of
the others. With this method for quantum simulation of a binary homogeneous
Markov process, an entangled state is created between every two sequential
qubits, where the each qubit plays the role of the control for the next one.
This way a directed chain is constructed using entangled qubits. The state of
each qubit defines the state of the next one, starting from qubit $q_{0}$
which acts as a control for the $q_{1}$, $q_{1}$ acts as a control for $q_{2}$
and so on. This way every qubit in the chain except the first and the last
($q_{0}$ and $q_{N}$) acts as a control qubit for the next one and a target
qubit for the previous. If $N$ is the number of discrete time steps for a
binary homogeneous Markov process, then an $N$-length quantum register is
needed for the quantum simulation.

Markov process division on parts

Figure 5: Hierarchical Tree structure showing the full set of possible paths
for a binary homogeneous Markov process which is described as a quantum-
mechanical system.

Figure 6: A binary homogeneous Markov process visualization using chain of
qubits. The red arrow shows the entanglement direction (the beginning of the
arrow is the control qubit and the end of the arrow is the target qubit). In
every discrete moment of time the process is represented by a single qubit,
which is in an entangled state with the next one. For a quantum simulation of
a process with N number of discrete time steps, a quantum register with N
qubits is required.

###  3.2 Algorithm for determining the angle of rotation for a qubit over the
X axis

An implementation of a new quantum logic gate in QISKIT framework is required
so that the rotation over the X axis could be achieved. This is the
$\sqrt[n]{X}$ gate and it is a single qubit quantum logic gate with the
following matrix representation:

$\sqrt[n]{X}={1\over{2}}\begin{vmatrix}1+e^{i\pi\over{n}}&1-e^{i\pi\over{n}}\\\
1-e^{i\pi\over{n}}&1+e^{i\pi\over{n}}\end{vmatrix}$ (3.1)

The realization of this gate is achieved using some of the basis standard
quantum logic gates in QISKIT:

  * •

Hadamard gate (see equation 2.12

  * •

U1 gate, which is the QISKIT equivalent of $R_{z}$ gate. This is a single
qubit quantum logic gate, which does a rotation over the $Z$ axis where the
angle is defined in radians. It has the following matrix representation:

$U1=R_{z}=\sqrt[n]{Z}=\begin{vmatrix}1&0\\\ 0&e^{i\pi\over{n}}\end{vmatrix}$
(3.2)

Using the rule for enclosure of a Pauli-Z gate with Hadamard gates to create
Pauli-X gate (Aharonov,, 2003; Nielsen and Chuang,, 2011):

$H\sqrt[n]{Z}H=\sqrt[n]{X}$ (3.3)

Where the probabilities for the two states of the qubit - $\ket{0}$ and
$\ket{1}$ are respectively $\left|{{\alpha_{0}}^{2}}\right|$ and
$\left|{{\alpha_{1}}^{2}}\right|$:

$\left|{{\alpha_{0}}^{2}}\right|=\left|{1+e^{i\pi\over n}}\over
2\right|and\left|{{\alpha_{1}}^{2}}\right|=\left|{1-e^{i\pi\over n}}\over
2\right|$ (3.4)

or

$\left|{{\alpha_{0}}^{2}}\right|=\left|{1-e^{i\pi\over n}}\over
2\right|and\left|{{\alpha_{1}}^{2}}\right|=\left|{1+e^{i\pi\over n}}\over
2\right|$ (3.5)

The algorithm for determining the angle of rotation for a qubit over the X
axis is actually reduced to solving the following equation, where n is the
unknown variable:

$\left|{{\alpha_{0}}^{2}}\right|=\left|{1+e^{i\pi\over n}}2\right|$ (3.6)

Using the Euler’s formula from complex analysis (Euler,, 1748) for connection
between trigonometrical functions and the complex exponent the following
solution of 3.6 is found:

$n={\pi\over acos(2\left|{{\alpha_{0}}^{2}}\right|-1)}$ (3.7)

The denominator of the right-hand side of the equation is the so-called
’lambda’ parameter in the QISKIT software framework, which determines the
angle of rotation of the qubit along the X axis.

###  3.3 Building a quantum logic gate C$\sqrt[n]{X}$

The construction of a quantum logical gate that acts on two qubits, creating
an etangled state between them, is accomplished by a unitary transformation of
the states of the qubits. Thus, at two points in time, the evolution of the
state change from point 1 to point 2 is described by a unitary matrix. This
quantum logic gate will be called controlled- $\sqrt[n]{X}$ ($C\sqrt[n]{X}$).
Knowing the matrix representation of the gate shown in 3.1, it is possible to
construct a controlled gate (Barenco et al.,, 1995) with the following matrix
representation:

$C\sqrt[n]{X}=\begin{vmatrix}1&0&0&0\\\ 0&1&0&0\\\
0&0&{1+e^{i\pi\over{n}}}\over 2&{1-e^{i\pi\over{n}}}\over 2\\\
0&0&{1-e^{i\pi\over{n}}}\over 2&{1+e^{i\pi\over{n}}}\over 2\end{vmatrix}$
(3.8)

Thus, the state of the first qubit that plays the role of control does not
change, but the state of the second qubit (target) changes depending on the
state of the first. The roots of the controlled Pauli-Z gate (two-qubit gate
that performs rotation along the Z axis on the target qubit, depending on the
state of the control qubit) can be constructed by phase shifting by half the
desired angle over the Z axis with opposite direction, after which the two
qubits are phase-shifted along the Z axis by half the desired angle, applying
a CNOT gate between the two qubit turns. Thus, enclosing this operation for
the second qubit (the target qubit) with Adamar gates, is obtained the
$C\sqrt[n]{X}$.

Figure 7: Quantum circuit for construction of a two-qubit quantum logic gate
that does a controlled phase-shift over the Z axis for the target qubit.

Figure 8: Quantum circuit for construction of a two-qubit quantum logic gate
that does a controlled phase-shift over the X axis for the target qubit.

As seen from figures 7 and 8 the construction of $C\sqrt[n]{X}$ is achieved
only by using three basic quantum logic gates which are supposed to be
available on any modern platform for gate-based quantum computing.

###  3.4 Algorithm for finding the complete set of possible paths for a
stochastic process described by a binary homogeneous Markov model

This algorithm consists of four steps described bellow.

  1. i

Calculate the rotation over the X axis for the $\sqrt[n]{X}$ and
C$\sqrt[n]{X}$ gates so that these are representing the Markov process
transition probabilities.

  2. ii

Initializing the system in the desired superposition of all qubits by applying
$\sqrt[n]{X}$ to each qubit in the register. For example, if the desired
binary homogeneous Markov model is absorbent in the state $\ket{0}$ \- all the
qubits must be initialized in the state $\ket{0}$ with a probability of 1
(deterministic state) (Note: if $q_{0}$ is initialized in the state $\ket{0}$
with probability of 1, the process will not undergo any development because it
will enter its absorbing state from the first discrete moment of time).

  3. iii

Repeat the following unitary operation n-1 times: $C\sqrt[n]{X}$ for all
consecutive pairs of qubits from $q_{0}$ to $q_{n-1}$.

  4. iv

Measuring the resultant state of a quantum system. As a result of the
measurement, the probability distribution for each possible path of the binary
homogeneous Markov process is obtained. Each possible state of the quantum
register corresponds to one possible path.

Conclude Using the method presented in this chapter to simulate a binary
homogeneous Markov process, the distinguishing properties of quantum computers
- superposition, probability calculations and entangled states can be
effectively used. To implement an algorithm based on this method, a new
quantum logic gate was implemented to create entangled states between two
qubits. This gate performs a rotation along the X-axis for the qubit acting as
a target with a predetermined angle $\Theta$, this angle (offset) accurately
represents the transient probabilities for the given Markov process when the
control qubit is in a state $\ket{1}$. 222Representation of the transient
probabilities for the given Markov in author’s work (Author’s publication
iii). An algorithm has been developed to determine the rotation of the qubit
along the X axis, by which the necessary distributions for the transient
probabilities of a binary homogeneous Markov process are introduced.
333Algorithm for determining qubit rotation over the X axis in author’s work
(Author’s publication i and ii). An algorithm has been developed to find the
full set of possible paths for a stochastic process, described by a binary
homogeneous Markov model.

##  4 Applications

###  4.1 Implementation of a quantum logic gate which rotates the qubit with
custom angle over the X axis

The realization of a quantum logic gate which does a phase-shift over the X
axis for a single qubit is somehow straightforward and easy task using QISKIT
framework. It could be achieved by using the following standard quantum logic
gate available in the framework:

  * •

Hadamard gate - equation 2.12

  * •

U1 gate, which is the equivalent of a $R_{z}$ gate - equation 3.2

And using the rule for bracketing the Pauli-Z gate with Hadamard gates to
create a Pauli-X gate ( equation 3.3), the following quantum circuit is
constructed:

Figure 9: Graphical representation of a quantum logic gate, which shifts the
qubit over the X axis with custom angle in QISKIT framework.

###  4.2 Implementation of a controlled quantum logic gate which rotates the
qubit with custom angle over the X axis

This is so-called controlled $C\sqrt[n]{X}$ gate and it acts on two qubits
where the first one plays the role of control and the second one is the
target. The purpose of this gate is to change the state of the target qubit
only if the control is in state $\ket{1}$. The quantum circuit which
represents this logic gate is shown on figure 8. The implementation in the
QISKIT framework is similar to the one done for the $\sqrt[n]{X}$ gate, and a
validation circuit should be designed, so that the gate’s conditional fire is
validated. The verification and validation of the $C\sqrt[n]{X}$ gate could be
achieved by using a modified variant of the quantum circuit shown on figure 8.
And the new circuit gets the following look:

Figure 10: Quantum circuit used for verification and validation of the
$C\sqrt[n]{X}$ gate, where the gate will always fire.

The difference between 8 and 10 is the initialization of the qubits in the
beginning of the quantum operation, before the actual $C\sqrt[n]{X}$ gate
application. As it is shown on the figure 10, the control qubit $q_{0}$ is in
state $\ket{1}$ and the target qubit $q_{1}$ is in state $\ket{0}$. The fact
that the control qubit will always be in state $\ket{1}$ means that the
$C\sqrt[n]{X}$ gate will always fire and the target qubit $q_{1}$ will be
rotated over its X axis with the desired angle. The most right part in the
quantum circuit is the quantum measurement operator for the two qubits. Using
this circuit the quantum operation will verify the $C\sqrt[n]{X}$ gate. Also
another quantum circuits could be use for more detailed experiments and
results, regarding the validation and verification of this quantum logic gate.
For example the control qubit $q_{0}$ could be superposed using the Hadamard
gate when initialized, so that it will be with equal probabilities to be in
state $\ket{0}$ and $\ket{1}$. An example quantum circuit is shown on figure

Figure 11: Quantum circuit example for verification and validation of the
$C\sqrt[n]{X}$ gate, where the gate will fire only 50% of the time.

###  4.3 Development of a quantum circuit allowing modelling on a real quantum
processor of any stochastic problem described by a binary homogeneous Markov
model.

Let’s look at a system that has two possible states, and at any one time is in
one of those two states. By presenting this system as quantum information
system - by using 1 qubit, the two orthonormal states of the qubit will be
analogous to the states of the system. The system is updated as states are
defined only in certain values over time - i.e. it can be considered as a
discrete signal. When updating its state from moment $i$ to moment $i+1$, it
is represented by a single qubit. The connection between the present and the
next state of the system is realized by one of the basic quantum properties -
the entangled states. Each qubit in the quantum circuit is in an entangled
state with the next one by applying the $C\sqrt[n]{X}$ gate between these, so
that the qubit $q_{1}$ is control qubit for the quantum logic gate and the
qubit $q_{2}$ is the target, $q_{2}$ is control for $q_{3}$ and so on
$q_{k-1}$ is control for $q_{k}$. Where $k$ is the length of the quantum
register, which represents the number of the discrete time steps in the
evolution of the process.

Figure 12: Quantum circuit showing the initialization of the binary
homogeneous Markov process.

Figure 13: Quantum circuit showing the repetitive unitary operation for the
binary homogeneous Markov process.

Figure 14: Quantum circuit showing the schematic representation of an
algorithm for quantum simulation of a binary homogeneous Markov process.

The quantum circuit model for application of this algorithm on a real hardware
is shown on figure 14 and this circuit can be simplified in two steps - first
the quantum register is initialized in the desired quantum state using the
$\sqrt[n]{X}$ quantum logic gate applied on every qubit in this register (
figure 12 and second - a unitary operation is applied throught the controlled
quantum logic gate $C\sqrt[n]{X}$ between every two consecutive qubits like
described in the previous paragraph (step $iii$ in the 3.4).

###  4.4 Development of an experimental quantum circuit, which to be
implemented on both a high-performance quantum simulator and real quantum
processors at IBM’s cloud service through the QISIKT software framework.

Since the algorithm described in the previous chapter (4.3) allows for many
variations of quantum circuits depending on the structure of the process for
which a model is to be constructed, in this dissertation an example of a
process will be described starting with an initial probability distribution
for its two states - $\alpha$ for a state $\ket{0}$, and $\alpha-1$ for state
$\ket{1}$. As state $\ket{0}$ it will be an absorbing state for the process.
For convenience, as well as allowing the algorithm to run on the maximum
number of real quantum processors in the IBM cloud platform, there will be a
limit on the number of steps for the stochastic process to be 3. Let k = 2,
which means that $i_{0},i_{1},i_{2}$ and the distribution P form a Markov
chain in the following order:

$X_{0}\rightarrow X_{1}\rightarrow X_{2}$ (4.1)

Following the Markov rule for a stochastic process, all the information about
the $X_{2}$ state is in $X_{1}$, so if the task is to find the $X_{2}$ state,
there is no need to know the $X_{0}$ state. Every $X_{i}$ for the process is
represented in the quantum system with its corresponding qubit $q_{i}$ and the
Markov property (the process retains no memory) is represented in a quantum
way by applying the $C\sqrt[n]{X}$ gate as described in 4.3.

Figure 15: Quantum circuit showing the quantum simulation of a binary
homogeneous Markov process with absorbing state in $\ket{0}$.

N=3 defines the required length of the quantum register for a successful
simulation ($k=2^{N}-1$). All possible states for the quantum register are 8,
so its superposition hypothetically could be constructed by 8 ket vectors:

$\begin{split}\ket{\Psi}=\alpha_{0}\ket{000}+\alpha_{1}\ket{001}+\alpha_{2}\ket{010}+\alpha_{3}\ket{011}+\\\
+\alpha_{4}\ket{100}+\alpha_{5}\ket{101}+\alpha_{6}\ket{110}+\alpha_{7}\ket{111}\end{split}$
(4.2)

The first step of this quantum simulation is the register to be initialized in
state $1\ket{000}$. The next step is the application of a $\sqrt[n]{X}$
quantum logic gate on the first qubit ($q_{0}$) - the first discrete time step
for the binary homogeneous Markov process. This way the initial probability
distribution is initialized as probability $\alpha$ for state $\ket{0}$ and
$1-\alpha$ for state $\ket{1}$. Where state $\ket{0}$ is absorbing state for
the process following the limitations described in 4.3.

$\ket{\sqrt[n]{X^{q_{0}}}}={{1+e^{i\pi\over n}}\over
2}\ket{000}+{{1-e^{i\pi\over n}}\over 2}\ket{001}$ (4.3)

The final superposition of the quantum register is achieved with applying the
$C\sqrt[n]{X}$ quantum logic gate as shown in figure 15.

###  4.5 Conclusion

The constructed quantum logic gates are created by using the three standard
basic quantum logic gates available in each modern quantum computing platform.
The development of software in the Python programming language and the use of
the Jupyter Notebook open source software development environment allow
experimental research on various hardware devices - both on a real quantum
processor and on high-performance quantum simulators. The synthesized
algorithm simulates a binary homogeneous Markov process by representing it
through the superposition of the quantum register. When measuring the quantum
register, the full set of possible paths for the process is obtained. The next
chapter will introduce the algorithm in the QISKIT software framework on
various hardware devices on the IBM cloud platform. 444Binary homogeneous
Markov process simulation with quantum computer in author’s work (Author’s
publication iii).

##  5 Experimental Verification

###  5.1 Implementation considerations

The algorithm for binary homogeneous Markov process simulation seems easy to
implement in modern quantum computing systems compared to other quantum-
mechanical algorithms, and the following advantages can be highlighted:

  * •

All the quantum transformations that are needed are:

    * –

Hadamard gate.

    * –

Z axis rotation gate.

    * –

CNOT gate.

These transformations are relatively simple, and are available as ready-to-use
solutions in the QSIKIT software framework.

  * •

The implementation requires only a CNOT gate, as a two-qubit gate, with
entanglement between the control qubit and the target qubit are between any
two consecutive ones, which is possible in a large number of hardware
configurations.

  * •

The controlled phase rotation at the $C\sqrt[n]{X}$ gate can be accomplished
by using classical computer memory to preserve the probability distributions
for the stochastic process. The quantum measuring gives as a result the
complete set of possible paths for the binary homogeneous Markov process,
given as the superposition of the measured quantum register.

When implementing quantum algorithms on real hardware platforms, one of the
main considerations is the hardware limitations of quantum processors. In an
ideal world, it would be great to have full control over the qubits so that
operations can be performed allowing entangled states between any two (or
more) qubits in the system. Unfortunately, in today’s quantum processor
hardware solutions, there are many limitations associated with this quantum
property. A fundamental rule of gate-based superconducting quantum processors
in the IBM platform is that for multiple-qubit gates, the control qubit(s)
must be at a higher frequency of the resonant oscillator, than the target one.
With exceptions to this rule, the direction of the gate must be reversed if
degenerative effects on the target qubit are observed as a result of the
higher frequency of the controller. The next paragraph will look at existing
quantum processors in the IBM cloud platform that will be used to verify and
validate the quantum gate $C\sqrt[n]{X}$, as well as the development of an
experimental quantum circuit for the implementation of the algorithm for
finding the full set of possible paths for a stochastic process described by a
binary homogeneous Markov model.

Figure 16: Configuration maps of quantum processors in the IBM cloud platform
that have been subjected to experimental verification and validation. a)
T-shape layout of the qubits used in Ourence, Vigo, London, Burlington, Essex
processors. b) Diagram with bow-tie type used with the Yorktown processor. c)
Directional ladder geometry diagram of Melbourne processor.

The available quantum processors in the IBM cloud platform that have been
experimented with in this thesis are the following 5-qubit (Ourence, Vigo,
London, Burlington, Essex, Yorktown) and a 14-qubit (Melbourne) processors:

  * •

Ourence, Vigo, London, Burlington, Essex - IBM’s 5-qubit quantum systems,
whose configuration maps have a graphical representation of figure 16a.

  * •

Yorktown - IBM’s 5-qubit quantum system. Connectivity in the device is
accomplished by two coplanar waveguide resonators with resonances of about 6.6
Ghz and 7 Ghz. Each of the qubits has its own waveguide for control and
measurement. The configuration map has a graphical representation shown in
figure 16b.

  * •

Melbourne - IBM quantum directional ladder system. The connectivity of the
device is made up of 22 coplanar waveguide ”bus” resonators, each of which is
connected to 2 qubits, using 3 different configuration frequencies - 6.25 GHz,
6.45 GHz and 6.65 GHz. The configuration map has a graphical representation
shown in figure 16c.

###  5.2 Verification and validation of $C\sqrt[n]{X}$ quantum logic gate

As described in 4 and the circuits shown in figures 9 and
LABEL:fig:CnX_validation, quantum circuits have been designed to verify and
validate the $C\sqrt[n]{X}$ gate.

Figure 17: Quantum circuits for gate verification and validation.
a) Circuit in which the controlled qubit is $q_{1}$.
b) Circuit with inverted qubit functions: $q_{0}$ is the objective and $q_{1}$
is the control.

Both circuits, that are shown on figure 17 are applied to both a high-
performance quantum simulator and the following real quantum processors in the
IBM cloud platform:

  * •

High-performance quantum simulator

Figure 18: Results from the implementation of $C\sqrt[n]{X}$ quantum gate
validation and verification circuits on a high-performance quantum simulator.
a) Results of circuit 17a.
b) Outcome of circuit 17b

  * •

Ourence (Avg. T1: 88.7, Avg. T2: 63.3)

Figure 19: Results from the implementation of $C\sqrt[n]{X}$ quantum gate
validation and verification circuits on a real quantum processor Ourence.
a) Results of circuit 17a.
b) Results of circuit 17b

  * •

Vigo (Avg. T1: 99.1, Avg. T2: 72.5)

Figure 20:
Results from the implementation of $C\sqrt[n]{X}$ quantum gate validation and
verification circuits on a real quantum processor Vigo.
a) Results of circuit 17a.
b) Results of circuit 17b

  * •

London (Avg. T1: 66.1, Avg. T2: 71.7)

Figure 21: Results from the implementation of $C\sqrt[n]{X}$ quantum gate
validation and verification circuits on a real quantum processor London.
a) Results of circuit 17a.
b) Results of circuit 17b

  * •

Burlington (Avg. T1: 67.8, Avg. T2: 73.7)

Figure 22: Results from the implementation of $C\sqrt[n]{X}$ quantum gate
validation and verification circuits on a real quantum processor Burlington.
a) Results of circuit 17a.
b) Results of circuit 17b

  * •

Essex (Avg. T1: 118.5, Avg. T2: 81.6)

Figure 23: Results from the implementation of $C\sqrt[n]{X}$ quantum gate
validation and verification circuits on a real quantum processor Essex.
a) Results of circuit 17a.
b) Results of circuit 17b

  * •

Yorktown (Avg. T1: 56.7, Avg. T2: 47.6)

Figure 24: Results from the implementation of $C\sqrt[n]{X}$ quantum gate
validation and verification circuits on a real quantum processor Yorktown.
a) Results of circuit 17a.
b) Results of circuit 17b

  * •

Melbourne (Avg. T1: 51.7, Avg. T2: 71.9)

Figure 25: Results from the implementation of $C\sqrt[n]{X}$ quantum gate
validation and verification circuits on a real quantum processor Melbourne.
a) Results of circuit 17a.
b) Results of circuit 17b

###  5.3 Results of quantum simulation of a binary homogeneous Markov process
on various hardware back-ends

The quantum circuit used to simulate the binary homogeneous Markov process
explained in 4 shown in figure 15 is implemented in two variants - the CNOT
gates are respectively {CX_01, CX_12} and {CX_21, CX_10}. The two circuits are
as follows:

Figure 26: Quantum circuit for simulation of a binary homogeneous Markov
process with absorbin state in $\ket{0}$ on a high-performance quantum
simulator and real quantum processors in IBM cloud platform with CNOT gates
directions {CX_21, CX_10} respectively.

Figure 27: Quantum circuit for simulation of a binary homogeneous Markov
process with absorbing state in $\ket{0}$ on a high-performance quantum
simulator and real quantum processors in IBM cloud platform with CNOT gates
directions {CX_01, CX_12} respectively.

The two quantum circuits 26 and 27 have been executed both on high-performance
simulator and several real quantum processors in the cloud platform of IBM.
The results are as follows:

  * •

High-performance quantum simulator

Figure 28: Results of the execution of quantum circuits for the simulation of
a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a
high-performance quantum simulator.
a) Results of circuit 26.
b) Outcome of circuit 27.

  * •

Ourence (Avg. T1: 88.7, Avg. T2: 63.3)

Figure 29: Results of the execution of quantum circuits for the simulation of
a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a
real quantum processor Ourence.
a) Results of circuit 26.
b) Outcome of circuit 27.

  * •

Vigo (Avg. T1: 99.1, Avg. T2: 72.5)

Figure 30: Results of the execution of quantum circuits for the simulation of
a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a
real quantum processor Vigo.
a) Results of circuit 26.
b) Outcome of circuit 27.

  * •

London (Avg. T1: 66.1, Avg. T2: 71.7)

Figure 31: Results of the execution of quantum circuits for the simulation of
a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a
real quantum processor London.
a) Results of circuit 26.
b) Outcome of circuit 27.

  * •

Burlington (Avg. T1: 67.8, Avg. T2: 73.7)

Figure 32: Results of the execution of quantum circuits for the simulation of
a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a
real quantum processor Burlington.
a) Results of circuit 26.
b) Outcome of circuit 27.

  * •

Essex (Avg. T1: 118.5, Avg. T2: 81.6)

Figure 33: Results of the execution of quantum circuits for the simulation of
a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a
real quantum processor Essex.
a) Results of circuit 26.
b) Outcome of circuit 27.

  * •

Yorktown (Avg. T1: 56.7, Avg. T2: 47.6)

Figure 34: Results of the execution of quantum circuits for the simulation of
a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a
real quantum processor Yorktown.
a) Results of circuit 26.
b) Outcome of circuit 27.

  * •

Melbourne (Avg. T1: 51.7, Avg. T2: 71.9)

Figure 35: Results of the execution of quantum circuits for the simulation of
a homogeneous binary Markov process with an absorbing state in $\ket{0}$ on a
real quantum processor Melbourne.
a) Results of circuit 26.
b) Outcome of circuit 27.

###  5.4 Analysis of the results

Since quantum computers are still in their early stage of development, the
qubits (observed environment) interact with the (unobserved) environment,
which causes the system and its environment to become entangled driving
decoherence of the system. This decoherence can be reversed in theory by
applying a recovery transformation, which entangles the data with ancilla. The
ancilla introduced can be discarded and replaced with another fresh ancilla
for any future rounds in the error correction. Another obstacle on the road of
mass usage of quantum computers is the limited lifetime of a qubit. Usually
the best qubits are available for much less than a second due to this
decoherence. Large-scale quantum algorithms need qubit lifetime in order of
hours or even days.

The approaches that are used in IBM’s platform for quantum computing could be
classified in two classes - hardware improvement for better qubits (reduce
noise coming from the environment, build tools for better qubit control, etc.)
and error correction techniques. Despite the enormous improvements in the
hardware in the past decade, there are a lot of limitations of this approach.
On the other hand, the quantum error correction is a relatively new approach,
which allows researchers and engineers to achieve better performance of the
quantum computers. The techniques used here are redundant encoding of
information, diagnose and correct errors, and in theory - unlimited qubit
lifetime.

Redundant encoding is a technique for encoding information from one qubit into
many qubits, which allows the diagnostics and correction of quantum errors
caused by decoherence. The redundancy was first introduced by Peter Shor in
(Shor,, 1995), where he reduces the effect of decoherence by assuming that the
decoherence acts independently on each qubit in the quantum system. Those
quantum codes introduced by Shor find applications in many areas of quantum
research - better and scalable quantum computers (Extend qubit lifetime and
improve precision of quantum logic gates), quantum Shannon theory (Reliable
transmission of qubits through noisy quantum channels), topological quantum
order (Explain robustness of ground state degeneracy to local pertubations),
quantum gravity and more (Holographic quantum codes).

Quantum error correction could simply be explained this way:

$\ket{\Psi}\rightarrow Encoding\ket{\overline{\Psi}}\rightarrow
Error\rightarrow Decoding\ket{\Psi}\rightarrow\ket{\Psi}$

and one of main tasks here is how to map this (one qubit) state $\ket{\Psi}$
to multi qubit. The actual error correction and diagnosis happens in the
decoding state, where from multiple $\ket{\overline{\Psi}}$ states, the result
is a single $\ket{\Psi}$ state.

  * •

Encoding The task here is to encode k logical qubits into n physical qubits
and it could basically be represented as a linear subspace of orthonormal
basis. The k and n define the dimension of the subspace.

$C=(\mathbb{C}^{2})^{\otimes n}$

$dim(C)=2^{k}$

Where the codespace is C, the codeword is any state $\ket{\overline{\Psi}}\in
C$, and the error is n-qubit linear operator, which might not be unitary.

  * •

Error The conditions to detect an error E with quantum code are:

$\begin{cases}\bra{\overline{x}}E\ket{\overline{y}}=0\\\
\bra{\overline{x}}E\ket{\overline{x}}=\bra{\overline{y}}E\ket{\overline{y}}\end{cases}$
for all $x\neq y$

* All diagonal matrix elements must be zeroes. And all diagonal matrix elements must be the same.

  * •

Decoding The quantum code C can detect an error E if and only if:

$\Pi_{C}E\Pi_{C}=\eta\Pi_{C}$

The $\eta$ is a complex number.

The $\Pi_{C}$ is the codespace projector.

The relations in quantum mechanical systems are part of the foundational
features in quantum physics - non-linearity and Bell’s inequality violations.
As shown in (Spehner et al.,, 2017), the geometric discord and the discord of
response with Hellinger distance are reliable enough and offer non-
computational expensive measures. If a bipartite quantum system AB is being
considered, formed by putting together two quantum systems - A and B, with a
finite dimensional Hilbert space $\mathcal{H}_{AB}$:

$n_{a}=dim(\mathcal{H}_{A})<\infty$ and $n_{b}=dim(\mathcal{H}_{B})<\infty$.

A state of AB is then given by a density matrix $\rho$, which is a non-
negative operator on $\mathcal{H}_{AB}$ and with unit trace tr $\rho$ = 1.

If there is a finite sample space ${1,2,...,n}$ and the
$\mathcal{E}_{clas}={p\in\mathcal{R}_{+}^{n};\sum{p_{k}}=1}$. The classical
Hellinger distance $d_{clas}$ on $\mathcal{E}_{clas}$ is:

$d_{clas}(\rho,\sigma)=\left(\sum_{k=1}^{n}{\left(\sqrt{\rho_{k}}-\sqrt{\sigma_{k}}\right)^{2}}\right)^{1/2}$

In general, even with the current hardware solutions for quantum processors,
two-qubit gates are possible for realization between two adjacent qubits that
are connected via a superconducting bus resonator. IBM hardware uses cross-
resonance impact as the basis for the CNOT gate, a higher frequency control
and a lower frequency target. The functions of the two qubits must be reversed
if a degenerate effect on the qubit playing the target is observed, and if it
is connected to a third qubit that has the same or higher frequency. Due to
the possibility of these exceptions, the quantum circuit 15 was implemented in
two variants - 26 and 27, respectively, with two-qubit gates for figure 26 \-
{CX_01}, {CX_12}, and for figure 26 \- {CX_21, CX_10}.

In quantum information theory, fidelity is a measure of the ”closeness”
between two quantum-mechanical states. Criteria for fidelity and distances
between probability distributions are a topic of study in both classical and
quantum information sciences. Hellinger’s fidelity is the main measure adopted
to study the proximity of two quantum distributions.

Let’s $P=\\{pi\\}i\in[n],Q=\\{qi\\}i\in[n]$ are two probability distributions,
then the Hellinger distance will have the following look:

$h(P,Q)={1\over\sqrt{2}}\left|\sqrt{P}-\sqrt{Q}\right|_{2}$ (5.1)

Where $h(P,Q)\leq 1$ for all distributions, and the fidelity is:

$F[P,Q]=1-h(P,Q)$ (5.2)

Increasing the number of execution for each quantum circuit on the respective
IBM quantum systems does not lead to significant error mitigation. The
experiments performed are at the maximum value of the input parameter for the
number of executions - namely 8192 executions.

IBM Q Backend |  Quantum Circuit on fig. 26 |  Quantum Circuit on fig. 27
---|---|---
Burlington |  0.71475 |  0.689795
Essex |  0.760052 |  0.744267
London |  0.753879 |  0.714005
Melbourne |  0.595152 |  0.546999
Ourense |  0.756185 |  0.721887
Vigo |  0.832508 |  0.773089
Yorktown |  0.818702 |  0.821362
Table 1: Hellinger fidelity calculated from the distance between the high-
performance quantum simulator and various hardware backends in IBM cloud
platform for the quantum circuits shown on figures 26 and 27.

Figure 36: Hellinger fidelity calculated from the distance between the high-
performance quantum simulator and various hardware backends in IBM cloud
platform for the quantum circuits shown on figures 26 and 27.

The quantum gates construction and the simulation of a binary homogeneous
Markov process on various hardware backends have been verified and validated.
It has been shown that creating a quantum gate with the basic gates available
on multiple platforms is possible, although the hardware devices are still too
noisy and this results in a significant increase in measurement error.
In the $C\sqrt[n]{X}$ gate implementation, IBM’s 5-qubit quantum T-shaped
systems, along with the 14-qubit Melbourne quantum system, perform
significantly worse than the 5-qubit Yorktown processor with a ”bow-tie”
configuration map.
In the simulation of a homogeneous binary Markov model, the best performing
quantum processors are Vigo and Yorktown. Improving accuracy ( 0.82) is
achieved by using circuit from figure 26, and this is fully expected since, as
mentioned at the beginning of this chapter, this scheme is applicable when
there are no exceptions to the rule for determining the direction of the gate
and the gate direction should not be reversed - there are no degenerative
effects on the target qubit as a result of the higher frequency of the
control.
Choosing the right quantum circuit based on the available hardware backends,
as well as choosing a hardware device with the number of qubits as close as
possible to the simulation required, would be the right approach to achieve
maximum fidelity.

##  6 Scientific and Scientifically Applied Contributions

A method has been developed to find the complete set of possible paths of a
stochastic process, described by a homogeneous binary Markov model with the
apparatus of quantum computational operations.

An algorithm for determining the phase shift of the qubit along the X axis is
developed, depending on the desired probability distribution for the
amplitudes of its states, with application in the modelling of stochastic
processes through the apparatus of quantum computational operations.

Based on the method developed to find the complete set of possible random
process paths, described by a binary homogeneous Markov model, an algorithm
applicable to real quantum processors has been synthesized (a test version of
the algorithm is implemented on quantum processors in the IBM Quantum
Experience platform).

Software has been developed in the Jupyter Notebook environment with Python
3.7 software kernel, which implements the phase shifting algorithm and its
applicability in comparison to the solutions used so far.

A quantum circuit has been developed to allow modelling on a real quantum
processor of any stochastic problem described by a binary homogeneous Markov
model.

An analysis of the scientific sectors in quantum information theory and a
classification, including 8 technological clusters with the definition of
perspective and key problems have been made.

##  Appendix A Appendix A

Author’s work

  1. i

Petar N. Nikolov,Vassil T. Galabov, ”Experimental realization of Controlled
Square Root of Z Gate Using IBM‘s Cloud Quantum Experience Platform” in FDIBA
Conference Proceedings, vol. 1, dec. 2017, pp. 11-13

  2. ii

Nikolov, P. (2019). Controlled nth root of X gate on a real quantum computer.
PROCEEDINGS OF THE 45TH INTERNATIONAL CONFERENCE ON APPLICATION OF MATHEMATICS
IN ENGINEERING AND ECONOMICS (AMEE’19). PROCEEDINGS OF THE 45TH INTERNATIONAL
CONFERENCE ON APPLICATION OF MATHEMATICS IN ENGINEERING AND ECONOMICS
(AMEE’19).
https://doi.org/10.1063/1.5133583

  3. iii

Nikolov, P., Galabov, V. (2019). Markov process simulation on a real quantum
computer. PROCEEDINGS OF THE 45TH INTERNATIONAL CONFERENCE ON APPLICATION OF
MATHEMATICS IN ENGINEERING AND ECONOMICS (AMEE’19). PROCEEDINGS OF THE 45TH
INTERNATIONAL CONFERENCE ON APPLICATION OF MATHEMATICS IN ENGINEERING AND
ECONOMICS (AMEE’19).
https://doi.org/10.1063/1.5133584

  4. iv

Petar Nikolov, Vassil Galabov, ”The Journey of Quantum Information
Technology,” in FDIBA Conference Proceedings, vol. 3, Nov. 2019, pp. 11-25

##  Appendix B Appendix B

Here is attached a sample code in the form of a Jupyter Notebook used for
execution of the quantum circuits shown on figure 26 and figure 27. The
results here are not the ones used in the dissertation, but as mentioned -
this is a sample code, and should be used for experiment replication.

See pages 2- of Figures/appendix/appendix.pdf

## References

  * Aaronson, (2015) Aaronson, S. (2015).  Read the fine print.  Nature Physics, 11(4):291–293.
  * Abraham et al., (2019) Abraham, H., Akhalwaya, I. Y., Aleksandrowicz, G., Alexander, T., Alexandrowics, G., Arbel, E., Asfaw, A., Azaustre, C., AzizNgoueya, Barkoutsos, P., Barron, G., Bello, L., Ben-Haim, Y., Bevenius, D., Bishop, L. S., Bosch, S., Bravyi, S., Bucher, D., Cabrera, F., Calpin, P., Capelluto, L., Carballo, J., Carrascal, G., Chen, A., Chen, C.-F., Chen, R., Chow, J. M., Claus, C., Clauss, C., Cross, A. J., Cross, A. W., Cross, S., Cruz-Benito, J., Culver, C., Córcoles-Gonzales, A. D., Dague, S., Dandachi, T. E., Dartiailh, M., DavideFrr, Davila, A. R., Ding, D., Doi, J., Drechsler, E., Drew, Dumitrescu, E., Dumon, K., Duran, I., EL-Safty, K., Eastman, E., Eendebak, P., Egger, D., Everitt, M., Fernández, P. M., Ferrera, A. H., Frisch, A., Fuhrer, A., GEORGE, M., Gacon, J., Gadi, Gago, B. G., Gambetta, J. M., Gammanpila, A., Garcia, L., Garion, S., Gomez-Mosquera, J., de la Puente González, S., Gould, I., Greenberg, D., Grinko, D., Guan, W., Gunnels, J. A., Haide, I., Hamamura, I., Havlicek, V., Hellmers, J., Herok, Ł., Hillmich, S., Horii, H., Howington, C., Hu, S., Hu, W., Imai, H., Imamichi, T., Ishizaki, K., Iten, R., Itoko, T., Javadi-Abhari, A., Jessica, Johns, K., Kachmann, T., Kanazawa, N., Kang-Bae, Karazeev, A., Kassebaum, P., King, S., Knabberjoe, Kovyrshin, A., Krishnan, V., Krsulich, K., Kus, G., LaRose, R., Lambert, R., Latone, J., Lawrence, S., Liu, D., Liu, P., Maeng, Y., Malyshev, A., Marecek, J., Marques, M., Mathews, D., Matsuo, A., McClure, D. T., McGarry, C., McKay, D., Meesala, S., Mevissen, M., Mezzacapo, A., Midha, R., Minev, Z., Moll, N., Mooring, M. D., Morales, R., Moran, N., Murali, P., Müggenburg, J., Nadlinger, D., Nannicini, G., Nation, P., Naveh, Y., Neuweiler, P., Niroula, P., Norlen, H., O’Riordan, L. J., Ogunbayo, O., Ollitrault, P., Oud, S., Padilha, D., Paik, H., Perriello, S., Phan, A., Pistoia, M., Pozas-iKerstjens, A., Prutyanov, V., Puzzuoli, D., Pérez, J., Quintiii, Raymond, R., Redondo, R. M.-C., Reuter, M., Rice, J., Rodríguez, D. M., Rossmannek, M., Ryu, M., SAPV, T., SamFerracin, Sandberg, M., Sathaye, N., Schmitt, B., Schnabel, C., Schoenfeld, Z., Scholten, T. L., Schoute, E., Sertage, I. F., Setia, K., Shammah, N., Shi, Y., Silva, A., Simonetto, A., Singstock, N., Siraichi, Y., Sitdikov, I., Sivarajah, S., Sletfjerding, M. B., Smolin, J. A., Soeken, M., Sokolov, I. O., Steenken, D., Stypulkoski, M., Takahashi, H., Tavernelli, I., Taylor, C., Taylour, P., Thomas, S., Tillet, M., Tod, M., de la Torre, E., Trabing, K., Treinish, M., TrishaPe, Turner, W., Vaknin, Y., Valcarce, C. R., Varchon, F., Vazquez, A. C., Vogt-Lee, D., Vuillot, C., Weaver, J., Wieczorek, R., Wildstrom, J. A., Wille, R., Winston, E., Woehr, J. J., Woerner, S., Woo, R., Wood, C. J., Wood, R., Wood, S., Wootton, J., Yeralin, D., Young, R., Yu, J., Zachow, C., Zdanski, L., Zoufal, C., Zoufalc, azulehner, bcamorrison, brandhsn, chlorophyll zz, dime10, drholmie, elfrocampeador, faisaldebouni, fanizzamarco, gruu, kanejess, klinvill, kurarrr, lerongil, ma5x, merav aharoni, ordmoj, sethmerkel, strickroman, sumitpuri, tigerjack, toural, vvilpas, willhbang, yang.luh, and yotamvakninibm (2019).  Qiskit: An open-source framework for quantum computing.
  * Ackley et al., (1985) Ackley, D. H., Hinton, G. E., and Sejnowski, T. J. (1985).  A learning algorithm for boltzmann machines.  Cognitive Science, 9(1):147 – 169.
  * Aharonov, (2003) Aharonov, D. (2003).  A simple proof that toffoli and hadamard are quantum universal.
  * Aharonov and Ta-Shma, (2003) Aharonov, D. and Ta-Shma, A. (2003).  Adiabatic quantum state generation and statistical zero knowledge.  In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’03, pages 20–29, New York, NY, USA. Association for Computing Machinery.
  * Ambrose, (1940) Ambrose, W. (1940).  On measurable stochastic processes.  Transactions of the American Mathematical Society, 47(1):66–66.
  * Amico et al., (2019) Amico, M., Saleem, Z. H., and Kumph, M. (2019).  Experimental study of shor's factoring algorithm using the IBM q experience.  Physical Review A, 100(1).
  * Amin et al., (2018) Amin, M. H., Andriyash, E., Rolfe, J., Kulchytskyy, B., and Melko, R. (2018).  Quantum boltzmann machine.  Physical Review X, 8(2).
  * Arunachalam et al., (2015) Arunachalam, S., Gheorghiu, V., Jochym-O’Connor, T., Mosca, M., and Srinivasan, P. V. (2015).  On the robustness of bucket brigade quantum RAM.  New Journal of Physics, 17(12):123010.
  * Azuma, (2017) Azuma, H. (2017).  An entangling-probe attack on shor’s algorithm for factorization.  Journal of Modern Optics, 65(4):415–422.
  * AÃ¯meur et al., (2006) AÃ¯meur, E., Brassard, G., and Gambs, S. (2006).  Machine learning in a quantum world.  In Advances in Artificial Intelligence, pages 431–442. Springer Berlin Heidelberg.
  * Bacon, (2003) Bacon, D. (2003).  Decoherence, control, and symmetry in quantum computers.
  * Barenco et al., (1995) Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J., and Weinfurter, H. (1995).  Elementary gates for quantum computation.  Physical Review A, 52(5):3457–3467.
  * Beckman et al., (1996) Beckman, D., Chari, A. N., Devabhaktuni, S., and Preskill, J. (1996).  Efficient networks for quantum factoring.  Physical Review A, 54(2):1034–1063.
  * (15) Bengio, Y. (2009a).  Learning deep architectures for ai.  Found. Trends Mach. Learn., 2(1):1–127.
  * (16) Bengio, Y. (2009b).  Learning deep architectures for ai.  Foundations and TrendsÂ® in Machine Learning, 2(1):1–127.
  * Bengio and Delalleau, (2009) Bengio, Y. and Delalleau, O. (2009).  Justifying and generalizing contrastive divergence.  Neural Computation, 21(6):1601–1621.
  * Berry et al., (2006) Berry, D. W., Ahokas, G., Cleve, R., and Sanders, B. C. (2006).  Efficient quantum algorithms for simulating sparse hamiltonians.  Communications in Mathematical Physics, 270(2):359–371.
  * Biamonte et al., (2017) Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., and Lloyd, S. (2017).  Quantum machine learning.  Nature, 549(7671):195–202.
  * Biamonte and Love, (2008) Biamonte, J. D. and Love, P. J. (2008).  Realizable hamiltonians for universal adiabatic quantum computers.  Physical Review A, 78(1).