AF: Small: Provable Quantum Advantages in Optimization

University Of Maryland, College Park, College Park MD

Investigators

Abstract

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.