重访线性回归的量子算法：无数据依赖参数的二次加速

Nov, 2023

重访线性回归的量子算法：无数据依赖参数的二次加速

Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters

Zhao Song, Junze Yin, Ruizhe Zhang

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

Abstract

linear regression is one of the most fundamental linear algebra problems. Given a dense matrix $A \in \mathbb{R}^{n \times d}$ and a vector $b$, the goal is to find $x'$ such that $ \| Ax' - b \|_2^2 \leq (1+\epsilon) \min_{x} \| A x - b \|_2^2 $. The best classical →

linear regression quantum linear regression algorithm quantum speedup condition number

发现论文，激发创造

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

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

Apr, 2017

用于训练线性和基于内核分类器的次线性量子算法

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

Apr, 2019

解线性方程组的量子算法

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

Nov, 2008

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

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

Nov, 2015

高效强多项式算法用于分位数回归

本文提出了针对 Quantile Regression 的多个高效确定性和随机多项式算法，连接到 k 集的几何概念和随机分治算法，分别解决了二维和多维 Quantile Regression 问题。

Jul, 2023

关于鲁棒线性回归的高效算法及下界

研究了高维线性回归在对抗性污染下的稳健模型问题，并针对从高斯分布生成的未被修正的样本的基本情况给出了几乎最紧的上界和计算下界。

May, 2018

路径稀疏 Lasso 的量子算法

我们提出了一种新颖的量子高维线性回归算法，基于经典的 LARS（最小角度回归）路径算法，通过引入量子求解子程序和近似量子最小寻找子程序，实现在目标参数变化时得到完整的正则化路径，以相对比较快的速度实现了二次加速。我们的研究还证明了 LARS 算法和我们的量子算法对误差具有鲁棒性，并给出了关于未知系数向量和近似 Lasso 解的界限。

Dec, 2023

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

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

Dec, 2020

在量子计算机上通过线性回归算法进行预测

该研究提出了一种基于量子计算机的线性回归模型和最小二乘优化算法的预测算法，并着重关注于数据点的输出猜测，通过适应算法处理低秩逼近表示的非稀疏数据矩阵，同时在联合量子信息处理过程中，可以通过单量子比特测量获得预测结果。

Jan, 2016

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

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

Dec, 2023