  We propose quantum subroutines for the simplex method that avoid classical
computation of the basis inverse. We show how to quantize all steps of the
simplex algorithm, including checking optimality, unboundedness, and
identifying a pivot (i.e., pricing the columns and performing the ratio test)
according to Dantzig's rule or the steepest edge rule. The quantized
subroutines obtain a polynomial speedup in the dimension of the problem, but
have worse dependence on other numerical parameters. For example, for a problem
with $m$ constraints, $n$ variables, at most $d_c$ nonzero elements per column
of the costraint matrix, at most $d$ nonzero elements per column or row of the
basis, basis condition number $\kappa$, and optimality tolerance $\epsilon$,
pricing can be performed in $\tilde{O}(\frac{1}{\epsilon}\kappa d \sqrt{n}(d_c
n + d m))$ time, where the $\tilde{O}$ notation hides polylogarithmic factors;
classically, pricing requires $O(d_c^{0.7} m^{1.9} + m^{2 + o(1)} + d_c n)$
time in the worst case using the fastest known algorithm for sparse matrix
multiplication. For well-conditioned sparse problems the quantum subroutines
scale better in $m$ and $n$, and may therefore have an advantage for very large
problems. The running time of the quantum subroutines can be improved if the
constraint matrix admits an efficient algorithmic description, or if quantum
RAM is available.
