量子线性代数算法通常通过量子随机存取存储器（QRAM）访问矩阵 $A$，并准备与线性系统解成比例的量子态。对应的去量子化经典算法在获得对 $A$ 的抽样和查询访问后，返回对近似解的抽样和查询访问。两类算法的查询次数均为归一化 Frobenius 范数 $\rho=\|A\|_F/\|A\|$ 的多项式，并且不直接依赖维度。\
在固定条件数 $\kappa$ 和精度的情况下，量子算法的查询复杂度为 $\widetilde O(\rho)$，而已知的最佳去量子化算法为 $\widetilde O(\rho^4)$。本文证明，在最坏情况下，这一四次方差距是紧的（至多差一个对数因子）。具体而言，对于任意常数 $\kappa_0>1$，我们构造了条件数不超过 $\kappa_0$ 的稠密线性系统，使得在足够小的总变分距离下抽样解需要 $\Omega(\rho^4/\log\rho)$ 次经典查询，而仅需 $\Theta(\rho)$ 次量子查询。\
相同的分离结果同样适用于正定系统、最小二乘、岭回归、矩阵幂与平方根、虚时与实时哈密顿演化以及主成分抽样，只要误差阈值足够小。因而，许多线性代数的量子算法在最坏情况下相较于拥有抽样和查询访问的经典算法实现了近四次方的加速。所有这些经典下界均来源于同一框架：基于对依赖于未知布尔函数固定傅里叶系数的分布抽样的下界。\
点评：本文通过构造性下界证明了量子线性代数算法相对于去量子化算法的四次方加速是不可进一步提升的，巩固了量子优势的理论极限。