Institute of Information Science, Academia Sinica

The talk will be twofold. The first part will cover simple concepts of quantum walk and and its superiority over classical random walk.  The second part of the talk will be systematic dimensionality reduction for quantum walk. The reduction is important for the near-term quantum technology because of limited quantum resources. In a recent work by Novo et al. (Sci. Rep. 5, 13304, 2015), the invariant subspace method was applied to the study of quantum walk. The method helps to reduce a graph into a simpler version that allows more transparent analyses of the quantum walk model. The search remains optimal and applicable graphs are complete graphs, star graphs and complete bipartite graphs. In this work, we adopt and extend the aforementioned method to apply to uniform complete multipartite graphs.