Recently quantum walk with two-step memory has been investigated for its properties. It is
showing certain similarities with classical random walk and some other similarities with
quantum Hadamard walk. Following this other models of quantum walks with history have
been constructed by using multiple coins or modifying Hamiltonian. It should also be noted
that a general method for proving properties of probabilistic program, in which a probabilistic
program is modeled by a quantum Markov chain and an assertion on the output distribution
is extended into an invariant assertion on all intermediate distributions has been developed.
The proposed topic "Asymptotics of Higher Order Quantum Markov Chains" aims at
investigating limiting behaviour of higher-order quantum Markov chains, thereby pave way
for advancement in the design of efficient quantum algorithms in the near future. Dr. M. Mc
Gettrick has initiated studies on this by analising the order 2 case ["One dimensional
quantum walks with memory", Journal of Quantum Information and Computation, Volume 10,
Issues 5-6 (2010)].

The aim is to not only do theoretical/mathematical calculations, but also to do computer
simulations (e.g. using PYTHON). We also hope to investigate how the properties of higher
order quantum Markov chains could be used to construct more efficient (quantum) search
algorithms running on a graph/network. We see many applications of such graph-based
algorithms in real-world problems.
It is known that (classical) higher order Markov chains can be written (with a different state
space) as first order ones: Whether or not this can be done in the quantum regime is a
central question of this PhD proposal.

PLAN:
YEAR 1:
Reading of many research papers on the subject.
Getting familiar with coding quantum random walks on a computer
Taking some available graduate courses in maths at NUIG (e.g. algebra courses)
Attending seminars, and going to a relevant summer/winter school in quantum computation.
YEAR 2:
Doing my own calculations on higher order Markov chains.
Publishing results on the 2nd. order example of Hadamard walk.
YEARS 3 and 4:
Solving the general case of writing higher order quantum Markov chain as a first order one.
Applying the results to quantum walks in 1-dimension, then 2-dimension, to investigate
algorithms on a network.