Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning

Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li +3

We give two quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with $m$ constraint matrices, each of dimension $n$,…