Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

Dong An; Hantao Nie; Zaiwen Wen

REVIEW 3 major objections 4 minor 47 references

Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

T0 review · 3 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read An inexact ADMM enhanced by quantum singular value transformation converges to an epsilon-optimal solution of any semidefinite program under strong duality, with a per-iteration cost that avoids classical eigendecompositions.

desk verdict The QADMM construction is genuinely new and worth engaging, but the convergence theorem analyzes different iterates than the algorithm outputs, and the bridge between them is not proven. read the letter →

arxiv 2510.10056 v4 pith:PABCPDDK submitted 2025-10-11 math.OC quant-ph

Hantao Nie , Dong An , Zaiwen Wen This is my paper

classification math.OCquant-ph MSC 90C2268Q1290C25

keywords semidefiniteprogrammingADMMquantumalgorithmsingularvaluetransformationinexactcomplexityanalysisconvexoptimization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper presents QADMM, a quantum alternating direction method of multipliers for semidefinite programming (SDP), and proves it converges to an epsilon-optimal solution under the strong duality assumption. The key idea is to replace the costly eigenvalue decomposition in each ADMM step with a polynomial spectral transformation implemented by quantum singular value transformation (QSVT). The inexact ADMM framework tolerates errors in all the variable updates arising from block-encoding approximation and quantum measurement. The authors derive a convergence rate of O(1/K) plus an error term linear in the per-iteration inaccuracies, then set those inaccuracies to Theta(epsilon) to get an iteration count of O((R_X^2+R_S^2)/epsilon). If correct, the total quantum gate complexity scales as O_tilde((m kappa_A^2 (1+R_y)^2 + n^2 (kappa_A^2 (1+R_y)+R_X))(R_X+R_S)^3/epsilon^3), with dimension scaling improved relative to classical ADMM and quantum interior point methods.

What carries the argument

The central object is the polynomial proximal operator: a polynomial g (and an analogous g2) that approximates the projection onto the positive semidefinite cone, so that the proximal map of the slack variable S becomes g(V) instead of Proj_{S^n_+}(V). This polynomial is chosen to have degree O(1/epsilon) and is implemented via quantum singular value transformation (QSVT), which evaluates a polynomial on the eigenvalues of a Hermitian matrix without classical eigendecomposition. The convergence argument is carried by an error-tolerant recursion on a primal-dual gap function Q(z^k,z), which absorbs the bounded errors from the y-, S-, and X-updates and leads to the O(1/K + delta) ergodic bound

What would settle it

Run the exact inexact ADMM scheme (E.2a)-(E.2i) on a classical computer for a small SDP with a starting point far from the bounded sets, so that the projections Proj_Y, Proj_S, Proj_X substantially move the iterates; if the observed convergence rate or error bound violates O(1/K + delta), the claimed guarantee for the algorithm's outputs fails.

Watch

Extended reading notes

Core claim

