# 量子半定规划：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{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}
$$

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

$$
\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}
$$

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 覆盖

- Zoo 313：Brandão--Svore, [Quantum Speed-ups for Semidefinite Programming](https://arxiv.org/abs/1609.05537).
- Zoo 383、425：[Quantum SDP Solvers: Better Upper and Lower Bounds](https://arxiv.org/abs/1705.01843) 及 quantum-learning 应用。
- Zoo 121、307：Gibbs sampling/hitting-time 子程序。
- Zoo 421：sampling-based low-rank dequantization。