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 $ϵ=\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 $ϵ\in [1/n,1/2]$, any quantum algorithm capable of producing \(\frac\{\epsilo