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 (\epsilon)-close to optimal, and runs in time (\sqrt{n} \cdot \mathrm{poly}(d,log(n),log(1/\epsilon))) 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 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.