A fast quantum Interior Point algorithm for Linear Programming

Today I have uploaded to Arxiv what I expect will be my first academic article. In it I introduce a new algorithm for dealing with a class of problems known as Linear Programming.

Linear Programming and the Predictor-Corrector approach

Linear programming is the mathematical problem of optimising a linear function with n variables and m linear constraints. For example, it is the kind of problem that you have to deal with when you are playing a video game, you have constrained resources, and you want to optimise the output.

Every linear problem (a maximisation, primal problem) corresponds to another problem (minimisation, dual problem). For example, if a company wants to maximise its profit selling cars (assuming it can sell every can it makes with constraints in the resources to make those cars) it will minimise the overall cost of each car. Classically, two kinds of algorithms have been used for this: the simplex method and interior point methods.

My algorithm is of the second kind. In particular it is a hybrid algorithm that uses the framework of the Predictor-Corrector algorithm of Mizuno, Todd y Ye. Their algorithm solves the primal and dual problem at the same and requires a number of iterations that run as the square root of the number of variables. The aim of my article is being able to run every iteration of the Predictor-Corrector algorithm so fast that the total mathematical complexity is roughly the square root of the number of variables.

What is the complexity of an algorithm? To answer that question we have to think first of how can we compare how fast two algorithms run. One might attempt running them and seeing which one runs faster, although the problem is that this will depend on the actual computer you are using. Thus, what mathematicians thought is that you can calculate how long will it take compared with the length of the input. Saying if a number is even takes a constant amount of time (just compare the last digit if it is given to you in base 2 or 10). Inverting a matrix by the Gauss procedure is cubic in the size of the matrix. And 3-SAT is thought to be (horribly) exponential. So in general you want, in order of decreasing preference, an algorithm that runs in constant, logarithmic, polynomial and exponential complexity.

The Quantum Linear System Algorithm

Two years or so there was a paper by Brandao and Svore where they proposed a method to solve Semi-Definite Programming (a more general class of Linear Programming) and they showed that the fastest a quantum algorithm can solve Linear Programming is square root in the number of variables, and a classical algorithm can just wish to be linear. Therefore we wanted to find a way to have a super fast iteration so that the number of iterations is the final complexity. As it is indicated in the original Predictor-Corrector algorithm, in each iteration one must solve two linear systems of equations that correspond to the Predictor and Corrector step.

We did that by using the Quantum Linear System Algorithm of Childs et al, which is an improved version of a previous work by Harrow, Hassidim and Lloyd. The key of the algorithm is that it is no more than logarithmic in the number of variables (ie, super fast). Therefore, we have used a quantum heart to keep the complexity on n as low as possibly attainable. To do that we have needed some procedures called sparsification and preconditioning to control other parameters of QLSA.

But using the QLSA comes at a price. Namely, one cannot read the full solution from one quantum state. Therefore, one must parallelise this procedure in a classical sense so that one can read the solution: one element of the solution vector from each parallel computation. Additionally, one needs the matrix of constraints to be sparse. That is, with few non-zero terms: in each constraint only s variables should intervine. Finally, the readout procedure carries a complexity linear on the precision, while the classical algorithms are usually logarithmic on it.

When we expect this algorithm to be useful?

Unfortunately, quantum computing is still in its infancy, and most applications of quantum computing can be better solved with a classical computer. However, we expect that in some years that will change. Then, I expect my algorithm to be useful for those applications that need some way of very quickly getting an answer for the Linear Programming problem, even if it is not an extremely precise one.