Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2507.14127

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

Garrido, M. Isabel Franco, Alexander M. Dalzell, Sam McArdle

Published Jul 18, 2025• 0 citations
arXivHTMLPDF

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 \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.

DOI
10.48550/arxiv.2507.14127

Related papers

Quantum algorithms for Second-Order Cone Programming and Support Vector Machines

Iordanis Kerenidis, Anupam Prakash, Dániel Szilágyi

We present a quantum interior-point method (IPM) for second-order cone programming (SOCP) that runs in time O~(nrζκδ2log⁡(1/ϵ)) where r is the rank and n the dimension of the SOCP, δ bounds the distance of intermediate solutions from the cone boundary, ζ is a parameter upper bounded by n , and κ is an upper bound on the condition number of matrices arising in the classical IPM for SOCP. The algorithm takes as its input a suitable quantum description of an arbitrary SOCP and outputs a classical description of a δ -approximate ϵ -optimal solution of the given problem.Furthermore, we perform numerical simulations to determine the values of the aforementioned parameters when solving the SOCP up to a fixed precision ϵ . We present experimental evidence that in this case our quantum algorithm exhibits a polynomial speedup over the best classical algorithms for solving general SOCPs that run in time O(nω+0.5) (here, ω is the matrix multiplication exponent, with a value of roughly 2.37 in theory, and up to 3 in practice). For the case of random SVM (support vector machine) instances of size O(n) , the quantum algorithm scales as O(nk) , where the exponent k is estimated to be 2.59 using a least-squares power law. On the same family random instances, the estimated scaling exponent for an external SOCP solver is 3.31 while that for a state-of-the-art SVM solver is 3.11 .

arXiv:1908.06720•Quantum•Apr 8, 2021•34 citations

Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches

Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin +1 more

Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. Recently, quantum algorithms with superpolynomial speedups for solving SDPs have been proposed assuming access to its constraint matrices in quantum superposition. Mutually inspired by both classical and quantum SDP solvers, in this paper we present a sublinear classical algorithm for solving low-rank SDPs which is asymptotically as good as existing quantum algorithms. Specifically, given an SDP with $m$ constraint matrices, each of dimension $n$ and rank $\mathrm{poly}(\log n)$, our algorithm gives a succinct description and any entry of the solution matrix in time $O(m\cdot\mathrm{poly}(\log n,1/\varepsilon))$ given access to a sample-based low-overhead data structure of the constraint matrices, where $\varepsilon$ is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with both the SDP solvers based on the matrix multiplicative weight (MMW) framework and the recent studies of quantum-inspired machine learning algorithms. The cost of solving SDPs by MMW mainly comes from the exponentiation of Hermitian matrices, and we propose two new technical ingredients (compared to previous sample-based algorithms) for this task that may be of independent interest: $\bullet$ Weighted sampling: assuming sampling access to each individual constraint matrix $A_{1},\ldots,A_{\tau}$, we propose a procedure that gives a good approximation of $A=A_{1}+\cdots+A_{\tau}$. $\bullet$ Symmetric approximation: we propose a sampling procedure that gives low-rank spectral decomposition of a Hermitian matrix $A$. This improves upon previous sampling procedures that only give low-rank singular value decompositions, losing the signs of eigenvalues.

•Jan 10, 2019•7 citations

Quantum Speed-ups for Semidefinite Programming

Fernando G. S. L. Brandão, Krysta M. Svore

We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time $n^{\frac{1}{2}} m^{\frac{1}{2}} s^2 \text{poly}(\log(n), \log(m), R, r, 1/δ)$, with $n$ and $s$ the dimension and row-sparsity of the input matrices, respectively, $m$ the number of constraints, $δ$ the accuracy of the solution, and $R, r$ a upper bounds on the size of the optimal primal and dual solutions. This gives a square-root unconditional speed-up over any classical method for solving SDPs both in $n$ and $m$. We prove the algorithm cannot be substantially improved (in terms of $n$ and $m$) giving a $Ω(n^{\frac{1}{2}}+m^{\frac{1}{2}})$ quantum lower bound for solving semidefinite programs with constant $s, R, r$ and $δ$. The quantum algorithm is constructed by a combination of quantum Gibbs sampling and the multiplicative weight method. In particular it is based on a classical algorithm of Arora and Kale for approximately solving SDPs. We present a modification of their algorithm to eliminate the need for solving an inner linear program which may be of independent interest.