The core discovery is that an inexact ADMM scheme for the dual SDP remains convergent even when the projection onto the positive semidefinite cone is replaced by a polynomial spectral operator that can be implemented efficiently on a quantum computer. The authors construct a monotone polynomial g(x) on [-1,1] of degree O(1/epsilon) that approximates max(0,x) to within epsilon, so that its matrix version g(V) approximates the PSD projection of V. They then prove an ergodic convergence theorem for the averaged iterates of the inexact scheme, showing the objective gap and constraint violation are O(1/K + delta), where delta aggregates the per-iteration error bounds. Setting delta = Theta(epsilo

Load-bearing premise

The error bounds in the convergence proof are stated for the unprojected iterates tilde y, tilde S, tilde X, but the algorithm actually projects these onto bounded sets, and the projection step can move an iterate by an arbitrarily large amount without being accounted for in the error analysis.

Editorial extensions

If this is right

If the convergence proof is valid, QADMM reaches an epsilon-optimal SDP solution with K = O((R_X^2+R_S^2)/epsilon) iterations, matching the classical ADMM iteration count while making each iteration cheaper.
The quantum gate complexity O_tilde((m kappa_A^2 (1+R_y)^2 + n^2 (kappa_A^2 (1+R_y)+R_X))(R_X+R_S)^3/epsilon^3) improves over classical ADMM's O(n^6) dimension dependence for dense problems with m=O(n^2).
For SDPs where the optimal primal solution is diagonal or nearly diagonal, QADMM's dependence on the Frobenius radius R_X is more favorable than QMWU's dependence on the trace radius, since R_X grows like sqrt(n) whereas the trace radius grows like n.
The inexact ADMM framework itself provides a robust convergence guarantee for ADMM with errors in all variable updates, which could be reused in other inexact or stochastic ADMM settings.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The main gap in the analysis is that the convergence proof bounds errors on the unprojected iterates, while the algorithm projects y, S, X onto the bounded sets Y, S, X; if the projection moves the iterate by more than the assumed delta, the claimed error bound may not hold for the actual outputs.
The polynomial approximation of the projection is restricted to inputs with bounded spectral norm; extrapolating to unbounded iterates would require an additional scaling argument or a different barrier construction.
A practical implementation would need to test whether the QRAM size eO(2n^2/epsilon) and the condition-number dependence make the speedup real for moderately sized instances, especially for ill-conditioned SDPs.
The same polynomial-proximal plus QSVT template might extend to other conic constraints (for example, second-order cones) as long as a polynomial approximation of the projection exists, opening a wider class of quantum conic optimization problems.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here is the short version: this paper has a genuinely new algorithmic idea — an inexact ADMM whose S-update and X-update use a polynomial approximation of the PSD projection implemented by QSVT — and the complexity model is worked out in unusual detail. But the main theorem does not prove convergence of what Algorithm 1 actually outputs. That gap is central, not cosmetic, and as written the main claim should not be taken as established.

What is actually good: the framing of an ADMM that tolerates errors in the dual variable update, not just in the subproblem solves, is a useful step for quantum optimization. The polynomial proximal operator construction is interesting: replacing eigenvalue decomposition by a degree O(1/epsilon) polynomial and then using QSVT is the right kind of quantum primitive for this problem. The complexity table and per-iteration accounting are careful and give a concrete sense of where the method would sit relative to QMWU and QIPMs.

The soft spots, in order of seriousness.

First, Corollary E.1 is not justified. Theorem E.1 bounds the averaged unprojected variables (tilde X, hat y, tilde S). Algorithm 1 outputs averages of y^k = Proj_Y(tilde y^k + Delta y^k), S^k = Proj_S(...), X^k = Proj_X(...). Projection onto the l1 ball or the bounded PSD set is not an operation whose error is controlled by delta_y, delta_S, delta_X relative to the unprojected point. If hat y^k leaves Y, the projection can move it by roughly ||hat y^k||_1 - R_y, and nothing in the proof bounds that quantity. The same issue applies to S and X. The one-line proof of Corollary E.1 simply asserts the needed bounds.

Second, the implemented loop and the analyzed scheme disagree. Section 3.2 step 2 constructs V^{k+1} from the projected classical y^{k+1}, while the convergence proof uses tilde y^{k+1}. Those are different iterates; the projection error can enter V directly, not through the delta terms. So even the Theorem E.1 analysis may not match what the algorithm computes.

Third, the "exponential speedup" language in Section 1.1 is not supported by the paper's own complexity table, which shows polynomial improvement in n (n^2 vs n^6), and Lemma D.1 hides its construction behind a citation to [36]. These are minor relative to the projection issue.

The paper is for people working on quantum SDP solvers. It deserves a serious referee, not a desk reject: the construction is new, the complexity analysis is detailed, and if the projection bridge can be repaired, this could be a real contribution. I would not cite the convergence guarantee as stated until that repair is made.

Referee Report

3 major / 4 minor

Summary. The paper proposes a quantum alternating direction method of multipliers (QADMM) for the dual SDP (1.2b). An inexact ADMM scheme (3.4a)–(3.4i) is introduced that tolerates errors in the y-, S-, and X-updates arising from quantum subroutines; the PSD projection is replaced by a polynomial proximal operator implemented via QSVT, and the linear system in the y-update is solved by a quantum linear solver. The main theoretical claims are: (i) an ergodic convergence rate O((R_X^2+R_S^2)/K + δ) for the averaged unprojected iterates (Theorem 4.1/E.1); (ii) a corollary asserting the same rate for the projected classical outputs of Algorithm 1 (Corollary 4.1/E.1); and (iii) total complexity bounds in Theorem 4.2/E.2, namely O((s_A+n^2)(R_X^2+R_S^2)/ε_abs) classical operations and O_tilde((m κ_A^2(1+R_y)^2 + n^2(κ_A^2(1+R_y)+R_X))(R_X+R_S)^3/ε_abs^3) quantum gates.

Significance. If the main convergence claim were correct, the dimension scaling would be a substantial improvement over QIPM (polylog n vs. n^3.5) and over classical ADMM for densely constrained SDPs. The inexact-ADMM-with-quantum-errors framework is a natural and potentially useful design, and the explicit polynomial approximation and complexity accounting are strengths. However, the central theorem is proved only for unprojected variables, while the algorithm outputs projected variables; the bridge between the two is not established and, as written, is false in general. This is a load-bearing gap that undermines the paper's central claim.

major comments (3)

[Appendix E, Corollary E.1 (and Corollary 4.1)] Corollary E.1 asserts that ||y_out − \bar y^K||_2 ≤ δ_{\tilde y}+δ_y and ||S_out − \bar S^K||_2 ≤ δ_S, and that the guarantees of Theorem E.1 therefore transfer to Algorithm 1's output. This is not proved. From (E.2b)–(E.2c), y^{k+1} = Proj_Y(\hat y^{k+1}+Δ\tilde y^{k+1}+Δy^{k+1}). Since \hat y^{k+1} is not shown to lie in Y, the projection can move the point by ||\hat y^{k+1}||_1 − R_y, which is independent of δ_{\tilde y} and δ_y and can be arbitrarily large. The same issue applies to S^{k+1}=Proj_S(\tilde S^{k+1}+ΔS^{k+1}) and X^{k+1}=Proj_X(\tilde X^{k+1}+ΔX^{k+1}). No bound is given for ||\hat y^k||_1, ||\tilde S^k||_F, or ||\tilde X^k||_F. Thus the claimed O(1/K+δ) convergence of the algorithm's projected outputs is unsupported.
[Section 3.2, V-update and eq. (3.8)] The implemented V-update uses the projected classical vector y^{k+1} to form the LCU block-encoding (eq. (3.8) and surrounding text), whereas the analyzed scheme (3.4d) defines \hat V^{k+1} := C − A^*(\tilde y^{k+1}) − γ X^k, i.e., it uses \tilde y^{k+1}. These differ by A^*(y^{k+1} − \tilde y^{k+1}). Because y^{k+1} is a projection of \tilde y^{k+1}+Δy^{k+1} and \tilde y^{k+1} is not known to lie in Y, this difference is not controlled by any of the δ tolerances. Consequently, the implemented iteration is not the iteration analyzed in Theorem E.1, even before the projection-bridge issue of Corollary E.1.
[Appendix E, Theorem E.1 proof, eqs. (E.6)–(E.9)] The proof defines the error terms e^{(1)} and e^{(2)} and bounds them using R_X, R_y, R_S, e.g., e^{(1)} = 2δ_{\tilde V}R_X + δ_{\tilde X}R_X + δ_{\tilde S}(R_X+2R_y). These bounds are applied to the unprojected iterates \tilde X^{k+1}, \hat X^{k+1}, and \hat y^{k+1}, which are not constrained to the sets X, Y, S. For instance, the term ⟨Δ\tilde S^{k+1}, \hat X^{k+1} − A^*(\hat y^{k+1}−y)⟩ is bounded by δ_{\tilde S}(R_X+2R_y) without any proof that ||\hat X^{k+1}||_F ≤ R_X or ||\hat y^{k+1}||_1 ≤ R_y. Similarly, the proof assumes a uniform bound B on \tilde V^{k+1} before (E.4). Since these bounds are essential to the telescoping argument, inequality (E.9) and hence the theorem do not follow as stated.

minor comments (4)

[Throughout] There are numerous typos: 'deveplopments' in the Acknowledgements, 'utlizing' in §1.1, 'Quatum linear solver' in §2.5, and 'min' appears stray in Proposition 2.2.
[Section 3.3, Lemma 3.2] The text says 'a convex h satisfying prox = g1 may not exist' and then constructs h via (3.12). It would be helpful to state explicitly whether the constructed h is convex or not; the current wording is confusing, and the claim that nonconvexity 'does not affect the convergence' is not justified in the proof.
[Table 1] The complexity of classical ADMM is listed as O(n^6 + n^4(R_X^2+R_S^2)/ε), but Appendix B.3 derives O(m^3+m^2n^ω+(m^2+s_A+n^ω)(R_X^2+R_S^2)/ε). The table's simplification to n^6 and n^4 should be stated as assuming m=O(n^2) and ω≈2.376, otherwise the comparison is misleading.
[Section 1.1] The phrase 'exponential speedup with respect to the dimension' is overstated: the total gate complexity still scales polynomially (quadratically) in n. The speedup relative to classical ADMM is polynomial, not exponential, in the full complexity expression.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: convergence and complexity follow from explicit approximation and error-tolerance assumptions; the main caveats are correctness gaps, not circularity.

full rationale

The claimed derivation chain is: (i) reformulate the dual SDP as an ADMM; (ii) replace the exact PSD projection by polynomial spectral operators g1 and g2 with a controlled approximation error; (iii) prove an ergodic convergence bound for the inexact ADMM scheme in Theorem E.1 with error term δ = Θ(δ_y + δ_V + δ_X + δ_S); (iv) set δ = Θ(epsilon) and count the per-iteration quantum/classical costs. Each step is derived from stated assumptions rather than from the target conclusion. The polynomial in Lemma 3.1 / D.1 is constructed with an explicit approximation-theoretic error bound of degree O(1/epsilon), not fitted to the SDP solution; the inexact ADMM proof is a descent argument in which the error terms e^(1), e^(2) are bounded by the specified tolerances and assumed radii R_X, R_y, R_S. No inequality in the proof is used as both premise and conclusion. The only self-citation, Wen et al. [44], supports the classical SDPAD comparison and the ADMM iterate form, while the convergence theorem depends on generic ADMM theory [29] and external QSVT/QLS subroutines [22,10,3]; it is not load-bearing. The most serious concern is a correctness gap rather than circularity: Corollary E.1 asserts ∥y_out − bar y^K∥ ≤ δ_y + δ_tilde_y and ∥S_out − bar S^K∥ ≤ δ_S, but Algorithm 1 projects y and S after adding errors, and projection can move the iterate by an amount not controlled by the δ tolerances; also the implemented V-update in Section 3.2 uses projected y^{k+1}, while the analyzed scheme uses tilde y^{k+1}. This is an unproved bridge, not a reduction of the output to the input. The paper also explicitly acknowledges the QRAM limitation in the conclusion, which is an external assumption rather than circularity.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

No free parameters are fit to data. The central assumptions are QRAM, strong duality/bounded optimal solutions, and unproven boundedness of unprojected iterates. No new physical entities are introduced.

free parameters (1)

gamma (ADMM penalty parameter) = 1
Chosen 'without loss of generality' in the convergence analysis; no evidence the complexity estimate is independent of this choice.

assumptions (5)

domain assumption Strong duality holds and a bounded primal-dual optimal solution exists with known bounds R_X, R_y, R_S.
Invoked in Section 1 and Corollary 4.2; standard Slater-type condition not proved for the instances.
domain assumption QRAM data structure can store and query the data matrices and iterates, yielding efficient block-encodings.
Used in Section 2.2 and throughout; the conclusion itself lists QRAM as the main limitation.
standard math Existence of a monotone polynomial approximating max(0,x) on [-1,1] with degree O(1/epsilon), with the same monotonicity.
Lemma D.1 relies on comonotone approximation results [36] but the exact theorem is not quoted; reference [1] is an encyclopedia page.
standard math Quantum subroutines (QLS, QSVT, LCU, tomography) behave as stated in Propositions 2.3-2.5.
The complexity analysis is built on these cited prior results; no re-derivation is provided.
ad hoc to paper The unprojected iterates \hat y^k, \tilde S^k, \tilde X^k satisfy the same norm bounds R_y, R_S, R_X used in the error estimates.
Theorem E.1 and Corollary E.1 require errors proportional to R_X, R_y, R_S for unprojected variables, but only the projected variables are actually bounded; this is the projection gap.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quantum Alternating Direction Method of Multipliers for Semidefinite Programming." pith.science (2026). https://pith.science/paper/PABCPDDK

@misc{pith2026251010056,
  author       = {Pith},
  title        = {Pith review of: Quantum Alternating Direction Method of Multipliers for Semidefinite Programming},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PABCPDDK}},
  note         = {Machine review of arXiv:2510.10056}
}

