CRII: FET: New Theoretical Foundations for Quantum Walks with Applications

点击翻译按钮获取中文摘要

In principle, quantum algorithms can perform certain computational tasks faster than any known classical algorithms. However, the postulates of quantum mechanics underpinning quantum algorithms, create unique challenges that need to be overcome in order to expand their applications. This project investigates the power and limitations of quantum walks, which is a quantum analogue of classical random walks. Quantum walks have been used in state-of-the-art quantum algorithms; from finding a marked vertex in a graph to simulation of quantum systems. Despite this, the dynamical behavior of the “quantum walker” is not well understood, which can be highly non-trivial due to its wave-like interference properties. This makes it difficult to effectively guide the propagation of the “quantum walker” when the underlying geometry of the search problem is complicated. The primary aim of this project is to develop mathematical and algorithmic tools to broaden our understanding of quantum walks. Through education, curriculum development and outreach activities, the project will also contribute towards training an interdisciplinary cohort of students in quantum computing. Further, this project will foster research across mathematics (group and representation theory, simplicial homology, graph theory), physics (scattering theory, quantum walks) and computer science (property testing, subgraph finding). Expanding the applications of quantum walks poses several challenges. First, it is difficult to derive analytical expressions for the resulting distribution of certain important classes of quantum walks, even on highly symmetric graphs. This is due to the presence of destructive interference. Second, we do not have a good understanding of when quantum walks can lead to super-polynomial or exponential speedup. Third, apart from a few carefully constructed examples, we do not know how to apply quantum walks to find or detect non-trivial subgraphs of a given graph. To overcome some of the above obstacles, this project undertakes a systematic study of quantum walks as a generative model for non-trivial distributions on vertices and edges of graphs and their higher dimensional extensions such as simplicial complexes (SC). The resulting theory will be used in testing certain properties of and finding complex sub-structures within these objects. More specifically, the following topics will be investigated: dynamics of quantum walks on non-abelian Cayley graphs and SCs with certain cohomologies, applications of quantum walks for property testing and search problems on SCs, and connection between scattering quantum walks and the symmetries of the underlying graph.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.