{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T11:44:04Z","timestamp":1783079044669,"version":"3.54.6"},"reference-count":23,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T00:00:00Z","timestamp":1675987200000},"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\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["CAREER DMS-2143915"],"award-info":[{"award-number":["CAREER DMS-2143915"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["W911NF2010022"],"award-info":[{"award-number":["W911NF2010022"]}],"id":[{"id":"10.13039\/100000001","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"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Quantum linear system algorithms (QLSAs) have the potential to speed up algorithms that rely on solving linear systems. Interior point methods (IPMs) yield a fundamental family of polynomial-time algorithms for solving optimization problems. IPMs solve a Newton linear system at each iteration to compute the search direction; thus, QLSAs can potentially speed up IPMs. Due to the noise in contemporary quantum computers, quantum-assisted IPMs (QIPMs) only admit an inexact solution to the Newton linear system. Typically, an inexact search direction leads to an infeasible solution, so, to overcome this, we propose an inexact-feasible QIPM (IF-QIPM) for solving linearly constrained quadratic optimization problems. We also apply the algorithm to \u21131-norm soft margin support vector machine (SVM) problems, and demonstrate that our algorithm enjoys a speedup in the dimension over existing approaches. This complexity bound is better than any existing classical or quantum algorithm that produces a classical solution.<\/jats:p>","DOI":"10.3390\/e25020330","type":"journal-article","created":{"date-parts":[[2023,2,13]],"date-time":"2023-02-13T03:07:57Z","timestamp":1676257677000},"page":"330","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization"],"prefix":"10.3390","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5695-7579","authenticated-orcid":false,"given":"Zeguan","family":"Wu","sequence":"first","affiliation":[{"name":"Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18015, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4046-0672","authenticated-orcid":false,"given":"Mohammadhossein","family":"Mohammadisiahroudi","sequence":"additional","affiliation":[{"name":"Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18015, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8265-1779","authenticated-orcid":false,"given":"Brandon","family":"Augustino","sequence":"additional","affiliation":[{"name":"Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18015, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0882-2650","authenticated-orcid":false,"given":"Xiu","family":"Yang","sequence":"additional","affiliation":[{"name":"Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18015, USA"}],"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":"Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18015, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2023,2,10]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Nocedal, J., and Wright, S.J. (1999). Numerical Optimization, Springer.","DOI":"10.1007\/b98874"},{"key":"ref_2","unstructured":"Haussler, D. (1992, January 27\u201329). A training algorithm for optimal margin classifiers. Proceedings of the Fifth Annual Workshop on Computational Learning Theory, Pittsburgh, PA, USA."},{"key":"ref_3","unstructured":"Roos, C., Terlaky, T., and Vial, J.P. (1997). Theory and Algorithms for Linear Optimization: An Interior Point Approach, John Wiley & Sons."},{"key":"ref_4","unstructured":"Gianni Di Pillo, F.S. (2010). Nonlinear Optimization, Springer."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1510","DOI":"10.1137\/120886017","article-title":"Convergence analysis of an inexact feasible interior point method for convex quadratic programming","volume":"23","author":"Gondzio","year":"2013","journal-title":"SIAM J. Optim."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/04060771X","article-title":"An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming","volume":"17","author":"Lu","year":"2006","journal-title":"SIAM J. Optim."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1137\/0708060","article-title":"Direct methods for solving symmetric indefinite systems of linear equations","volume":"8","author":"Bunch","year":"1971","journal-title":"SIAM J. Numer. Anal."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"022342","DOI":"10.1103\/PhysRevA.94.022342","article-title":"Prediction by linear regression on a quantum computer","volume":"94","author":"Schuld","year":"2016","journal-title":"Phys. Rev. A"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"427","DOI":"10.22331\/q-2021-04-08-427","article-title":"Quantum algorithms for second-order cone programming and support vector machines","volume":"5","author":"Kerenidis","year":"2021","journal-title":"Quantum"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"150502","DOI":"10.1103\/PhysRevLett.103.150502","article-title":"Quantum algorithm for linear systems of equations","volume":"103","author":"Harrow","year":"2009","journal-title":"Phys. Rev. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3406306","article-title":"A quantum interior point method for LPs and SDPs","volume":"1","author":"Kerenidis","year":"2020","journal-title":"ACM Trans. Quantum Comput."},{"key":"ref_12","unstructured":"Mohammadisiahroudi, M., Fakhimi, R., and Terlaky, T. (2022). Efficient use of quantum linear system algorithms in interior point methods for linear optimization. arXiv."},{"key":"ref_13","unstructured":"Augustino, B., Nannicini, G., Terlaky, T., and Zuluaga, L.F. (2021). Quantum interior point methods for semidefinite optimization. arXiv."},{"key":"ref_14","unstructured":"Mohammadisiahroudi, M., Fakhimi, F., Wu, Z., and Terlaky, T. (2021). An Inexact Feasible Interior Point Method for Linear Optimization with High Adaptability to Quantum Computers, Department of ISE, Lehigh University. Technical Report: 21T-006."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01587074","article-title":"A polynomial-time algorithm for a class of linear complementarity problems","volume":"44","author":"Kojima","year":"1989","journal-title":"Math. Program."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/BF01587076","article-title":"Interior path following primal-dual algorithms. part II: Convex quadratic programming","volume":"44","author":"Monteiro","year":"1989","journal-title":"Math. Program."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF01588795","article-title":"An O (n 3L) primal interior point algorithm for convex quadratic programming","volume":"49","author":"Goldfarb","year":"1990","journal-title":"Math. Program."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Gily\u00e9n, A., Su, Y., Low, G.H., and Wiebe, N. (2018). Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. arXiv.","DOI":"10.1145\/3313276.3316366"},{"key":"ref_19","unstructured":"Chakraborty, S., Gily\u00e9n, A., and Jeffery, S. (2018). The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation. arXiv."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"van Apeldoorn, J., Cornelissen, A., Gily\u00e9n, A., and Nannicini, G. (2022). Quantum tomography using state-preparation unitaries. arXiv.","DOI":"10.1137\/1.9781611977554.ch47"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Horn, R.A., and Johnson, C.R. (2012). Matrix Analysis, Cambridge University Press.","DOI":"10.1017\/CBO9781139020411"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF00994018","article-title":"Support-vector networks","volume":"20","author":"Cortes","year":"1995","journal-title":"Mach. Learn."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"130503","DOI":"10.1103\/PhysRevLett.113.130503","article-title":"Quantum support vector machine for big data classification","volume":"113","author":"Rebentrost","year":"2014","journal-title":"Phys. Rev. Lett."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/2\/330\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:30:53Z","timestamp":1760121053000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/2\/330"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,10]]},"references-count":23,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2023,2]]}},"alternative-id":["e25020330"],"URL":"https:\/\/doi.org\/10.3390\/e25020330","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,10]]}}}