AF: Small: Provable Quantum Advantages in Optimization

该项目旨在调查我们日常生活中普遍存在的可证明的量子优势在优化和机器学习方面的情况，并为量子计算的应用，特别是在近期量子设备和建立量子优势方面建立坚实的理论基础。通过集成优化和量子算法设计的现代工具，该项目旨在通过量化最先进的经典优化算法来设计用于凸优化和各种半定程序类的量子算法。获得的成果将通过各种场所传播，包括会议、新课程材料、说明性写作和高中开放日，旨在让年轻的计算机科学家接触到量子信息研究的前沿。本研究项目由计算与信息科学与工程局计算与通信基础司的算法基础(AF)计划和数学与物理科学局物理司的量子信息科学(QIS)计划联合支持。本研究项目研究可证明的量子在求解凸优化、一般半定程序和正定程序方面的优势，以及可在近期量子器件上执行的变分优化方法。具体目标包括：(1)基于抽样的凸优化方法和隶属度分离方法；(2)基于宽度相关和宽度无关方法以及内点法的最优半定规划求解器。研究人员还致力于在近期量子器件上设计新的量子优化算法，并提供基于变分方法和量子近似优化算法(QAOA)的量子优化算法的理论证明。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.