{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,14]],"date-time":"2026-11-14T00:51:56Z","timestamp":1794617516268,"version":"4.9.1"},"reference-count":77,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,9,11]],"date-time":"2023-09-11T00:00:00Z","timestamp":1694390400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Defense Advanced Research Projects Agency","award":["W911NF2010022"],"award-info":[{"award-number":["W911NF2010022"]}],"id":[{"id":"https:\/\/ror.org\/02caytj08","id-type":"ROR","asserted-by":"crossref"}]},{"name":"Oak Ridge Leadership Computing Facility","award":["DE-AC05-00OR22725"],"award-info":[{"award-number":["DE-AC05-00OR22725"]}],"id":[{"id":"https:\/\/ror.org\/05p915b28","id-type":"ROR","asserted-by":"crossref"}]},{"name":"Oak Ridge National Lab","award":["N000142312585"],"award-info":[{"award-number":["N000142312585"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>\n                    We present two quantum interior point methods for semidefinite optimization problems, building on recent advances in quantum linear system algorithms. The first scheme, more similar to a classical solution algorithm, computes an inexact search direction and is not guaranteed to explore only feasible points; the second scheme uses a nullspace representation of the Newton linear system to ensure feasibility even with inexact search directions. The second is a novel scheme that might seem impractical in the classical world, but it is well-suited for a hybrid quantum-classical setting. We show that both schemes converge to an optimal solution of the semidefinite optimization problem under standard assumptions. By comparing the theoretical performance of classical and quantum interior point methods with respect to various input parameters, we show that our second scheme obtains a speedup over classical algorithms in terms of the dimension of the problem\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:math>\n                    , but has worse dependence on other numerical parameters.\n                  <\/jats:p>","DOI":"10.22331\/q-2023-09-11-1110","type":"journal-article","created":{"date-parts":[[2023,9,11]],"date-time":"2023-09-11T11:56:12Z","timestamp":1694433372000},"page":"1110","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":28,"title":["Quantum Interior Point Methods for Semidefinite Optimization"],"prefix":"10.22331","volume":"7","author":[{"given":"Brandon","family":"Augustino","sequence":"first","affiliation":[{"name":"Department of Industrial and Systems Engineering, Quantum Computing and Optimization Lab, Lehigh University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giacomo","family":"Nannicini","sequence":"additional","affiliation":[{"name":"Department of Industrial and Systems Engineering, University of Southern California"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tam\u00e1s","family":"Terlaky","sequence":"additional","affiliation":[{"name":"Department of Industrial and Systems Engineering, Quantum Computing and Optimization Lab, Lehigh University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luis F.","family":"Zuluaga","sequence":"additional","affiliation":[{"name":"Department of Industrial and Systems Engineering, Quantum Computing and Optimization Lab, Lehigh University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2023,9,11]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Leonid G. Khachiyan. ``Polynomial algorithms in linear programming&apos;&apos;. USSR Computational Mathematics and Mathematical Physics 20, 53\u201372 (1980).","DOI":"10.1145\/800057.808695"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Narendra Karmarkar. ``A new polynomial-time algorithm for linear programming&apos;&apos;. CombinatoricaPages 373\u2013395 (1984).","DOI":"10.1145\/800057.808695"},{"key":"2","unstructured":"Yurii E. Nesterov and Arkadi Nemirovskii. ``A general approach to polynomial-time algorithms design for convex programming&apos;&apos;. Report, Central Economical and Mathematical Institute, USSR Academy of Sciences, Moscow (1988)."},{"key":"3","doi-asserted-by":"publisher","unstructured":"Yurii E. Nesterov and Arkadi Nemirovskii. ``Interior-Point Polynomial Algorithms in Convex Programming&apos;&apos;. Volume 13. SIAM. (1995).","DOI":"10.1137\/1.9781611970791"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Stephen Boyd, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan. ``Linear Matrix Inequalities in System and Control Theory&apos;&apos;. SIAM. (1994).","DOI":"10.1137\/1.9781611970777"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Eric M. Rains. ``A semidefinite program for distillable entanglement&apos;&apos;. IEEE Transactions on Information Theory 47, 2921\u20132933 (2001).","DOI":"10.1109\/18.959270"},{"key":"6","unstructured":"Gert R.G. Lanckriet, Nello Cristianini, Peter Bartlett, Laurent El Ghaoui, and Michael I. Jordan. ``Learning the kernel matrix with semidefinite programming&apos;&apos;. Journal of Machine Learning Research 5, 27\u201372 (2004)."},{"key":"7","doi-asserted-by":"publisher","unstructured":"Kilian Q. Weinberger and Lawrence K. Saul. ``Unsupervised learning of image manifolds by semidefinite programming&apos;&apos;. International Journal of Computer Vision 70, 77\u201390 (2006).","DOI":"10.1007\/s11263-005-4939-z"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Alexandre d&apos;Aspremont, Laurent El Ghaoui, Michael I. Jordan, and Gert R.G. Lanckriet. ``A direct formulation for sparse PCA using semidefinite programming&apos;&apos;. SIAM Review 49, 434\u2013448 (2007). arXiv:https:\/\/doi.org\/10.48550\/arXiv.cs\/0406021.","DOI":"10.48550\/arXiv.cs\/0406021"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe. ``Handbook of semidefinite programming: Theory, algorithms, and applications&apos;&apos;. Springer Science & Business Media. (2012).","DOI":"10.1007\/978-1-4615-4381-7"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Yonina C. Eldar. ``A semidefinite programming approach to optimal unambiguous discrimination of quantum states&apos;&apos;. IEEE Transactions on Information Theory 49, 446\u2013456 (2003).","DOI":"10.1109\/TIT.2002.807291"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow, Anand Natarajan, and Xiaodi Wu. ``An improved semidefinite programming hierarchy for testing entanglement&apos;&apos;. Communications in Mathematical Physics 352, 881\u2013904 (2017).","DOI":"10.1007\/s00220-017-2859-0"},{"key":"12","unstructured":"John Watrous. ``Semidefinite programs for completely bounded norms&apos;&apos; (2009)."},{"key":"13","doi-asserted-by":"publisher","unstructured":"Michel X. Goemans and David P. Williamson. ``Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming&apos;&apos;. Journal of the ACM (JACM) 42, 1115\u20131145 (1995).","DOI":"10.1145\/227683.227684"},{"key":"14","doi-asserted-by":"publisher","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz. ``On the Shannon capacity of a graph&apos;&apos;. IEEE Transactions on Information Theory 25, 1\u20137 (1979).","DOI":"10.1109\/TIT.1979.1055985"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Erling D. Andersen and Knud D. Andersen. ``The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm&apos;&apos;. In Hans Frenk, Kees Roos, Tam\u00e1s Terlaky, and Shuzhong Zhang, editors, High Performance Optimization. Pages 197\u2013232. Springer (2000).","DOI":"10.1007\/978-1-4757-3216-0_8"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Jos F. Sturm. ``Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones&apos;&apos;. Optimization Methods and Software 11, 625\u2013653 (1999).","DOI":"10.1080\/10556789908805766"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Kim-Chuan Toh, Michael J. Todd, and Reha H. T\u00fct\u00fcnc\u00fc. ``SDPT3\u2014a MATLAB software package for semidefinite programming, version 1.3&apos;&apos;. Optimization Methods and Software 11, 545\u2013581 (1999).","DOI":"10.1080\/10556789908805762"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Farid Alizadeh, Jean-Pierre A. Haeberly, and Michael L. Overton. ``Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results&apos;&apos;. SIAM Journal on Optimization 8, 746\u2013768 (1998).","DOI":"10.1137\/S1052623496304700"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong. ``An improved cutting plane method for convex optimization, convex-concave games, and its applications&apos;&apos;. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Pages 944\u2013953. (2020).","DOI":"10.1145\/3357713.3384284"},{"key":"20","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&apos;&apos;. In Rafail Ostrovsky and Venkatesan Guruswami, editors, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). Pages 1049\u20131065. IEEE (2015).","DOI":"10.1109\/FOCS.2015.68"},{"key":"21","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&apos;&apos;. In Sandy Irani, Lisa O\u2019Conner, and Patrick Kellenberger, editors, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). Pages 910\u2013918. IEEE (2020).","DOI":"10.1109\/FOCS46700.2020.00089"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Renato D.C. Monteiro. ``Polynomial convergence of primal-dual algorithms for semidefinite programming based on the Monteiro and Zhang family of directions&apos;&apos;. SIAM Journal on Optimization 8, 797\u2013812 (1998).","DOI":"10.1137\/S1052623496308618"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Yurii E. Nesterov and Michael J. Todd. ``Self-scaled barriers and interior-point methods for convex programming&apos;&apos;. Mathematics of Operations ResearchPages 1\u201342 (1997).","DOI":"10.1287\/moor.22.1.1"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Yurii E. Nesterov and Michael J. Todd. ``Primal-dual interior-point methods for self-scaled cones&apos;&apos;. SIAM Journal on Optimization 8, 324\u2013364 (1998).","DOI":"10.1137\/S1052623495290209"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora, Elad Hazan, and Satyen Kale. ``The multiplicative weights method: a meta-algorithm and its applications&apos;&apos;. Theory of Computing, 8(6) 121-164 (2012).","DOI":"10.4086\/toc.2012.v008a006"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Fernando G.S.L. Brand\u00e3o and Krysta M. Svore. ``Quantum speed-ups for solving semidefinite programs&apos;&apos;. In Rafail Ostrovsky and Chris Umans, editors, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). Pages 415\u2013426. IEEE (2017).","DOI":"10.1109\/FOCS.2017.45"},{"key":"27","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&apos;&apos;. Quantum 4, 230 (2020).","DOI":"10.22331\/q-2020-02-14-230"},{"key":"28","unstructured":"Sander Gribling. ``Applications of Optimization to Factorization Ranks and Quantum Information Theory&apos;&apos;. PhD. Thesis, CentER, Tilburg University. (2019)."},{"key":"29","doi-asserted-by":"publisher","unstructured":"Joran van Apeldoorn and Andr\u00e1s Gily\u00e9n. ``Improvements in Quantum SDP-Solving with Applications&apos;&apos;. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 99:1\u201399:15. Dagstuhl, Germany (2019). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik.","DOI":"10.4230\/LIPIcs.ICALP.2019.99"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis and Anupam Prakash. ``A quantum interior point method for LPs and SDPs&apos;&apos;. ACM Transactions on Quantum Computing 1, 1\u201332 (2020).","DOI":"10.1145\/3406306"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Pablo A.M. Casares and Miguel Angel Martin-Delgado. ``A quantum interior-point predictor\u2013corrector algorithm for linear programming&apos;&apos;. Journal of Physics A: Mathematical and Theoretical 53, 445305 (2020).","DOI":"10.1088\/1751-8121\/abb439"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis, Anupam Prakash, and D\u00e1niel Szil\u00e1gyi. ``Quantum algorithms for second-order cone programming and support vector machines&apos;&apos;. Quantum 5, 427 (2021).","DOI":"10.22331\/q-2021-04-08-427"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Aharon Ben-Tal and Arkadi Nemirovskii. ``Lectures on modern convex optimization: Analysis, algorithms, and engineering applications&apos;&apos;. SIAM. (2001).","DOI":"10.1137\/1.9780898718829"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Michael J. Todd. ``A study of search directions in primal-dual interior-point methods for semidefinite programming&apos;&apos;. Optimization Methods and Software 11, 1\u201346 (1999).","DOI":"10.1080\/10556789908805745"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Masakazu Kojima, Susumu Shindoh, and Shinji Hara. ``Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices&apos;&apos;. SIAM Journal on Optimization 7, 86\u2013125 (1997).","DOI":"10.1137\/S1052623494269035"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Renato D.C. Monteiro. ``Primal\u2013dual path-following algorithms for semidefinite programming&apos;&apos;. SIAM Journal on Optimization 7, 663\u2013678 (1997).","DOI":"10.1137\/S1052623495293056"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Renato D.C. Monteiro and Yin Zhang. ``A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming&apos;&apos;. Mathematical Programming 81, 281\u2013299 (1998).","DOI":"10.1007\/BF01580085"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Yin Zhang. ``On extending some primal\u2013dual interior-point algorithms from linear programming to semidefinite programming&apos;&apos;. SIAM Journal on Optimization 8, 365\u2013386 (1998).","DOI":"10.1137\/S1052623495296115"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Renato D.C. Monteiro and Takashi Tsuchiya. ``Polynomial convergence of a new family of primal-dual algorithms for semidefinite programming&apos;&apos;. SIAM Journal on Optimization 9, 551\u2013577 (1999).","DOI":"10.1137\/S1052623496312836"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Paul Tseng. ``Search directions and convergence analysis of some infeasible path-following methods for the monotone semi-definite LCP&apos;&apos;. Optimization Methods and Software 9, 245\u2013268 (1998).","DOI":"10.1080\/10556789808805695"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Florian A. Potra and Rongqin Sheng. ``A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming&apos;&apos;. SIAM Journal on Optimization 8, 1007\u20131028 (1998).","DOI":"10.1137\/S1052623495294955"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Yin Zhang. ``On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem&apos;&apos;. SIAM Journal on Optimization 4, 208\u2013227 (1994).","DOI":"10.1137\/0804012"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Janos Korzak. ``Convergence analysis of inexact infeasible-interior-point algorithms for solving linear programming problems&apos;&apos;. SIAM Journal on Optimization 11, 133\u2013148 (2000).","DOI":"10.1137\/S1052623497329993"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Shinji Mizuno and Florian Jarre. ``Global and polynomial-time convergence of an infeasible-interior-point algorithm using inexact computation&apos;&apos;. Mathematical Programming 84 (1999).","DOI":"10.1007\/s10107980020a"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Jacek Gondzio. ``Convergence analysis of an inexact feasible interior point method for convex quadratic programming&apos;&apos;. SIAM Journal on Optimization 23, 1510\u20131527 (2013).","DOI":"10.1137\/120886017"},{"key":"46","doi-asserted-by":"publisher","unstructured":"Guanglu Zhou and Kim-Chuan Toh. ``Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming&apos;&apos;. Mathematical programming 99, 261\u2013282 (2004).","DOI":"10.1007\/s10107-003-0431-5"},{"key":"47","doi-asserted-by":"publisher","unstructured":"Christoph Helmberg, Franz Rendl, Robert J. Vanderbei, and Henry Wolkowicz. ``An interior-point method for semidefinite programming&apos;&apos;. SIAM Journal on Optimization 6, 342\u2013361 (1996).","DOI":"10.1137\/0806020"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Michael B. Cohen, Yin Tat Lee, and Zhao Song. ``Solving linear programs in the current matrix multiplication time&apos;&apos;. Journal of the ACM (JACM) 68, 1\u201339 (2021).","DOI":"10.1145\/3424305"},{"key":"49","doi-asserted-by":"publisher","unstructured":"Fernando G.S.L. Brand\u00e3o, Richard Kueng, and Daniel Stilck Fran\u00e7a. ``Faster quantum and classical SDP approximations for quadratic binary optimization&apos;&apos;. Quantum 6, 625 (2022).","DOI":"10.22331\/q-2022-01-20-625"},{"key":"50","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations&apos;&apos;. Physical Review Letters 103, 150502 (2009).","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"51","doi-asserted-by":"publisher","unstructured":"Ambros M. Gleixner and Daniel E. Steffy. ``Linear programming using limited-precision oracles&apos;&apos;. Mathematical Programming 183, 525\u2013554 (2020).","DOI":"10.1007\/s10107-019-01444-6"},{"key":"52","doi-asserted-by":"publisher","unstructured":"Ambros M. Gleixner, Daniel E. Steffy, and Kati Wolter. ``Improving the accuracy of linear programming solvers with iterative refinement&apos;&apos;. In Joris van der Hoeven and Mark van Hoeij, editors, Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation. Pages 187\u2013194. (2012).","DOI":"10.1145\/2442829.2442858"},{"key":"53","doi-asserted-by":"publisher","unstructured":"Ambros M. Gleixner, Daniel E. Steffy, and Kati Wolter. ``Iterative refinement for linear programming&apos;&apos;. INFORMS Journal on Computing 28, 449\u2013464 (2016).","DOI":"10.1287\/ijoc.2016.0692"},{"key":"54","doi-asserted-by":"publisher","unstructured":"Rolando D. Somma and Yi\u011fit Suba\u015f\u0131. ``Complexity of quantum state verification in the quantum linear systems problem&apos;&apos;. PRX Quantum 2, 010315 (2021).","DOI":"10.1103\/PRXQuantum.2.010315"},{"key":"55","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&apos;&apos;. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Volume 132, pages 33:1\u201333:14. Dagstuhl, Germany (2019). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik.","DOI":"10.48550\/arXiv.1804.01973"},{"key":"56","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&apos;&apos;. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Pages 193\u2013204. (2019).","DOI":"10.1145\/3313276.3316366"},{"key":"57","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs, Robin Kothari, and Rolando D. Somma. ``Quantum algorithm for systems of linear equations with exponentially improved dependence on precision&apos;&apos;. SIAM Journal on Computing 46, 1920\u20131950 (2017).","DOI":"10.1137\/16M1087072"},{"key":"58","doi-asserted-by":"publisher","unstructured":"Lov Grover and Terry Rudolph. ``Creating superpositions that correspond to efficiently integrable probability distributions&apos;&apos; (2002). arXiv:https:\/\/doi.org\/10.48550\/arXiv.quant-ph\/0208112.","DOI":"10.48550\/arXiv.quant-ph\/0208112"},{"key":"59","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis and Anupam Prakash. ``Quantum recommendation systems&apos;&apos; (2016). arXiv:https:\/\/doi.org\/10.48550\/arXiv.1603.08675.","DOI":"10.48550\/arXiv.1603.08675"},{"key":"60","doi-asserted-by":"publisher","unstructured":"Michael Keyl. ``Quantum state estimation and large deviations&apos;&apos;. Reviews in Mathematical Physics 18, 19\u201360 (2006).","DOI":"10.1142\/S0129055X06002565"},{"key":"61","doi-asserted-by":"publisher","unstructured":"Ryan O&apos;Donnell and John Wright. ``Efficient quantum tomography&apos;&apos;. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing. Pages 899\u2013912. (2016).","DOI":"10.1145\/2897518.2897544"},{"key":"62","doi-asserted-by":"publisher","unstructured":"Joran van Apeldoorn, Arjan Cornelissen, Andr\u00e1s Gily\u00e9n, and Giacomo Nannicini. ``Quantum tomography using state-preparation unitaries&apos;&apos;. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 1265\u20131318. SIAM (2023).","DOI":"10.1137\/1.9781611977554.ch47"},{"key":"63","doi-asserted-by":"publisher","unstructured":"Etienne de Klerk, Cornelis Roos, and Tam\u00e1s Terlaky. ``Initialization in semidefinite programming via a self-dual skew-symmetric embedding&apos;&apos;. Operations Research Letters 20, 213\u2013221 (1997).","DOI":"10.1016\/S0167-6377(97)00011-4"},{"key":"64","doi-asserted-by":"publisher","unstructured":"Michael J. Todd, Kim-Chuan Toh, and Reha H. T\u00fct\u00fcnc\u00fc. ``On the Nesterov\u2013Todd direction in semidefinite programming&apos;&apos;. SIAM Journal on Optimization 8, 769\u2013796 (1998).","DOI":"10.1137\/S105262349630060X"},{"key":"65","doi-asserted-by":"publisher","unstructured":"Ron S. Dembo, Stanley C. Eisenstat, and Trond Steihaug. ``Inexact Newton Methods&apos;&apos;. SIAM Journal on Numerical Analysis 19, 400\u2013408 (1982).","DOI":"10.1137\/0719025"},{"key":"66","doi-asserted-by":"publisher","unstructured":"Carl T. Kelley. ``Iterative methods for linear and nonlinear equations&apos;&apos;. SIAM. (1995).","DOI":"10.1137\/1.9781611970944"},{"key":"67","doi-asserted-by":"publisher","unstructured":"Peter B\u00fcrgisser, Michael Clausen, and Mohammad A. Shokrollahi. ``Algebraic complexity theory&apos;&apos;. Springer Science & Business Media. (2013).","DOI":"10.1007\/978-3-662-03338-8"},{"key":"68","doi-asserted-by":"publisher","unstructured":"Volker Strassen. ``Gaussian elimination is not optimal&apos;&apos;. Numerische Mathematik 13, 354\u2013356 (1969).","DOI":"10.1007\/BF02165411"},{"key":"69","doi-asserted-by":"publisher","unstructured":"Raphael Yuster and Uri Zwick. ``Fast sparse matrix multiplication&apos;&apos;. ACM Transactions On Algorithms (TALG) 1, 2\u201313 (2005).","DOI":"10.1145\/1077464.1077466"},{"key":"70","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis and Anupam Prakash. ``A quantum interior point method for LPs and SDPs&apos;&apos; (2018). arXiv:https:\/\/doi.org\/10.48550\/arXiv.1808.09266.","DOI":"10.48550\/arXiv.1808.09266"},{"key":"71","doi-asserted-by":"publisher","unstructured":"Yousef Saad. ``Iterative methods for sparse linear systems&apos;&apos;. SIAM. (2003).","DOI":"10.1137\/1.9780898718003"},{"key":"72","doi-asserted-by":"publisher","unstructured":"Nisheeth K. Vishnoi. ``$Lx= b$: Laplacian Solvers and Their Algorithmic Applications&apos;&apos;. Foundations and Trends\u00ae in Theoretical Computer Science 8, 1\u2013141 (2013).","DOI":"10.1007\/978-3-642-13562-0_2"},{"key":"73","doi-asserted-by":"publisher","unstructured":"Fernando G.S.L. 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&apos;&apos;. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Volume 132, pages 27:1\u201327:14. Dagstuhl, Germany (2019). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik.","DOI":"10.48550\/arXiv.1710.02581"},{"key":"74","doi-asserted-by":"publisher","unstructured":"Yin Tat Lee and Swati Padmanabhan. ``An $\\widetilde{\\mathcal{O}}(m\/\\varepsilon^{3.5})$-cost algorithm for semidefinite programs with diagonal constraints&apos;&apos;. In Jacob Abernethy and Shivani Agarwal, editors, Conference on Learning Theory. Pages 3069\u20133119. PMLR (2020).","DOI":"10.48550\/arXiv.1903.01859"},{"key":"75","doi-asserted-by":"publisher","unstructured":"Cornelis Roos, Tam\u00e1s Terlaky, and Jean-Phillipe Vial. ``Interior Point Methods for Linear Optimization&apos;&apos;. Springer Science & Business Media. (2005).","DOI":"10.1007\/b100325"},{"key":"76","doi-asserted-by":"publisher","unstructured":"Ali Mohammad-Nezhad and Tam\u00e1s Terlaky. ``On the identification of the optimal partition for semidefinite optimization&apos;&apos;. INFOR: Information Systems and Operational Research 58, 1\u201339 (2019). arXiv:https:\/\/doi.org\/10.1080\/03155986.2019.1572853.","DOI":"10.1080\/03155986.2019.1572853"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-09-11-1110\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,11,13]],"date-time":"2026-11-13T15:47:05Z","timestamp":1794584825000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-09-11-1110\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,11]]},"references-count":77,"URL":"https:\/\/doi.org\/10.22331\/q-2023-09-11-1110","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,11]]},"article-number":"1110"}}