Discrete-time quantum walks on the symmetric group (quantum card shuffling)

The next stage in uses of classical stochastic approaches, going beyond Markov chains (random walks on graphs), are walks on algebraic structures. The prime and classic example of such a problem is ``card shuffling,'' a walk on the permutation (symmetric) group. The richness of this non-Abelian group lends itself to modeling of complex phenomena, while it also quickly leads to rather complicated problems. The challenge of studying such quantum processes is no lesser, but the benefits can be expected to even outweigh the classical uses. We study a quantum analog of the classical ``top-to-random'' shuffle, where the top card is placed at random in the deck. We construct a ``coined'' DTQW on the permutation group: based on the action of a (unitary) ``coin'' operator in an additional (``coin'') space, (unitary) steps in the group space are taken, resulting in a (quantum) walk over group elements. We use general techniques for the eigenvalue problem of the combined coin and permutation operators, utilizing regularities in the block structure. We have reached preliminary solutions for low-dimensional cases. Currently we are integrating them into a more general solution, which will yield the first step in this deep and far-reaching, while challenging problem.