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.