Quantum Algorithms: Applications in Communications

Abstract

The recent advances in Quantum Information science are well known. There has also been considerable research into the physical realisation of Quantum Computers. However, with the advent of a new paradigm in computing it is imperative to develop algorithms that are able to exploit the quantum mechanical resources of superposition and entanglement in order to make a larger set of useful problems tractable. This is also likely to provide insight into the nature of conventional complexity classes and NP- problems in particular. Shor's exponentially faster prime number factorisation algorithm and Grover's quadratically faster search algorithm are the first and most well known of the quantum algorithms. This paper will present an adaptation of Grover's algorithm to find the shortest path by optimising a Markov Decision Process (MDP). Properties of the quantum walk, especially with regard to propagation through graphs will also be discussed since graphical representations are prevalent in coding theory and network modelling.