HHL 与线性方程组：量子线性代数与矩阵求逆

几乎所有数值问题都归结为矩阵运算：
  线性方程组 Ax = b    → LU / 迭代法
  特征值问题 Ax = λx   → QR / Lanczos
  最小二乘 min||Ax-b|| → 正规方程 / SVD
  矩阵求逆 A^(-1)      → 分解后回代

代价：O(N^3)（稠密）或 O(N·nnz)（稀疏迭代）
→ N = 10^6 时，经典计算已是「不可承受之重」

经典：把向量 x 完整地写下来（N 个数）→ 至少 O(N) 的代价
量子：把 x 编码成 N 维振幅的量子态 |x⟩
      一次酉操作即可「同时作用」到所有分量
→ 若能「不解出全部分量」而只提取「全局性质」，指数加速可期

输入：N×N 的厄米矩阵 A（可扩展为非厄米）+ 向量 b
目标：求解 A x = b，即 x = A^(-1) b

量子版的目标（关键！）：
  制备量子态 |x⟩ ∝ A^(-1)|b⟩
  使得测量某个算符 M 的期望 ⟨x|M|x⟩ 可被估计
  → 不是「读出 x 的每个分量」，而是「得到 x 的全局性质」

1. A 是稀疏的（每行非零元数 ≤ s，且 s 为常数或对数级）
2. 能高效实现 e^(iAt) 的受控版本（稀疏矩阵的哈密顿量模拟）
3. A 的条件数 κ 不太大（或已知且可控）
4. 能高效制备态 |b⟩（即 b 的振幅编码可行）
5. 只要求「全局性质」，不要求读出完整解向量
→ 五条缺一，指数加速都会打折甚至消失

A 的特征分解：A = Σ λ_j |u_j⟩⟨u_j|
则 A^(-1) = Σ (1/λ_j) |u_j⟩⟨u_j|

把 |b⟩ 在 A 的特征基上展开：|b⟩ = Σ β_j |u_j⟩
则 |x⟩ ∝ A^(-1)|b⟩ = Σ (β_j / λ_j) |u_j⟩

关键洞察：
  求逆 = 「把每个特征分量的振幅除以对应的特征值」
  → 只要能「知道 λ_j」，就能做这个缩放
  → 相位估计正是「把 λ_j 提取到寄存器」的工具

1. 制备 |b⟩ 并附加一个「特征值寄存器」（初态 |0⟩）
2. 受控酉演化 U = e^(iAt)：
   在特征分量 |u_j⟩ 上累积相位 ∝ λ_j t
   经逆 QFT 后，寄存器读出 λ_j 的二进制近似
3. 用「受控旋转」把 1/λ_j 写进辅助比特的振幅
→ 结果：Σ β_j (1/λ_j)|u_j⟩ ⊗ |λ_j⟩，即 |x⟩ 与特征值寄存器的纠缠态

κ = λ_max / λ_min（最大与最小特征值之比）

HHL 的两处依赖：
  1. 相位估计需要分辨 λ_min → 寄存器位数 ∝ log(κ)
  2. 受控旋转需要「成功概率」，而成功概率 ∝ 1/κ^2
→ 整体复杂度 ≈ O(log(N)·s^2·κ^2/ε)
→ κ 的平方级依赖是 HHL 最大的软肋

- 用「变量时间演化」或「最优哈密顿量模拟」降 s 的幂次
- 用「量子奇异值变换」做多项式逼近，把 κ 降到线性
- 用「块编码」替代稀疏模拟假设，扩展可处理矩阵族
→ 现代量子线性代数已把 κ 依赖从 κ^2 降到 κ

线路结构（三个寄存器）：
  R1：辅助比特（用于受控旋转）
  R2：特征值寄存器（n_pe 位）
  R3：工作寄存器（编码 |b⟩ → |x⟩）

步骤：
  1. |0⟩|0⟩|b⟩ —— 制备 b 的振幅编码
  2. 对 R2、R3 做相位估计：e^(iAt) 受控演化 + 逆 QFT
  3. R1 上做受控旋转 R_y(θ)，θ ∝ 1/λ_j
  4. 反相位估计（uncompute），清空 R2
  5. 测量 R1：得到 |1⟩ 时，R3 上即 |x⟩（未归一化）

R_y(θ_j)|0⟩ = cos(θ_j/2)|0⟩ + sin(θ_j/2)|1⟩
取 sin(θ_j/2) ∝ 1/λ_j（在 λ_j 的有效范围内）

于是「成功分支」（R1 = |1⟩）的联合态：
  Σ_j β_j (1/λ_j)|u_j⟩ = |x⟩（未归一化）
