## 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 Oe(√mn/ε4) for scaling or balancing an n × n matrix (given by an oracle) with m non-zero entries to within ℓ1-error ε. Their classical analogs use time Oe(m/ε2), 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 ℓ1-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 ℓ1-setting, obtaining an Oe(n1.5/ε3)-time quantum algorithm for ε-ℓ1-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 ℓ1-error w.r.t. uniform marginals needs Ω(√mn) queries.

Using amplitude estimation as our main tool, our quantum implementations both run in time Oe(√mn/ε4) for scaling or balancing an n × n matrix (given by an oracle) with m non-zero entries to within ℓ1-error ε. Their classical analogs use time Oe(m/ε2), 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 ℓ1-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 ℓ1-setting, obtaining an Oe(n1.5/ε3)-time quantum algorithm for ε-ℓ1-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 ℓ1-error w.r.t. uniform marginals needs Ω(√mn) queries.

Original language | English |
---|---|

Title of host publication | 48th International Colloquium on Automata, Languages, and Programming |

Subtitle of host publication | (ICALP 2021) |

Pages | 110:1-110:17 |

ISBN (Electronic) | 9783959771955 |

DOIs | |

Publication status | Published - Jul 2021 |

Externally published | Yes |

Event | 48th International Colloquium on Automata, Languages, and Programming - online Duration: 12 Jul 2021 → 16 Jul 2021 |

### Publication series

Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|

### Conference

Conference | 48th International Colloquium on Automata, Languages, and Programming |
---|---|

Abbreviated title | ICALP 2021 |

Period | 12/07/21 → 16/07/21 |

## Keywords

- matrix scaling
- matrix balancing
- quantum algorithms