Implementing the Simplex Method with Grover’s Search
Adeline Jordon, Prashanti Priya Angara, Saasha Joshi · 2021
The simplex method, as proposed by Dantzig in 1947, is a widely-used practical algorithm for solving Linear Programs (LPs)—systems of linear inequalities headed by a single linear objective function. We examine the difficulty of implementing quantum subroutines outlined by Nannicini in Fast quantum subroutines for the simplex method. Classically, choosing an entering variable in an LP with n optimization variables, m constraints, and at most dcnon-zero entries per column requires $O\left({d_c^{0.7}{m^{1.9}} + {m^{2 + o(1) + {d_c}n}}}\right)$ time using the fastest known algorithm for sparse matrix multiplication. By using quantum subroutines Nannicini’s approach results in $O\left({\frac{1}{\varepsilon }\kappa d\sqrt n \left({{d_c}n + dm}\right)}\right)$ time, where Õ hides polylogarithmic factors. We examine the implementation of subroutine FindColumn (A,B,ϵ) that selects a valid entering variable (if any) using quantum search and quantum phase estimation algorithms; here, A is the constraint matrix, B is the basis and ϵ is optimality tolerance. We focus on challenges presented by transforming the matrices and vectors given by an LP into quantum states and the preparation of the oracle. We discuss our implementation and encountered challenges when implementing the algorithm using IBM’s Quantum Experience.