QSlack: A slack-variable approach for variational quantum semi-definite programming

Understand

Solving optimization problems is a key task for which quantum computers could possibly provide a speedup over the best known classical algorithms.

• Particular classes of optimization problems including semi-definite programming (SDP) and linear programming (LP) have wide applicability in many domains of computer science, engineering, mathematics, and physics.
• Here we focus on semi-definite and linear programs for which the dimensions of the variables involved are exponentially large, so that standard classical SDP and LP solvers are not helpful for such large-scale problems.
• We propose the QSlack and CSlack methods for estimating their optimal values, respectively, which work by 1) introducing slack variables to transform inequality constraints to equality constraints, 2) transforming a constrained optimization to an unconstrained one via the penalty method, and 3) replacing the optimizations over all possible non-negative variables by optimizations over parameterized quantum states and parameterized probability distributions.