License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.110
URN: urn:nbn:de:0030-drops-141793
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14179/
van Apeldoorn, Joran ;
Gribling, Sander ;
Li, Yinan ;
Nieuwboer, Harold ;
Walter, Michael ;
de Wolf, Ronald
Quantum Algorithms for Matrix Scaling and Matrix Balancing
Abstract
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 Õ(√{mn}/ε⁴) for scaling or balancing an n × n matrix (given by an oracle) with m non-zero 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 speed-up in terms of n, at the expense of a worse polynomial dependence on the obtained ?₁-error ε. Even for constant ε these problems are already non-trivial (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 entrywise-positive 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:1--110:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-195-5},
ISSN = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14179},
URN = {urn:nbn:de:0030-drops-141793},
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 |