abstract

Semidefinite programming (SDP) is a fundamental convex optimization problem with wide-ranging applications. However, solving large-scale instances remains computationally challenging due to the high cost of solving linear systems and performing eigenvalue decompositions. In this paper, we present a quantum alternating direction method of multipliers (QADMM) for SDPs, building on recent advances in quantum computing. An inexact ADMM framework is developed, which tolerates errors in the iterates arising from block-encoding approximation and quantum measurement. Within this robust scheme, we design a polynomial proximal operator to address the semidefinite conic constraints and apply the quantum singular value transformation to accelerate the most costly projection updates. We prove that the scheme converges to an $\epsilon$-optimal solution of the SDP problem under the strong duality assumption. A detailed complexity analysis shows that the QADMM algorithm achieves favorable scaling with respect to dimension compared to the classical ADMM algorithm and quantum interior point methods, highlighting its potential for solving large-scale SDPs.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

47 extracted references · 5 linked inside Pith

[36]

Passow and L

E. Passow and L. Raymon. Copositive polynomial approximation.Journal of Approximation Theory, 12 (3):299–304, 1974.(Cited on page 17.)

1974
[1]

R. M. Aarts. Comonotone approximation. MathWorld—A Wolfram Web Resource, n.d. URL https: //mathworld.wolfram.com/ComonotoneApproximation.html. Accessed May 14, 2025.(Cited on page 17.)

