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）计划和数学物理科学局物理部的量子信息科学（QIS）计划共同资助。本研究项目研究可证明的量子优势在解决凸优化问题中的作用，一般和半正定程序，以及变分优化方法可执行的近期量子设备。具体目标包括：（1）基于抽样的凸优化方法和隶属度分离法;（2）基于宽度相关和宽度无关方法以及内点法的半定规划最优解算器。该研究员还旨在设计新的量子优化算法在近期量子设备以及提供量子优化算法的理论论证的基础上变分方法和量子近似优化算法（QAOA）.该奖项反映了NSF的法定使命，并已被认为是值得支持的评估使用基金会的智力价值和更广泛的影响审查标准.

项目成果

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 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

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

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