作者: Jingyao Wang, Yanqiao Wang, Bowen Li, Jin-Peng Liu, Zhengfeng Ji

1. 核心物理图象

• 这篇论文研究的核心问题是：如何用量子计算机高效求解四类 Riccati 方程（连续/离散代数 Riccati 方程 CARE/DARE、微分 Riccati 方程 DRE、有限 Riccati 递推 RR）。这些方程在最优控制（LQR）和量子化学（RPA）中反复出现，本质是非线性矩阵方程，经典求解代价随维度立方增长。

• 论文的物理图象可以这样理解：Riccati 方程的解矩阵 (P) 的"图"（graph）——即所有向量对 ([v; Pv]) 构成的子空间——可以被一个谱投影算子（projector）精确刻画。对代数方程，这个投影是某个 Hamiltonian/辛 pencils 的稳定谱分支上的 Riesz 投影；对动态方程，它是随时间演化的图投影。因此，求解 Riccati 方程被转化为构造一个投影算子的块编码（block-encoding），再从投影算子的上下块行中"读出"解矩阵。

• 核心贡献是提出 Quantum Weighted Riesz Method：用"加权 Riesz 算子"统一处理四类 Riccati 问题，构造解图的投影，再通过块行伪逆恢复解。论文给出了近最优的查询复杂度上界，并证明了匹配的下界（含 BQP hardness），说明该算法在谱分离和输出归一化意义下是最优的。

2. 关键术语解释

• Block-encoding（块编码）：一种将矩阵 (T) 编码为某个酉算子的指定子块、乘以已知归一化 (\alpha_T) 的量子表示。本文的最终输出就是解矩阵的块编码，使其可直接参与后续量子计算（如矩阵元素估计读出反馈值）。

• Generalized singularity factor (R)（广义奇异性因子）：衡量沿分离围道移动的移位矩阵 ((zI-H)) 或 ((zL-M)) 离奇异有多近的量，定义如 (R=\sup_z(|z|+\alpha_M)|(zI-M)^{-1}|)。它把"谱分离"这一几何性质转化为算法代价的核心参数；当矩阵非正规时，仅靠特征值距离无法刻画，必须用此因子。

• Decaying graph projector（衰减图投影）：对 DRE 和 RR，初始图在正/反两个谱分支上通常都有分量，前向演化会在某一分支上指数增长。作者通过"在增长分支上用逆向演化、在衰减分支上用正向演化"的加权组合，构造出一个仍然投影到演化后图上的算子 (E(t)=\Pi_+ + e^{{tH}\Pi_-R_0(\Pi_+R_0)}+e^{-tH}\Pi_+)，其所有时间依赖都体现在衰减权重上，从而避免编码指数放大项。这是本文统一处理动态问题的关键技术。

3. 主要贡献 (Key Contributions)

• 统一框架与近最优上界：提出 Quantum Weighted Riesz Method，用同一套"Embed–QET–Recover"三步流程覆盖 CARE、DARE、DRE、RR 四类问题，得到查询复杂度 (\tilde O(R\alpha_X))（代数）和 (\tilde O(R,\kappa(\Pi_{\rm sel}R_0)\alpha_P))（动态），其中 (R) 为广义奇异性因子，(\alpha_X) 为输出归一化，(\kappa) 为初始列条件数。

• 匹配的下界与最优性：构造显式的双输入 oracle 家族，证明对 CARE/DARE 有 (\Omega(R\alpha_X)) 查询下界（与上界在对数因子内匹配），对 DRE/RR 有 (\Omega(R\kappa)) 下界，说明谱分离与初始化条件数在最坏情况下必须乘性进入代价，确立了近最优性。

• BQP 困难性：证明即使只有单个控制输入，以常数归一化和常数精度构造 DARE 与 DRE 解块编码也是 BQP-hard 的，相应的 selected-value 判定问题在显式电路生成家族上是 BQP-complete。这揭示了 LQR 最优值本身可以编码通用量子计算。

