我们设计了基于量子算法的子线性算法，用于分类问题和矩阵零和游戏问题的求解，其复杂度都是量级上界的平方根，相较现有技术有瓶颈的常数。我们的算法生成与传统算法完全相同的结果，推荐用于端到端应用，同时探讨了实现方式以及机器可达到的限制。

Apr, 2019

本文介绍了解决低秩线性系统的古典次线性时间算法。我们的算法受 HHL 量子算法解决线性系统和 Tang 去量子化推荐系统量子算法的最新突破的启发。我们提出了两种算法：提供 $A^{-1} b$ 样本的 “采样” 算法和输出 $A^{-1} b$ 条目的估计值的 “查询” 算法。我们考虑的算法的时间复杂度是次线性时间的。

Nov, 2018

提出量子计算的次线性时间的算法，基于 LP 问题和量子 SDP 求解器，用有效的 Gibbs 采样方法计算二人零和游戏的 Nash 均衡点。

Apr, 2019

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

Nov, 2008

算法设计为在欧几里得或单纯形域内最小化 max (f_i (x))，若每个 f_i 为 1-Lipschitz 和 1 - 光滑函数，我们的方法可以在评价复杂度中找到 ε- 近似解，并具有优化性能。

Nov, 2023

线性回归是最基本的线性代数问题之一，本研究提出了一个运行时间为 O (ε^(-1) * sqrt (n) * d^(1.5)) + poly (d/ε) 的量子算法，可以在不依赖数据相关参数的情况下，提供 n 的二次量子加速效果，同时还将结果推广到多次回归和岭线性回归。

Nov, 2023

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

Apr, 2017

本文提出了一种基于采样技术和新的乘性更新算法的新颖子线性时间逼近算法，可用于解决一些机器学习优化问题，如训练线性分类器和查找最小包含球，此外，还用于解决一些核化版本的这些问题，如 SVM 等。此外，文章还在半流数据流设置中给出了实现，实现了第一个低通多项式空间和次线性时间算法。

Oct, 2010

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

Sep, 2018

我们提出了首个在线量子算法，用于零和游戏，可以在 $\tilde O (1)$ 的时间内计算 $m \times n$ 矩阵零和游戏的 $\varepsilon$- 近似纳什均衡，与 $m$，$n$ 的经典算法相比，取得了二次的改进，同时实现了一个快速的量子线性规划求解器。

Apr, 2023