arXiv:1609.05537•Sep 18, 2016•31 citations

Quantum Speed-Ups for Solving Semidefinite Programs

Fernando G. S. L. Brandão, Krysta M. Svore

We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time n1/2m1/2s2poly(log(n), log(m), R, r, 1/δ), with n and s the dimension and row-sparsity of the input matrices, respectively, m the number of constraints, δ the accuracy of the solution, and R, r upper bounds on the size of the optimal primal and dual solutions, respectively. This gives a square-root unconditional speed-up over any classical method for solving SDPs both in n and m. We prove the algorithm cannot be substantially improved (in terms of n and m) giving a Ω(n1/2+ m2) quantum lower bound for solving semidefinite programs with constant s, R, r and δ. The quantum algorithm is constructed by a combination of quantum Gibbs sampling and the multiplicative weight method. In particular it is based on a classical algorithm of Arora and Kale for approximately solving SDPs. We present a modification of their algorithm to eliminate the need for solving an inner linear program which may be of independent interest.

Annual Symposium on Foundations of Computer Science•Oct 1, 2017•141 citations

Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming

Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin +1 more

Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. In this paper, we present a proof-of-principle sublinear-time algorithm for solving SDPs with low-rank constraints; specifically, given an SDP with $m$ constraint matrices, each of dimension $n$ and rank $r$, our algorithm can compute any entry and efficient descriptions of the spectral decomposition of the solution matrix. The algorithm runs in time $O(m\cdot\mathrm{poly}(\log n,r,1/\varepsilon))$ given access to a sampling-based low-overhead data structure for the constraint matrices, where $\varepsilon$ is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with 1) SDP solvers based on the matrix multiplicative weight (MMW) framework by Arora and Kale [TOC '12]; 2) sampling-based dequantizing framework pioneered by Tang [STOC '19]. In order to compute the matrix exponential required in the MMW framework, we introduce two new techniques that may be of independent interest: $\bullet$ Weighted sampling: assuming sampling access to each individual constraint matrix $A_{1},\ldots,A_τ$, we propose a procedure that gives a good approximation of $A=A_{1}+\cdots+A_τ$. $\bullet$ Symmetric approximation: we propose a sampling procedure that gives the \emph{spectral decomposition} of a low-rank Hermitian matrix $A$. To the best of our knowledge, this is the first sampling-based algorithm for spectral decomposition, as previous works only give singular values and vectors.

arXiv:1901.03254•Leibniz international proceedings in informatics•Jan 10, 2019•4 citations

Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming.

Nai-Hui Chia, Tongyang Li, Han Hsuan Lin +1 more

Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. In this paper, we present a proof-of-principle sublinear-time algorithm for solving SDPs with low-rank constraints; specifically, given an SDP with m constraint matrices, each of dimension n and rank r, our algorithm can compute any entry and efficient descriptions of the spectral decomposition of the solution matrix. The algorithm runs in time O(m⋅poly(log n,r,1/ε)) given access to a sampling-based low-overhead data structure for the constraint matrices, where ε is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with 1) SDP solvers based on the matrix multiplicative weight (MMW) framework by Arora and Kale [TOC '12]; 2) sampling-based dequantizing framework pioneered by Tang [STOC '19]. In order to compute the matrix exponential required in the MMW framework, we introduce two new techniques that may be of independent interest: - Weighted sampling: assuming sampling access to each individual constraint matrix A₁,…,A_τ, we propose a procedure that gives a good approximation of A = A₁+⋯+A_τ. - Symmetric approximation: we propose a sampling procedure that gives the spectral decomposition of a low-rank Hermitian matrix A. To the best of our knowledge, this is the first sampling-based algorithm for spectral decomposition, as previous works only give singular values and vectors.

