Talks
Spring 2020

Quantum Algorithms for Second-Order Cone Programming

Tuesday, February 25th, 2020, 2:30 pm3:00 pm

Add to Calendar

Speaker: 

Anupam Prakash (QC Ware)

Location: 

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.

AttachmentSize
PDF icon Anupam Prakash Slides617.16 KB