Controllability of quantum walks on graphs

In this paper, we consider discrete time quantum walks on graphs with coin, focusing on the decentralized model, where the coin operation is allowed to change with the vertex of the graph. When the coin operations can be modified at every time step, these systems can be looked at as control systems and techniques of geometric control theory can be applied. In particular, the set of states that one can achieve can be described by studying controllability. Extending previous results, we give a characterization of the set of reachable states in terms of an appropriate Lie algebra. Controllability is verified when any unitary operation between two states can be implemented as a result of the evolution of the quantum walk. We prove general results and criteria relating controllability to the combinatorial and topological properties of the walk. In particular, controllability is verified if and only if the underlying graph is not a bipartite graph and therefore it depends only on the graph and not on the particular quantum walk defined on it. We also provide explicit algorithms for control and quantify the number of steps needed for an arbitrary state transfer. The results of the paper are of interest in quantum information theory where quantum walks are used and analyzed in the development of quantum algorithms.