A quantum central path algorithm for linear optimization

技术摘要：一种用于线性优化的量子中心路径算法

问题陈述
本文研究了求解形式为 $\min c^\top x$ 且满足 $Ax \ge b, x \ge 0$ 的线性优化（LO）问题及其对偶问题的过程。虽然经典的内点法（IPM）是解决此类问题的最先进技术，但它们依赖于迭代牛顿步，这需要在每次迭代中求解大型线性系统（牛顿线性系统）。现有的量子内点法（QIPMs）试图通过使用量子线性系统算法（QLSAs）来加速这一过程。然而，目前的 QIPMs 面临两个主要局限性：（1）它们通常需要量子随机存取存储器（QRAM）模型，这在被认为是不切实际的近中期设备上往往难以实现；（2）它们仍然是迭代式的，继承了经典 IPM 的 $O(\sqrt{n} \log(1/\varepsilon)$ 迭代复杂度，并且依赖于昂贵的量子态层析技术来提取经典解。

方法论
作者提出了一种被称为**量子中心路径法（QCPM）**的新颖方法。与量化经典算法“步骤”的 QIPMs 不同，QCPM 量化的是中心路径本身的“动力学”。该方法论如下进行：

1. 哈密顿量公式化： 作者构建了一族定义在正交区域上的随时间变化的哈密顿算符 $H(\mu, h)$。该哈密顿量是一个由动能项和势能项组成的薛定谔算符：
   $$H(\mu, h) = -\frac{h^2}{2} \nabla^2 + \Phi_\mu(z)$$
   这里，$\mu$ 是中心路径参数（与对偶间隙相关），而 $h$ 是一个类似于普朗克常量的缩放参数。势函数 $\Phi_\mu(z)$ 源自自共轭障碍函数（具体为二次连续对数函数），其设计使得其全局最小值恰好对应于 LO 问题中心路径上的 $\mu$-中心。

2. 基态编码： 核心理论见解是：$H(\mu, h)$ 的基态（具有最低特征值的特征向量）编码了一个以中心路径为中心的概率分布。随着 $\mu \to 0$，该分布会向最优解处聚集。参数 $h$ 控制该分布的方差；减小 $h$ 会将波包“挤压”在解的周围。

3. 特征路径遍历： 该算法并非通过迭代牛顿步，而是通过遍历哈密顿量的基态轨迹来进行。作者采用了参数 $(\mu, h)$ 的两阶段调度：

   • 阶段 1（输运）： $\mu$ 从 1 减小到 $\varepsilon$，同时保持 $h = \mu$。这使得基态的中心沿着中心路径移动。
   • 阶段 2（挤压）： 固定 $\mu = \varepsilon$，并将 $h$ 减小到目标值 $h^*$，以使分布围绕 $\varepsilon$-最优解更加收敛。
     该调度经过精心设计，以确保连续的基态之间具有足够大的重叠（$> 1/\sqrt{3}$），从而满足高效特征路径遍历算法（特别是 Boixo, Knill, 和 Somma 的方法）的条件。

4. 实现： 算法准备初始基态（对应于 $\mu=1$），然后模拟薛定谔动力学以进行遍历。它利用空间离散化将无限维算符映射为适用于基于门电路的量子计算机的有限维矩阵。至关重要的是，该算法不需要 QRAM；它仅需要通过一个势函数的评估预言机（evaluation oracle）来访问问题数据的二进制描述 $(A, b, c)$。

核心贡献

• 新范式： 本文引入了第一个通过直接模拟薛定谔动力学来求解线性优化的量子算法，而非量化经典 IPM 的牛顿步。
• QRAM 独立性： 该算法在标准的门电路模型下运行，无需 QRAM，解决了以往 QIPM 提案中的一个主要实际瓶颈。
• 非迭代性质： 通过测量最终量子态以实现“一阶段式”（one-shot）求解，避免了迭代循环以及相关的误差累积或重复层析的需求。
• 理论保证： 作者为势函数的强凸性、哈密顿量的谱间隙以及基态在中心路径附近的集中性提供了严格证明。

结果与复杂度
本文确定了 QCPM 以 $\varepsilon$-最优性求解具有 $m$ 个约束和 $n$ 个变量的 LO 问题的复杂度：

• 查询复杂度： 对势函数预言机的查询次数为 $\tilde{O}\left((m + n)^{3/2} \varepsilon^{-1} + (m + n)^{1/2} \varepsilon^{-3/2}\right)$。
• 门复杂度： 基本门数为 $\tilde{O}\left(\left[(m + n)^{3/2} \varepsilon^{-1} + (m + n)^{1/2} \varepsilon^{-3/2}\right] \cdot \text{nnz}(A)\right)$，其中 $\text{nnz}(A)$ 是约束矩阵中非零元素的数量。

复杂度取决于问题的稀疏性和精度 $\varepsilon$，但值得注意的是，它避免了对问题数据条件数的依赖。

意义与主张
作者声称，这项工作提供了“令人信服的证据，表明即使在没有 QRAM 的电路模型中，也可能实现端到端的线性优化量子加速”。他们强调，QCPM 提供了一种全新的量子优化范式，有别于以往 QIPMs 的“量子子程序”方法。

论文对于其现状保持谦逊，指出：

• 资源分析表明，该算法在理论上是成立的，但若要在近中期设备上实现实用化，可能需要显著的增强（特别是在误差依赖方面）。
• 该算法求解的是 LO 问题的“自对偶嵌入模型”（self-dual embedding model），这是经典 IPM 中的一种标准理论方法，而非直接求解原始问题，尽管作者认为经典方法中使用的终止准则也适用于此处。
• 虽然该框架很有前景且目前尚无已知的直接经典对应物，但本文旨在建立“基础”性的严谨分析，而非声称立即具备优于现有最佳经典算法（目前运行时间为 $\tilde{O}((m+n)^\omega)$）的实际优越性。
• 作者明确表示，他们并未尝试构建该量子动力系统的经典对应物，并承认设计一个能够追踪随时间变化的势能全局最小值的经典系统将是一个巨大的挑战。

总之，本文通过将内点法与量子哈密顿量模拟相结合，提出了一个理论突破，为绕过 QRAM 和迭代层析限制的线性优化量子加速路径提供了可能的途径。