技术摘要：一种最优量子线性系统算法

问题陈述

量子线性系统问题（QLSP）涉及求解一个线性方程组 $A\vec{x} = \vec{b}$，其中 $A$ 是一个可逆的、$d$-稀疏的 $N \times N$ 矩阵，其条件数为 $\kappa$，且 $\vec{b}$ 是已知向量。目标不是输出经典向量 $\vec{x}$，而是准备一个与理想解状态的迹距离（trace distance）至多为 $\epsilon$ 的比例量子态 $|x\rangle$，该过程以成功标志为条件。该算法在标准的稀疏矩阵算子模型下运行，即通过位置算子（识别行中的非零项）和数值算子（返回条目值）获得访问权限。

在此项工作之前，已知的最佳 QLSP 量子算法查询复杂度为 $O(\kappa d \log(1/\epsilon))$ [CAS+22] 和 $\kappa \sqrt{d} (\kappa d / \epsilon)^{o(1)}$ [Low19]。已知的最佳下界为 $\Omega(\kappa \log(1/\epsilon))$ [CABB25] 和 $\Omega(\kappa \sqrt{d})$ [MKBR26]。在上下界之间存在差距，特别是在对稀疏度 $d$ 的依赖关系方面。

方法论

上界构建

作者通过构建一种新算法，证明了最优查询复杂度为 $\Theta(\kappa \sqrt{d} \log(1/\epsilon))$。其核心创新是一种规避了稀疏矩阵块编码中标准障碍的归约技术。

1. 障碍： 标准的稀疏矩阵 $A$ 的块编码通常依赖于分解 $A = F^\dagger T$。虽然映射 $T$（分配振幅）易于实现，仅需 $O(1)$ 次查询，但映射 $F$（加载行值）通常需要 $\Omega(\sqrt{d})$ 次查询以避免解决无结构搜索问题。这导致了以往算法中次优的 $O(\kappa d)$ 依赖关系。
2. 归约： 为了避免直接实现 $F$，作者引入了一个中间向量 $\vec{z}$，将方程 $F^\dagger T \vec{u} = \vec{b}$ 分解为两个耦合方程：$T \vec{u} = \vec{z}$ 和 $F^\dagger \vec{z} = \vec{b}$。
3. 扩大的系统： 这些方程被组合成一个更大的线性系统 $L \begin{pmatrix} \vec{z} \\ \vec{u} \end{pmatrix} = \begin{pmatrix} 0 \\ \vec{b} \end{pmatrix}$。矩阵 $L$ 的构造使得其解包含特定分块中的原始解 $\vec{x}$（经缩放）。
4. 扩大的系统块编码： 作者使用仅需 $O(1)$ 次稀疏矩阵算子查询的方法，为归一化后的 $L$（记作 $M$）构造了一个精确的块编码。这是通过以下方式实现的：
   • 定义状态准备映射，加载单个条目而非整个行。
   • 分别对每个状态准备映射进行归一化，从而允许通过这种方式绕过昂贵的 $F$ 映射。
   • 证明了新矩阵 $M$ 的条件数为 $O(\kappa \sqrt{d})$。
5. 求解： 使用现有的块编码 QLSP 算法 [CAS+22] 来求解扩大的系统。由于 $M$ 的条件数为 $O(\kappa \sqrt{d})$ 且通过 $O(1)$ 次查询访问，总复杂度变为 $O(\kappa \sqrt{d} \log(1/\epsilon))$。

下界构建

为了证明下界 $\Omega(\kappa \sqrt{d} \log(1/\epsilon))$，作者结合了两个来源的难度：

1. 无结构搜索： 嵌入一个规模为 $d$ 的无结构搜索问题，产生 $\Omega(\sqrt{d})$ 的下界。
2. 电路历史/奇偶性： 嵌入一个计算 $R$ 位奇偶性的电路，产生 $\Omega(R)$ 的下界，其中 $R$ 与条件数和精度相关。具体而言，线性系统构造中“历史状态”的衰减将条件数 $\kappa$ 与精度 $\epsilon$ 耦合，使得 $R = \Theta(\kappa \log(1/\epsilon))$。
3. 复合： 作者构造了一个需要计算 $R$ 位奇偶性的问题，其中每一位都是一个独立的规模为 $d$ 的无结构搜索的输出。利用 Lee 和 Roland [LR12] 的量子 XOR 引理，他们证明了该复合问题的查询复杂度为 $\Omega(R \sqrt{d})$，这转化为 $\Omega(\kappa \sqrt{d} \log(1/\epsilon))$。

关键结果

定理 1（最优查询复杂度）： QLSP 的查询复杂度为 $\Theta(\kappa \sqrt{d} \log(1/\epsilon))$。这填补了此前上界与下界之间的差距。

定理 2（平方根稀疏度块编码）： 对于任何满足 $\|H\| \le 1$ 的 Hermitian $d$-稀疏矩阵 $H$，可以使用 $O(\sqrt{d} \log(1/\eta))$ 次稀疏矩阵算子查询构造一个 $(O(1), \eta)$ 的块编码。这改进了以往需要 $O(d)$ 次查询才能达到常数误差的方法。

推论 3（黑盒酉矩阵实现）： 给定对 $N \times N$ 酉矩阵 $U$ 条目的算子访问，可以使用 $O(\sqrt{N} \log(1/\epsilon))$ 次查询将 $U$ 实现到误差 $\epsilon$。这解决了 Berry 和 Childs [BC12] 提出的关于 $\Omega(\sqrt{N})$ 下界是否能通过无结构搜索匹配的开放问题。

意义与主张

本文声称提供了对量子线性系统问题查询复杂度的完整表征。通过证明匹配的上下界，作者确立了对条件数 $\kappa$、稀疏度 $d$ 和精度 $\epsilon$ 的依赖关系是处于最优水平的。

这项工作的意义在于：

1. 最优性： 它确定了 QLSP 量子算法的理论极限，表明之前的 $O(\kappa d)$ 依赖关系并非本质特征，而是算法方法的产物。
2. 方法论进步： 通过将矩阵乘积拆分为更大的线性系统以避免昂贵的状态准备映射，该技术为量子算法设计提供了一种新的工具，特别是针对稀疏矩阵的块编码。
3. 解决开放问题： 这些结果直接解决了关于实现黑盒酉矩阵的最优查询复杂度的开放问题，确认了 $\Omega(\sqrt{N})$ 下界是紧致的。

作者指出，上界的证明是独立开发的，尽管他们承认使用了 AI 工具来简化证明和准备手稿。下界证明依赖于已建立的技术（历史状态、XOR 引理）应用于一种新的复合构造中。