论文标题
用于矩阵缩放和基质平衡的量子算法
Quantum algorithms for matrix scaling and matrix balancing
论文作者
论文摘要
矩阵缩放和矩阵平衡是两个基本的线性代数问题，具有多种应用，例如近似永久性和预处理的线性系统，以使它们在数值上更稳定。我们研究这些问题的量子算法的功能和局限性。 我们提供了两种经典方法的量子实现（从两种意义上讲）方法：用于矩阵缩放的sindhorn算法和用于矩阵平衡的Osborne的算法。使用振幅估计作为我们的主要工具，我们的量子实现都在时间$ \ tilde o（\ sqrt {mn}/\ varepsilon^4）$中，用于缩放或平衡$ n \ times n $ matrix（由Oracle给出$ m $ non-Zero nim $ M $ non-Zero n of $ m $ not-Zerion to $ n of $ n of-m $ n of to $ n n of $ el-ell-ZERO）。他们的经典类似物使用时间$ \ tilde o（m/\ varepsilon^2）$，并且使用小常数$ \ varepsilon $缩放或平衡的每种经典算法都需要$ω（m）$查询到输入矩阵的条目。因此，我们以$ n $的速度实现多项式加速，而牺牲了对所获得的$ \ ell_1 $ -error $ \ varepsilon $的多项式依赖。我们强调的是，即使对于常量的$ \ varepsilon $，这些问题也已经是不平凡的（并且在应用程序中相关）。 在此过程中，我们扩展了对Sindhorn和Osborne算法的经典分析，以在边际计算中出现错误。我们还改进了对Sindhorn的算法的进一步分析，用于进入$ \ ell_1 $ -setting，导致$ \ tilde o（n^{1.5}/\ varepsilon^3）$ - $ \ \ varepsilon $ - $ - $ - $ \ ell_1 $ -scal的时间量子量量； 我们还证明了一个下限，表明我们用于矩阵缩放的量子算法对于常数$ \ varepsilon $：每个用于矩阵缩放的量子算法的量子算法实质上是最佳的，该算法算法可实现达到常数的$ \ ell_1 $ - 相对于统一的Marginal，至少需要使至少$ω（\ queries）
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 $\tilde O(\sqrt{mn}/\varepsilon^4)$ for scaling or balancing an $n \times n$ matrix (given by an oracle) with $m$ non-zero entries to within $\ell_1$-error $\varepsilon$. Their classical analogs use time $\tilde O(m/\varepsilon^2)$, and every classical algorithm for scaling or balancing with small constant $\varepsilon$ 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 $\ell_1$-error $\varepsilon$. We emphasize that even for constant $\varepsilon$ 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 $\ell_1$-setting, leading to an $\tilde O(n^{1.5}/\varepsilon^3)$-time quantum algorithm for $\varepsilon$-$\ell_1$-scaling in this case. We also prove a lower bound, showing that our quantum algorithm for matrix scaling is essentially optimal for constant $\varepsilon$: every quantum algorithm for matrix scaling that achieves a constant $\ell_1$-error with respect to uniform marginals needs to make at least $Ω(\sqrt{mn})$ queries.
