  We describe a quantum algorithm based on an interior point method for solving
a linear program with $n$ inequality constraints on $d$ variables. The
algorithm explicitly returns a feasible solution that is $\varepsilon$-close to
optimal, and runs in time $\sqrt{n} \cdot
\mathrm{poly}(d,\log(n),\log(1/\varepsilon))$ which is sublinear for tall
linear programs (i.e., $n \gg d$). Our algorithm speeds up the Newton step in
the state-of-the-art interior point method of Lee and Sidford [FOCS~'14]. This
requires us to efficiently approximate the Hessian and gradient of the barrier
function, and these are our main contributions.
  To approximate the Hessian, we describe a quantum algorithm for the
\emph{spectral approximation} of $A^T A$ for a tall matrix $A \in \mathbb R^{n
\times d}$. The algorithm uses leverage score sampling in combination with
Grover search, and returns a $\delta$-approximation by making
$O(\sqrt{nd}/\delta)$ row queries to $A$. This generalizes an earlier quantum
speedup for graph sparsification by Apers and de Wolf~[FOCS~'20]. To
approximate the gradient, we use a recent quantum algorithm for multivariate
mean estimation by Cornelissen, Hamoudi and Jerbi [STOC '22]. While a naive
implementation introduces a dependence on the condition number of the Hessian,
we avoid this by pre-conditioning our random variable using our quantum
algorithm for spectral approximation.
