Search Results

Documents authored by Gribling, Sander

Document
DOI: 10.4230/LIPIcs.STACS.2022.35
Improved Quantum Lower and Upper Bounds for Matrix Scaling

Authors: Sander Gribling and Harold Nieuwboer

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Matrix scaling is a simple to state, yet widely applicable linear-algebraic problem: the goal is to scale the rows and columns of a given non-negative matrix such that the rescaled matrix has prescribed row and column sums. Motivated by recent results on first-order quantum algorithms for matrix scaling, we investigate the possibilities for quantum speedups for classical second-order algorithms, which comprise the state-of-the-art in the classical setting. We first show that there can be essentially no quantum speedup in terms of the input size in the high-precision regime: any quantum algorithm that solves the matrix scaling problem for n × n matrices with at most m non-zero 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 row-sum 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 low-precision regime: with quantum graph sparsification and amplitude estimation, a box-constrained Newton method can be sped up in the large-ε regime, and outperforms previous quantum algorithms. For entrywise-positive 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).
Cite as

Sander Gribling and Harold Nieuwboer. Improved Quantum Lower and Upper Bounds for Matrix Scaling. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 35:1-35:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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:1--35:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.35},
  URN =		{urn:nbn:de:0030-drops-158458},
  doi =		{10.4230/LIPIcs.STACS.2022.35},
  annote =	{Keywords: Matrix scaling, quantum algorithms, lower bounds}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.110
Quantum Algorithms for Matrix Scaling and Matrix Balancing

Authors: Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter, and Ronald de Wolf

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

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.
Cite as

Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter, and Ronald de Wolf. Quantum Algorithms for Matrix Scaling and Matrix Balancing. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 110:1-110:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ICALP.2021.110},
  URN =		{urn:nbn:de:0030-drops-141793},
  doi =		{10.4230/LIPIcs.ICALP.2021.110},
  annote =	{Keywords: Matrix scaling, matrix balancing, quantum algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact