The first general analytic solutions for the one-dimensional quantum walk in position and momentum space are derived. These solutions reveal new symmetry features of quantum walk probability densities and insight into the behaviour of their moments. The analytic expressions for the quantum walk probability distributions provide a means of modelling quantum phenomena that is analogous to that provided by random walks in the classical domain.
In this paper we address the quantum random walk on the real line. Specifically, we utilize a
dynamical system formulation of the walk, which leads to a momentum space expression of the
probability amplitude that is a function of only the initial condition. Our focus is, for the most part,
limited to the Hadamard walk. As such, this closed form expression is not as general as that given
by . This lack of generality is offset by the ease with which we obtain the expression, and the
insight offered by it. Our closed form expression allows us to easily compute the walk pdf, hence
the cdf (cumulative distribution function). It is shown that the cdf converges to its limiting form
relatively quickly. We push the simple mathematics in an to attempt to obtain a closed form
expression for this form. But it becomes too involved to take it to completion in this paper, without
running the risk of losing appreciation for the simplicity of our approach.
We explore the application of a quantum algorithm to optimisation problems over a structured space. For
example, problems in automated planning can be represented as automata. These automata are shown to posses
algebraic structure that can be exploited by a quantum period finding algorithm. The fact that the quantum
walk also provides exponential speed-up over these same structures is of particular interest and results of our
investigation will be presented.
There has been recent interest in implementing automated planning by optimizing a planning domain modeled as a stochastic system. Planning is viewed as a process where sequential decision problems are solved
in order to reach the goal, and thus, can be considered as instances of a Markov Decision Process (MDP). However, standard MDP techniques cannot solve a typical planning problem in polynomial time. Hence, the
motivation for investigating the use of quantum search techniques based on the Grover Search Algorithm, to identify policies with high utility.