Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers

技术摘要：量子线性系统求解器的稀疏度相关复杂度下界

问题陈述
本文研究了量子线性系统（Quantum Linear System, QLS）问题，该问题涉及寻找归一化量子态 $|x\rangle = A^{-1}|b\rangle / \|A^{-1}|b\rangle\|$ 的近似值 $|\tilde{x}\rangle$，使得 $\||\tilde{x}\rangle - |x\rangle\| \le \epsilon$。求解该问题的复杂度受三个主要参数控制：矩阵 $A$ 的条件数 $\kappa$、稀疏度 $s$（每行/每列非零条目的最大数量）以及目标误差 $\epsilon$。

虽然 QLS 求解器的查询复杂度上界已知为 $O(\kappa \log(1/\epsilon))$，但包含稀疏度 $s$ 的严格下界在之前一直是一个开放问题。尽管在学术界广泛接受（即“民间传闻”）下界应为 $\Omega(\kappa \sqrt{s} \log(1/\epsilon))$，并将其归功于 Harrow 和 Kothari 未发表的工作，但缺乏捕捉稀疏度依赖性的正式证明。

方法论
作者通过将已知的布尔问题归约为 QLS 问题来建立下界。他们利用稀疏矩阵 Oracle 访问模型，在该模型中，通过指定非零条目位置和数值的 Oracle 来访问矩阵 $A$。

1. 重新推导 $\kappa$ 与 $\epsilon$ 的依赖关系：
   为了重新确立 $\Omega(\kappa \log(1/\epsilon))$ 的界限，作者将**无限制误差 PARITY（unbounded-error PARITY）**问题归约为 QLS。他们构造了一个依赖于 PARITY 输入位的特定矩阵 $A$。通过分析该矩阵的谱性质以及应用 QLS 求解器后的所得量子态，他们证明了以特定误差容限求解 QLS 即可解决 PARITY 问题。由于 PARITY 的无限制误差查询复杂度为 $\Theta(n)$，这得出了所需的下界。

2. 推导稀疏度 ($s$) 的依赖关系：
   为了证明稀疏度相关的界限，作者将 有界误差 PARITY $\circ$ OR 问题归约为 QLS。该复合问题涉及计算 $n$ 个独立的 OR 函数（每个函数作用于 $m$ 个比特）结果的奇偶性（parity）。

   • 他们构造了一个矩阵 $A$，其非零条目编码了 OR 函数的输入。该构造确保矩阵的稀疏度 $s = \Theta(m)$。
   • 该矩阵经过设计，使其逆矩阵在应用于特定初始态时，能将 PARITY $\circ$ OR 问题的解编码在量子态的相位中。
   • 作者分析了所构造矩阵的条件数 $\kappa$，显示 $\kappa = \Theta(n)$，且稀疏度 $s = \Theta(m)$。
   • 通过利用已知的 PARITY $\circ$ OR 有界误差查询复杂度 $\Theta(n\sqrt{m})$，他们将该复杂度映射回 QLS 参数。

核心贡献与结果

• 对 $\Omega(\kappa \log(1/\epsilon))$ 的严格证明： 本文提供了 QLS 在常数稀疏度下的下界的详细且显式的推导，确认了近期算法在 $\kappa$ 和 $\epsilon$ 方面的最优性。该证明依赖于无限制误差 PARITY 的归约。
• 新下界 $\Omega(\kappa \sqrt{s})$： 本文的主要贡献是证明了任何求解 QLS 的量子算法（在常数误差下）其查询复杂度至少为 $\Omega(\kappa \sqrt{s})$。这是通过将有界误差 PARITY $\circ$ OR 问题归约为 QLS 实现的。
  • 证明表明，对于固定的常数误差，查询复杂度随稀疏度的平方根缩放。
  • 该结果是在目标误差 $\epsilon$ 为常数（$O(1)$）的假设下得出的，这意味着在此特定界限中并未显式捕捉 $\epsilon$ 的依赖关系。

意义与局限性
作者将这项工作定位为迈向完整表征 QLS 复杂度的关键一步。通过严格确立 $\sqrt{s}$ 的依赖性，他们验证了关于稀疏度在查询复杂度中作用的民间传闻。

然而，本文明确承认，同时捕捉所有三个参数的联合下界——$\Omega(\kappa \sqrt{s} \log(1/\epsilon))$——仍然是一个开放问题。

• 作者指出，试图使用无限制误差 PARITY $\circ$ OR 来捕捉所有参数是行不通的，因为无限制 OR 问题可以用 $O(1)$ 次查询解决，这会导致归约过程中的稀疏度依赖性坍缩。
• 他们建议，未来的工作可能需要从不同的布尔函数复合中归约 QLS，或者利用多项式逼近技术（具体而言是寻找 $\epsilon$-逼近 $1/x$ 的最小次数多项式），但后者目前缺乏关于 $\epsilon$ 依赖性的已知结果，且无法自然地引入稀疏度。

综上所述，本文提供了第一个关于稀疏度 $s$ 从根本上影响 QLS 求解器查询复杂度的严格证明，在常数误差下建立了 $\Omega(\kappa \sqrt{s})$ 的下界，同时将完整的多参数界限留作未来研究的课题。