Quantum and classical algorithms for SOCP based on the multiplicative weights update method
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908487439613952 |
|---|---|
| author | Garrido, M. Isabel Franco Dalzell, Alexander M. McArdle, Sam |
| author_facet | Garrido, M. Isabel Franco Dalzell, Alexander M. McArdle, Sam |
| contents | 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 \leq n$ second-order cones, our quantum algorithm requires $\widetilde{O}(\sqrt{r}γ^5 + \sqrt{m}γ^4)$ (coherent) queries to the underlying data defining the instance, where $γ$ 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 $\widetilde{O}(γ^{4}(n + γ\sqrt{n} + \sqrt{m}))$. Our classical algorithm for SOCP has complexity $\widetilde{O}(nγ^4 + m γ^6)$ in the sample-and-query model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_14127 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum and classical algorithms for SOCP based on the multiplicative weights update method Garrido, M. Isabel Franco Dalzell, Alexander M. McArdle, Sam Quantum Physics 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 \leq n$ second-order cones, our quantum algorithm requires $\widetilde{O}(\sqrt{r}γ^5 + \sqrt{m}γ^4)$ (coherent) queries to the underlying data defining the instance, where $γ$ 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 $\widetilde{O}(γ^{4}(n + γ\sqrt{n} + \sqrt{m}))$. Our classical algorithm for SOCP has complexity $\widetilde{O}(nγ^4 + m γ^6)$ in the sample-and-query model. |
| title | Quantum and classical algorithms for SOCP based on the multiplicative weights update method |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2507.14127 |