A Quantum IP Predictor-Corrector Algorithm for Linear Programming
share
We introduce a new quantum optimization algorithm for Linear Programming (LP) problems based on Interior Point (IP) Predictor-Corrector (PC) methods whose (worst case) time complexity is O(√(n)Ls^3 k ϵ^-1ϵ_s^-1) . This represents a quantum speed-up in the number n of variables in the cost function with respect to the comparable classical Interior Point (IP) algorithms that behave as O((n+m)√(nk)L s^3(ϵ^-1)ϵ_s^-1) or O(√(n)(n+m)L) depending on the technique employed, where m is the number of constraints and the rest of the variables are defined in the introduction. The average time complexity of our algorithm is O(√(n)s^3 k ϵ^-1ϵ_s^-1), which equals the behaviour on n of quantum Semidefinite Programming (SDP) algorithms based on multiplicative weight methods when restricted to LP problems and heavily improves on the precision ϵ^-1 of the algorithm. Unlike the quantum SDP algorithm, the quantum PC algorithm does not depend on size parameters of the primal and dual LP problems (R,r), and outputs a feasible and optimal solution whenever it exists.
READ FULL TEXT