2025
[2]

Arora, E

S. Arora, E. Hazan, and S. Kale. Multiplicative weights method: a meta-algorithm and its applications. Theory Comput.(2012, to appear), 2006.(Cited on page 2.)

2012
[3]

Augustino, G

B. Augustino, G. Nannicini, T. Terlaky, and L. F. Zuluaga. Quantum interior point methods for semidefinite optimization.Quantum, 7:1110, 2023.(Cited on pages 2, 4, and 13.)

2023
[4]

Banks, S

J. Banks, S. Mohanty, and P. Raghavendra. Local statistics, semidefinite programming, and community detection. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1298–1316. SIAM, 2021.(Cited on page 2.)

2021
[5]

Berta, F

M. Berta, F. Borderi, O. Fawzi, and V. B. Scholz. Semidefinite programming hierarchies for constrained bilinear optimization.Mathematical Programming, pages 1–49, 2022.(Cited on page 2.) 22

2022
[6]

Bertsimas and Y

D. Bertsimas and Y. Ye. Semidefinite relaxations, multivariate normal distributions, and order statistics. InHandbook of Combinatorial Optimization: Volume1–3, pages 1473–1491. Springer, 1998.(Cited on page 2.)

1998
[7]

S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan.Linear matrix inequalities in system and control theory. SIAM, 1994.(Cited on page 2.)

