量子半定规划：Matrix Multiplicative Weights、Gibbs Sampling 与输出模型

Semidefinite program（SDP）把线性目标和约束施加在 positive semidefinite matrix 上，统一线性规划、MaxCut relaxation 与许多量子信息问题。量子 solver 用 matrix multiplicative weights 维护 Gibbs-form density matrix，Grover 搜索违反约束，并以量子 trace estimation 提供反馈。在稀疏/状态输入、低 trace bounds 和隐式输出时可加速；一般 dense SDP 仍有接近 \(mn\) 的 lower bound。

1. Primal 与 dual

一种标准 primal 形式：

\[\begin{split} \begin{aligned} \text{maximize}\quad&\operatorname{Tr}(CX)\\ \text{subject to}\quad& \operatorname{Tr}(A_jX)\le b_j,quad j=1,\ldots,m,\\ &X\succeq0,\qquad \operatorname{Tr}X\le R. \end{aligned} \end{split}\]

Dual（符号随约束约定调整）：

\[\begin{split} \begin{aligned} \text{minimize}\quad&b\cdot y+Rz\\ \text{subject to}\quad& \sum_jy_jA_j+zI\succeq C,\\ &y\ge0, z\ge0. \end{aligned} \end{split}\]

Slater 条件等正则性保证 strong duality。算法通常先做 feasibility/binary search：给目标值 \(g\)，判断是否有 \(X\) 满足原约束及 \(\operatorname{Tr}(CX)\ge g\)。

2. Matrix Multiplicative Weights（MMW）

把 \(X/R\) 看作 density matrix \(\rho\)。若当前候选违反约束 \(j_t\)，构造 bounded loss matrix \(M_t\)，更新

\[ W_{t+1}=\exp\!\left(-\eta\sum_{\tau=1}^{t}M_\tau\right), \qquad \rho_{t+1}=\frac{W_{t+1}}{\operatorname{Tr}W_{t+1}}. \]

Noncommutative regret bound 给

\[ \sum_t\operatorname{Tr}(M_t\rho_t) -\min_{\rho}\sum_t\operatorname{Tr}(M_t\rho) \le O(\eta T+\log n/\eta). \]

取 \(T=\widetilde O(1/\epsilon^2)\) 级迭代后，要么所有约束近似满足，要么累计 \(M_t\)/对应 \(y\) 构成 dual infeasibility certificate。

3. 量子子程序在哪里加速

每轮需要两件事。

制备 Gibbs state：

\[ \rho_t\propto e^{-H_t},\qquad H_t=\eta\sum_{\tau<t}M_\tau. \]

若 \(A_j,C\) 稀疏或有 block encoding，可用 Hamiltonian simulation、Gibbs sampling 和 amplitude amplification 制备/近似 \(\rho_t\)。

**找违反约束：**对给定 \(j\)，估计

\[ v_j=\operatorname{Tr}(A_j\rho_t)-b_j/R. \]

Trace estimation 是 bounded expectation；用 amplitude estimation 改善精度。再对 \(m\) 个 \(j\) 做 quantum minimum/maximum finding，以

\[ \widetilde O(\sqrt m) \]

个 constraint checks 找到 \(v_j>\epsilon\) 的约束，而经典要线性扫描 \(m\)。

4. 复杂度参数不能只写 \(\log n\)

代表性上界具有

\[ \widetilde O\!\left( \sqrt m\;\operatorname{poly} (\log n,s,R,r,1/\epsilon) \right) \]

结构，其中：

  • \(s\)：矩阵 sparsity/block-encoding 成本；

  • \(R\)：primal trace/norm bound；

  • \(r\)：dual \(\ell_1\) bound 或相关宽度参数（不同论文记号不同，不应一律称“矩阵 rank”）；

  • \(\epsilon\)：可行性/目标加性误差；

  • state preparation 与 oracle 精度也进入 polylog/多项式项。

在 \(R,r,1/\epsilon\) 小、\(m,n\) 大时，可对 constraint 数和 matrix dimension 有 polynomial speedup。若这些参数随 \(n\) 线性/更大，优势可能消失。

5. 输出什么解

一般 \(X\) 有 \(n^2\) 个经典 entry，任何完整输出需 \(\Omega(n^2)\)。量子 SDP solver 常输出：

  1. 近似 optimum value；

  2. 稀疏 dual vector \(y\)（由被选约束组成）；

  3. 制备 \(X/\operatorname{Tr}X\) 的 quantum state/procedure；

  4. 对 \(X\) 的特定 observable/rounding 所需样本。

若应用要求逐 entry 经典 \(X\)，tomography 会消除指数 dimension 优势。速度声明必须与实际输出匹配。

6. MaxCut SDP 例子

图权 \(w_{ij}\)，令每顶点 unit vector \(v_i\)，放宽 cut signs \(z_i\in\{\pm1\}\)：

\[ \max\frac14\sum_{ij}w_{ij} \|v_i-v_j\|^2. \]

Gram matrix \(X_{ij}=v_i\cdot v_j\) 满足

\[ X\succeq0,\qquad X_{ii}=1. \]

目标

\[ \frac14\sum_{ij}w_{ij}(X_{ii}+X_{jj}-2X_{ij}) \]

线性于 \(X\)。Solver 给近似 Gram state/value 后，还需随机 hyperplane rounding 输出 classical cut；rounding 采样与读出成本是应用的一部分。

7. State-input speedups 与 dequantization

若矩阵不是 sparse oracle，而以 amplitude/sample-query access 提供，可在 \(\operatorname{polylog}n\) 时间估计某些低秩 trace。早期工作据此给 superpolynomial dimension speedup；但 Tang/Chia--Gilyén--Li 等 sampling-based low-rank arithmetic 可在相似数据访问假设下经典模拟许多子程序。

因此需问：

  • 量子 state 是否本来就由物理过程免费产生？

  • 经典算法是否也可采样行/列范数？

  • 输出是否只是 value/low-rank observable？

一般 quantum LP/SDP 还有 worst-case lower bounds：当 \(m\approx n\) 且输入无结构时，复杂度必须近线性于 \(mn\)，不存在普适指数加速。

8. QUBO 与低秩应用

Homogeneous QUBO/Ising 可做 SDP relaxation。若 constraint/solution 有低 rank 与小 width，量子 Gibbs/trace 子程序加速 SDP value，再配经典 rounding；某些工作同时改进 quantum 与 classical approximations。这再次说明“量子 SDP solver”是 pipeline 组件，最终 approximation ratio 应按完整算法证明。

9. 小结与习题

  • MMW 把候选解写成 loss matrices 的 Gibbs state。

  • 量子 Gibbs/trace estimation 和对约束的 Grover 搜索提供参数加速。

  • 复杂度显式依赖 sparsity、trace/dual bounds 和 \(1/\epsilon\)。

  • 完整经典矩阵输出、低秩 dequantization 与 worst-case lower bounds 限制指数优势。

  1. 从 primal 写出对应 dual 并检查 weak duality。

  2. 推导 MMW update 是 Gibbs state。

  3. 为三角形图写 MaxCut SDP 目标。

  4. 比较输出 optimum value 与输出全部 \(X_{ij}\) 的信息量。

参考文献与 Zoo 覆盖