NISQ Algorithm for Semidefinite Programming

Semidefinite programs (SDPs) are convex optimization programs with vast applications in control theory, quantum information and combinatorial optimization. Noisy intermediate-scale quantum (NISQ) algorithms aim to efficiently use the current generation of quantum hardware. However, optimizing variational quantum algorithms is a challenge as it is a NP-hard problem that in general requires an exponential time to solve and can contain many far from optimal local minima. 

Here, we present a NISQ algorithm for solving SDPs. The classical optimization program of our NISQ solver is another SDP over a lower dimensional ansatz space. Using the SDP formulation of the Hamiltonian ground state problem, we design a NISQ eigensolver. Unlike variational quantum eigensolvers, the classical optimization program of our eigensolver is convex, can be solved in polynomial time and every local minimum is a global minimum.

Further, we demonstrate the potential of our NISQ SDP solver by finding the largest eigenvalue of $2^{1000}$ dimensional matrices and solving graph problems related to quantum contextuality. We also discuss NISQ algorithms for rank-constrained SDPs. Our work extends the application of NISQ computers onto one of the most successful algorithmic frameworks of the past few decades.