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

Lecture notes in computer science

Semidefinite programming and its applications to approximation algorithms

Thomas Hofmeister, Martin Hühne

Published Jan 1, 1998• 1 citation
Publisher
DOI
10.1007/bfb0053021

Related papers

Semidefinite Relaxation for Two Mixed Binary Quadratically Constrained Quadratic Programs: Algorithms and Approximation Bounds

Zi Li Xu, Ming-Yi Hong

arXiv:1403.3998•Journal of the Operations Research Society of China•Jul 7, 2015•3 citations

Semidefinite programming and combinatorial optimization

Franz Rendl

Applied Numerical Mathematics•Mar 1, 1999•52 citations

Variational Quantum Algorithms for Semidefinite Programming

Dhrumil Patel, Patrick J. Coles, Mark M. Wilde

A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N ≫ M , where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.

arXiv:2112.08859•Quantum•Jun 17, 2024•25 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

Sparse Approximate Solutions to Semidefinite Programs

Elad Hazan

Springer eBooks•Apr 3, 2008•141 citations

Product Theorems Via Semidefinite Programming

Troy Lee, Rajat Mittal

arXiv:0803.4206•Lecture notes in computer science•Jan 1, 2008•6 citations
A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N ≫ M , where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.
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.