Variational Quantum Algorithms for Semidefinite Programming
ORAL
Abstract
A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N >> M, where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.
*The authors acknowledge support from the National Science Foundation under Grant No. 190761 and the initial support from the Los Alamos National Laboratory (LANL) ASC Beyond Moore's Law project, and later support from the U.S. Department of Energy (DOE), Office of Science, Office of Advanced Scientific Computing Research, under the Accelerated Research in Quantum Computing (ARQC) program
–
Publication: Patel, D., Coles, P. J., & Wilde, M. M. (2021). Variational Quantum Algorithms for Semidefinite Programming. arXiv preprint arXiv:2112.08859.
Presenters
-
Dhrumil J Patel
- Cornell University