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

原则上，量子算法可以比任何已知的经典算法更快地执行某些计算任务。然而，支撑量子算法的量子力学假设产生了独特的挑战，需要克服这些挑战才能扩大它们的应用。这个项目研究量子漫步的能力和局限性，量子漫步是经典随机漫步的量子模拟。量子漫步已经被用于最先进的量子算法中；从寻找图中的标记顶点到模拟量子系统。尽管如此，“量子步行者”的动力学行为还没有被很好地理解，由于它的波状干涉特性，它可能是非常不平凡的。这使得在搜索问题的底层几何很复杂的情况下，很难有效地指导“量子步行者”的传播。这个项目的主要目的是开发数学和算法工具，以扩大我们对量子行走的理解。通过教育、课程开发和外联活动，该项目还将有助于培训一批跨学科的量子计算学生。此外，这个项目将促进跨数学(群和表示论、单纯同调、图论)、物理学(散射理论、量子行走)和计算机科学(性质测试、子图查找)的研究。扩大量子行走的应用带来了几个挑战。首先，即使是在高度对称的图上，也很难推导出某些重要的量子游动的结果分布的解析表达式。这是由于相消干涉的存在。其次，我们没有很好地理解量子行走何时会导致超多项式或指数加速。第三，除了几个精心构建的例子，我们不知道如何应用量子漫步来寻找或检测给定图的非平凡子图。为了克服上述一些障碍，本项目系统地研究了量子游动作为图的顶点和边上的非平凡分布及其高维扩展(如单纯复形(SC))的生成模型。由此产生的理论将用于测试这些物体的某些性质，并在其中发现复杂的子结构。更具体地说，将研究以下主题：非阿贝尔Cayley图和具有某些上同调的SC上的量子行走的动力学，量子行走在SC上的性质测试和搜索问题中的应用，以及散射量子行走与底层图形的对称性之间的联系。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.