Everyone is invited to attend the online QuSoft seminar. Speaker Harold Nieuwboer (QuSoft, CWI) on: Quantum algorithms for matrix scaling and matrix balancing. If you would like to attend, please contact Jop Briët (j.briet@cwi.nl) or Subhasree Patro (Subhasree.Patro@cwi.nl).
Abstract:
Matrix scaling and balancing are two basic linear-algebraic problems with a long history and many surprising applications, such as
optimal transport, approximating the permanent of a matrix, and pre-conditioning linear systems for numerical stability.
Classically, the matrix scaling and balancing problems can be solved in almost-linear time, albeit with rather sophisticated algorithms. We give
a quantum implementation of the comparatively simple Sinkhorn algorithm for matrix scaling (and Osborne's algorithm for matrix balancing) and
show that these implementations run in sublinear time. We also prove a quantum lower bound for matrix scaling which matches our upper bound
when the desired error is not too small. [Joint work with Joran van Apeldoorn, Sander Gribling, Yinan Li, Michael Walter and Ronald de Wolf. Available at https://arxiv.org/abs/2011.12823 <https://arxiv.org/abs/2011.12823>]
