AF: Small: Provable Quantum Advantages in Optimization

该项目旨在研究可证明的量子优势在优化和机器学习方面的前景，这在我们的日常生活中无处不在，并为量子计算的应用，特别是近期量子设备和量子霸权的建立建立坚实的理论基础。通过整合优化和量子算法设计中的现代工具，该项目旨在通过量化最先进的经典优化算法，为凸优化和各种半定程序类设计量子算法。获得的结果将通过各种场所传播，包括会议、新课程材料、说说性著作和旨在使年轻计算机科学家接触量子信息研究前沿的高中开放日。本项目由计算机与信息科学与工程理事会计算与通信基础部的算法基础（AF）项目和数学与物理科学理事会物理部的量子信息科学（QIS）项目共同支持。本研究项目探讨可证明的量子在求解凸优化、一般和正半定规划以及可在近期量子器件上执行的变分优化方法方面的优势。具体目标包括：(1)基于抽样的凸优化方法和隶属-分离方法；(2)基于宽度相关法和宽度无关法以及内点法的最优半定规划求解。在近期量子器件上设计新的量子优化算法，并提供基于变分方法和量子近似优化算法（QAOA）的量子优化算法的理论依据。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The project aims to investigate the landscape of provable quantum advantages in optimization and machine learning, which is ubiquitous in our daily life, and to build a solid theoretical foundation for applications of quantum computing, especially with near-term quantum devices and in the establishment of quantum supremacy. By integrating modern tools in both optimization and quantum algorithm design, the project aims to design quantum algorithms for convex optimization and various semidefinite program classes, by quantizing the state-of-the-art classical optimization algorithms. The results obtained will be disseminated through a variety of venues, including conferences, new course materials, expository writings, and high school open days aimed at exposing young computer scientists to the frontiers of quantum information research. This project is jointly supported by the Algorithmic Foundations (AF) Program in the Division of Computing and Communications Foundations in the Directorate for Computer and Information Science and Engineering, and the Quantum Information Science (QIS) Program in the Division of Physics in the Directorate for Mathematical and Physical Sciences.This research project investigates provable quantum advantages in solving convex optimization, general and positive semidefinite programs, as well as variational optimization methods executable on near-term quantum devices. Specific targets include: (1) the sampling-based approach and the membership-to-separation approach for convex optimization; (2) optimal semidefinite program solvers based on the width-dependent and width-independent approaches as well as the interior point method. The investigator also aims to design new quantum optimization algorithms on near-term quantum devices as well as to provide theoretical justifications of quantum optimization algorithms based on the variational method and the quantum approximate optimization algorithm (QAOA).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.