Abstract
Matrix scaling and matrix balancing are two basic linearalgebraic problems with a wide variety of applications, such as approximating the permanent, and preconditioning 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 Õ(√{mn}/ε⁴) for scaling or balancing an n × n matrix (given by an oracle) with m nonzero entries to within ?₁error ε. Their classical analogs use time Õ(m/ε²), and every classical algorithm for scaling or balancing with small constant ε requires Ω(m) queries to the entries of the input matrix. We thus achieve a polynomial speedup in terms of n, at the expense of a worse polynomial dependence on the obtained ?₁error ε. Even for constant ε these problems are already nontrivial (and relevant in applications). Along the way, we extend the classical analysis of Sinkhorn’s and Osborne’s algorithm to allow for errors in the computation of marginals. We also adapt an improved analysis of Sinkhorn’s algorithm for entrywisepositive matrices to the ?₁setting, obtaining an Õ(n^{1.5}/ε³)time quantum algorithm for ε?₁scaling. We also prove a lower bound, showing our quantum algorithm for matrix scaling is essentially optimal for constant ε: every quantum algorithm for matrix scaling that achieves a constant ?₁error w.r.t. uniform marginals needs Ω(√{mn}) queries.
BibTeX  Entry
@InProceedings{vanapeldoorn_et_al:LIPIcs.ICALP.2021.110,
author = {van Apeldoorn, Joran and Gribling, Sander and Li, Yinan and Nieuwboer, Harold and Walter, Michael and de Wolf, Ronald},
title = {{Quantum Algorithms for Matrix Scaling and Matrix Balancing}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {110:1110:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14179},
URN = {urn:nbn:de:0030drops141793},
doi = {10.4230/LIPIcs.ICALP.2021.110},
annote = {Keywords: Matrix scaling, matrix balancing, quantum algorithms}
}
Keywords: 

Matrix scaling, matrix balancing, quantum algorithms 
Collection: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 
Issue Date: 

2021 
Date of publication: 

02.07.2021 