Research Projects

• PROJECT 1: Simulating 2D quantum random walks with alternating 1D quantum random walks.

  Standard 2-dimensional quantum walks (i.e. essentially walks where the particle can move up and down as well as left and right) are powered by a coin operator that has 4 possible states, each state corresponding to moving in one of the possible directions.
  However it is very hard experimentally to control such a larger state system. It has been shown (http://arxiv.org/abs/1010.2470) that if we alternate the walk (i.e. move first in vertical direction, followed by horizontal movement), we can use a 2-state quantum system (i.e. a standard coin), which is far easier to control. In certain cases this alternating process corresponds to well-known 2-dimensional walks. Right now, only a few correspondences have been found, and the general case (of which 2-dim quantum walks can be simulated by such an alternating walk) is unknown.
  In this research it is proposed to exam in general this correspondence. Of particular interest will be whether the entanglement generation is fundamentally different in an alternating walk compared to a non-alternating one. We need also to examine the complexity of the process and its resource usage: While a 2-state system is easier to control that a 4-state one, twice the number of steps are need to get to an arbitrary location in the integer plane.
  We expect this to be of use in quantum algorithms that rely on searching through a graph. Many of the applications of these quantum walks in algorithm design are already known (A. Ambainis, International Journal of Quantum Information, 1:507-518, 2003). The use of this work will be in developing quantum algorithms with faster search times and faster hitting times.

• PROJECT 2: Entanglement generation in quantum random walks

  It is well known for a number of years that the property of entanglement in a quantum system is an essential resource to allow the superior performance of quantum algorithms over classical ones. In recent years, the active research area of Quantum Random Walks (QRW) has shown that entanglement is generated by these walks. This project will examine (and quantify) the entanglement generated by various types of QRWs, for example

  • Lazy QRWs: In the "lazy" scenario, one of the options in the walk is for the walker to stay put. These walks have not been examined to date.
  • Walks with memory: In this scenario, the walkers moves depend not only on the quantum coin, but on his previous position(s) (corresponding to the idea of higher order Markov Chains). This gives different dynamics, most notably localization can occur at the origin (M. Mc Gettrick, Quantum Information and Computation, Vol. 10, No. 5&6 (2010) 0509-0524). Our research will examine what role memory plays in entanglement generation.
  • Simulated walks: If we have a higher dimensional walk in d dimensions, we can simulate the movement by using an alternating walk which just has a 2-state coin. The question is whether this simulation results in increased or decreased entanglement.