15442

Video URL

https://simons.berkeley.edu/talks/quantum-algorithms-second-order-cone-programming

Quantum Algorithms for Second-Order Cone Programming

(2020). Quantum Algorithms for Second-Order Cone Programming. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/quantum-algorithms-second-order-cone-programming

Quantum Algorithms for Second-Order Cone Programming. The Simons Institute for the Theory of Computing, Feb. 25, 2020, https://simons.berkeley.edu/talks/quantum-algorithms-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}}
          }
Anupam Prakash (QC Ware)
Talk number15442
Source RepositorySimons Institute
Subject

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.