Spring 2020

Quantum Algorithms for Second-Order Cone Programming

Tuesday, Feb. 25, 2020 2:30 pm3:00 pm PST

Add to Calendar


Anupam Prakash (QC Ware)


Calvin Lab Auditorium

Second-order cone programs (SOCPs) are a class of convex optimization problems that generalize linear programs (LPs).  We present a quantum interior-point method for SOCPs with n variables and r 
conic constraints with running time $O( n^{1.5} r^{0.5} \kappa/ \delta^2)$ where $\delta$ bounds the distance of intermediate solutions from the cone boundary and $\kappa$ is an upper bound on the condition number of matrices arising in the classical interior-point method for SOCPs. We present experimental evidence that the proposed quantum algorithm achieves a polynomial speedup over classical SOCP solvers for the Support Vector Machine (SVM) and Portfolio Optimization problems, which are known to be reducible to SOCPs.

PDF icon Anupam Prakash Slides617.16 KB