技术摘要：通过内点法实现线性规划的量子加速

问题陈述

本文探讨了解决形式为 $\min c^T x$ 且满足 $Ax \geq b$ 的线性规划（LP）这一基础任务，其中 $A \in \mathbb{R}^{n \times d}$，$b \in \mathbb{R}^n$，且 $c \in \mathbb{R}^d$。研究重点特别针对“高瘦型”（tall）线性规划，即不等式约束的数量 $n$ 显著大于变量数量 $d$ 的情况（$n \gg d$）。

虽然经典内点法（IPMs）是求解线性规划的最先进技术，但其在处理高瘦、稠密实例时的复杂度约为 $\tilde{O}(nd + d^{2.5})$。作者研究了量子算法是否能在这种情形下为 IPM 提供加速，旨在实现一个相对于输入规模（特别是相对于 $n$）呈亚线性的运行时间。

方法论

所提出的方法是一种量子内点法，它通过近似 IPM 迭代核心中的牛顿步（Newton step）来工作。该算法并非计算精确的 Hessian 矩阵和梯度，而是利用量子子程序来获取 Hessian 矩阵的谱近似以及在逆局部范数下的梯度近似。

该方法依赖于三个主要的量子组件：

1. 量子谱近似（Quantum Spectral Approximation）：
   算法构建了一个矩阵 $B^T B$ 的谱近似，其中 $B \in \mathbb{R}^{n \times d}$ 是一个高瘦矩阵。这是通过结合“重复减半”（repeated halving）策略与杠杆得分采样（leverage score sampling）来实现的。

   • 机制： 算法使用 Grover 搜索在 $n$ 行 $B$ 中识别重要的行，其查询次数为 $\tilde{O}(\sqrt{n})$，而非经典方法所需的 $\tilde{O}(n)$。
   • 引导（Bootstrapping）： 为了避免由于需要杠杆得分来进行行采样而导致的循环依赖（这需要 $B^T B$），作者将一种经典的引导技术（Cohen 等人）引入到量子设置中。他们使用一系列均匀下采样的矩阵来迭代估计广义杠杆得分，并将其用于加权采样。

2. 量子 Lewis 权重近似（Quantum Approximation of Lewis Weights）：
   对于高级障碍函数（体积障碍和 Lewis 权重障碍），算法需要近似 $\ell_p$-Lewis 权重。

   • 机制： Lewis 权重是通过涉及重缩放矩阵的杠杆得分的固定点方程定义的。作者实现了一个基于低精度经典算法（Apers, Gribling, and Sidford）的迭代量子算法。
   • 效率： 由于显式写出 $n$ 个权重过于昂贵，无法实现亚线性时间，因此算法维护了隐式数据结构，允许高效地查询中间权重，而无需进行完全实例化。

3. 量子梯度近似（矩阵-向量乘法）：
   算法近似在“逆局部范数” $\|\cdot\|_{H(x)^{-1}}$ 下的梯度 $g(x)$。

   • 机制： 梯度被视为一个随机变量的均值。作者采用了最近的一种用于多元均值估计的量子算法（Cornelissen, Hamoudi, and Jerbi）。
   • 预处理（Preconditioning）： 为了避免对 Hessian 矩阵条件数的依赖，算法首先构建 Hessian 矩阵的谱近似 $\tilde{H}$。随后，算法从使用 $\tilde{H}^{-1/2}$ 进行“预处理”后的随机变量中进行采样，从而确保协方差矩阵的迹得到控制，并使生成的估计量满足所需的范数界限。

核心贡献

1. 量子谱近似算法：
   本文提出了一种量子算法，对于高瘦矩阵 $B$，该算法能以 $\tilde{O}(\sqrt{nd}/\delta)$ 次行查询返回 $B^T B$ 的 $\delta$-谱近似。这将其之前的量子图稀疏化结果推广到了高瘦矩阵，并在该特定任务上实现了相对于经典 $\tilde{O}(n)$ 查询下界的二次加速。

