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:1901.03254 · Leibniz international proceedings in informatics

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

Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, Chunhao Wang

Published Jan 10, 2019• 4 citations
arXivHTMLPDF

Abstract

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.

DOI
10.4230/lipics.mfcs.2020.23

Related papers

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

Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma

Fernando G. S. L. Brandão, Alexander M. Dalzell, András Gilyén +1 more

We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved $\widetilde{O}(\sqrt{n}+\sqrt{m})$ dependence on matrix dimension $n$ and constraint number $m$. Compared with the $\widetilde{O}(mn)$ runtime of existing classical methods, this suggests a quartic quantum speedup when $m \approx n$. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let $s$ denote the the input matrix sparsity and $γ:=Rr/\varepsilon$ capture dependence on the primal $(R)$ and dual $(r)$ radii as well as target accuracy $(\varepsilon)$. When $γ^2\leq\min\{m,n/s\}$, our solver runs in time $\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)$. For $γ=O(1)$, this is $\widetilde{O}\left((n+m)s\right)$ and sublinear in the $O(mns)$ input size. Similar to the quantum algorithms, this matches known lower bounds with respect to $m$ and $n$, up to logarithmic factors. This implies that, with respect to dimensions $m$ and $n$, there is no super-quadratic quantum advantage for generic sparse SDP solving.

quant-pharXiv:2609.40302•Oct 1, 2026•0 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 SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning

Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li +3 more

We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s. The first algorithm assumes an input model where one is given access to an oracle to the entries of the matrices at unit cost. We show that it has run time O~(s^2 (sqrt{m} epsilon^{-10} + sqrt{n} epsilon^{-12})), with epsilon the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms (when m ~~ n). The second algorithm assumes a fully quantum input model in which the input matrices are given as quantum states. We show that its run time is O~(sqrt{m}+poly(r))*poly(log m,log n,B,epsilon^{-1}), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only polylogarithmically in n and polynomially in r. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state rho with rank at most r, we show we can find in time sqrt{m}*poly(log m,log n,r,epsilon^{-1}) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as rho on the m measurements, up to error epsilon. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding these Hamiltonians, with a poly-logarithmic dependence on its dimension, which is based on ideas developed in quantum principal component analysis. We also develop a "fast" quantum OR lemma with a quadratic improvement in gate complexity over the construction of Harrow et al. [Harrow et al., 2017]. We believe both techniques might be of independent interest.

•Jan 1, 2019•60 citations

Exponential Quantum Speed-ups for Semidefinite Programming with Applications to Quantum Learning

Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li +3 more

We give semidefinite program (SDP) quantum solvers with an exponential speed-up over classical ones. Specifically, we consider SDP instances with $m$ constraint matrices of dimension $n$, each of rank at most $r$, and assume that the input matrices of the SDP are given as quantum states (after a suitable normalization). Then we show there is a quantum algorithm that solves the SDP feasibility problem with accuracy $\epsilon$ by using $\sqrt{m}\log m\cdot\text{poly}(\log n,r,\epsilon^{-1})$ quantum gates. The dependence on $n$ provides an exponential improvement over the work of Brand\~ao and Svore and the work of van Apeldoorn et al., and demonstrates an exponential quantum speed-up when $m$ and $r$ are small. We apply the SDP solver to the problem of learning a good description of a quantum state with respect to a set of measurements: Given $m$ measurements and a supply of copies of an unknown state $\rho$, we show we can find in time $\sqrt{m}\log m\cdot\text{poly}(\log n,r,\epsilon^{-1})$ a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as $\rho$ on the $m$ measurements up to error $\epsilon$. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle. As in previous work, we obtain our algorithm by quantizing classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians with a poly-logarithmic dependence on its dimension based on the techniques developed in quantum principal component analysis, which could be of independent interest.

•Oct 6, 2017•14 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
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.
We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved O~(n+m)\widetilde{O}(\sqrt{n}+\sqrt{m})O(n​+m​) dependence on matrix dimension nnn and constraint number mmm. Compared with the O~(mn)\widetilde{O}(mn)O(mn) runtime of existing classical methods, this suggests a quartic quantum speedup when m≈nm \approx nm≈n. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let sss denote the the input matrix sparsity and γ:=Rr/εγ:=Rr/\varepsilonγ:=Rr/ε capture dependence on the primal (R)(R)(R) and dual (r)(r)(r) radii as well as target accuracy (ε)(\varepsilon)(ε). When γ2≤min⁡{m,n/s}γ^2\leq\min\{m,n/s\}γ2≤min{m,n/s}, our solver runs in time O~(nsγ4.5+msγ2)\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)O(nsγ4.5+msγ2). For γ=O(1)γ=O(1)γ=O(1), this is O~((n+m)s)\widetilde{O}\left((n+m)s\right)O((n+m)s) and sublinear in the O(mns)O(mns)O(mns) input size. Similar to the quantum algorithms, this matches known lower bounds with respect to mmm and nnn, up to logarithmic factors. This implies that, with respect to dimensions mmm and nnn, there is no super-quadratic quantum advantage for generic sparse SDP solving.
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 two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s. The first algorithm assumes an input model where one is given access to an oracle to the entries of the matrices at unit cost. We show that it has run time O~(s^2 (sqrt{m} epsilon^{-10} + sqrt{n} epsilon^{-12})), with epsilon the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms (when m ~~ n). The second algorithm assumes a fully quantum input model in which the input matrices are given as quantum states. We show that its run time is O~(sqrt{m}+poly(r))*poly(log m,log n,B,epsilon^{-1}), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only polylogarithmically in n and polynomially in r. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state rho with rank at most r, we show we can find in time sqrt{m}*poly(log m,log n,r,epsilon^{-1}) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as rho on the m measurements, up to error epsilon. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding these Hamiltonians, with a poly-logarithmic dependence on its dimension, which is based on ideas developed in quantum principal component analysis. We also develop a "fast" quantum OR lemma with a quadratic improvement in gate complexity over the construction of Harrow et al. [Harrow et al., 2017]. We believe both techniques might be of independent interest.
We give semidefinite program (SDP) quantum solvers with an exponential speed-up over classical ones. Specifically, we consider SDP instances with mmm constraint matrices of dimension nnn, each of rank at most rrr, and assume that the input matrices of the SDP are given as quantum states (after a suitable normalization). Then we show there is a quantum algorithm that solves the SDP feasibility problem with accuracy ϵ\epsilonϵ by using mlog⁡m⋅poly(log⁡n,r,ϵ−1)\sqrt{m}\log m\cdot\text{poly}(\log n,r,\epsilon^{-1})m​logm⋅poly(logn,r,ϵ−1) quantum gates. The dependence on nnn provides an exponential improvement over the work of Brand\~ao and Svore and the work of van Apeldoorn et al., and demonstrates an exponential quantum speed-up when mmm and rrr are small. We apply the SDP solver to the problem of learning a good description of a quantum state with respect to a set of measurements: Given mmm measurements and a supply of copies of an unknown state ρ\rhoρ, we show we can find in time mlog⁡m⋅poly(log⁡n,r,ϵ−1)\sqrt{m}\log m\cdot\text{poly}(\log n,r,\epsilon^{-1})m​logm⋅poly(logn,r,ϵ−1) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as ρ\rhoρ on the mmm measurements up to error ϵ\epsilonϵ. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle. As in previous work, we obtain our algorithm by quantizing classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians with a poly-logarithmic dependence on its dimension based on the techniques developed in quantum principal component analysis, which could be of independent interest.
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.