quantum-computing

Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

Hantao Nie, Dong An, and Zaiwen Wen

17 min read

0 likes

⚡ Quantum Brief

AI Audio Summary

0:00 / 0:00

Click to play

Quantum News · Media Library

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractSemidefinite 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.► BibTeX data@article{Nie2026quantumalternating, doi = {10.22331/q-2026-07-08-2154}, url = {https://doi.org/10.22331/q-2026-07-08-2154}, title = {Quantum {A}lternating {D}irection {M}ethod of {M}ultipliers for {S}emidefinite {P}rogramming}, author = {Nie, Hantao and An, Dong and Wen, Zaiwen}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2154}, month = jul, year = {2026} }► References [1] Joran Van Apeldoorn and András Gilyén. ``Improvements in quantum SDP-solving with applications''. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 99:1–99:15. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2019). https://doi.org/10.4230/LIPIcs.ICALP.2019.99 [2] Stephen Boyd, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan. ``Linear matrix inequalities in system and control theory''. SIAM. (1994). https://doi.org/10.1137/1.9781611970777 [3] Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe. ``Handbook of semidefinite programming: theory, algorithms, and applications''. Volume 27. Springer. (2000). https://doi.org/10.1007/978-1-4615-4381-7 [4] Bassem Fares, Dominikus Noll, and Pierre Apkarian. ``Robust control via sequential semidefinite programming''. SIAM Journal on Control and Optimization 40, 1791–1820 (2002). https://doi.org/10.1137/s0363012900373483 [5] Anirudha Majumdar, Georgina Hall, and Amir Ali Ahmadi. ``Recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics''. Annual Review of Control, Robotics, and Autonomous Systems 3, 331–360 (2020). https://doi.org/10.1146/annurev-control-091819-074326 [6] Jess Banks, Sidhanth Mohanty, and Prasad Raghavendra. ``Local statistics, semidefinite programming, and community detection''. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 1298–1316. SIAM (2021). https://doi.org/10.1137/1.9781611976465.79 [7] Dimitris Bertsimas and Yinyu Ye. ``Semidefinite relaxations, multivariate normal distributions, and order statistics''. In Handbook of Combinatorial Optimization: Volume1–3. Pages 1473–1491. Springer (1998). https://doi.org/10.1007/978-1-4613-0303-9_24 [8] Lieven Vandenberghe and Stephen Boyd. ``Applications of semidefinite programming''.

Applied Numerical Mathematics 29, 283–299 (1999). https://doi.org/10.1016/s0168-9274(98)00098-1 [9] Gert RG Lanckriet, Nello Cristianini, Peter Bartlett, Laurent El Ghaoui, and Michael I Jordan. ``Learning the kernel matrix with semidefinite programming''. Journal of Machine Learning Research 5, 27–72 (2004). https://doi.org/10.5555/1005332.1005334 [10] Tijl De Bie and Nello Cristianini. ``Semi-Supervised Learning Using Semi-Definite Programming''.

In Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien, editors, Semi-Supervised Learning. Pages 118–135. MIT Press (2006). https://doi.org/10.7551/mitpress/9780262033589.003.0007 [11] Mahyar Fazlyab, Manfred Morari, and George J Pappas. ``An introduction to neural network analysis via semidefinite programming''. In 2021 60th IEEE Conference on Decision and Control (CDC). Pages 6341–6350. IEEE (2021). https://doi.org/10.1109/cdc45484.2021.9683096 [12] Yi Zhang, Samuel Burer, W Nick Street, Kristin P Bennett, and Emilio Parrado-Hernández. ``Ensemble pruning via semi-definite programming''. Journal of Machine Learning Research 7 (2006). https://doi.org/10.5555/1248547.1248595 [13] Adrian Gepp, Geoff Harris, and Bruce Vanstone. ``Financial applications of semidefinite programming: a review and call for interdisciplinary research''. Accounting & Finance 60, 3527–3555 (2020). https://doi.org/10.1111/acfi.12543 [14] Friedemann Leibfritz and Jan H Maruhn. ``A successive SDP-NSDP approach to a robust optimization problem in finance''. Computational Optimization and Applications 44, 443–466 (2009). https://doi.org/10.1007/s10589-007-9163-4 [15] Hamza Fawzi, James Saunderson, and Pablo A Parrilo. ``Semidefinite approximations of the matrix logarithm''. Foundations of Computational Mathematics 19, 259–296 (2019). https://doi.org/10.1007/s10208-018-9385-0 [16] Mario Berta, Francesco Borderi, Omar Fawzi, and Volkher B Scholz. ``Semidefinite programming hierarchies for constrained bilinear optimization''. Mathematical Programming 194, 781–829 (2022). https://doi.org/10.1007/s10107-021-01650-1 [17] Piotr Mironowicz. ``Semi-definite programming and quantum information''. Journal of Physics A: Mathematical and Theoretical 57, 163002 (2024). https://doi.org/10.1088/1751-8121/ad2b85 [18] Paul Skrzypczyk and Daniel Cavalcanti. ``Semidefinite programming in quantum information science''. IOP Publishing. (2023). https://doi.org/10.1088/978-0-7503-3343-6 [19] Xin Wang, Kun Fang, and Runyao Duan. ``Semidefinite programming converse bounds for quantum communication''. IEEE Transactions on Information Theory 65, 2583–2592 (2018). https://doi.org/10.1109/tit.2018.2874031 [20] Yonina C Eldar. ``A semidefinite programming approach to optimal unambiguous discrimination of quantum states''. IEEE Transactions on Information Theory 49, 446–456 (2003). https://doi.org/10.1109/tit.2002.807291 [21] Michel X Goemans and David P Williamson. ``Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming''. Journal of the ACM (JACM) 42, 1115–1145 (1995). https://doi.org/10.1145/227683.227684 [22] Irene Waldspurger, Alexandre d’Aspremont, and Stéphane Mallat. ``Phase recovery, MaxCut and complex semidefinite programming''. Mathematical Programming 149, 47–81 (2015). https://doi.org/10.1007/s10107-013-0738-9 [23] Etienne de Klerk and Renata Sotirov. ``Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry''. Mathematical Programming 133, 75–91 (2012). https://doi.org/10.1007/s10107-010-0411-5 [24] Qing Zhao, Stefan E Karisch, Franz Rendl, and Henry Wolkowicz. ``Semidefinite programming relaxations for the quadratic assignment problem''. Journal of Combinatorial Optimization 2, 71–109 (1998). https://doi.org/10.1023/a:1009795911987 [25] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. ``A faster cutting plane method and its implications for combinatorial and convex optimization''. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. Pages 1049–1065. IEEE (2015). https://doi.org/10.1109/focs.2015.68 [26] Sanjeev Arora, Elad Hazan, and Satyen Kale. ``The multiplicative weights update method: A meta-algorithm and applications''. Theory of Computing 8, 121–164 (2012). https://doi.org/10.4086/toc.2012.v008a006 [27] Qi Deng, Qing Feng, Wenzhi Gao, Dongdong Ge, Bo Jiang, Yuntian Jiang, Jingsong Liu, Tianhao Liu, Chenyu Xue, Yinyu Ye, and Chuwen Zhang. ``An enhanced alternating direction method of multipliers-based interior point method for linear and conic optimization''. INFORMS Journal on Computing 37, 338–359 (2024). https://doi.org/10.1287/ijoc.2023.0017 [28] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. ``Distributed optimization and statistical learning via the alternating direction method of multipliers''. Foundations and Trends in Machine Learning 3, 1–122 (2011). https://doi.org/10.1561/2200000016 [29] Antonin Chambolle and Thomas Pock. ``A first-order primal-dual algorithm for convex problems with applications to imaging''. Journal of Mathematical Imaging and Vision 40, 120–145 (2011). https://doi.org/10.1007/s10851-010-0251-1 [30] Zaiwen Wen, Donald Goldfarb, and Wotao Yin. ``Alternating direction augmented Lagrangian methods for semidefinite programming''.

Mathematical Programming Computation 2, 203–230 (2010). https://doi.org/10.1007/s12532-010-0017-1 [31] Zhouchen Lin, Huan Li, and Cong Fang. ``Alternating direction method of multipliers for machine learning''. Springer. (2022). https://doi.org/10.1007/978-981-16-9840-8 [32] Brendan O’donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. ``Conic optimization via operator splitting and homogeneous self-dual embedding''. Journal of Optimization Theory and Applications 169, 1042–1068 (2016). https://doi.org/10.1007/s10957-016-0892-3 [33] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M Svore, and Xiaodi Wu. ``Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning''. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:14. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2019). https://doi.org/10.4230/LIPIcs.ICALP.2019.27 [34] Brandon Augustino, Giacomo Nannicini, Tamás Terlaky, and Luis F Zuluaga. ``Quantum interior point methods for semidefinite optimization''. Quantum 7, 1110 (2023). https://doi.org/10.22331/q-2023-09-11-1110 [35] Mohammadhossein Mohammadisiahroudi, Brandon Augustino, Pouya Sampourmahani, and Tamás Terlaky. ``Quantum computing inspired iterative refinement for semidefinite optimization''. Mathematical Programming (2025). https://doi.org/10.1007/s10107-024-02183-z [36] Joran Van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. ``Quantum SDP-Solvers: Better Upper and Lower Bounds''. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). Pages 403–414. IEEE (2017). https://doi.org/10.1109/focs.2017.44 [37] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics''. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Pages 193–204. (2019). https://doi.org/10.1145/3313276.3316366 [38] Chao Ding, Defeng Sun, Jie Sun, and Kim-Chuan Toh. ``Spectral operators of matrices''. Mathematical Programming 168, 509–531 (2018). https://doi.org/10.1007/s10107-017-1162-3 [39] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. ``The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation''. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:14. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2019). https://doi.org/10.4230/LIPIcs.ICALP.2019.33 [40] Lin Lin. ``Lecture notes on quantum algorithms for scientific computation'' (2022). arXiv:2201.08309. arXiv:2201.08309 [41] Paul J. Goulart and Yuwen Chen. ``Clarabel: An interior-point solver for conic programs with quadratic objectives''.

Mathematical Programming Computation (2026). https://doi.org/10.1007/s12532-026-00320-7 [42] Steven Diamond and Stephen Boyd. ``CVXPY: A Python-embedded modeling language for convex optimization''. Journal of Machine Learning Research 17, 1–5 (2016). https://doi.org/10.5555/2946645.3007036 [43] Giacomo Nannicini. ``Quantum algorithms for optimizers''. Volume 37 of MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics. (2025). https://doi.org/10.1137/1.9781611978766 [44] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. ``A faster interior point method for semidefinite programming''. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). Pages 910–918. IEEE (2020). https://doi.org/10.1109/focs46700.2020.00089 [45] Jim Douglas and Henry H Rachford. ``On the numerical solution of heat conduction problems in two and three space variables''. Transactions of the American Mathematical Society 82, 421–439 (1956). https://doi.org/10.1090/s0002-9947-1956-0084194-4 [46] Eli Passow and Louis Raymon. ``Copositive polynomial approximation''. Journal of Approximation Theory 12, 299–304 (1974). https://doi.org/10.1016/0021-9045(74)90071-9 [47] Eli Passow and Louis Raymon. ``Monotone and comonotone approximation''. Proceedings of the American Mathematical Society 42, 390–394 (1974). https://doi.org/10.1090/s0002-9939-1974-0336176-9 [48] Donald J Newman. ``Efficient co-monotone approximation''. Journal of Approximation Theory 25, 189–192 (1979). https://doi.org/10.1016/0021-9045(79)90009-1Cited by[1] Nana Liu and Mark M. Wilde, "Fermi-Dirac thermal measurements: A framework for quantum hypothesis testing and semidefinite optimization", arXiv:2603.04061, (2026). [2] Zhehao Yi and Rahul Bhadani, "The PID Controller Strikes Back: Classical Controller Helps Mitigate Barren Plateaus in Noisy Variational Quantum Circuits", arXiv:2511.14820, (2025). The above citations are from SAO/NASA ADS (last updated successfully 2026-07-08 19:05:02). The list may be incomplete as not all publishers provide suitable and complete citation data.Could not fetch Crossref cited-by data during last attempt 2026-07-08 19:04:54: Could not fetch cited-by data for 10.22331/q-2026-07-08-2154 from Crossref. This is normal if the DOI was registered recently.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractSemidefinite 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.► BibTeX data@article{Nie2026quantumalternating, doi = {10.22331/q-2026-07-08-2154}, url = {https://doi.org/10.22331/q-2026-07-08-2154}, title = {Quantum {A}lternating {D}irection {M}ethod of {M}ultipliers for {S}emidefinite {P}rogramming}, author = {Nie, Hantao and An, Dong and Wen, Zaiwen}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2154}, month = jul, year = {2026} }► References [1] Joran Van Apeldoorn and András Gilyén. ``Improvements in quantum SDP-solving with applications''. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 99:1–99:15. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2019). https://doi.org/10.4230/LIPIcs.ICALP.2019.99 [2] Stephen Boyd, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan. ``Linear matrix inequalities in system and control theory''. SIAM. (1994). https://doi.org/10.1137/1.9781611970777 [3] Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe. ``Handbook of semidefinite programming: theory, algorithms, and applications''. Volume 27. Springer. (2000). https://doi.org/10.1007/978-1-4615-4381-7 [4] Bassem Fares, Dominikus Noll, and Pierre Apkarian. ``Robust control via sequential semidefinite programming''. SIAM Journal on Control and Optimization 40, 1791–1820 (2002). https://doi.org/10.1137/s0363012900373483 [5] Anirudha Majumdar, Georgina Hall, and Amir Ali Ahmadi. ``Recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics''. Annual Review of Control, Robotics, and Autonomous Systems 3, 331–360 (2020). https://doi.org/10.1146/annurev-control-091819-074326 [6] Jess Banks, Sidhanth Mohanty, and Prasad Raghavendra. ``Local statistics, semidefinite programming, and community detection''. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 1298–1316. SIAM (2021). https://doi.org/10.1137/1.9781611976465.79 [7] Dimitris Bertsimas and Yinyu Ye. ``Semidefinite relaxations, multivariate normal distributions, and order statistics''. In Handbook of Combinatorial Optimization: Volume1–3. Pages 1473–1491. Springer (1998). https://doi.org/10.1007/978-1-4613-0303-9_24 [8] Lieven Vandenberghe and Stephen Boyd. ``Applications of semidefinite programming''.

Read Original

Source Information

Source: Quantum Science and Technology (arXiv overlay)

Website: https://quantum-journal.org/feed

Discussion

0 professional contributions

Be the first to add a constructive contribution.

Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

Tags

Source Information