2. 量子 Lewis 权重计算：
   作者开发了一种量子算法，可提供对 $\ell_p$-Lewis 权重的 $\epsilon$-乘性近似的查询访问。这包括一个具有 $\tilde{O}(\sqrt{n} d^{7/2})$ 查询复杂度的预处理阶段，并允许后续以亚线性成本进行查询，从而在亚线性量子设置下使用 Lewis 权重障碍函数。

3. IPM 对近似的鲁棒性：
   本文正式确立了基于自共轭障碍函数（对数、体积和 Lewis 权重）的 IPM 在使用近似 Hessian 和近似梯度实现牛顿步时仍保持鲁棒性。具体而言，研究表明使用 Hessian 的谱近似以及在逆局部范数下的梯度近似足以维持收敛保证。

4. 针对高瘦型 LP 的量子 IPM：
   通过结合上述子程序，作者构建了一个求解具有 $n$ 个约束和 $d$ 个变量的高瘦型 LP 的量子 IPM。

   • 复杂度： 对于 Lewis 权重障碍函数，算法的运行时间为 $\tilde{O}(\sqrt{n} \cdot \text{poly}(d, \log(1/\epsilon)))$。
   • 查询复杂度： 该算法对输入数据进行 $\tilde{O}(\sqrt{n} d^5)$ 次行查询。当 $n \gg d^{10}$ 时，该算法在 $n$ 上是亚线性的。

结果

本文提供了以下理论结果：

• 定理 1.1（主要结果）： 存在一个量子 IPM 可以返回一个可行解 $\tilde{x}$，使得 $c^T \tilde{x} \leq \text{val} + \epsilon$。

  • 对于对数障碍函数：$\tilde{O}(nd)$ 次查询。
  • 对于体积障碍函数：$\tilde{O}(n^{3/4} d^{5/4})$ 次查询。
  • 对于Lewis 权重障碍函数：$\tilde{O}(\sqrt{n} d^5)$ 次查询。
  • Lewis 权重障碍函数的运行时间为 $\tilde{O}(\sqrt{n} \cdot \text{poly}(d))$。

• 下界（Lower Bounds）：

  • 论文证明了任何用于 $A^T A$ 谱近似的量子算法都需要 $\Omega(\sqrt{nd})$ 次行查询，这表明其算法中的 $\sqrt{n}$ 依赖关系是优化的。
  • 论文复现了一个下界，表明求解达到常数精度的 LP 需要 $\Omega(\sqrt{nd})$ 次量子查询（或 $\Omega(n)$ 次经典查询），这表明其算法中的 $d$ 依赖关系是潜在改进的主要领域。

• 基准对比：

  • 作者将其结果与基于切割平面法（使用 Grover 搜索作用于分离算子）的量子加速进行了比较，后者实现了 $\tilde{O}(\sqrt{n} d)$ 次查询。
  • 作者指出，虽然其 IPM 的 $d$ 依赖关系较差（$d^5$ 对比 $d$），但它代表了一种“白盒”方法，利用了 IPM 的内部结构；而切割平面法则是 Grover 搜索的一种“黑盒”应用。

意义与主张

本文声称为“高瘦型”线性规划是否可以使用量子算法加速这一问题提供了肯定的回答。

• 亚线性加速： 其主要意义在于实现了在高瘦型 LP 中，相对于约束数量 $n$ 的亚线性时间及查询复杂度，而在这种情形下经典算法是线性的。
• 新颖的子程序： 该工作引入了用于谱近似和 Lewis 权重计算的新颖量子子程序，这些子程序在统计回归和降维领域也具有独立的价值。
• 与条件数无关： 与以往依赖于量子线性系统求解器（引入了条件数依赖）的量子 IPM 提案不同，本方法通过使用谱近似和预处理规避了此类依赖。
• 误差依赖： 算法实现了对精度 $\epsilon$ 的 $\log(1/\epsilon)$ 依赖，优于以往通常具有 $1/\epsilon$ 多项式依赖关系的量子 LP 算法。

作者对 $d$ 的依赖关系保持谦逊，承认目前的界限（$d^5$）明显差于 $\sqrt{n} d$ 的切割平面基准。他们将改进梯度近似和利用动态数据结构确定为填补这一差距的关键研究方向。