1994

Show all 47 references

[8]

S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers.Foundations and Trends®in Machine learning, 3(1):1–122, 2011.(Cited on page 2.)

2011
[9]

F. G. Brand˜ ao, A. Kalev, T. Li, C. Y.-Y. Lin, K. M. Svore, and X. Wu. Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning.arXiv preprint arXiv:1710.02581, 2017. (Cited on pages 2 and 12.)

2017 arXiv
[10]

Chakraborty, A

S. Chakraborty, A. Gily´ en, and S. Jeffery. The power of block-encoded matrix powers: improved regression techniques via faster hamiltonian simulation.arXiv preprint arXiv:1804.01973, 2018.(Cited on page 5.)

2018 arXiv
[11]

Chambolle and T

A. Chambolle and T. Pock. A first-order primal-dual algorithm for convex problems with applications to imaging.Journal of mathematical imaging and vision, 40:120–145, 2011.(Cited on page 2.)

2011
[12]

De Bie and N

T. De Bie and N. Cristianini. Semi-supervised learning using semi-definite programming., 2006.(Cited on page 2.)

2006
[13]

de Klerk and R

E. de Klerk and R. Sotirov. Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry.Mathematical programming, 133:75–91, 2012.(Cited on page 2.)

2012
[14]

Q. Deng, Q. Feng, W. Gao, D. Ge, B. Jiang, Y. Jiang, J. Liu, T. Liu, C. Xue, Y. Ye, et al. An enhanced alternating direction method of multipliers-based interior point method for linear and conic optimization. INFORMS Journal on Computing, 2024.(Cited on pages 2 and 11.)

2024
[15]

C. Ding, D. Sun, J. Sun, and K.-C. Toh. Spectral operators of matrices.Mathematical Programming, 168:509–531, 2018.(Cited on page 5.)

2018
[16]

Douglas and H

