Quantum Semidefinite Programming

Semidefinite programs (SDPs) in the classical optimization literature are considered as a generalization of linear programs (LPs), in which the vector inequalities of linear programs are replaced by matrix inequalities. Many quantum information problems can be formulated as SDPs, including combinatorial optimization, control theory, and state discrimination. Typically, SDPs can be solved efficiently in time polynomial in the dimension of the input matrices, using classical algorithms; however with an increase in the involved matrices size, many first-order and second-order methods require multiple gradient evaluations at each iteration that subsequently leads to significant computational overhead.

So far, quantum algorithms have been proposed for solving SDPs with a proven quadratic speedup over their classical counterpart, however such quantum algorithms require a fault-tolerant quantum computer to realize the promised speedup. Since there are no fault-tolerant quantum computers available at the moment, the focus is currently on designing quantum algorithms for solving SDPs that can be implemented on NISQ devices. The authors in this work develop variational quantum algorithms for solving three different kinds of SDPs. The additional objective is to analyze the convergence rates of the algorithms corresponding to the standard formulation of an SDP.

The considered SDPs cases are i) General form (GF): when SDPs are not weakly constrained i.e. the dimension of the constraint variable is not much smaller than the dimension of the objective variable. ii) Standard Form (SF): when SDPs are weakly constrained i.e. the dimension of the constraint variable is much smaller than the dimension of the objective variable. Besides the form (general or standard), the authors further categorize the SDP cases for SF based on the constraints, namely the Equality Constrained Standard Form (ECSF) and Inequality Constrained Standard Form (ICSF).

Firstly, these constrained optimization problems are reduced to their unconstrained forms by employing a series of identities. Then, the final unconstrained form is expressed as a function of expectation values of the input Hermitian operators. These final unconstrained formulations are solved by implementing a gradient-based method using parameterized quantum circuits. These parameterized quantum circuits use the parameter shift rule to evaluate the partial derivatives of the objective function with respect to circuit parameters. Finally, variational quantum algorithms are designed to solve these unconstrained optimization problems. The proposed methods provide bounds on the optimal values, due to the reduction in the search space, as well as the non-convex nature of the objective function landscape in terms of ansatz parameters.

The convergence of the proposed algorithms is simulated for three cases based on the number of constraints (M) and the dimension of the input Hermitian operators (N), and the nature of the constraints: i) N=M, ii) N>M (Equality constraint), and iii) N>M (Inequality Constraint). The algorithms were simulated using the QASM simulator of the Qiskit Python package for three different shot settings, namely 10, 50, and 100 shots. The numerical simulations demonstrate that all three algorithms approximately converge to their respective optimal value, even in the case of few shots.

Overall, the work proposes variational quantum algorithms for different instances of SDPs and demonstrates numerical simulations of their convergence rates. The estimation of the gradient (of the objective function) of the proposed forms is done using parameterized circuits assuming that the estimators are unbiased and with small variance. These results are promising since they indicate that even with small amount of shots and some noise in the quantum system, the algorithm is capable of converging to the optimal solution of the optimization problem, and a potential next step would be to study the effect that a large variance in these estimators would have on the convergence rate of the algorithms. Nevertheless, one should keep in mind that this algorithm is focused on solving simple problems defined as semidefinite programs employing the advantages that variational quantum algorithms provide, in an effort to bridge the gap between existing classical implementations and future quantum fault-tolerant ones. This work focuses on the estimation of the gradient descent that can be challenging in the classical algorithms, and is in line with other quantum implementations that indicate the speedup, while maintaining good performance, compared to corresponding classical implementations.