{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T02:10:22Z","timestamp":1773281422446,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T00:00:00Z","timestamp":1764288000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T00:00:00Z","timestamp":1764288000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["W911NF2010022"],"award-info":[{"award-number":["W911NF2010022"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CAREER DMS-2143915"],"award-info":[{"award-number":["CAREER DMS-2143915"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-AC05-00OR22725"],"award-info":[{"award-number":["DE-AC05-00OR22725"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2026,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Quantum Interior Point Methods (QIPMs) have been attracting significant interests recently due to their potential of solving optimization problems substantially faster than state-of-the-art conventional algorithms. In general, QIPMs use Quantum Linear System Algorithms (QLSAs) to substitute classical linear system solvers. However, the performance of QLSAs depends on the condition numbers of the linear systems, which are typically proportional to the square of the reciprocal of the duality gap in QIPMs. To improve conditioning, a preconditioned inexact infeasible QIPM (II-QIPM) based on optimal partition estimation is developed in this work. We improve the condition number of the linear systems in II-QIPMs from quadratic dependence on the reciprocal of the duality gap to linear, and obtain better dependence with respect to the accuracy when compared to other II-QIPMs. Our method also attains better dependence with respect to the dimension when compared to other inexact infeasible Interior Point Methods.<\/jats:p>","DOI":"10.1007\/s10589-025-00750-4","type":"journal-article","created":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T00:34:56Z","timestamp":1764290096000},"page":"1225-1257","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A preconditioned inexact infeasible quantum interior point method for linear optimization"],"prefix":"10.1007","volume":"93","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5695-7579","authenticated-orcid":false,"given":"Zeguan","family":"Wu","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0882-2650","authenticated-orcid":false,"given":"Xiu","family":"Yang","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1953-1971","authenticated-orcid":false,"given":"Tam\u00e1s","family":"Terlaky","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,11,28]]},"reference":[{"issue":"2","key":"750_CR1","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10957-008-9500-5","volume":"141","author":"G Al-Jeiroudi","year":"2009","unstructured":"Al-Jeiroudi, G., Gondzio, J.: Convergence analysis of the inexact infeasible interior-point method for linear optimization. J. Optim. Theory Appl. 141(2), 231\u2013247 (2009)","journal-title":"J. Optim. Theory Appl."},{"key":"750_CR2","doi-asserted-by":"publisher","first-page":"1110","DOI":"10.22331\/q-2023-09-11-1110","volume":"7","author":"B Augustino","year":"2023","unstructured":"Augustino, B., Nannicini, G., Terlaky, T., Zuluaga, L.F.: Quantum interior point methods for semidefinite optimization. Quantum 7, 1110 (2023)","journal-title":"Quantum"},{"key":"750_CR3","volume-title":"Introduction to Linear Optimization","author":"D Bertsimas","year":"1997","unstructured":"Bertsimas, D., Tsitsiklis, J.N.: Introduction to Linear Optimization. Athena Scientific, Belmont, MA (1997)"},{"issue":"4","key":"750_CR4","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1137\/0708060","volume":"8","author":"JR Bunch","year":"1971","unstructured":"Bunch, J.R., Parlett, B.N.: Direct methods for solving symmetric indefinite systems of linear equations. SIAM J. Numer. Anal. 8(4), 639\u2013655 (1971)","journal-title":"SIAM J. Numer. Anal."},{"issue":"2","key":"750_CR5","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s10589-006-9006-8","volume":"36","author":"JS Chai","year":"2007","unstructured":"Chai, J.S., Toh, K.C.: Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming. Comput. Optim. Appl. 36(2), 221\u2013247 (2007)","journal-title":"Comput. Optim. Appl."},{"key":"750_CR6","unstructured":"Chakraborty, S., Gily\u00e9n, A., Jeffery, S.: The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation (2018). arXiv preprint arXiv:1804.01973"},{"issue":"6","key":"750_CR7","doi-asserted-by":"publisher","first-page":"1920","DOI":"10.1137\/16M1087072","volume":"46","author":"AM Childs","year":"2017","unstructured":"Childs, A.M., Kothari, R., Somma, R.D.: Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM J. Comput. 46(6), 1920\u20131950 (2017)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"750_CR8","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.3.040303","volume":"3","author":"PC Costa","year":"2022","unstructured":"Costa, P.C., An, D., Sanders, Y.R., Su, Y., Babbush, R., Berry, D.W.: Optimal scaling quantum linear-systems solver via discrete adiabatic theorem. PRX Quantum 3(4), 040303 (2022)","journal-title":"PRX Quantum"},{"issue":"2","key":"750_CR9","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1090\/S0002-9939-1969-0255573-1","volume":"22","author":"DE Crabtree","year":"1969","unstructured":"Crabtree, D.E., Haynsworth, E.V.: An identity for the Schur complement of a matrix. Proc. Am. Math. Soc. 22(2), 364\u2013366 (1969)","journal-title":"Proc. Am. Math. Soc."},{"key":"750_CR10","unstructured":"Dalzell, A.M.: A shortcut to an optimal quantum linear system solver (2024). arXiv preprint arXiv:2406.12086"},{"key":"750_CR11","unstructured":"Dalzell, A.M., McArdle, S., Berta, M., Bienias, P., Chen, C.F., Gily\u00e9n, A., Hann, C.T., Kastoryano, M.J., Khabiboulline, E.T., Kubica, A., et\u00a0al.: Quantum algorithms: A survey of applications and end-to-end complexities (2023). arXiv preprint arXiv:2310.03011"},{"issue":"2","key":"750_CR12","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1137\/0719025","volume":"19","author":"RS Dembo","year":"1982","unstructured":"Dembo, R.S., Eisenstat, S.C., Steihaug, T.: Inexact Newton methods. SIAM J. Numer. Anal. 19(2), 400\u2013408 (1982)","journal-title":"SIAM J. Numer. Anal."},{"key":"750_CR13","doi-asserted-by":"crossref","unstructured":"Gily\u00e9n, A., Su, Y., Low, G.H., Wiebe, N.: 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, pp. 193\u2013204 (2019)","DOI":"10.1145\/3313276.3316366"},{"key":"750_CR14","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BF02096259","volume":"46","author":"O G\u00fcler","year":"1993","unstructured":"G\u00fcler, O., den Hertog, D., Roos, C., Terlaky, T., Tsuchiya, T.: Degeneracy in interior point methods for linear programming: a survey. Ann. Oper. Res. 46, 107\u2013138 (1993)","journal-title":"Ann. Oper. Res."},{"issue":"15","key":"750_CR15","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502","volume":"103","author":"AW Harrow","year":"2009","unstructured":"Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103(15), 150502 (2009)","journal-title":"Phys. Rev. Lett."},{"key":"750_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139020411","volume-title":"Matrix Analysis","author":"RA Horn","year":"2012","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge, UK (2012)"},{"key":"750_CR17","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 373\u2013395 (1984)","journal-title":"Combinatorica"},{"key":"750_CR18","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970944","volume-title":"Iterative Methods for Linear and Nonlinear Equations","author":"CT Kelley","year":"1995","unstructured":"Kelley, C.T.: Iterative Methods for Linear and Nonlinear Equations. SIAM, Philadelphia, PA (1995)"},{"issue":"1","key":"750_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3406306","volume":"1","author":"I Kerenidis","year":"2020","unstructured":"Kerenidis, I., Prakash, A.: A quantum interior point method for LPs and SDPs. ACM Trans. Quantum Comput. 1(1), 1\u201332 (2020)","journal-title":"ACM Trans. Quantum Comput."},{"key":"750_CR20","unstructured":"Low, G.H., Su, Y.: Quantum linear system algorithm with optimal queries to initial state preparation, (2024). arXiv preprint arXiv:2410.18178"},{"key":"750_CR21","doi-asserted-by":"crossref","unstructured":"Mohammadisiahroudi, M., Fakhimi, F., Wu, Z., Terlaky, T.: An inexact feasible interior point method for linear optimization with high adaptability to quantum computers. SIAM J. Optim. 35(4), 2203\u20132233 (2025)","DOI":"10.1137\/23M1589414"},{"issue":"1","key":"750_CR22","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/s10957-024-02452-z","volume":"202","author":"M Mohammadisiahroudi","year":"2024","unstructured":"Mohammadisiahroudi, M., Fakhimi, R., Terlaky, T.: Efficient use of quantum linear system algorithms in inexact infeasible IPMs for linear optimization. J. Optim. Theory Appl. 202(1), 146\u2013183 (2024)","journal-title":"J. Optim. Theory Appl."},{"key":"750_CR23","unstructured":"Monteiro, R.D., O\u2019Neal, J.W.: Convergence analysis of a long-step primal-dual infeasible interior-point LP algorithm based on iterative linear solvers. Georgia Institute of Technology (2003)"},{"key":"750_CR24","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791","volume-title":"Interior-point Polynomial Algorithms in Convex Programming","author":"Y Nesterov","year":"1994","unstructured":"Nesterov, Y., Nemirovskii, A.: Interior-point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia, PA (1994)"},{"key":"750_CR25","doi-asserted-by":"crossref","unstructured":"P\u00f3lik, I., Terlaky, T.: Interior point methods for nonlinear optimization. In: Di Pillo, G., Schoen, F. (eds.) Nonlinear Optimization, Volume 1989, Berlin, Heidelberg, pp. 215\u2013276. Springer (2010)","DOI":"10.1007\/978-3-642-11339-0_4"},{"issue":"1","key":"750_CR26","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1137\/0806002","volume":"6","author":"FA Potra","year":"1996","unstructured":"Potra, F.A.: An infeasible-interior-point predictor-corrector algorithm for linear programming. SIAM J. Optim. 6(1), 19\u201332 (1996)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"750_CR27","doi-asserted-by":"publisher","first-page":"1110","DOI":"10.1137\/050623917","volume":"16","author":"C Roos","year":"2006","unstructured":"Roos, C.: A full-Newton step $${O}(n)$$ infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16(4), 1110\u20131136 (2006)","journal-title":"SIAM J. Optim."},{"key":"750_CR28","volume-title":"Theory and Algorithms for Linear Optimization: An Interior Point Approach","author":"C Roos","year":"1997","unstructured":"Roos, C., Terlaky, T., Vial, J.P.: Theory and Algorithms for Linear Optimization: An Interior Point Approach. John Wiley & Sons, Chichester (1997)"},{"key":"750_CR29","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0024-3795(92)90321-Z","volume":"177","author":"RL Smith","year":"1992","unstructured":"Smith, R.L.: Some interlacing properties of the Schur complement of a Hermitian matrix. Linear Algebra Appl. 177, 137\u2013144 (1992)","journal-title":"Linear Algebra Appl."},{"key":"750_CR30","doi-asserted-by":"crossref","unstructured":"van Apeldoorn, J., Cornelissen, A., Gily\u00e9n, A., Nannicini, G.: Quantum tomography using state-preparation unitaries. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1265\u20131318. SIAM (2023)","DOI":"10.1137\/1.9781611977554.ch47"},{"issue":"2","key":"750_CR31","doi-asserted-by":"publisher","first-page":"330","DOI":"10.3390\/e25020330","volume":"25","author":"Z Wu","year":"2023","unstructured":"Wu, Z., Mohammadisiahroudi, M., Augustino, B., Yang, X., Terlaky, T.: An inexact feasible quantum interior point method for linearly constrained quadratic optimization. Entropy 25(2), 330 (2023)","journal-title":"Entropy"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-025-00750-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-025-00750-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-025-00750-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T11:17:34Z","timestamp":1773227854000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-025-00750-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,28]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["750"],"URL":"https:\/\/doi.org\/10.1007\/s10589-025-00750-4","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,28]]},"assertion":[{"value":"30 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 November 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 November 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The third author is an editor for the journal Computation Optimization and Applications.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Not applicable.","order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}