Quantum algorithms for matrix scaling and matrix balancing

Understand

Matrix scaling and matrix balancing are two basic linear-algebraic problems with a wide variety of applications, such as approximating the permanent, and pre-conditioning linear systems to make them more numerically stable.

• We study the power and limitations of quantum algorithms for these problems.
• We provide quantum implementations of two classical (in both senses of the word) methods: Sinkhorn's algorithm for matrix scaling and Osborne's algorithm for matrix balancing.
• Using amplitude estimation as our main tool, our quantum implementations both run in time $\tilde O(\sqrt{mn}/\varepsilon^4)$ for scaling or balancing an $n \times n$ matrix (given by an oracle) with $m$ non-zero entries to within $\ell_1$-error $\varepsilon$.