Abstract
Matrix scaling is a simple to state, yet widely applicable linearalgebraic problem: the goal is to scale the rows and columns of a given nonnegative matrix such that the rescaled matrix has prescribed row and column sums. Motivated by recent results on firstorder quantum algorithms for matrix scaling, we investigate the possibilities for quantum speedups for classical secondorder algorithms, which comprise the stateoftheart in the classical setting.
We first show that there can be essentially no quantum speedup in terms of the input size in the highprecision regime: any quantum algorithm that solves the matrix scaling problem for n × n matrices with at most m nonzero entries and with 𝓁₂error ε = Θ~(1/m) must make Ω(m) queries to the matrix, even when the success probability is exponentially small in n. Additionally, we show that for ε ∈ [1/n,1/2], any quantum algorithm capable of producing ε/100𝓁₁approximations of the rowsum vector of a (dense) normalized matrix uses Ω(n/ε) queries, and that there exists a constant ε₀ > 0 for which this problem takes Ω(n^{1.5}) queries.
To complement these results we give improved quantum algorithms in the lowprecision regime: with quantum graph sparsification and amplitude estimation, a boxconstrained Newton method can be sped up in the largeε regime, and outperforms previous quantum algorithms. For entrywisepositive matrices, we find an ε𝓁₁scaling in time O~(n^{1.5}/ε²), whereas the best previously known bounds were O~(n²polylog(1/ε)) (classical) and O~(n^{1.5}/ε³) (quantum).
BibTeX  Entry
@InProceedings{gribling_et_al:LIPIcs.STACS.2022.35,
author = {Gribling, Sander and Nieuwboer, Harold},
title = {{Improved Quantum Lower and Upper Bounds for Matrix Scaling}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {35:135:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772228},
ISSN = {18688969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15845},
URN = {urn:nbn:de:0030drops158458},
doi = {10.4230/LIPIcs.STACS.2022.35},
annote = {Keywords: Matrix scaling, quantum algorithms, lower bounds}
}
Keywords: 

Matrix scaling, quantum algorithms, lower bounds 
Collection: 

39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) 
Issue Date: 

2022 
Date of publication: 

09.03.2022 