量智信息中心_量科网

该研究团队描述并分析了一种用于线性系统𝐀𝐱=𝐛解𝐱∗:=𝐀⁺𝐛采样的简易算法。该方法假设存在可按照𝐀行/列范数平方比例抽取索引的采样器。该算法能在Õ(κ_F⁴κ²/ε²)时间内生成满足‖𝐱∗−𝐱‖<ε‖𝐱∗‖的向量𝐱压缩表示，其中κ_F:=‖𝐀‖_F‖𝐀⁺‖，κ:=‖𝐀‖‖𝐀⁺‖。该表示支持在Õ(κ_F²)时间内查询𝐱分量，并在Õ(κ_F⁴κ⁶)时间内实现按分量平方采样的功能（需预设𝐀任意行的分量平方采样器）。这项基础性、非渐近且完全自洽的分析，简化并澄清了文献[Gilyén等，2022]与[Shao和Montanaro，2022-2023]中的多个既往分析框架。