CRII: FET: Quantum Advantages through Discrete Quantum Walks

量子计算在有效探索解决方案空间和增强供应链和物流优化任务方面显示出巨大潜力。量子计算中的一个关键工具，被称为离散量子行走，可用于构建量子电路并为包括格罗弗搜索在内的许多量子算法建模。虽然离散量子行走的优势通过数值证据变得清晰，但一个统一的图理论框架却使研究人员无法证明这些优势。为了弥补这一差距，该项目解决了以下问题：离散量子行走的行为是如何由底层图的组合属性决定的？这个问题的答案将有助于确定离散量子行走表现出优势的图表，并最终导致基于量子行走算法的新结构。该项目更广泛的影响包括人工智能技术、生物医学研究、气候科学、优化、金融建模以及培养量子科学和技术方面的多元化劳动力。这个项目的技术目标是用图论和代数证明（或证伪）离散量子行走中的某些现象。研究者先前的工作已经揭示了离散量子行走的跃迁矩阵和各种组合结构的关联矩阵之间的谱关系。在这些关系的基础上，该项目将(1)提供“频谱良好”的图形特征，以实现所需的量子现象，如高保真状态转移和均匀混合；(2)建立离散量子行走和连续量子行走之间的联系，它们在物理上不同，但共享可转移的数学机制；(3)确定离散量子行走方法解决难组合问题的测试用例。从而评估其有效性。该项目的成果不仅将促进对量子行走的科学理解，还将通过将这些发现纳入未来的量子计算课程和让学生参与指导活动来丰富教育经验。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Quantum computing has shown great potential in efficiently exploring solution spaces and enhancing optimization tasks in supply chain and logistics. A key tool in quantum computing, known as discrete quantum walks, can be used to build quantum circuits and model a number of quantum algorithms including Grover's search. While advantages of discrete quantum walks become clear through numerical evidence, a unified, graph-theoretical framework that allows researchers to prove these advantages is missing. To bridge the gap, this project addresses the following question: how is the behavior of a discrete quantum walk determined by the combinatorial properties of the underlying graph? Answers to this question will help pinpoint graphs on which discrete quantum walks exhibit advantages, and ultimately lead to new constructions of quantum-walk-based algorithms. Broader impacts of this project include quantum-inspired transformations in AI technology, biomedical research, climate science, optimization, financial modelling, and training of a diverse workforce in quantum science and technology.The technical objective of this project is to prove (or disprove) certain phenomena in discrete quantum walks using graph theory and algebra. Prior work by the investigator has revealed spectral relations between the transition matrix of a discrete quantum walk and the incidence matrices of various combinatorial structures. Built upon these relations, this project will (1) offer characterizations of graphs that are "spectrally nice" to enable desired quantum phenomena, such as high-fidelity state transfer and uniform mixing, (2) establish connections between discrete quantum walks and continuous quantum walks, which are physically different but share transferable mathematical machinery, and (3) identify test cases for discrete-quantum-walk approaches to hard combinatorial problems, thereby assessing their effectiveness. Outcomes of this project will not only advance scientific understanding of quantum walks, but also enrich educational experience by incorporating these findings into future quantum computing courses and engaging students in mentoring activities.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.