J. Douglas and H. H. Rachford. On the numerical solution of heat conduction problems in two and three space variables.Transactions of the American mathematical Society, 82(2):421–439, 1956.(Cited on page 14.)

1956
[17]

Y. C. Eldar. A semidefinite programming approach to optimal unambiguous discrimination of quantum states.IEEE Transactions on information theory, 49(2):446–456, 2003.(Cited on page 2.)

2003
[18]

Fares, D

B. Fares, D. Noll, and P. Apkarian. Robust control via sequential semidefinite programming.SIAM Journal on Control and Optimization, 40(6):1791–1820, 2002.(Cited on page 2.)

2002
[19]

Fawzi, J

H. Fawzi, J. Saunderson, and P. A. Parrilo. Semidefinite approximations of the matrix logarithm. Foundations of Computational Mathematics, 19:259–296, 2019.(Cited on page 2.)

2019
[20]

Fazlyab, M

M. Fazlyab, M. Morari, and G. J. Pappas. An introduction to neural network analysis via semidefinite programming. In2021 60th IEEE Conference on Decision and Control (CDC), pages 6341–6350. IEEE, 2021.(Cited on page 2.)

2021
[21]

A. Gepp, G. Harris, and B. Vanstone. Financial applications of semidefinite programming: a review and call for interdisciplinary research.Accounting & Finance, 60(4):3527–3555, 2020.(Cited on page 2.)

2020
[22]

Gily´ en, Y

A. Gily´ en, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019.(Cited on pages 4, 5, and 16.) 23

2019
[23]

M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.Journal of the ACM (JACM), 42(6):1115–1145, 1995.(Cited on page 2.)

1995
[24]

Jiang, T

H. Jiang, T. Kathuria, Y. T. Lee, S. Padmanabhan, and Z. Song. A faster interior point method for semidefinite programming. In2020 IEEE 61st annual symposium on foundations of computer science (FOCS), pages 910–918. IEEE, 2020.(Cited on page 11.)

2020
[25]

G. R. Lanckriet, N. Cristianini, P. Bartlett, L. E. Ghaoui, and M. I. Jordan. Learning the kernel matrix with semidefinite programming.Journal of Machine learning research, 5(Jan):27–72, 2004.(Cited on page 2.)

2004
[26]

Y. T. Lee, A. Sidford, and S. C.-w. Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1049–1065. IEEE, 2015.(Cited on pages 2 and 11.)

2015
[27]

Leibfritz and J

F. Leibfritz and J. H. Maruhn. A successive SDP-NSDP approach to a robust optimization problem in finance.Computational Optimization and Applications, 44:443–466, 2009.(Cited on page 2.)

2009
[28]

L. Lin. Lecture notes on quantum algorithms for scientific computation.arXiv preprint arXiv:2201.08309, 2022.(Cited on page 7.)

2022 arXiv
[29]

Z. Lin, H. Li, and C. Fang.Alternating direction method of multipliers for machine learning. Springer, 2022.(Cited on pages 2 and 15.)

2022
[30]

Majumdar, G

A. Majumdar, G. Hall, and A. A. Ahmadi. Recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics.Annual Review of Control, Robotics, and Autonomous Systems, 3(1):331–360, 2020.(Cited on page 2.)

2020
[31]

Mironowicz

P. Mironowicz. Semi-definite programming and quantum information.Journal of Physics A: Mathematical and Theoretical, 57(16):163002, 2024.(Cited on page 2.)

2024
[32]

Mohammadisiahroudi, B

M. Mohammadisiahroudi, B. Augustino, P. Sampourmahani, and T. Terlaky. Quantum computing inspired iterative refinement for semidefinite optimization.Mathematical Programming, pages 1–40, 2025. (Cited on pages 2, 3, and 13.)

2025
[33]

Nannicini

G. Nannicini. Quantum algorithms for optimizers.arXiv preprint arXiv:2408.07086, 2024.(Cited on page 11.)

2024 arXiv
[34]

D. J. Newman. Efficient co-monotone approximation.Journal of Approximation Theory, 25(3):189–192, 1979.(Cited on page 17.)

1979
[35]

O’donoghue, E

B. O’donoghue, E. Chu, N. Parikh, and S. Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding.Journal of Optimization Theory and Applications, 169:1042–1068, 2016.(Cited on pages 2 and 11.)

2016
[37]

Passow and L

E. Passow and L. Raymon. Monotone and comonotone approximation.Proceedings of the American Mathematical Society, 42(2):390–394, 1974.(Cited on page 17.)

