{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T11:46:14Z","timestamp":1783079174226,"version":"3.54.6"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T00:00:00Z","timestamp":1736812800000},"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":"crossref","award":["W911NF2010022"],"award-info":[{"award-number":["W911NF2010022"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation CAREER","award":["DMS-2143915"],"award-info":[{"award-number":["DMS-2143915"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>Quantum linear system algorithms (QLSAs) have the potential to speed up Interior Point Methods (IPMs). However, a major bottleneck is the inexactness of quantum tomography to extract classical solutions from quantum states. In addition, QLSAs are sensitive to the condition number, and this sensitivity is exacerbated when the Newton systems arising in IPMs converge to a singular matrix. Recently, an Inexact Feasible Quantum IPM (IF-QIPM) has been developed that addresses the inexactness of QLSAs. However, this method requires a large number of gates and qubits to be implemented. Here, we propose a new IF-QIPM using the normal equation system, which requires fewer gates and qubits. To mitigate the sensitivity to the condition number and other input data-related parameters, we use preconditioning coupled with iterative refinement to obtain better complexity. Finally, we demonstrate the effectiveness of our approach on IBM Qiskit simulators.<\/jats:p>","DOI":"10.1145\/3702244","type":"journal-article","created":{"date-parts":[[2024,10,29]],"date-time":"2024-10-29T10:11:39Z","timestamp":1730196699000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Improvements to Quantum Interior Point Method for Linear Optimization"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4046-0672","authenticated-orcid":false,"given":"Mohammadhossein","family":"Mohammadisiahroudi","sequence":"first","affiliation":[{"name":"Industrial and System Engineering Department, Lehigh University, Bethlehem, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5695-7579","authenticated-orcid":false,"given":"Zeguan","family":"Wu","sequence":"additional","affiliation":[{"name":"Industrial and System Engineering Department, Lehigh University, Bethlehem, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8265-1779","authenticated-orcid":false,"given":"Brandon","family":"Augustino","sequence":"additional","affiliation":[{"name":"Sloan School of Management, Massachusetts Institute of Technology, Cambridge, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5827-0132","authenticated-orcid":false,"given":"Arielle","family":"Carr","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering Department, Lehigh University, Bethlehem, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1953-1971","authenticated-orcid":false,"given":"Tam\u00e1s","family":"Terlaky","sequence":"additional","affiliation":[{"name":"Industrial and System Engineering Department, Lehigh University, Bethlehem, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,1,14]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-008-9500-5"},{"key":"e_1_3_2_3_2","first-page":"636","volume-title":"Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS \u201912)","volume":"14","author":"Ambainis Andris","year":"2012","unstructured":"Andris Ambainis. 2012. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS \u201912), Vol. 14. 636\u2013647."},{"key":"e_1_3_2_4_2","article-title":"Quantum speedups for linear programming via interior point methods","author":"Apers Simon","year":"2023","unstructured":"Simon Apers and Sander Gribling. 2023. Quantum speedups for linear programming via interior point methods. arXiv preprint arXiv:2311.03215 (2023).","journal-title":"arXiv preprint arXiv:2311.03215"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2023-09-11-1110"},{"key":"e_1_3_2_6_2","volume-title":"An Inexact-feasible Quantum Interior Point Method for Second-Order Cone Optimization","author":"Augustino Brandon","year":"2021","unstructured":"Brandon Augustino, Tam\u00e1s Terlaky, Mohammadhossein Mohammadisiahroudi, and Luis F. Zuluaga. 2021. An Inexact-feasible Quantum Interior Point Method for Second-Order Cone Optimization. Technical Report 21T-009. ISE, Lehigh University."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/11666806_72"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022663100715"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8121\/abb439"},{"key":"e_1_3_2_10_2","article-title":"The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation","author":"Chakraborty Shantanav","year":"2018","unstructured":"Shantanav Chakraborty, Andr\u00e1s Gily\u00e9n, and Stacey Jeffery. 2018. The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation. arXiv preprint arXiv:1804.01973 (2018).","journal-title":"arXiv preprint arXiv:1804.01973"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1087072"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3424305"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","unstructured":"Fabio D\u2019Andreagiovanni and Ambros M. Gleixner. 2016. Towards an accurate solution of wireless network design problems. In Combinatorial Optimization. Lecture Notes in Computer Science Vol. 9849. Springer 135\u2013147.","DOI":"10.1007\/978-3-319-45587-7_12"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01749-5"},{"key":"e_1_3_2_15_2","article-title":"A quantum approximate optimization algorithm","author":"Farhi Edward","year":"2014","unstructured":"Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 (2014). https:\/\/arxiv.org\/abs\/1411.4028","journal-title":"arXiv preprint arXiv:1411.4028"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.1.50"},{"key":"e_1_3_2_17_2","volume-title":"Quantum Singular Value Transformation and Its Algorithmic Applications","author":"Gily\u00e9n Andr\u00e1s","year":"2019","unstructured":"Andr\u00e1s Gily\u00e9n. 2019. Quantum Singular Value Transformation and Its Algorithmic Applications. Ph.D. Dissertation. University of Amsterdam."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316366"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01444-6"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/3215177.3215182"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.56021\/9781421407944"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/120886017"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406306"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582151"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497329993"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.23"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-07-12-163"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107980020a"},{"key":"e_1_3_2_30_2","volume-title":"Accurately Solving Linear Systems with Quantum Oracles","author":"Mohammadisiahroudi Mohammadhossein","year":"2023","unstructured":"Mohammadhossein Mohammadisiahroudi, Brandon Augustino, Ramin Fakhimi, Giacomo Nannicini, and Tam\u00e1s Terlaky. 2023. Accurately Solving Linear Systems with Quantum Oracles. Technical Report 23T-006. ISE, Lehigh University."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2024.2308677"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-024-02452-z"},{"key":"e_1_3_2_33_2","article-title":"An inexact feasible interior point method for linear optimization with high adaptability to quantum computers","author":"Mohammadisiahroudi Mohammadhossein","year":"2023","unstructured":"Mohammadhossein Mohammadisiahroudi, Ramin Fakhimi, Zeguan Wu, and Tam\u00e1s Terlaky. 2023. An inexact feasible interior point method for linear optimization with high adaptability to quantum computers. arXiv preprint arXiv:2307.14445 (2023).","journal-title":"arXiv preprint arXiv:2307.14445"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-54621-2_851-1"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403426398"},{"key":"e_1_3_2_36_2","volume-title":"Convergence Analysis of a Long-Step Primal-Dual Infeasible Interior-Point LP Algorithm Based on Iterative Linear Solvers","author":"Monteiro Renato D. C.","year":"2003","unstructured":"Renato D. C. Monteiro and Jerome W. O\u2019Neal. 2003. Convergence Analysis of a Long-Step Primal-Dual Infeasible Interior-Point LP Algorithm Based on Iterative Linear Solvers. Technical Report 30332. ISyE, Georgia Institute of Technology. http:\/\/www.optimization-online.org\/DB_FILE\/2003\/10\/768.pdf"},{"key":"e_1_3_2_37_2","article-title":"Fast quantum subroutines for the simplex method","author":"Nannicini Giacomo","year":"2022","unstructured":"Giacomo Nannicini. 2022. Fast quantum subroutines for the simplex method. Operations Research. Published Online, October 18, 2022.","journal-title":"Operations Research."},{"key":"e_1_3_2_38_2","volume-title":"The Use of Preconditioned Iterative Linear Solvers in Interior-Point Methods and Related Topics","author":"O\u2019Neal Jerome W.","year":"2006","unstructured":"Jerome W. O\u2019Neal. 2006. The Use of Preconditioned Iterative Linear Solvers in Interior-Point Methods and Related Topics. Georgia Institute of Technology."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/b100325"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch47"},{"key":"e_1_3_2_41_2","first-page":"259","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Brand Jan van den","year":"2020","unstructured":"Jan van den Brand. 2020. A deterministic linear program solver in current matrix multiplication time. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 259\u2013278."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3490631"},{"key":"e_1_3_2_43_2","volume-title":"Rounding Errors in Algebraic Processes","author":"Wilkinson James Hardy","year":"1963","unstructured":"James Hardy Wilkinson. 1963. Rounding Errors in Algebraic Processes. Prentice Hall, Englewood Cliffs, NJ, USA."},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.120.050502"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971453"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.3390\/e25020330"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.1.53"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0431-5"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3702244","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3702244","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:10:31Z","timestamp":1750295431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3702244"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,14]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3702244"],"URL":"https:\/\/doi.org\/10.1145\/3702244","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,14]]},"assertion":[{"value":"2023-10-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-08","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}