→ 归一化常数 ≈ ||A^(-1)b||，其倒数即成功概率

振幅编码 |b⟩ = Σ b_i|i⟩ 需要 O(N) 个振幅
经典数据装入量子态：
  一般情况需要 O(N) 的线路深度（量子随机存取存储器 QRAM 假设）
  → 「指数加速」被输入制备吃掉了！

特例可高效制备：
  均匀叠加、可积函数、低秩结构、由量子过程自然产生
→ 数据来源决定 HHL 是否真的加速

若要求「读出 x 的 N 个分量」：
  需要 O(N) 次测量（层析/采样）
  → 指数加速完全蒸发

若只要求「⟨x|M|x⟩」这类全局性质：
  用 Hadamard 测试 + 多次测量即可估计
  代价 O(1/ε^2)（与 N 无关）
→ HHL 的加速只在「全局量」场景成立

核心思想：
  任何「矩阵函数」f(A) 都可以用「块编码 + 多项式逼近」实现
  A 被编码为酉算符的一个「块」：
    U_A = [[A, ·], [·, ·]]（块编码）
  对 A 的特征值做多项式变换 → 得到 f(A)

统一性：
  HHL、量子模拟、量子搜索、qPCA、振幅放大
  全都是 QSVT 的特例（选择不同的 f）
→ QSVT 是「量子算法的通用编译器」

定义：若存在酉 U 使得 ⟨0|U|0⟩ = A/α（α 为归一化因子）
      则称 U 是 A 的 α-块编码
优点：
  不再要求 A 稀疏，只要求「能块编码」
  覆盖稠密矩阵、线性组合、乘积、张量积
→ 现代量子线性代数的事实标准接口

dequantization（Tang 等，2018 起）：
  若输入是「经典可采样」的低秩矩阵
  经典算法也能达到 poly(log N) 级别的复杂度
→ 许多「量子机器学习加速」其实来自低秩假设，而非量子性
→ 必须逐案检查「加速究竟来自量子，还是来自数据假设」

问题：min_x ||Ax - b||
解法：正规方程 A^†A x = A^†b
量子版：
  构造增广矩阵 → 用 HHL/QSVT 求解
  → 得到 ⟨x|M|x⟩ 形式的全局量

适用：低条件数、稀疏、数据量子可得
不适用：需要完整回归系数的传统统计场景

目标：找出密度矩阵 ρ 的主特征向量
方法：
  用相位估计把 ρ 的特征值提取到寄存器
  通过受控旋转 + 振幅放大「筛选」大特征值分量
→ 与 HHL 共享「相位估计 + 受控旋转」骨架

最小可行实例（原理验证）：
  2×2 或 4×4 的线性系统
  需要：相位估计（多比特寄存器）+ 受控旋转 + 反计算
  线路深度远超 NISQ 设备的相干时间
→ 实验多在「小规模 + 大量误差缓解」下完成

- 核磁共振（NMR）：最早的小规模原理验证
- 光子：用线性光学实现 2×2 系统求解
- 超导：3~4 比特的原理验证 + 误差缓解
- 离子阱：高保真度的少量比特演示
→ 全部停留在「原理验证」而非「实用规模」

变分量子线性求解器（VQLS）：
  用变分线路近似 A|x⟩ ∝ |b⟩
  代价函数 = 残差范数，用 Hadamard 测试估计
  优点：浅线路、NISQ 友好
  缺点：无复杂度保证、易陷入贫瘠高原
→ 从「算法保证」退化为「启发式求解」

正确表述：
  HHL 在「输入量子可得 + 只求全局量 + 稀疏良态」时
  对维度 N 有指数级（对数依赖）的加速
  但 κ 与 1/ε 的多项式依赖完全保留
→ 省略前提的表述是错的

读出完整解向量需要 O(N) 次测量
→ 指数加速蒸发
HHL 输出的是「量子态 |x⟩」而非「经典向量 x」
→ 它更像「量子态的制备器」而非「求解器」

去量子化研究（Tang 等）显示：
  低秩 + 可采样假设下，经典算法也能达到类似复杂度
  许多「量子 ML 加速」的根源是数据假设，不是量子性
→ 端到端量子 ML 优势尚无定论

- QSVT 与块编码把 HHL 推广到更广的矩阵族
- 变分求解器在 NISQ 上的实用化探索
- 量子优势的「去量子化」边界刻画
- 与量子模拟结合：数据天然量子的场景
→ HHL 的价值已从「实用算法」转为「理论范式」