2026-06-27T10:49:09Zhttps://docta.ucm.es/rest/oai/request
oai:docta.ucm.es:20.500.14352/67032024-08-27T16:29:58Zcom_20.500.14352_14col_20.500.14352_15
Docta Complutense author Casares, P. A. M. author Martín-Delgado Alcántara, Miguel Ángel 2023-06-16T15:27:03Z 2023-06-16T15:27:03Z 2020-11-06 1751-8113 10.1088/1751-8121/abb439 https://hdl.handle.net/20.500.14352/6703 http://dx.doi.org/10.1088/1751-8121/abb439 https://iopscience.iop.org/ We introduce a new quantum optimization algorithm for dense linear programming problems, which can be seen as the quantization of the interior point predictor-corrector algorithm [1] using a quantum linear system algorithm [2]. The (worst case) work complexity of our method is, up to polylogarithmic factors, O(L root n(n+m)(parallel to M parallel to) over bar (F) (kappa)over bar> over bar epsilon(-2)) for n the number of variables in the cost function,mthe number of constraints,epsilon(-1)the target precision,Lthe bit length of the input data, (parallel to M parallel to) over bar (F) over bar <ian upper bound to the Frobenius norm of the linear systems of equations that appear, <(parallel to M parallel to)over bar>(F), and (kappa) over bar an upper bound to the condition number kappa of those systems of equations. This represents a quantum speed-up in the number n of variables in the cost function with respect to the comparable classical interior point algorithms when the initial matrix of the problem A is dense: if we substitute the quantum part of the algorithm by classical algorithms such as conjugate gradient descent, that would mean the whole algorithm has complexity O(L root n(n + m)(2) (kappa) over bar log(epsilon(-1))), or with exact methods, at least O(L root n(n + m)(2.373)). Also, in contrast with any quantum linear system algorithm, the algorithm described in this article outputs a classical description of the solution vector, and the value of the optimal solution. eng A quantum interior-point predictor-corrector algorithm for linear programming journal article URL https://docta.ucm.es/bitstreams/39d08782-4e7f-4318-9b06-38914147060c/download File MD5 75c6568d233aedb0d08dc64f2b47ba0d 962723 application/pdf Martín Delgado Alcántara MÁ 126 preprint.pdf