Quantum Interior Point Methods for Semidefinite Optimization

Brandon Augustino1, Giacomo Nannicini2, Tamás Terlaky1, and Luis F. Zuluaga1

1Department of Industrial and Systems Engineering, Quantum Computing and Optimization Lab, Lehigh University
2Department of Industrial and Systems Engineering, University of Southern California

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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$, but has worse dependence on other numerical parameters.

Semidefinite optimization (SDO) yields a fundamental family of convex optimization problems with vast expressive power. SDO problems generalize linear optimization problems, and aside from finding application in control, information theory, statistics and machine learning, SDO can also be used to approximate the solution to combinatorial optimization problems. The best performing classical algorithms for solving SDO problems are Interior Point Methods (IPMs), and therefore it is natural to investigate whether the IPM framework can be accelerated in a quantum setting. We propose two convergent quantum IPMs for SDO, obtaining a quantum speedup in the problem dimension at the cost of worse dependence on the precision and a condition number bound for the Newton linear systems that arise in each iteration.

► BibTeX data

► References

[1] Leonid G. Khachiyan. ``Polynomial algorithms in linear programming''. USSR Computational Mathematics and Mathematical Physics 20, 53–72 (1980).

[2] Narendra Karmarkar. ``A new polynomial-time algorithm for linear programming''. CombinatoricaPages 373–395 (1984).

[3] Yurii E. Nesterov and Arkadi Nemirovskii. ``A general approach to polynomial-time algorithms design for convex programming''. Report, Central Economical and Mathematical Institute, USSR Academy of Sciences, Moscow (1988).

[4] Yurii E. Nesterov and Arkadi Nemirovskii. ``Interior-Point Polynomial Algorithms in Convex Programming''. Volume 13. SIAM. (1995).

[5] Stephen Boyd, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan. ``Linear Matrix Inequalities in System and Control Theory''. SIAM. (1994).

[6] Eric M. Rains. ``A semidefinite program for distillable entanglement''. IEEE Transactions on Information Theory 47, 2921–2933 (2001).

[7] Gert R.G. 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).

[8] Kilian Q. Weinberger and Lawrence K. Saul. ``Unsupervised learning of image manifolds by semidefinite programming''. International Journal of Computer Vision 70, 77–90 (2006).

[9] Alexandre d'Aspremont, Laurent El Ghaoui, Michael I. Jordan, and Gert R.G. Lanckriet. ``A direct formulation for sparse PCA using semidefinite programming''. SIAM Review 49, 434–448 (2007). arXiv:https:/​/​doi.org/​10.48550/​arXiv.cs/​0406021.

[10] Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe. ``Handbook of semidefinite programming: Theory, algorithms, and applications''. Springer Science & Business Media. (2012).

[11] Yonina C. Eldar. ``A semidefinite programming approach to optimal unambiguous discrimination of quantum states''. IEEE Transactions on Information Theory 49, 446–456 (2003).

[12] Aram W. Harrow, Anand Natarajan, and Xiaodi Wu. ``An improved semidefinite programming hierarchy for testing entanglement''. Communications in Mathematical Physics 352, 881–904 (2017).

[13] John Watrous. ``Semidefinite programs for completely bounded norms'' (2009).

[14] 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).

[15] László Lovász. ``On the Shannon capacity of a graph''. IEEE Transactions on Information Theory 25, 1–7 (1979).

[16] Erling D. Andersen and Knud D. Andersen. ``The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm''. In Hans Frenk, Kees Roos, Tamás Terlaky, and Shuzhong Zhang, editors, High Performance Optimization. Pages 197–232. Springer (2000).

[17] Jos F. Sturm. ``Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones''. Optimization Methods and Software 11, 625–653 (1999).

[18] Kim-Chuan Toh, Michael J. Todd, and Reha H. Tütüncü. ``SDPT3—a MATLAB software package for semidefinite programming, version 1.3''. Optimization Methods and Software 11, 545–581 (1999).

[19] Farid Alizadeh, Jean-Pierre A. Haeberly, and Michael L. Overton. ``Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results''. SIAM Journal on Optimization 8, 746–768 (1998).

[20] 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''. 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–953. (2020).

[21] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. ``A faster cutting plane method and its implications for combinatorial and convex optimization''. In Rafail Ostrovsky and Venkatesan Guruswami, editors, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). Pages 1049–1065. IEEE (2015).