• 应用：RPA 与热边界控制：在量子化学 RPA 中，利用"逐节点局部逆范数"替代统一逆范数，把能量读出的查询复杂度从 (\tilde O(u^{-3}/\epsilon_c)) 改进到 (\tilde O(u^{-2}/\epsilon_c))（(u) 为稳定性参数）；在热边界控制中，证明固定物理参数下谱因子、初始化逆、输出归一化均为 (O(1))，总门代价为 (\epsilon_u^{-1}\log(1/\delta),\mathrm{polylog}(n),\mathrm{polylog}(1/\epsilon_u))，并给出数值验证。

4. 研究方法 (Methodology)

• 线性提升（Embed）：将 Riccati 方程的解图表示为线性矩阵问题的谱子空间——CARE 用 Hamiltonian 矩阵的稳定不变子空间，DARE 用辛 pencil (M-zL) 的有限单位圆内 deflating 子空间，DRE 用 Hamiltonian 流 (e^{tH_{\rm DRE}}R_0)，RR 用线性分式提升 (S_F) 的幂次传播。

• 量子特征值变换（QET）：用两种方式构造加权 Riesz 算子：(i) 围道-预解 LCU——将围道积分离散为移位逆的加权和，用 QSVT 伪逆原语逐个编码逆，再用 LCU 相干组合；(ii) Weyl–LCHM——对半平面投影，用多项式选择器 (\frac12(1\pm zq(z^2))) 近似 sign 函数，通过 Hermitian 矩阵线性组合的相干平均实现。动态问题再将两个谱分支的加权 Riesz 块与初始数据组合成衰减图投影。

• 恢复（Recover）：利用图投影的块行恒等式 (P=(E_2^*\Pi)(E_1*\Pi)^+)，用上块行的 Moore–Penrose 伪逆控制读出代价，伪逆范数由解的范数上界控制（(|(E_1^*\Pi)+|\le\sqrt{1+|P|^2})），从而避免额外的方阵可逆假设。

• 下界与困难性：用 Julia 输入酉算子的连续性与"量子查询混合论证"证明乘积下界；用"clock 寄存器 + 受控门序列"将 BQP 电路嵌入单控制 DARE/DRE 实例，使最优值编码接受概率。

5. 实验结果与结论 (Results and Conclusion)

• 关键结论：四类 Riccati 问题的解块编码可在近最优查询复杂度内构造，参数依赖（谱分离 (R)、输出归一化 (\alpha)、初始化条件数 (\kappa)）在最坏情况下是紧的。常数归一化、常数精度的 DARE/DRE 解编码是 BQP-hard 的。在 RPA 与热边界控制应用中，局部逆尺度带来实际复杂度改进，热网络在固定物理参数下总门代价对维度 (n) 仅为 polylog。

• 对领域的意义：这是首个对四类 Riccati 问题给出统一量子算法并同时建立匹配上下界的工作，把"量子线性代数"从线性系统/矩阵函数推广到一类重要的非线性矩阵方程；同时表明量子控制中的值函数提取具有内在的计算困难性，为量子控制算法的复杂度研究提供了基准。

• 开放问题与启示：一般输入下归一化缩减与重编码代价的最优依赖仍未解决；如何高效制备输入块编码（input block-encoding preparation）是实用化的关键；未来方向包括将方法推广到耦合/高阶非线性矩阵方程，以及当线性表示不存在时结合 QLSA 与时间离散化的策略。论文还提到 Dalzell–Su 的斜投影预处理在额外假设下可进一步降低 CARE 的投影归一化，值得后续比较。

6. 论文标签 (Tags)

量子算法, 量子复杂性, 量子信息, 模拟

📄 点击此处展开/折叠原文 PDF

原文链接： Near-Optimal Quantum Algorithm and Complexity Analysis for Riccati Problems