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

CRII：FET：量子行走的新理论基础及其应用

• 批准号: 2246144
• 负责人: Avah Banerjee
• 金额: $ 17.5万
• 依托单位: Missouri University of Science and Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-03-01 至 2025-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2246144&HistoricalAwards=false
• 关键词: CRII; FET; New; Theoretical; Foundations

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.

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

项目成果

Mitigating CNOT Errors via Noise-aware Token Swapping

通过噪声感知令牌交换减轻 CNOT 错误

• DOI: 10.1109/qce57702.2023.00044
• 发表时间: 2023-09
• 期刊: 2023 IEEE International Conference on Quantum Computing and Engineering (QCE
• 作者: Sharma, Asim;Banerjee, Avah
• 通讯作者: Banerjee, Avah