Quantum Algorithms for the Pathwise Lasso

我们提出了一种新颖的基于$\ell_1$-惩罚的高维量子线性回归算法，该算法基于经典的LARS（最小角回归）路径算法。与现有的Lasso经典数值算法类似，我们的量子算法提供了完整的正则化路径，随着惩罚项的变化而变化，但在特定条件下，每次迭代的速度比经典算法快二次方。通过使用D\"urr和Hoyer（arXiv'96）的简单量子最小查找子程序来获得每次迭代的连接时间，可以在特征/预测变量数量$d$上实现二次速度提升。然后，我们改进了这个简单的量子算法，并通过使用Chen和de Wolf（ICALP'23）最近的近似量子最小查找子程序，在特征数$d$和观测数$n$上实现了二次速度提升。作为我们的主要贡献之一，我们构建了一个基于量子幅度估计的量子酉来近似计算加入时间，以便由近似量子最小查找搜索。由于不再精确计算加入时间，因此不清楚得到的近似量子算法是否获得了良好的解。作为我们的第二个主要贡献，我们通过近似的KKT条件和对偶间隙证明，LARS算法（因此我们的量子算法）对误差具有鲁棒性。这意味着，如果连接时间仅被近似计算，它仍然输出最小化Lasso成本函数的路径，直到小的误差。最后，在由未知系数向量生成观测值的模型中，我们证明了未知系数向量和近似Lasso解之间差异的界限，这扩展了关于经典统计学习理论分析中收敛速度的已知结果。

本论文旨在提出一种新的量子高维线性回归算法，该算法基于经典LARS算法，使用L1惩罚项。

本文提出的量子算法可以在每次迭代中以二次速度快速计算得到完整的正则化路径，具有比现有经典算法更快的速度。

本文的亮点包括使用量子最小查找子程序实现每次迭代中的加入时间，并使用量子幅度估计构建量子酉矩阵，从而近似计算加入时间。此外，本文证明了LARS算法对误差具有鲁棒性，并在线性模型下证明了未知系数向量与近似Lasso解之间的误差界。

近期的相关研究包括基于量子计算的其他机器学习算法，如量子支持向量机和量子主成分分析。