QSlack I: Theory of a slack-variable approach for variational quantum semi-definite programming

Many optimization tasks in the classical regime fall under the broad category of semidefinite programs (SDPs). In this work, we introduce a new way of reformulating semidefinite programs as quantum optimization tasks that can be solved by variational quantum algorithms (VQAs). Our variational method guarantees bounds on both the primal and dual optimization problems, thus bounding the actual optimal value from both above and below. To do so, we employ slack variables in the form of scaled, parametrized quantum states to transform inequality constraints to equality constraints. Then, we approximately enforce this constraint in an unconstrained formulation through the introduction of a penalty term defined by the Hilbert-Schmidt norm, which we can efficiently estimate on a quantum computer via the destructive swap test. Working with Pauli basis representations of the various components of the general SDP formulation allows us to apply our method to a broad range of example applications. In the sequel presentation, "QSlack II: Applications of a slack-variable approach for variational quantum semi-definite programming," we provide numerical evidence that showcases how our algorithm works in practice for applications of interest in quantum information.