Succinct Infinite-Horizon Lyapunov and LQR Value Problems Are BQP-Complete

技术摘要：简洁型无限时域李雅普诺夫与 LQR 价值问题是 BQP-完全的

问题定义
本研究调查了当系统矩阵以**简洁（succinct）**方式表示时，评估无限时域性能度量的计算复杂度。与标准数值分析中显式列出矩阵（其存储空间与维度 $n$ 成正比）不同，本文考虑由布尔查找电路定义的 $n \times n$ 矩阵。这些电路定义了稀疏矩阵的非零项，使得输入长度与 $\log n$ 成多项式关系，而非与 $n$ 成正比。

在上述简洁输入模型下，定义了两个特定的承诺问题（promise problems）：

1. 简洁李雅普诺夫价值 (SLV)： 给定一个耗散自治系统 $\dot{x} = Ax$，初始状态为 $b$，输出为 $y=Cx$，判定其无限时域输出能量 $J(b) = b^\top P b$（其中 $P$ 满足李雅普诺夫方程 $A^\top P + PA + C^\top C = 0$）是否低于阈值 $a_0$ 或高于 $a_1$。
2. 简洁 LQR 价值 (SLQRV)： 给定受控系统 $\dot{x} = Ax + Bu$ 及涉及矩阵 $C$ 和 $R$ 的代价函数，判定最优无限时域二次代价 $V(b)$（源自代数 Riccati 方程）是否低于 $a_0$ 或高于 $a_1$。

方法论
作者结合了量子复杂度理论与控制理论分析：

• 硬度归约 (SLV)： 为了证明 SLV 是 BQP-难 (BQP-hard) 的，作者构造了一个从任意属于有界误差量子多项式时间 (BQP) 问题到该问题的归约。他们利用 Feynman 时钟构造 (Feynman clock construction) 将离散时间量子电路 $\{Y_r\}$ 映射到连续时间线性系统。

  • 将量子电路转换为作用在扩大寄存器（包括一个辅助量子比特）上的实正交矩阵 $D_r$。
  • 将该矩阵嵌入到作用在组合时钟-工作空间上的幂零“时钟传播算子” $W_r$ 中。
  • 构建连续时间系统矩阵 $A_r$ 为单位矩阵与 $W_r$ 的缩放和。作者确保 $A_r$ 是严格耗散（Hurwitz）的，且具有单个重复实特征值。
  • 在特定坐标向量处评估所构造系统的输出能量，其结果直接对应于原始量子电路的接受概率。通过引理 1，量子电路被正交门以有理数项的形式进行近似，从而确保生成的系统矩阵符合简洁的二进编码要求。

• 成员资格 (SLQRV)： 为了证明 SLQRV 属于 BQP，作者利用了现有的求解线性矩阵方程的量子算法。

  • 他们利用了 Riccati 解与相关哈密顿矩阵的 稳定 Riesz 投影器 (stable Riesz projector) 之间的联系。
  • 在定量可稳定性和可检测性假设（这些假设限制了瞬态放大和衰减率）下，他们应用量子算法来估计谱投影器和线性系统（例如，块编码技术），以高精度估计标量值 $V(b)$，其运行时间与简洁输入长度的多项式成正比。

• 嵌入： 作者证明了 SLV 是 SLQRV 的一个特例（通过设置控制输入矩阵 $B=0$ 及适当的权重），从而确立了 SLV 的硬度适用于更一般的 SLQRV 问题。

主要贡献与结果

1. BQP-完全性： 本文确定了 SLV 和 SLQRV 问题均为 BQP-完全 (BQP-complete)。
   • 硬度： SLV 是 BQP-难的，这意味着任何可在量子计算机上以多项式时间解决的问题都可以归约为 SLV 的一个实例。
   • 成员资格： SLQRV（以及 SLV）属于 BQP，因为存在量子算法可以在与系统维度的对数成多项式的时间内解决它。
2. 经典不可解性： BQP-完全性的直接结果是，除非 BPP = BQP，否则在简洁输入模型下，不存在经典的随机算法能在多项式时间内解决这些问题的所有承诺实例。即使对于具有高度结构化矩阵（单重复实特征值）的严格耗散自治系统，这一结论依然成立。
3. 精细的复杂度分类： 本研究深化了对控制理论中经典与量子可处理性边界的理解。它识别了一类特定的无限时域性能评估任务，这类任务在简洁输入模型下，即使系统矩阵是稀疏且稳定的，对于经典计算机也是不可处理的。

意义
本文声称为量子计算机在系统分析与控制领域的潜在优势提供了严谨的复杂度理论依据。虽然以往的研究表明在特定数值方法（如策略梯度法或求解线性系统）中存在量子加速，但本文证明了在简洁设置下，评估无限时域代价这一基本任务本质上对于经典计算机是困难的。

这些结果补充了现有的关于稀疏线性系统和矩阵几何平均值的复杂度分类。通过将问题定义为标量值（输出能量或最优代价）的决策任务，而非完整的矩阵解，作者使该问题与量子算法的自然输出能力相契合——即量子算法可以估计此类标量，而无需显式计算指数级大的 Gramian 或 Riccati 解。这项工作表明，对于由简洁电路定义的超高维系统，经典随机算法面临着高效评估的条件性障碍，而量子算法则可以克服这一障碍。