Giacomo Nannicini, IBM Research

Abstract

We propose quantum subroutines for the simplex method that avoid classical computation of the basis inverse. For a well-conditioned $m times n$ constraint matrix with at most $d_c$ nonzero elements per column, at most $d$ nonzero elements per column or row of the basis, and optimality tolerance $epsilon$, we show that pricing can be performed in time $tilde{O}(frac{1}{epsilon}sqrt{n}(d_c n + d^2 m))$, where the $tilde{O}$ notation hides polylogarithmic factors; if the sparsity is constant, which is often the case in practice, this yields a runtime of $tilde{O}(frac{1}{epsilon}  sqrt{n}(n + m))$. If the ratio $n/m$ is larger than a certain threshold, the runtime of the quantum routine can be reduced to $tilde{O}(frac{1}{epsilon}d sqrt{d_c} n sqrt{m})$. Classically, pricing would require $O(m^{2.373} + d_c n)$ in the worst case. The ratio test can be performed in time $tilde{O}(frac{1}{delta} d^2 m^{1.5})$, where $delta$ is a feasibility tolerance; classically, this requires $O(m^2)$ in the worst case. For well-conditioned sparse problems, the quantum subroutines may therefore have a worst-case asymptotic advantage. The input of our quantum subroutines is the natural description of the problem data, and the output is the index of the variables that should leave or enter the basis.