Variational Quantum Algorithms for Semidefinite Programming

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\gg 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.

40 pages, 12 figures

References in corpus (17)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum algorithm for solving linear systems of equations
• Variational Quantum Algorithms
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum Circuit Learning
• Evaluating analytic gradients on quantum hardware
• Self-testing of quantum systems: a review
• Hybrid Quantum-Classical Approach to Quantum Optimal Control
• Efficient quantum measurement of Pauli operators in the presence of finite sampling error
• A Semidefinite Programming Approach to Optimal Unambiguous Discrimination of Quantum States
• Quantum SDP-Solvers: Better upper and lower bounds
• Semidefinite programming strong converse bounds for classical capacity
• Characterizing the loss landscape of variational quantum circuits
• Noisy intermediate-scale quantum algorithm for semidefinite programming

Cited by in corpus (7)

• Stochastic noise can be helpful for variational quantum algorithms
• Recursive Quantum Relaxation for Combinatorial Optimization Problems
• QSlack: A slack-variable approach for variational quantum semi-definite programming
• Enhancing Variational Quantum Circuit Training: An Improved Neural Network Approach for Barren Plateau Mitigation
• Dual-VQE: A quantum algorithm to lower bound the ground-state energy
• Quantum natural gradient with thermal-state initialization
• Constrained free energy minimization for the design of thermal states and stabilizer thermodynamic systems