Mathematical Foundations of Computer Science•Aug 1, 2020•10 citations
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 mmm linear constraints over nnn variables partitioned into r≤nr \leq nr≤n second-order cones, our quantum algorithm requires O~(rγ5+mγ4)\widetilde{O}(\sqrt{r}γ^5 + \sqrt{m}γ^4)O(r​γ5+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≫rn \gg rn≫r) the naive approach that applies existing SDP algorithms onto SOCPs, which has complexity O~(γ4(n+γn+m))\widetilde{O}(γ^{4}(n + γ\sqrt{n} + \sqrt{m}))O(γ4(n+γn​+m​)). Our classical algorithm for SOCP has complexity O~(nγ4+mγ6)\widetilde{O}(nγ^4 + m γ^6)O(nγ4+mγ6) in the sample-and-query model.
We present a quantum interior-point method (IPM) for second-order cone programming (SOCP) that runs in time O~(nrζκδ2log⁡(1/ϵ)) where r is the rank and n the dimension of the SOCP, δ bounds the distance of intermediate solutions from the cone boundary, ζ is a parameter upper bounded by n , and κ is an upper bound on the condition number of matrices arising in the classical IPM for SOCP. The algorithm takes as its input a suitable quantum description of an arbitrary SOCP and outputs a classical description of a δ -approximate ϵ -optimal solution of the given problem.Furthermore, we perform numerical simulations to determine the values of the aforementioned parameters when solving the SOCP up to a fixed precision ϵ . We present experimental evidence that in this case our quantum algorithm exhibits a polynomial speedup over the best classical algorithms for solving general SOCPs that run in time O(nω+0.5) (here, ω is the matrix multiplication exponent, with a value of roughly 2.37 in theory, and up to 3 in practice). For the case of random SVM (support vector machine) instances of size O(n) , the quantum algorithm scales as O(nk) , where the exponent k is estimated to be 2.59 using a least-squares power law. On the same family random instances, the estimated scaling exponent for an external SOCP solver is 3.31 while that for a state-of-the-art SVM solver is 3.11 .
Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. Recently, quantum algorithms with superpolynomial speedups for solving SDPs have been proposed assuming access to its constraint matrices in quantum superposition. Mutually inspired by both classical and quantum SDP solvers, in this paper we present a sublinear classical algorithm for solving low-rank SDPs which is asymptotically as good as existing quantum algorithms. Specifically, given an SDP with mmm constraint matrices, each of dimension nnn and rank poly(log⁡n)\mathrm{poly}(\log n)poly(logn), our algorithm gives a succinct description and any entry of the solution matrix in time O(m⋅poly(log⁡n,1/ε))O(m\cdot\mathrm{poly}(\log n,1/\varepsilon))O(m⋅poly(logn,1/ε)) given access to a sample-based low-overhead data structure of the constraint matrices, where ε\varepsilonε is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with both the SDP solvers based on the matrix multiplicative weight (MMW) framework and the recent studies of quantum-inspired machine learning algorithms. The cost of solving SDPs by MMW mainly comes from the exponentiation of Hermitian matrices, and we propose two new technical ingredients (compared to previous sample-based algorithms) for this task that may be of independent interest: ∙\bullet∙ Weighted sampling: assuming sampling access to each individual constraint matrix A1,…,AτA_{1},\ldots,A_{\tau}A1​,…,Aτ​, we propose a procedure that gives a good approximation of A=A1+⋯+AτA=A_{1}+\cdots+A_{\tau}A=A1​+⋯+Aτ​. ∙\bullet∙ Symmetric approximation: we propose a sampling procedure that gives low-rank spectral decomposition of a Hermitian matrix AAA. This improves upon previous sampling procedures that only give low-rank singular value decompositions, losing the signs of eigenvalues.
We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time n12m12s2poly(log⁡(n),log⁡(m),R,r,1/δ)n^{\frac{1}{2}} m^{\frac{1}{2}} s^2 \text{poly}(\log(n), \log(m), R, r, 1/δ)n21​m21​s2poly(log(n),log(m),R,r,1/δ), with nnn and sss the dimension and row-sparsity of the input matrices, respectively, mmm the number of constraints, δδδ the accuracy of the solution, and R,rR, rR,r a upper bounds on the size of the optimal primal and dual solutions. This gives a square-root unconditional speed-up over any classical method for solving SDPs both in nnn and mmm. We prove the algorithm cannot be substantially improved (in terms of nnn and mmm) giving a Ω(n12+m12)Ω(n^{\frac{1}{2}}+m^{\frac{1}{2}})Ω(n21​+m21​) quantum lower bound for solving semidefinite programs with constant s,R,rs, R, rs,R,r and δδδ. The quantum algorithm is constructed by a combination of quantum Gibbs sampling and the multiplicative weight method. In particular it is based on a classical algorithm of Arora and Kale for approximately solving SDPs. We present a modification of their algorithm to eliminate the need for solving an inner linear program which may be of independent interest.
We give a quantum algorithm for solving semidefinite programs (SDPs). It has worst-case running time n1/2m1/2s2poly(log(n), log(m), R, r, 1/δ), with n and s the dimension and row-sparsity of the input matrices, respectively, m the number of constraints, δ the accuracy of the solution, and R, r upper bounds on the size of the optimal primal and dual solutions, respectively. This gives a square-root unconditional speed-up over any classical method for solving SDPs both in n and m. We prove the algorithm cannot be substantially improved (in terms of n and m) giving a Ω(n1/2+ m2) quantum lower bound for solving semidefinite programs with constant s, R, r and δ. The quantum algorithm is constructed by a combination of quantum Gibbs sampling and the multiplicative weight method. In particular it is based on a classical algorithm of Arora and Kale for approximately solving SDPs. We present a modification of their algorithm to eliminate the need for solving an inner linear program which may be of independent interest.
Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. In this paper, we present a proof-of-principle sublinear-time algorithm for solving SDPs with low-rank constraints; specifically, given an SDP with mmm constraint matrices, each of dimension nnn and rank rrr, our algorithm can compute any entry and efficient descriptions of the spectral decomposition of the solution matrix. The algorithm runs in time O(m⋅poly(log⁡n,r,1/ε))O(m\cdot\mathrm{poly}(\log n,r,1/\varepsilon))O(m⋅poly(logn,r,1/ε)) given access to a sampling-based low-overhead data structure for the constraint matrices, where ε\varepsilonε is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with 1) SDP solvers based on the matrix multiplicative weight (MMW) framework by Arora and Kale [TOC '12]; 2) sampling-based dequantizing framework pioneered by Tang [STOC '19]. In order to compute the matrix exponential required in the MMW framework, we introduce two new techniques that may be of independent interest: ∙\bullet∙ Weighted sampling: assuming sampling access to each individual constraint matrix A1,…,AτA_{1},\ldots,A_τA1​,…,Aτ​, we propose a procedure that gives a good approximation of A=A1+⋯+AτA=A_{1}+\cdots+A_τA=A1​+⋯+Aτ​. ∙\bullet∙ Symmetric approximation: we propose a sampling procedure that gives the \emph{spectral decomposition} of a low-rank Hermitian matrix AAA. To the best of our knowledge, this is the first sampling-based algorithm for spectral decomposition, as previous works only give singular values and vectors.
Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. In this paper, we present a proof-of-principle sublinear-time algorithm for solving SDPs with low-rank constraints; specifically, given an SDP with m constraint matrices, each of dimension n and rank r, our algorithm can compute any entry and efficient descriptions of the spectral decomposition of the solution matrix. The algorithm runs in time O(m⋅poly(log n,r,1/ε)) given access to a sampling-based low-overhead data structure for the constraint matrices, where ε is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with 1) SDP solvers based on the matrix multiplicative weight (MMW) framework by Arora and Kale [TOC '12]; 2) sampling-based dequantizing framework pioneered by Tang [STOC '19]. In order to compute the matrix exponential required in the MMW framework, we introduce two new techniques that may be of independent interest: - Weighted sampling: assuming sampling access to each individual constraint matrix A₁,…,A_τ, we propose a procedure that gives a good approximation of A = A₁+⋯+A_τ. - Symmetric approximation: we propose a sampling procedure that gives the spectral decomposition of a low-rank Hermitian matrix A. To the best of our knowledge, this is the first sampling-based algorithm for spectral decomposition, as previous works only give singular values and vectors.