[22] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. ``A faster interior point method for semidefinite programming''. In Sandy Irani, Lisa O’Conner, and Patrick Kellenberger, editors, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). Pages 910–918. IEEE (2020).

[23] Renato D.C. Monteiro. ``Polynomial convergence of primal-dual algorithms for semidefinite programming based on the Monteiro and Zhang family of directions''. SIAM Journal on Optimization 8, 797–812 (1998).

[24] Yurii E. Nesterov and Michael J. Todd. ``Self-scaled barriers and interior-point methods for convex programming''. Mathematics of Operations ResearchPages 1–42 (1997).

[25] Yurii E. Nesterov and Michael J. Todd. ``Primal-dual interior-point methods for self-scaled cones''. SIAM Journal on Optimization 8, 324–364 (1998).

[26] Sanjeev Arora, Elad Hazan, and Satyen Kale. ``The multiplicative weights method: a meta-algorithm and its applications''. Theory of Computing, 8(6) 121-164 (2012).

[27] Fernando G.S.L. Brandão and Krysta M. Svore. ``Quantum speed-ups for solving semidefinite programs''. In Rafail Ostrovsky and Chris Umans, editors, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). Pages 415–426. IEEE (2017).

[28] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. ``Quantum SDP-solvers: Better upper and lower bounds''. Quantum 4, 230 (2020).

[29] Sander Gribling. ``Applications of Optimization to Factorization Ranks and Quantum Information Theory''. PhD. Thesis, CentER, Tilburg University. (2019).

