Improved quantum lower and upper bounds for matrix scaling

Abstract

Matrix scaling is a simple to state, yet widely applicable linear-algebraic problem: the goal is to scale the rows and columns of a given non-negative matrix such that the rescaled matrix has prescribed row and column sums. Motivated by recent results on first-order quantum algorithms for matrix scaling, we investigate the possibilities for quantum speedups for classical second-order algorithms, which comprise the state-of-the-art in the classical setting. We first show that there can be essentially no quantum speedup in terms of the input size in the high-precision regime: any quantum algorithm that solves the matrix scaling problem for $n\times n$ matrices with at most $m$ non-zero entries and with ${\ell }_2$-error $\epsilon =\tilde{\Theta }(1/m)$ must make $\tilde{\Omega }(m)$ queries to the matrix, even when the success probability is exponentially small in $n$. Additionally, we show that for $\epsilon \in [1/n,1/2]$, any quantum algorithm capable of producing $\frac{\epsilon }{100}$-${\ell }_1$-approximations of the row-sum vector of a (dense) normalized matrix uses $\Omega (n/\epsilon )$ queries, and that there exists a constant ${\epsilon }_0>0$ for which this problem takes $\Omega (n^{1.5})$ queries. To complement these results we give improved quantum algorithms in the low-precision regime: with quantum graph sparsification and amplitude estimation, a box-constrained Newton method can be sped up in the large-$\epsilon$ regime, and outperforms previous quantum algorithms. For entrywise-positive matrices, we find an $\epsilon$-${\ell }_1$-scaling in time $\tilde{O}(n^{1.5}/{\epsilon }^2)$, whereas the best previously known bounds were $\tilde{O}(n^2\mathrm{polylog}(1/\epsilon ))$ (classical) and $\tilde{O}(n^{1.5}/{\epsilon }^3)$ (quantum).

30 pages