AF: Small: Provable Quantum Advantages in Optimization

AF：小：优化中可证明的量子优势

• 批准号: 1816695
• 负责人: Xiaodi Wu
• 金额: $ 45万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1816695&HistoricalAwards=false
• 关键词: AF; Small; Provable; Quantum; Advantages

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.

该项目旨在调查优化和机器学习中可证明的量子优势的景观，这在我们的日常生活中无处不在，并为量子计算的应用建立一个可靠的理论基础，尤其是在近期量子设备上以及在建立中建立量子至高无上。通过将现代工具集成到优化和量子算法设计中，该项目旨在通过量化最先进的古典优化算法来设计用于凸优化和各种半限制程序类的量子算法。获得的结果将通过各种场所进行传播，包括会议，新课程材料，说明性著作以及旨在将年轻计算机科学家暴露于量子信息研究边界的高中开放日。该项目由计算机和信息科学与工程局的计算和通信基金会的算法基础（AF）计划共同支持数学和物理科学。本研究项目研究了在求解凸优化，一般和积极的半决赛程序以及可在近期量子设备上可执行的变异优化方法方面的可证明的量子优势。具体目标包括：（1）基于抽样的方法和凸优化的成员到分离方法； （2）基于宽度依赖性和宽度独立的方法以及内部点方法的最佳半数程序求解器。研究人员还旨在设计近期量子设备上的新量子优化算法，并基于变异方法和量子近似优化算法（QAOA）提供量子优化算法的理论理由。使用基金会的知识分子优点和更广泛的审查标准，被认为值得通过评估来支持。

项目成果

Quantum Algorithms for Escaping from Saddle Points

• DOI: 10.22331/q-2021-08-20-529
• 发表时间: 2020-07
• 期刊: ArXiv
• 作者: Chenyi Zhang;Jiaqi Leng;Tongyang Li

Quantum Wasserstein Generative Adversarial Networks

• 发表时间: 2019-10
• 期刊: ArXiv
• 作者: Shouvanik Chakrabarti;Yiming Huang;Tongyang Li;S. Feizi;Xiaodi Wu

Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning

• DOI: 10.4230/lipics.icalp.2019.27
• 发表时间: 2017-10
• 作者: F. Brandão;A. Kalev;Tongyang Li;Cedric Yen-Yu Lin;K. Svore;Xiaodi Wu

Quantum Algorithm for Estimating Volumes of Convex Bodies

• DOI: 10.1145/3588579
• 发表时间: 2019-08
• 期刊: ACM Transactions on Quantum Computing
• 作者: Shouvanik Chakrabarti;Andrew M. Childs;S. Hung;Tongyang Li;C. Wang;Xiaodi Wu

ICCAD Special Session Paper: Quantum Variational Methods for Quantum Applications

ICCAD 特别会议论文：量子应用的量子变分方法

• DOI: 10.1109/iccad51958.2021.9643519
• 发表时间: 2021
• 期刊: 2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD
• 作者: Chakrabarti, Shouvanik;You, Xuchen;Wu, Xiaodi
• 通讯作者: Wu, Xiaodi