Reversibility and Hierarchy in Higher Order Quantum Walks

We will present in this talk some new ideas and features pertaining to Higher Order Quantum Walks (also known as Quantum Walks with memory). It is known that quantum walks play a very important role in the design of algorithms for our "soon to arrive at a store near you" quantum computers. Because of this, there is an active research community constructing various different types of quantum walks with different properties. There is an abundance of established literature on classical random walks (a particular case of the more generalized Markov Chains), which has also found widespread application in algorithms in classical Computer Science. Thus, in our research, we always compare and contrast our quantum walks with the classical ones. In the case of higher order walks, our intuition is that the higher the order, the less "random" is the walk - simply because, for infinite order, everything is prescribed. In the presentation, we show how we can construct either reversible or irreversible walks, depending on our definition of the shift operator. We further explain our new idea on varying the order of the walk dynamically (going from the amnesiac to the person that remembers everything!). We can view the current walk order as a parameter which is governed separately by a stochastic matrix, thus creating a hierarchy of Markov Chains.