[30] Joran van Apeldoorn and András Gilyén. ``Improvements in Quantum SDP-Solving with Applications''. 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–99:15. Dagstuhl, Germany (2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.

[31] Iordanis Kerenidis and Anupam Prakash. ``A quantum interior point method for LPs and SDPs''. ACM Transactions on Quantum Computing 1, 1–32 (2020).

[32] Pablo A.M. Casares and Miguel Angel Martin-Delgado. ``A quantum interior-point predictor–corrector algorithm for linear programming''. Journal of Physics A: Mathematical and Theoretical 53, 445305 (2020).

[33] Iordanis Kerenidis, Anupam Prakash, and Dániel Szilágyi. ``Quantum algorithms for second-order cone programming and support vector machines''. Quantum 5, 427 (2021).

[34] Aharon Ben-Tal and Arkadi Nemirovskii. ``Lectures on modern convex optimization: Analysis, algorithms, and engineering applications''. SIAM. (2001).

[35] Michael J. Todd. ``A study of search directions in primal-dual interior-point methods for semidefinite programming''. Optimization Methods and Software 11, 1–46 (1999).

[36] Masakazu Kojima, Susumu Shindoh, and Shinji Hara. ``Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices''. SIAM Journal on Optimization 7, 86–125 (1997).

[37] Renato D.C. Monteiro. ``Primal–dual path-following algorithms for semidefinite programming''. SIAM Journal on Optimization 7, 663–678 (1997).

[38] 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''. Mathematical Programming 81, 281–299 (1998).

[39] Yin Zhang. ``On extending some primal–dual interior-point algorithms from linear programming to semidefinite programming''. SIAM Journal on Optimization 8, 365–386 (1998).

[40] Renato D.C. Monteiro and Takashi Tsuchiya. ``Polynomial convergence of a new family of primal-dual algorithms for semidefinite programming''. SIAM Journal on Optimization 9, 551–577 (1999).

[41] Paul Tseng. ``Search directions and convergence analysis of some infeasible path-following methods for the monotone semi-definite LCP''. Optimization Methods and Software 9, 245–268 (1998).

[42] Florian A. Potra and Rongqin Sheng. ``A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming''. SIAM Journal on Optimization 8, 1007–1028 (1998).

[43] Yin Zhang. ``On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem''. SIAM Journal on Optimization 4, 208–227 (1994).

[44] Janos Korzak. ``Convergence analysis of inexact infeasible-interior-point algorithms for solving linear programming problems''. SIAM Journal on Optimization 11, 133–148 (2000).

[45] Shinji Mizuno and Florian Jarre. ``Global and polynomial-time convergence of an infeasible-interior-point algorithm using inexact computation''. Mathematical Programming 84 (1999).

[46] Jacek Gondzio. ``Convergence analysis of an inexact feasible interior point method for convex quadratic programming''. SIAM Journal on Optimization 23, 1510–1527 (2013).

[47] Guanglu Zhou and Kim-Chuan Toh. ``Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming''. Mathematical programming 99, 261–282 (2004).

[48] Christoph Helmberg, Franz Rendl, Robert J. Vanderbei, and Henry Wolkowicz. ``An interior-point method for semidefinite programming''. SIAM Journal on Optimization 6, 342–361 (1996).

[49] Michael B. Cohen, Yin Tat Lee, and Zhao Song. ``Solving linear programs in the current matrix multiplication time''. Journal of the ACM (JACM) 68, 1–39 (2021).

[50] Fernando G.S.L. Brandão, Richard Kueng, and Daniel Stilck França. ``Faster quantum and classical SDP approximations for quadratic binary optimization''. Quantum 6, 625 (2022).

[51] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Physical Review Letters 103, 150502 (2009).

[52] Ambros M. Gleixner and Daniel E. Steffy. ``Linear programming using limited-precision oracles''. Mathematical Programming 183, 525–554 (2020).

[53] Ambros M. Gleixner, Daniel E. Steffy, and Kati Wolter. ``Improving the accuracy of linear programming solvers with iterative refinement''. In Joris van der Hoeven and Mark van Hoeij, editors, Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation. Pages 187–194. (2012).

[54] Ambros M. Gleixner, Daniel E. Steffy, and Kati Wolter. ``Iterative refinement for linear programming''. INFORMS Journal on Computing 28, 449–464 (2016).

[55] Rolando D. Somma and Yiğit Subaşı. ``Complexity of quantum state verification in the quantum linear systems problem''. PRX Quantum 2, 010315 (2021).

[56] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. ``The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation''. 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–33:14. Dagstuhl, Germany (2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.

[57] 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 Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Pages 193–204. (2019).

[58] Andrew M. Childs, Robin Kothari, and Rolando D. Somma. ``Quantum algorithm for systems of linear equations with exponentially improved dependence on precision''. SIAM Journal on Computing 46, 1920–1950 (2017).

[59] Lov Grover and Terry Rudolph. ``Creating superpositions that correspond to efficiently integrable probability distributions'' (2002). arXiv:https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0208112.

[60] Iordanis Kerenidis and Anupam Prakash. ``Quantum recommendation systems'' (2016). arXiv:https:/​/​doi.org/​10.48550/​arXiv.1603.08675.

[61] Michael Keyl. ``Quantum state estimation and large deviations''. Reviews in Mathematical Physics 18, 19–60 (2006).

[62] Ryan O'Donnell and John Wright. ``Efficient quantum tomography''. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing. Pages 899–912. (2016).

[63] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, and Giacomo Nannicini. ``Quantum tomography using state-preparation unitaries''. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 1265–1318. SIAM (2023).

[64] Etienne de Klerk, Cornelis Roos, and Tamás Terlaky. ``Initialization in semidefinite programming via a self-dual skew-symmetric embedding''. Operations Research Letters 20, 213–221 (1997).

[65] Michael J. Todd, Kim-Chuan Toh, and Reha H. Tütüncü. ``On the Nesterov–Todd direction in semidefinite programming''. SIAM Journal on Optimization 8, 769–796 (1998).

[66] Ron S. Dembo, Stanley C. Eisenstat, and Trond Steihaug. ``Inexact Newton Methods''. SIAM Journal on Numerical Analysis 19, 400–408 (1982).

[67] Carl T. Kelley. ``Iterative methods for linear and nonlinear equations''. SIAM. (1995).

[68] Peter Bürgisser, Michael Clausen, and Mohammad A. Shokrollahi. ``Algebraic complexity theory''. Springer Science & Business Media. (2013).

[69] Volker Strassen. ``Gaussian elimination is not optimal''. Numerische Mathematik 13, 354–356 (1969).

[70] Raphael Yuster and Uri Zwick. ``Fast sparse matrix multiplication''. ACM Transactions On Algorithms (TALG) 1, 2–13 (2005).

[71] Iordanis Kerenidis and Anupam Prakash. ``A quantum interior point method for LPs and SDPs'' (2018). arXiv:https:/​/​doi.org/​10.48550/​arXiv.1808.09266.

[72] Yousef Saad. ``Iterative methods for sparse linear systems''. SIAM. (2003).

[73] Nisheeth K. Vishnoi. ``$Lx= b$: Laplacian Solvers and Their Algorithmic Applications''. Foundations and Trends® in Theoretical Computer Science 8, 1–141 (2013).

[74] Fernando G.S.L. 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 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–27:14. Dagstuhl, Germany (2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.

[75] Yin Tat Lee and Swati Padmanabhan. ``An $\widetilde{\mathcal{O}}(m/​\varepsilon^{3.5})$-cost algorithm for semidefinite programs with diagonal constraints''. In Jacob Abernethy and Shivani Agarwal, editors, Conference on Learning Theory. Pages 3069–3119. PMLR (2020).

[76] Cornelis Roos, Tamás Terlaky, and Jean-Phillipe Vial. ``Interior Point Methods for Linear Optimization''. Springer Science & Business Media. (2005).

[77] Ali Mohammad-Nezhad and Tamás Terlaky. ``On the identification of the optimal partition for semidefinite optimization''. INFOR: Information Systems and Operational Research 58, 1–39 (2019). arXiv:https:/​/​doi.org/​10.1080/​03155986.2019.1572853.

Cited by

[1] B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, and William J. Zeng, "Quantum Resources Required to Block-Encode a Matrix of Classical Data", IEEE Transactions on Quantum Engineering 3, 1 (2022).

[2] Mohammadhossein Mohammadisiahroudi, Zeguan Wu, Brandon Augustino, Tamas Terlaky, and Arielle Carr, 2022 IEEE/ACM 7th Symposium on Edge Computing (SEC) 375 (2022) ISBN:978-1-6654-8611-8.

[3] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[4] Dylan Herman, Cody Googin, Xiaoyuan Liu, Yue Sun, Alexey Galda, Ilya Safro, Marco Pistoia, and Yuri Alexeev, "Quantum computing for finance", Nature Reviews Physics 5 8, 450 (2023).

[5] Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang, "A Faster Quantum Algorithm for Semidefinite Programming via Robust IPM Framework", arXiv:2207.11154, (2022).

[6] Taylor L. Patti, Jean Kossaifi, Anima Anandkumar, and Susanne F. Yelin, "Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints", Quantum 7, 1057 (2023).

[7] Alexander M. Dalzell, B. David Clader, Grant Salton, Mario Berta, Cedric Yen-Yu Lin, David A. Bader, Nikitas Stamatopoulos, Martin J. A. Schuetz, Fernando G. S. L. Brandão, Helmut G. Katzgraber, and William J. Zeng, "End-To-End Resource Analysis for Quantum Interior-Point Methods and Portfolio Optimization", PRX Quantum 4 4, 040325 (2023).

[8] Oscar Watts, Yuta Kikuchi, and Luuk Coopmans, "Quantum Semidefinite Programming with Thermal Pure Quantum States", arXiv:2310.07774, (2023).

[9] Mohammadhossein Mohammadisiahroudi, Ramin Fakhimi, and Tamás Terlaky, "Efficient Use of Quantum Linear System Algorithms in Interior Point Methods for Linear Optimization", arXiv:2205.01220, (2022).

[10] B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, and William J. Zeng, "Quantum Resources Required to Block-Encode a Matrix of Classical Data", arXiv:2206.03505, (2022).

[11] Brandon Augustino, Giacomo Nannicini, Tamás Terlaky, and Luis Zuluaga, "Solving the semidefinite relaxation of QUBOs in matrix multiplication time, and faster with a quantum computer", arXiv:2301.04237, (2023).

[12] Mohammadhossein Mohammadisiahroudi, Ramin Fakhimi, Zeguan Wu, and Tamás Terlaky, "An Inexact Feasible Interior Point Method for Linear Optimization with High Adaptability to Quantum Computers", arXiv:2307.14445, (2023).

[13] Ojas Parekh, "Synergies Between Operations Research and Quantum Information Science", arXiv:2301.05554, (2023).

[14] Zeguan Wu, Mohammadhossein Mohammadisiahroudi, Brandon Augustino, Xiu Yang, and Tamás Terlaky, "An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization", Entropy 25 2, 330 (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-06-22 06:43:10) and SAO/NASA ADS (last updated successfully 2024-06-22 06:43:11). The list may be incomplete as not all publishers provide suitable and complete citation data.