1974
[38]

Skrzypczyk and D

P. Skrzypczyk and D. Cavalcanti.Semidefinite programming in quantum information science. IOP Publishing, 2023.(Cited on page 2.)

2023
[39]

Van Apeldoorn and A

J. Van Apeldoorn and A. Gily´ en. Improvements in quantum SDP-solving with applications.arXiv preprint arXiv:1804.05058, 2018.(Cited on pages 1, 2, 3, and 12.)

2018 arXiv
[40]

Van Apeldoorn, A

J. Van Apeldoorn, A. Gily´ en, S. Gribling, and R. de Wolf. Quantum SDP-solvers: Better upper and lower bounds. In2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 403–414. IEEE, 2017.(Cited on pages 2, 3, and 12.) 24

2017
[41]

Vandenberghe and S

L. Vandenberghe and S. Boyd. Applications of semidefinite programming.Applied Numerical Mathematics, 29(3):283–299, 1999.(Cited on page 2.)

1999
[42]

Waldspurger, A

I. Waldspurger, A. d’Aspremont, and S. Mallat. Phase recovery, maxcut and complex semidefinite programming.Mathematical Programming, 149:47–81, 2015.(Cited on page 2.)

2015
[43]

X. Wang, K. Fang, and R. Duan. Semidefinite programming converse bounds for quantum communication. IEEE Transactions on Information Theory, 65(4):2583–2592, 2018.(Cited on page 2.)

2018
[44]

Z. Wen, D. Goldfarb, and W. Yin. Alternating direction augmented Lagrangian methods for semidefinite programming.Mathematical Programming Computation, 2(3):203–230, 2010.(Cited on pages 2, 3, 6, and 11.)

2010
[45]

Wolkowicz, R

H. Wolkowicz, R. Saigal, and L. Vandenberghe.Handbook of semidefinite programming: theory, algorithms, and applications, volume 27. Springer Science & Business Media, 2012.(Cited on page 2.)

2012
[46]

Zhang, S

Y. Zhang, S. Burer, W. Nick Street, K. P. Bennett, and E. Parrado-Hern´ andez. Ensemble pruning via semi-definite programming.Journal of machine learning research, 7(7), 2006.(Cited on page 2.)

2006
[47]

Q. Zhao, S. E. Karisch, F. Rendl, and H. Wolkowicz. Semidefinite programming relaxations for the quadratic assignment problem.Journal of Combinatorial Optimization, 2:71–109, 1998.(Cited on page 2.) 25

1998

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [36]

Passow and L

E. Passow and L. Raymon. Copositive polynomial approximation.Journal of Approximation Theory, 12 (3):299–304, 1974.(Cited on page 17.)

1974

[2] [1]

R. M. Aarts. Comonotone approximation. MathWorld—A Wolfram Web Resource, n.d. URL https: //mathworld.wolfram.com/ComonotoneApproximation.html. Accessed May 14, 2025.(Cited on page 17.)

2025

[3] [2]

Arora, E

S. Arora, E. Hazan, and S. Kale. Multiplicative weights method: a meta-algorithm and its applications. Theory Comput.(2012, to appear), 2006.(Cited on page 2.)

2012

[4] [3]

Augustino, G

B. Augustino, G. Nannicini, T. Terlaky, and L. F. Zuluaga. Quantum interior point methods for semidefinite optimization.Quantum, 7:1110, 2023.(Cited on pages 2, 4, and 13.)

2023

[5] [4]

Banks, S

J. Banks, S. Mohanty, and P. Raghavendra. Local statistics, semidefinite programming, and community detection. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1298–1316. SIAM, 2021.(Cited on page 2.)

2021

[6] [5]

Berta, F

M. Berta, F. Borderi, O. Fawzi, and V. B. Scholz. Semidefinite programming hierarchies for constrained bilinear optimization.Mathematical Programming, pages 1–49, 2022.(Cited on page 2.) 22

2022

[7] [6]

Bertsimas and Y

D. Bertsimas and Y. Ye. Semidefinite relaxations, multivariate normal distributions, and order statistics. InHandbook of Combinatorial Optimization: Volume1–3, pages 1473–1491. Springer, 1998.(Cited on page 2.)

1998

[8] [7]

S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan.Linear matrix inequalities in system and control theory. SIAM, 1994.(Cited on page 2.)

1994