Quantum and classical algorithms for SOCP based on the multiplicative weights update method

Abstract

We give classical and quantum algorithms for approximately solving second-order cone programs (SOCPs) based on the multiplicative weights (MW) update method. Our approach follows the MW framework previously applied to semidefinite programs (SDPs), of which SOCP is a special case. We show that the additional structure of SOCPs can be exploited to give better runtime with SOCP-specific algorithms. For an SOCP with $m$ linear constraints over $n$ variables partitioned into $r\le n$ second-order cones, our quantum algorithm requires $\tilde{O}(\sqrt{r}{\gamma }^5+\sqrt{m}{\gamma }^4)$ (coherent) queries to the underlying data defining the instance, where $\gamma$ is a scale-invariant parameter proportional to the inverse precision. This nearly matches the complexity of solving linear programs (LPs), which are a less expressive subset of SOCP. It also outperforms (especially if $n\gg r$) the naive approach that applies existing SDP algorithms onto SOCPs, which has complexity $\tilde{O}({\gamma }^4(n+\gamma \sqrt{n}+\sqrt{m}))$. Our classical algorithm for SOCP has complexity $\tilde{O}(n{\gamma }^4+m{\gamma }^6)$ in the sample-and-query model.