机构名称：
¥ 1.0
矩阵缩放和矩阵平衡是两个基本的线性代数问题，具有广泛的应用，例如近似永久系统和预处理线性系统以使其在数值上更稳定。我们研究了这些问题的量子算法的能力和局限性。我们提供了两种经典（两种意义上的）方法的量子实现：用于矩阵缩放的 Sinkhorn 算法和用于矩阵平衡的 Osborne 算法。使用幅度估计作为主要工具，我们的量子实现都需要花费时间 e O ( √ mn/ε 4 ) 来缩放或平衡具有 m 个非零条目的 n × n 矩阵（由 oracle 给出），使其在 ℓ 1 -error ε 以内。它们的经典类似物使用时间为 e O ( m/ε 2 )，并且每个用于缩放或平衡具有小常数 ε 的经典算法都需要对输入矩阵的条目进行 Ω(m) 次查询。因此，我们实现了 n 的多项式加速，但代价是对于获得的 ℓ 1 误差 ε 的多项式依赖性更差。即使对于常数 ε ，这些问题也已不简单（并且与应用相关）。在此过程中，我们扩展了 Sinkhorn 和 Osborne 算法的经典分析，以允许在边际计算中出现错误。我们还将 Sinkhorn 针对逐项正矩阵算法的改进分析调整到 ℓ 1 设置，获得了一个 e O ( n 1 . 5 /ε 3 ) 时间量子算法，用于 ε - ℓ 1 缩放。我们还证明了一个下限，表明我们的矩阵缩放量子算法对于常数 ε 本质上是最优的：每个实现均匀边际的常数 ℓ 1 误差的矩阵缩放量子算法都需要 Ω( √ mn ) 次查询。
矩阵缩放和矩阵平衡的量子算法
主要关键词
相关文件推荐
