{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T19:49:07Z","timestamp":1783540147567,"version":"3.55.0"},"reference-count":48,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T00:00:00Z","timestamp":1783468800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Quantum Science and Technology - National Science and Technology Major Projec","award":["2024ZD0301900"],"award-info":[{"award-number":["2024ZD0301900"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"\n 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\n \n &#x03F5;<\/mml:mi>\n <\/mml:math>\n -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.\n <\/jats:p>","DOI":"10.22331\/q-2026-07-08-2154","type":"journal-article","created":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T19:06:52Z","timestamp":1783537612000},"page":"2154","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":0,"title":["Quantum Alternating Direction Method of Multipliers for Semidefinite Programming"],"prefix":"10.22331","volume":"10","author":[{"given":"Hantao","family":"Nie","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences, Peking University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dong","family":"An","sequence":"additional","affiliation":[{"name":"Beijing International Center for Mathematical Research, Peking University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zaiwen","family":"Wen","sequence":"additional","affiliation":[{"name":"Beijing International Center for Mathematical Research, Peking University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2026,7,8]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Joran Van Apeldoorn and Andr\u00e1s Gily\u00e9n. ``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\u201399:15. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2019).","DOI":"10.4230\/LIPIcs.ICALP.2019.99"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Stephen Boyd, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan. ``Linear matrix inequalities in system and control theory''. SIAM. (1994).","DOI":"10.1137\/1.9781611970777"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe. ``Handbook of semidefinite programming: theory, algorithms, and applications''. Volume 27. Springer. (2000).","DOI":"10.1007\/978-1-4615-4381-7"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Bassem Fares, Dominikus Noll, and Pierre Apkarian. ``Robust control via sequential semidefinite programming''. SIAM Journal on Control and Optimization 40, 1791\u20131820 (2002).","DOI":"10.1137\/s0363012900373483"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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\u2013360 (2020).","DOI":"10.1146\/annurev-control-091819-074326"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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\u20131316. SIAM (2021).","DOI":"10.1137\/1.9781611976465.79"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Dimitris Bertsimas and Yinyu Ye. ``Semidefinite relaxations, multivariate normal distributions, and order statistics''. In Handbook of Combinatorial Optimization: Volume1\u20133. Pages 1473\u20131491. Springer (1998).","DOI":"10.1007\/978-1-4613-0303-9_24"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Lieven Vandenberghe and Stephen Boyd. ``Applications of semidefinite programming''. Applied Numerical Mathematics 29, 283\u2013299 (1999).","DOI":"10.1016\/s0168-9274(98)00098-1"},{"key":"8","doi-asserted-by":"publisher","unstructured":"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\u201372 (2004).","DOI":"10.5555\/1005332.1005334"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Tijl De Bie and Nello Cristianini. ``Semi-Supervised Learning Using Semi-Definite Programming''. In Olivier Chapelle, Bernhard Sch\u00f6lkopf, and Alexander Zien, editors, Semi-Supervised Learning. Pages 118\u2013135. MIT Press (2006).","DOI":"10.7551\/mitpress\/9780262033589.003.0007"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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\u20136350. IEEE (2021).","DOI":"10.1109\/cdc45484.2021.9683096"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Yi Zhang, Samuel Burer, W Nick Street, Kristin P Bennett, and Emilio Parrado-Hern\u00e1ndez. ``Ensemble pruning via semi-definite programming''. Journal of Machine Learning Research 7 (2006).","DOI":"10.5555\/1248547.1248595"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Adrian Gepp, Geoff Harris, and Bruce Vanstone. ``Financial applications of semidefinite programming: a review and call for interdisciplinary research''. Accounting & Finance 60, 3527\u20133555 (2020).","DOI":"10.1111\/acfi.12543"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Friedemann Leibfritz and Jan H Maruhn. ``A successive SDP-NSDP approach to a robust optimization problem in finance''. Computational Optimization and Applications 44, 443\u2013466 (2009).","DOI":"10.1007\/s10589-007-9163-4"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Hamza Fawzi, James Saunderson, and Pablo A Parrilo. ``Semidefinite approximations of the matrix logarithm''. Foundations of Computational Mathematics 19, 259\u2013296 (2019).","DOI":"10.1007\/s10208-018-9385-0"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Mario Berta, Francesco Borderi, Omar Fawzi, and Volkher B Scholz. ``Semidefinite programming hierarchies for constrained bilinear optimization''. Mathematical Programming 194, 781\u2013829 (2022).","DOI":"10.1007\/s10107-021-01650-1"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Piotr Mironowicz. ``Semi-definite programming and quantum information''. Journal of Physics A: Mathematical and Theoretical 57, 163002 (2024).","DOI":"10.1088\/1751-8121\/ad2b85"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Paul Skrzypczyk and Daniel Cavalcanti. ``Semidefinite programming in quantum information science''. IOP Publishing. (2023).","DOI":"10.1088\/978-0-7503-3343-6"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Xin Wang, Kun Fang, and Runyao Duan. ``Semidefinite programming converse bounds for quantum communication''. IEEE Transactions on Information Theory 65, 2583\u20132592 (2018).","DOI":"10.1109\/tit.2018.2874031"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Yonina C Eldar. ``A semidefinite programming approach to optimal unambiguous discrimination of quantum states''. IEEE Transactions on Information Theory 49, 446\u2013456 (2003).","DOI":"10.1109\/tit.2002.807291"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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\u20131145 (1995).","DOI":"10.1145\/227683.227684"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Irene Waldspurger, Alexandre d\u2019Aspremont, and St\u00e9phane Mallat. ``Phase recovery, MaxCut and complex semidefinite programming''. Mathematical Programming 149, 47\u201381 (2015).","DOI":"10.1007\/s10107-013-0738-9"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Etienne de Klerk and Renata Sotirov. ``Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry''. Mathematical Programming 133, 75\u201391 (2012).","DOI":"10.1007\/s10107-010-0411-5"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Qing Zhao, Stefan E Karisch, Franz Rendl, and Henry Wolkowicz. ``Semidefinite programming relaxations for the quadratic assignment problem''. Journal of Combinatorial Optimization 2, 71\u2013109 (1998).","DOI":"10.1023\/a:1009795911987"},{"key":"24","doi-asserted-by":"publisher","unstructured":"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\u20131065. IEEE (2015).","DOI":"10.1109\/focs.2015.68"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora, Elad Hazan, and Satyen Kale. ``The multiplicative weights update method: A meta-algorithm and applications''. Theory of Computing 8, 121\u2013164 (2012).","DOI":"10.4086\/toc.2012.v008a006"},{"key":"26","doi-asserted-by":"publisher","unstructured":"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\u2013359 (2024).","DOI":"10.1287\/ijoc.2023.0017"},{"key":"27","doi-asserted-by":"publisher","unstructured":"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\u2013122 (2011).","DOI":"10.1561\/2200000016"},{"key":"28","doi-asserted-by":"publisher","unstructured":"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\u2013145 (2011).","DOI":"10.1007\/s10851-010-0251-1"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Zaiwen Wen, Donald Goldfarb, and Wotao Yin. ``Alternating direction augmented Lagrangian methods for semidefinite programming''. Mathematical Programming Computation 2, 203\u2013230 (2010).","DOI":"10.1007\/s12532-010-0017-1"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Zhouchen Lin, Huan Li, and Cong Fang. ``Alternating direction method of multipliers for machine learning''. Springer. (2022).","DOI":"10.1007\/978-981-16-9840-8"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Brendan O\u2019donoghue, 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\u20131068 (2016).","DOI":"10.1007\/s10957-016-0892-3"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Fernando GSL Brand\u00e3o, 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\u201327:14. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2019).","DOI":"10.4230\/LIPIcs.ICALP.2019.27"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Brandon Augustino, Giacomo Nannicini, Tam\u00e1s Terlaky, and Luis F Zuluaga. ``Quantum interior point methods for semidefinite optimization''. Quantum 7, 1110 (2023).","DOI":"10.22331\/q-2023-09-11-1110"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Mohammadhossein Mohammadisiahroudi, Brandon Augustino, Pouya Sampourmahani, and Tam\u00e1s Terlaky. ``Quantum computing inspired iterative refinement for semidefinite optimization''. Mathematical Programming (2025).","DOI":"10.1007\/s10107-024-02183-z"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Joran Van Apeldoorn, Andr\u00e1s Gily\u00e9n, 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\u2013414. IEEE (2017).","DOI":"10.1109\/focs.2017.44"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, 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\u2013204. (2019).","DOI":"10.1145\/3313276.3316366"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Chao Ding, Defeng Sun, Jie Sun, and Kim-Chuan Toh. ``Spectral operators of matrices''. Mathematical Programming 168, 509\u2013531 (2018).","DOI":"10.1007\/s10107-017-1162-3"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Shantanav Chakraborty, Andr\u00e1s Gily\u00e9n, 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\u201333:14. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2019).","DOI":"10.4230\/LIPIcs.ICALP.2019.33"},{"key":"39","unstructured":"Lin Lin. ``Lecture notes on quantum algorithms for scientific computation'' (2022). arXiv:2201.08309."},{"key":"40","doi-asserted-by":"publisher","unstructured":"Paul J. Goulart and Yuwen Chen. ``Clarabel: An interior-point solver for conic programs with quadratic objectives''. Mathematical Programming Computation (2026).","DOI":"10.1007\/s12532-026-00320-7"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Steven Diamond and Stephen Boyd. ``CVXPY: A Python-embedded modeling language for convex optimization''. Journal of Machine Learning Research 17, 1\u20135 (2016).","DOI":"10.5555\/2946645.3007036"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Giacomo Nannicini. ``Quantum algorithms for optimizers''. Volume 37 of MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics. (2025).","DOI":"10.1137\/1.9781611978766"},{"key":"43","doi-asserted-by":"publisher","unstructured":"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\u2013918. IEEE (2020).","DOI":"10.1109\/focs46700.2020.00089"},{"key":"44","doi-asserted-by":"publisher","unstructured":"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\u2013439 (1956).","DOI":"10.1090\/s0002-9947-1956-0084194-4"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Eli Passow and Louis Raymon. ``Copositive polynomial approximation''. Journal of Approximation Theory 12, 299\u2013304 (1974).","DOI":"10.1016\/0021-9045(74)90071-9"},{"key":"46","doi-asserted-by":"publisher","unstructured":"Eli Passow and Louis Raymon. ``Monotone and comonotone approximation''. Proceedings of the American Mathematical Society 42, 390\u2013394 (1974).","DOI":"10.1090\/s0002-9939-1974-0336176-9"},{"key":"47","doi-asserted-by":"publisher","unstructured":"Donald J Newman. ``Efficient co-monotone approximation''. Journal of Approximation Theory 25, 189\u2013192 (1979).","DOI":"10.1016\/0021-9045(79)90009-1"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-07-08-2154\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T19:06:54Z","timestamp":1783537614000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-07-08-2154\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,8]]},"references-count":48,"URL":"https:\/\/doi.org\/10.22331\/q-2026-07-08-2154","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,8]]},"article-number":"2154"}}