Quantum Algorithms for Second-Order Cone Programming

          @misc{ scivideos_15442,
            doi = {},
            url = {https://simons.berkeley.edu/talks/quantum-algorithms-second-order-cone-programming},
            author = {},
            keywords = {},
            language = {en},
            title = {Quantum Algorithms for Second-Order Cone Programming},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {feb},
            note = {15442 see, \url{https://scivideos.org/Simons-Institute/15442}}
          }
          

Abstract

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.