Nov, 2018

量子启发的次线性经典算法求解低秩线性系统

PDF
TL;DR本文介绍了解决低秩线性系统的古典次线性时间算法。我们的算法受 HHL 量子算法解决线性系统和 Tang 去量子化推荐系统量子算法的最新突破的启发。我们提出了两种算法：提供 $A^{-1} b$ 样本的 “采样” 算法和输出 $A^{-1} b$ 条目的估计值的 “查询” 算法。我们考虑的算法的时间复杂度是次线性时间的。
low-rank linear systemssublinear-time algorithmsquantum algorithmmoore-penrose pseudo-inversecondition number
发现论文，激发创造
  • 基于量子理论的低秩随机回归，其维度对数依赖性

    本论文构建了一个高效的量子矩阵反演算法（HHL）的经典模拟器，基于 Tang 的最近研究成果，通过对输入数据进行长度平方采样，实现了低秩矩阵的伪逆并使用快速抽样技术从问题 $Ax=b$ 的解中采样。本文通过子采样来找到 $A$ 的近似奇异值分解，从而实现伪逆。该方法也可用于把任何期望的 “平滑” 函数应用到奇异值上。既然许多量子算法可以表示为奇异值变换问题，我们的结果表明更多的低秩量子算法可以有效地 “去量子化” 成为使用长度平方采样的经典算法。

    Nov, 2018

  • 稠密矩阵的量子线性系统算法

    介绍了一个基于奇异值估算子程序的量子算法，可解决线性方程组问题，其运行时间与矩阵 A 的条件数、Frobenius 范数和精度参数有关。当应用于具有范数受到限制的密集矩阵时，所提出的算法的运行时间受到限制，其运行时间比已知的量子线性系统算法提高了平方级别。

    Apr, 2017

  • 解线性方程组的量子算法

    该研究探讨了解决稀疏矩阵线性系统的期望值问题，通过使用量子算法实现了在 poly (log N, kappa) 时间内运行，这是目前最佳经典算法的指数级改进。

    Nov, 2008

  • 关于亚线性时间求解线性系统

    本文主要研究解决局部线性系统的亚线性算法，并比较了对称对角占优矩阵和半正定矩阵在坐标近似问题上的差异。通过开发出近似坐标的算法，我们证明了存在一定的定量差距，并证明条件数假设是必要且紧束缚的。相比于对称对角占优矩阵，我们证明了对于某些半正定矩阵，其运行时间必须是多项式级别的。

    Sep, 2018

  • 高效求解密集线性系统的方法

    提出了一种随机优化算法，通过块坐标下降方法和矩阵草图技术，在线性系统中实现了良好的收敛性能和快速迭代时间。

    Dec, 2023

  • 量子算法对线性方程组的指数级精度改进

    该研究旨在通过改进基于傅里叶 / 切比雪夫级数表示的算子实现通用技术，构建了一个可以求解线性系统方程的量子算法，该算法在时间复杂度方面与精度具有同等重要的依赖性。

    Nov, 2015

  • 一般矩阵博弈的次线性经典和量子算法

    本研究提出了一种插值算法，该算法能够在两个特殊情况之间插值，并解决矩阵游戏问题。我们同时提供经典算法和量子算法，用于近似 Cara​théodore 问题和 lq-margin 支持向量机。

    Dec, 2020

  • 基于采样的次线性低秩矩阵算法框架来去量子化量子机器学习

    提出了一种基于量子思想的经典算法框架，用于解决接近低秩矩阵问题并快速实现量子算法的经典版本，证明了量子 SVT 框架并不能提供指数级的速度提升，并给出了该框架的多种经典化结果。

    Oct, 2019

  • 一种基于量子启发式思想的经典推荐系统算法

    通过使用简单例程来操纵 $\ell^2$ -norm 抽样分布，并提供一个给定数据结构的算法来生成从矩阵秩 - $k$ 近似值的 $\ell^2$ -norm 样本，本研究为 Kerenidis 和 Prakash 的量子推荐系统提供了古典类比，进一步证明此算法并未超越经典算法；此外，尽管假定输入数据重程度较大，但我们的经典推荐系统与先前线性 m 和 n 时间运行的经典系统相比能够在指数上更快地产生推荐。

    Jul, 2018

  • 受绝热量子计算启发的线性方程组量子算法

    本研究基于量子算法，提出了两种解决线性方程组问题的演化随机化算法，这种算法由哈密顿量组成，不需要大量辅助系统，并在某些条件下实现了指数级的量子加速。

    May, 2018