QuSoft Seminar

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).
  • QuSoft Seminar
  • 2021-01-08T15:00:00+01:00
  • 2021-01-08T16:00:00+01:00
  • 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).
  • What English Algorithms & Complexity
  • When 08-01-2021 from 15:00 to 16:00 (Europe/Amsterdam / UTC100)
  • Contact Name
  • Add event to calendar iCal

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>]