Talks
Spring 2020

# Quantum Algorithms for Second-Order Cone Programming

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

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
617.16 KB