Quantum algorithms for matrix scaling and matrix balancing

Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter, Ronald de Wolf

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 ~O(sqrt(mn)/eps^4) for scaling or balancing an nx n matrix (given by an oracle) with m non-zero entries to within ell_1-error eps. Their classical analogs use ~O(m/eps^2) time, and every classical algorithm for scaling or balancing with small constant eps requires Omega(m) queries to the entries of the input matrix. We thus achieve a polynomial speed-up in terms of n, at the expense of a worse polynomial dependence on the obtained ell_1-error eps . We emphasize that even for constant eps these problems are already non-trivial (and relevant in applications).

On arXiv

Quantum SDP-Solvers: Better upper and lower bounds

Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf

Brandão and Svore very recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension n of the problem and the number m of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure.

We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimizations problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with mn when mn, which is the same as classical.

Appeared in Quantum
In the proceedings of FOCS 58
On arXiv