# 量子半定规划：Matrix Multiplicative Weights、Gibbs Sampling 与输出模型 Semidefinite program（SDP，半定规划）把"线性目标 + 线性约束"施加在一个 positive semidefinite（半正定）矩阵变量上。它是线性规划的严格推广：线性规划要求变量向量逐分量非负，SDP 则要求整个矩阵半正定。这一推广足以统一线性规划、组合优化中的 MaxCut relaxation（半定松弛）、以及量子信息中的大量问题（态区分、纠缠度量、信道优化等——量子态本身就是 trace 为 $1$ 的半正定矩阵，因此 SDP 约束天然契合量子力学）。 经典计算机上，SDP 可以用内点法（interior point method）在多项式时间内求解到任意精度，但多项式的次数很高：每次迭代要求解一个规模随约束数增长的线性方程组，对约束数 $m$ 和矩阵维数 $n$ 都很大的实例并不实用。Arora 与 Kale 提出的 multiplicative weights（乘性权重）框架把 SDP 求解转化为一个"在线博弈"：每轮维护一个密度矩阵形式的候选解，根据被违反的约束指数地调整权重，$\widetilde O(1/\epsilon^2)$ 轮后收敛到近似解。这个框架的每一步——制备 Gibbs 态、估计约束期望值、搜索被违反的约束——恰好都是量子算法擅长的事情。 2016 年 Brandão 与 Svore 给出了第一个系统性的量子 SDP solver（Zoo 313），随后 van Apeldoorn、Gilyén、Gribling 与 de Wolf 等人改进了上界并给出几乎匹配的下界（Zoo 383、425）。结论大致是：量子 solver 用 matrix multiplicative weights（MMW）维护 Gibbs-form 的密度矩阵，用 Grover 型搜索寻找违反的约束，并以量子 trace estimation 提供反馈信号；在稀疏/量子态输入、较小的 trace bound、以及隐式输出的前提下可以相对经典算法取得多项式甚至更强的参数加速；但对无结构的一般 dense SDP，复杂度仍有接近 $mn$ 的下界，不存在普适的指数加速。与此同时，Tang 与 Chia–Gilyén–Li 等人的 sampling-based 经典算法（dequantization，Zoo 421）进一步压缩了"量子态输入"场景下的加速空间。 本教程的目标是把这条流水线讲清楚：先给出 primal/dual 形式并亲手验证 weak duality，再从在线学习的角度推导 MMW 更新与 regret bound，然后逐一说明量子子程序在哪里、以什么代价加速，最后讨论一个常被忽略但决定成败的问题——算法到底输出什么。 :::{admonition} 本课知识点 :class: tip 1. **[SDP 的 primal/dual 形式与 weak duality](#sdp-primal-dual)**——能写出标准 primal 与 dual 形式并说明各约束的作用，再用半正定平方根与迹的循环不变性证明 weak duality。 2. **[MMW 更新规则与 Gibbs 态](#mmw-update-gibbs)**——能写出 MMW 的指数更新与归一化，完成 $2\times2$ 对角损失例子的逐轮手算，并用自由能变分原理解释 Gibbs 形式的来源。 3. **[Regret bound 与参数平衡](#mmw-regret-bound)**——能解释 regret bound 中 $\eta T$ 与 $\log n/\eta$ 两项的来源，并推导最优步长 $\eta^\star$ 与迭代轮数 $T=\Theta(\ln n/\epsilon^2)$。 4. **[量子子程序的加速来源](#quantum-speedup-sources)**——能列出 Gibbs 态制备、振幅估计与 Grover 型搜索三处加速，并比较它们与经典做法的复杂度差距。 5. **[复杂度参数与适用边界](#complexity-parameters)**——能解释复杂度结构中 $\sqrt m$、$\log n$、$s$、$R$、$r$、$1/\epsilon$ 各因子的来源，并据此判断量子优势何时消失。 6. **[输出模型与信息论下界](#output-model-lower-bound)**——能比较四种输出形态的信息量与最小成本，并说明输出完整矩阵 $X$ 为何有 $\Omega(n^2)$ 的信息论下界。 7. **[MaxCut 的 SDP 松弛与 rounding](#maxcut-sdp-rounding)**——能把符号向量松弛改写为 Gram 矩阵形式的 SDP，完成三角形例子的数值计算，并推导随机超平面 rounding 的割边概率 $\theta/\pi$。 8. **[Dequantization 与端到端评估](#dequantization-end-to-end)**——能解释 dequantization 压缩哪类加速，并按"求解 SDP + 经典 rounding + 读出"的完整链条评估 QUBO 类应用的端到端保证。 ::: ## 预备知识与记号 - 矩阵 $C, A_1,\ldots,A_m$ 均为 $n\times n$ Hermitian 矩阵，$b_1,\ldots,b_m\in\mathbb R$。$X\succeq0$ 表示 $X$ 半正定，即 $X$ Hermitian 且所有特征值非负，等价于对一切向量 $\langle\psi|X|\psi\rangle\ge0$。 - $\operatorname{Tr}$ 是矩阵的迹。密度矩阵 $\rho$ 是满足 $\rho\succeq0$、$\operatorname{Tr}\rho=1$ 的矩阵，即归一化的半正定矩阵——这正是把 SDP 与量子力学对接的桥梁。 - 对 Hermitian 矩阵 $H$，矩阵指数 $e^{-H}$ 由谱分解定义：若 $H=\sum_i\lambda_i|u_i\rangle\langle u_i|$，则 $e^{-H}=\sum_ie^{-\lambda_i}|u_i\rangle\langle u_i|$。**Gibbs 态** $\rho\propto e^{-H}$ 在[第 6 章](../ch06-scientific-computing/gibbs-state.md)有专门讨论。 - 我们默认读者熟悉 [Grover 搜索与振幅放大](../ch03-algo-basics/grover.md)、[相位估计](../ch03-algo-basics/phase-estimation.md)（振幅估计是其直接推论），以及 [block encoding 与 Hamiltonian simulation](../ch05-hamiltonian-qsp/block-encoding-tutorial.md)；这些子程序在本篇只作为黑箱调用。 - $\widetilde O(\cdot)$ 隐藏对数因子，即 $\widetilde O(f)=O(f\cdot\operatorname{polylog}(f))$。 (sdp-primal-dual)= ## 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} $$ 逐个符号说明：$X$ 是优化变量（$n\times n$ 半正定矩阵）；$\operatorname{Tr}(CX)$ 是线性目标函数（对固定的 $C$，它是 $X$ 各元素的线性组合）；$\operatorname{Tr}(A_jX)\le b_j$ 是第 $j$ 个线性约束，共 $m$ 个。约束 $\operatorname{Tr}X\le R$ 是一个"归一化预算"：它把可行域的尺度固定下来，使得我们可以把 $\rho=X/R$ 当作密度矩阵处理——这一步是后面整个量子算法的关键，请留意它的来历。 对应的 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} $$ 这里 $y\in\mathbb R^m$、$z\in\mathbb R$ 是对偶变量，约束 $\sum_jy_jA_j+zI\succeq C$ 是一个半正定约束（等价于 $\sum_jy_jA_j+zI-C\succeq0$）。对偶变量的数目是 $m+1$ 个标量，而不是 $n\times n$ 矩阵——这就是为什么后文说"输出稀疏的 dual vector $y$"比输出整个 $X$ 便宜得多。 在引用 strong duality 之前，我们先把 weak duality 亲手推导一遍，因为它的每一步后面都会反复用到。 **Lemma 1**. 若 $M\succeq0$ 且 $X\succeq0$，则 $\operatorname{Tr}(MX)\ge0$。 **证明**。半正定矩阵有唯一的半正定平方根 $M^{1/2}$。利用迹的循环不变性 $\operatorname{Tr}(PQ)=\operatorname{Tr}(QP)$， $$ \operatorname{Tr}(MX)=\operatorname{Tr}(M^{1/2}M^{1/2}X)=\operatorname{Tr}(M^{1/2}XM^{1/2}). $$ 对任意 $|\psi\rangle$，$\langle\psi|M^{1/2}XM^{1/2}|\psi\rangle=\langle\phi|X|\phi\rangle\ge0$（令 $|\phi\rangle=M^{1/2}|\psi\rangle$，再用 $X\succeq0$），所以 $M^{1/2}XM^{1/2}\succeq0$，其迹（特征值之和）非负。Q.E.D. **Theorem 2（weak duality）**. 对任意 primal 可行的 $X$ 与 dual 可行的 $(y,z)$， $$ \operatorname{Tr}(CX)\ \le\ b\cdot y+Rz. $$ 即 primal 目标值永远不超过 dual 目标值。 **证明**。令 $M=\sum_jy_jA_j+zI-C$。dual 可行性恰好是说 $M\succeq0$，于是由 Lemma 1 与 $\operatorname{Tr}(MX)\ge0$ 展开： $$ \operatorname{Tr}(CX)\le\operatorname{Tr}(CX)+\operatorname{Tr}(MX) =\operatorname{Tr}\!\left(\Big(\sum_jy_jA_j+zI\Big)X\right) =\sum_jy_j\operatorname{Tr}(A_jX)+z\operatorname{Tr}X, $$ 其中第二个等号把 $M$ 的定义代回并合并同类项，第三个等号用迹的线性性。接着逐顶放松：因为 $y_j\ge0$ 且 $\operatorname{Tr}(A_jX)\le b_j$，有 $y_j\operatorname{Tr}(A_jX)\le y_jb_j$；因为 $z\ge0$ 且 $\operatorname{Tr}X\le R$，有 $z\operatorname{Tr}X\le zR$。代入即得 $$ \operatorname{Tr}(CX)\le\sum_jy_jb_j+zR=b\cdot y+Rz. $$ Q.E.D. 这个证明透露了一个重要信息：primal 约束被违反的程度 $\operatorname{Tr}(A_jX)-b_j$ 与对偶变量 $y_j$ 是"配对"出现的。后面 MMW 算法找不到可行解时，正是把累计的被违反约束组合成一个 dual 解来给出 infeasibility certificate（不可行证书）。 在适当的正则性条件下，不等式可以取等。**Slater 条件**（存在严格可行的内点，即存在 $X\succ0$ 使所有不等式严格成立）保证 strong duality：primal 与 dual 的最优值相等。因此求解 SDP 等价于在 primal 与 dual 之间"夹逼"。 实践中还有一个标准简化：**化优化为可行性判定**。给定目标值候选 $g$，把 $\operatorname{Tr}(CX)\ge g$ 当作第 $m+1$ 个约束，问题变成"是否存在满足全部约束的 $X$"。若能以加性误差 $\epsilon$ 回答每个可行性问题，就对 $g$ 做二分搜索，$O(\log(1/\epsilon))$ 轮后即可把最优值定到误差 $\epsilon$ 以内。因此下文只需讨论可行性版本：判断是否存在 $X\succeq0$、$\operatorname{Tr}X\le R$ 使 $\operatorname{Tr}(A_jX)\le b_j$ 对所有 $j$ 成立。 ## 2. Matrix Multiplicative Weights（MMW） ### 2.1 在线博弈的直觉 MMW 来自在线学习中的"专家意见"问题。设想一个 $T$ 轮的博弈：每轮你必须下注一个密度矩阵 $\rho_t$（可以看作在 $n$ 个"纯态专家"上的概率分布），然后环境公布一个有界的 **loss matrix** $M_t$（满足 $\|M_t\|\le1$，算子范数有界保证单次损失不会爆炸），你承受损失 $\operatorname{Tr}(M_t\rho_t)$。你的目标是让累计损失接近"事后诸葛亮"的最优固定策略 $\min_\rho\sum_t\operatorname{Tr}(M_t\rho)$，二者之差称为 **regret（后悔值）**。 它与 SDP 的联系是：如果当前候选 $\rho_t=X/R$ 严重违反第 $j$ 个约束，即 $\operatorname{Tr}(A_j\rho_t)>b_j/R+\epsilon$，我们就把与该约束关联的矩阵（例如归一化后的 $A_j$，或带符号的 $A_j-\frac{b_j}{R}I$）作为 loss matrix 喂给算法。直觉是：在 $\operatorname{Tr}(A_j\rho)$ 大的方向上"惩罚"$\rho$，下一轮指数更新就会压低这些方向上的权重，把概率质量推向满足约束的方向。于是每轮只有两种结局：要么所有约束都近似满足（找到近似可行解，算法成功停止），要么找到一个被违反的约束并继续迭代。下面会看到，迭代次数有界，因此"永远找不到可行解"本身就会导出 dual 不可行证书。 (mmw-update-gibbs)= ### 2.2 更新规则与 Gibbs 态 MMW 的更新规则是：维护累计 loss 的矩阵指数，并归一化为密度矩阵： $$ 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}}. $$ 这里 $\eta>0$ 是学习率（步长），$W_{t+1}$ 称为权重矩阵。两点说明： - 为什么叫"multiplicative"（乘性）？在经典情形（所有 $M_\tau$ 都是对角矩阵，即普通的专家算法），权重向量逐分量做乘法更新 $w_i\leftarrow w_i e^{-\eta (M_t)_{ii}}$。矩阵版本把逐分量乘法推广为矩阵指数。注意我们**直接以累计和定义** $W_{t+1}=\exp(-\eta\sum_\tau M_\tau)$，而不写成 $\exp(-\eta M_t)W_t$ 的递推：一般 $M_t$ 与之前的累计和不对易，$e^{A+B}\ne e^Ae^B$，因此这两种写法在矩阵情形下并不等价。分析时一律以"累计和的指数"为准。 - 为什么是密度矩阵？$W_{t+1}$ 是半正定矩阵的指数，故 $W_{t+1}\succ0$；除以迹后 $\rho_{t+1}\succeq0$ 且 $\operatorname{Tr}\rho_{t+1}=1$。所以每一轮的候选解自动落回可行域的归一化部分，剩下的只是检查约束。 **一个可以手算的最小例子。** 取 $n=2$，初始 $\rho_1=I/2$（最大混合态），第一轮公布的 loss matrix 为对角矩阵 $$ M_1=\begin{pmatrix}1&0\\0&-1\end{pmatrix}. $$ 第一轮损失 $\operatorname{Tr}(M_1\rho_1)=\frac12(1)+\frac12(-1)=0$——均匀下注时高低损失恰好抵消。更新权重矩阵（对角矩阵的指数即逐对角元取指数）： $$ W_2=e^{-\eta M_1}=\begin{pmatrix}e^{-\eta}&0\\0&e^{\eta}\end{pmatrix}, \qquad \rho_2=\frac{W_2}{\operatorname{Tr}W_2} =\frac{1}{2\cosh\eta}\begin{pmatrix}e^{-\eta}&0\\0&e^{\eta}\end{pmatrix}. $$ 第二轮若再次面对 $M_1$，损失变为 $$ \operatorname{Tr}(M_1\rho_2)=\frac{e^{-\eta}-e^{\eta}}{2\cosh\eta}=-\tanh\eta. $$ 损失从 $0$ 降到 $-\tanh\eta<0$：权重被指数地从"高损失"的第一个基矢转移到"低损失"的第二个基矢，且转移速率由 $\eta$ 控制——$\eta\to0$ 时几乎不动，$\eta$ 大时几乎把全部权重压到最优方向上。这正是 MMW 名称中"乘性"的含义：每一轮把各方向的权重乘以 $e^{-\eta\times\text{损失}}$。 这个 $\rho_{t+1}$ 正是以 $H_t=\eta\sum_{\tau=1}^t M_\tau$ 为 Hamiltonian 的 Gibbs 态。Gibbs 态有一个变分刻画，它解释了"为什么指数形式是对的"： **Lemma 3（自由能变分原理）**. 固定 Hermitian 矩阵 $H$，在所有密度矩阵中， $$ \rho^\star=\frac{e^{-H}}{\operatorname{Tr}e^{-H}} $$ 唯一最小化自由能泛函 $F(\rho)=\operatorname{Tr}(H\rho)-S(\rho)$，其中 $S(\rho)=-\operatorname{Tr}(\rho\ln\rho)$ 是 von Neumann 熵；且最小值为 $-\ln\operatorname{Tr}e^{-H}$。 **证明**。记 $Z=\operatorname{Tr}e^{-H}$、$\sigma=e^{-H}/Z$。相对熵 $D(\rho\|\sigma)=\operatorname{Tr}(\rho\ln\rho)-\operatorname{Tr}(\rho\ln\sigma)$ 对任意两个密度矩阵非负（Klein 不等式），且等号成立当且仅当 $\rho=\sigma$。展开 $\ln\sigma=-H-\ln Z\cdot I$： $$ D(\rho\|\sigma) =-S(\rho)-\operatorname{Tr}\big(\rho(-H-\ln Z\,I)\big) =-S(\rho)+\operatorname{Tr}(H\rho)+\ln Z =F(\rho)+\ln Z\ \ge\ 0. $$ （第二步用 $\operatorname{Tr}\rho=1$ 把 $\operatorname{Tr}(\rho\ln Z\,I)$ 化为 $\ln Z$。）于是 $F(\rho)\ge-\ln Z$，等号当且仅当 $\rho=\sigma$。Q.E.D. 这条引理给出 MMW 的热力学图像：每一轮的 $\rho_{t+1}$ 是"尽量压低累计损失 $\operatorname{Tr}(H_t\rho)$"与"尽量保持熵（不把所有权重押在单一方向上）"之间的最优折中，$\eta$ 控制两者的相对权重。$\eta$ 越大越激进（快速惩罚坏方向，但容易被噪声带偏），越小越保守。 (mmw-regret-bound)= ### 2.3 Regret bound 与参数平衡 矩阵版本的乘性权重定理给出如下 noncommutative regret bound： $$ \sum_t\operatorname{Tr}(M_t\rho_t) -\min_{\rho}\sum_t\operatorname{Tr}(M_t\rho) \ \le\ O\!\left(\eta T+\frac{\log n}{\eta}\right). $$ 我们不证这个定理，但解释右端两项各自的来源，因为参数平衡全靠这个结构： - **$\log n/\eta$ 项**：初始时刻 $\rho_1=I/n$（最大混合态，对所有方向一视同仁）。用相对熵作为"距离"度量，任何最优策略 $\rho^\star$ 到 $\rho_1$ 的初始距离满足 $D(\rho^\star\|\rho_1)=\ln n-S(\rho^\star)\le\ln n$。这是"起点的信息量"除以步长 $\eta$：$\eta$ 越小，把这段初始差距走完所需的代价越大。维数 $n$ 只以 $\log n$ 出现——这是整个方法对维数温和依赖的根源，也是量子版本能对 $n$ 取得指数级改善的前提。 - **$\eta T$ 项**：每一轮用指数更新近似真实损失时产生 $O(\eta)$ 量级的二阶误差（来自 $\|M_t\|\le1$ 时 $e^{-\eta M_t}$ 的 Taylor 展开中 $\eta^2$ 以上的项），$T$ 轮累积为 $O(\eta T)$。$\eta$ 越大这项越大。 两项对 $\eta$ 的依赖方向相反，存在最优折中。把 $f(\eta)=\eta T+\frac{\ln n}{\eta}$ 对 $\eta$ 求导：$f'(\eta)=T-\frac{\ln n}{\eta^2}=0$，解得 $$ \eta^\star=\sqrt{\frac{\ln n}{T}}, \qquad f(\eta^\star)=2\sqrt{T\ln n}. $$ 于是 regret 至多为 $O(\sqrt{T\ln n})$，**平均每轮**的 regret 为 $$ \frac{1}{T}\cdot O\!\left(\sqrt{T\ln n}\right)=O\!\left(\sqrt{\frac{\ln n}{T}}\right). $$ 要让平均 regret 降到 $\epsilon$ 以下，令 $\sqrt{\ln n/T}\lesssim\epsilon$，解出 $$ T=\Theta\!\left(\frac{\ln n}{\epsilon^2}\right)=\widetilde O\!\left(\frac{1}{\epsilon^2}\right). $$ 这就是"$\widetilde O(1/\epsilon^2)$ 级迭代"的完整来历：$\epsilon^{-2}$ 来自均摊后的 $\sqrt{\cdot}$，对数因子来自初始相对熵。 $T$ 轮之后的收尾逻辑是：若某一轮所有约束都满足到 $\epsilon$ 以内，输出当前的 $\rho_t$（乘以 $R$ 即近似可行解）；否则，把各轮的 loss matrix 加权平均，zero-sum 博弈的 von Neumann 极小极大定理（等价地，LP/SDP 对偶）保证这个平均值给出 dual 变量 $y$，使得 dual 目标小于 primal 约束所允许的值，从而构成 dual infeasibility certificate——即证明原问题本身不可行。所以算法不会在两种结局之间悬置。 (quantum-speedup-sources)= ## 3. 量子子程序在哪里加速 每一轮迭代需要做两件繁重的事，经典实现里它们各自正比于矩阵规模或约束数；量子算法分别用 Gibbs sampling 与 Grover 型搜索加速。 **第一件事：制备 Gibbs state。** $$ \rho_t\propto e^{-H_t},\qquad H_t=\eta\sum_{\tau\epsilon$ 的 $j$。这里有两个层次的加速。 第一层是**单个 $v_j$ 的估计**。$\operatorname{Tr}(A_j\rho_t)$ 是在状态 $\rho_t$ 上测量可观测量 $A_j$ 的期望值，是一个 bounded expectation（$\|A_j\|$ 有界）。经典做法是重复制备 $\rho_t$、测量、取样本均值：由 Hoeffding 型集中不等式，加性误差 $\epsilon$ 需要 $O(1/\epsilon^2)$ 个样本。量子做法是 amplitude estimation（[相位估计](../ch03-algo-basics/phase-estimation.md)的直接应用）：把期望值编码为某个标志比特的振幅，用相位估计读出，达到同样精度只需 $\widetilde O(1/\epsilon)$ 次制备——这是振幅放大类技术标志性的二次加速（参见 [Grover 与振幅放大](../ch03-algo-basics/grover.md)）。 第二层是**对 $j$ 的搜索**。给定能对固定 $j$ 判定"$v_j>\epsilon$ 与否"的子程序后，要在 $m$ 个约束里找出一个被违反者，经典方法只能线性扫描，最坏 $m$ 次检查；量子方法用 quantum minimum/maximum finding（Dürr–Høyer，Grover 搜索的变体），只需 $$ \widetilde O(\sqrt m) $$ 个 constraint checks。这个 $\sqrt m$ 因子与 Grover 的 $\sqrt N$ 同源：无结构搜索的二次量子加速。 把两层乘起来再乘上迭代轮数 $T=\widetilde O(1/\epsilon^2)$，就得到下节的总体复杂度结构。 (complexity-parameters)= ## 4. 复杂度参数不能只写 $\log n$ 一个常见的误读是宣称"量子 SDP solver 的复杂度是 $\operatorname{polylog}n$"。这是错的。代表性上界具有 $$ \widetilde O\!\left( \sqrt m\;\operatorname{poly} (\log n,s,R,r,1/\epsilon) \right) $$ 的结构，其中每个因子都有明确的物理/算法来源： - $\sqrt m$：上节第二层，对被违反约束的 Grover 型搜索；经典对应物是 $m$。 - $\log n$：Gibbs 态制备的寄存器大小，以及 MMW regret 中的初始相对熵；矩阵维数只以 $\log n$ 进入，这是量子加速的核心来源。 - $s$：矩阵的 sparsity（每行非零元个数）或等价的 block-encoding 成本；Hamiltonian simulation 的复杂度随 $s$ 多项式增长。稠密且无结构的输入会让这项变大。 - $R$：primal 的 trace/norm bound。它度量可行域的尺度，约束违反量 $v_j$ 的归一化、loss matrix 的算子范数界都依赖它。 - $r$：dual 的 $\ell_1$ bound 或相关的宽度（width）参数——直觉上它度量"对偶证据的大小"，即把约束组合成有效 dual certificate 所需的系数总量。**注意：不同论文对此参数的记号不同，它不应被一律称为"矩阵 rank"**；把它误读成 rank 会严重低估实际问题中该项的大小。 - $1/\epsilon$：可行性/目标的加性误差。它出现在至少三处并相乘：迭代轮数 $T=\widetilde O(1/\epsilon^2)$、每轮的 trace estimation 精度 $\widetilde O(1/\epsilon)$、以及二分搜索的 $O(\log(1/\epsilon))$。 - 此外，state preparation 与 oracle 精度也以 polylog 或多项式项进入总量。 由此可以得到一个清晰的判断准则：在 $R,r,1/\epsilon$ 较小（与 $n$ 无关或至多对数增长）、$m,n$ 很大时，量子 solver 相对经典方法可以对约束数与矩阵维数取得 polynomial speedup（对 $n$ 甚至是指数级的表达压缩）；反之，若 $R$ 或 $r$ 随 $n$ 线性或更快增长，poly 因子会吃掉 $\sqrt m$ 与 $\log n$ 带来的全部收益，优势可能完全消失。读任何"量子 SDP 加速"的声明时，第一件事就是把 $R,r,s,\epsilon$ 的依赖找出来。 (output-model-lower-bound)= ## 5. 输出什么解 还有一层更微妙的限制，与速度无关，而与"解的形态"有关。一般的 $X$ 有 $n^2$ 个经典矩阵元，仅把它们逐一写出就需要 $\Omega(n^2)$ 次操作——这对任何算法（量子或经典）都是信息论下界，无法绕开。因此声称"对 $n$ 指数加速"的量子 SDP solver，输出的绝不可能是完整的经典矩阵 $X$。实际文献中的输出通常是以下之一： 1. **近似 optimum value**：一个标量，即最优目标值的 $\epsilon$ 近似。信息量最小，成本也最小；许多应用（如估计 MaxCut 的上界）只需要这个。 2. **稀疏 dual vector $y$**：dual 解由 $m+1$ 个标量组成，且 MMW 给出的 $y$ 只由实际被选中的约束支撑，往往很稀疏。它是 primal 最优值的证书。 3. **制备 $X/\operatorname{Tr}X$ 的 quantum state/procedure**：输出一个量子线路，运行它就制备出（近似）最优解对应的密度矩阵。这是"隐式输出"：解以量子态的形式存在，后续可直接作为其他量子子程序的输入。 4. **对 $X$ 的特定 observable/rounding 所需样本**：例如只需要 $\operatorname{Tr}(FX)$ 的若干估计值，或下游随机取整所需的测量样本。 若应用真的要求逐矩阵元的经典 $X$，则必须对输出的量子态做 tomography（态层析），其成本随维数多项式甚至更强地增长，会立即消除维度上的指数优势。**任何速度声明都必须与实际输出模型匹配**：说"求解 SDP 有指数加速"而默认输出是经典矩阵，是这类文献中最常见的夸大方式。 (maxcut-sdp-rounding)= ## 6. MaxCut SDP 例子 我们用 MaxCut 把上面的抽象框架落到地上，并完整算一个小例子。 ### 6.1 从符号向量到 Gram 矩阵 给定带非负权 $w_{ij}$ 的图，MaxCut 要求给每个顶点 $i$ 分配符号 $z_i\in\{\pm1\}$，使被割开的边的权重之和最大。一条边 $(i,j)$ 被割开当且仅当 $z_i\ne z_j$；由于 $(z_i-z_j)^2$ 在两端同号时为 $0$、异号时为 $4$，指示函数可以写成 $\frac14(z_i-z_j)^2$。于是 $$ \text{MaxCut}=\max_{z\in\{\pm1\}^n}\ \frac14\sum_{ij}w_{ij}(z_i-z_j)^2. $$ 目标关于 $z$ 是二次的，可行域是离散的——这是 NP-hard 的组合问题。Goemans–Williamson 的松弛想法是：把标量符号 $z_i$ 升级为高维单位向量 $v_i$（$\|v_i\|=1$），把乘积 $z_iz_j$ 换成内积 $v_i\cdot v_j$： $$ \max\ \frac14\sum_{ij}w_{ij}\|v_i-v_j\|^2. $$ 这是一次放松：任何符号赋值都是一维的单位向量，所以松弛后的最优值不小于真正的 MaxCut。 它为什么是 SDP？定义 **Gram matrix** $X_{ij}=v_i\cdot v_j$。展开范数： $$ \|v_i-v_j\|^2=\|v_i\|^2+\|v_j\|^2-2\,v_i\cdot v_j=X_{ii}+X_{jj}-2X_{ij}, $$ 代回目标得 $$ \frac14\sum_{ij}w_{ij}(X_{ii}+X_{jj}-2X_{ij}), $$ 这是 $X$ 的各矩阵元的线性组合，即 $\operatorname{Tr}(CX)$ 的形式。而"存在一组单位向量使其 Gram 矩阵为 $X$"恰好等价于 $$ X\succeq0,\qquad X_{ii}=1\ \ (\forall i): $$ Gram 矩阵必半正定（对任意 $c$，$c^TXc=\|\sum_ic_iv_i\|^2\ge0$），反之任何半正定矩阵都有 Cholesky 型分解 $X=V^TV$，其列向量即所求向量；对角线约束 $X_{ii}=1$ 就是单位长度约束。于是向量优化问题被精确改写为标准形式的 SDP——目标线性、约束线性、变量半正定。 ### 6.2 三角形上的完整计算 取三角形（3 个顶点、3 条边、权重全为 1）。真实 MaxCut 为 $2$：任取两个顶点放一侧、一个放另一侧，恰有 2 条边被割，而 3 条边不可能同时被割（沿三角形走一圈要奇数次换侧，矛盾）。 现在解它的 SDP 松弛。猜测最优向量取为平面内互成 $120^\circ$ 的三个单位向量，则任意 $i\ne j$ 有 $v_i\cdot v_j=\cos120^\circ=-\tfrac12$，对应的 Gram 矩阵为 $$ X=\begin{pmatrix}1&-\tfrac12&-\tfrac12\\[2pt]-\tfrac12&1&-\tfrac12\\[2pt]-\tfrac12&-\tfrac12&1\end{pmatrix}=\frac32I-\frac12J, $$ 其中 $J$ 是全 1 矩阵。先验证可行性：$J$ 的特征值是 $3,0,0$（特征向量 $(1,1,1)$ 给出 $3$，与其正交的子空间给出二重 $0$），所以 $X$ 的特征值是 $$ \frac32-\frac12\cdot3=0,\qquad \frac32-\frac12\cdot0=\frac32\ (\text{二重}), $$ 全部非负，$X\succeq0$；对角元显然为 $1$。再算目标：每条边贡献 $\frac14(X_{ii}+X_{jj}-2X_{ij})=\frac14(1+1+1)=\frac34$，三条边共 $$ 3\times\frac34=\frac94=2.25. $$ 于是 SDP 值 $9/4$ 落在真实 MaxCut 值 $2$ 与 $3$ 之间：它确为上界（$9/4\ge2$），但严格大于整数最优（$9/4>2$）——这个缝隙就是"松弛 gap"，也是为什么 SDP 之后还必须做 rounding（取整）。补充一句：可以证明 $9/4$ 确为松弛的最优值（由问题的置换对称性，最优 $X$ 可取为上述"对角 $1$、非对角全相等"的形式，再对非对角元做单变量优化即得），比值 $2/(9/4)=8/9\approx0.889$。 ### 6.3 Rounding：从向量回到割 SDP 解出的是向量（或 Gram 矩阵/量子态），不是 $\pm1$ 赋值。Goemans–Williamson 的取整方法是**随机超平面（random hyperplane）**：随机取一个单位向量 $r$，令 $z_i=\operatorname{sign}(v_i\cdot r)$，即以过原点、法向为 $r$ 的超平面把顶点分成两侧。 单边分析只需要二维几何：两个单位向量 $v_i,v_j$ 张成一个平面，$r$ 在该平面的投影方向均匀随机；$z_i\ne z_j$ 当且仅当投影落在"分隔两个向量"的扇区内，该扇区总角度为 $2\theta_{ij}$（$\theta_{ij}$ 是两向量夹角），故 $$ \Pr[z_i\ne z_j]=\frac{2\theta_{ij}}{2\pi}=\frac{\theta_{ij}}{\pi}, \qquad \cos\theta_{ij}=X_{ij}. $$ 割的期望权重因此是 $\sum w_{ij}\theta_{ij}/\pi$。与 SDP 目标 $\frac12\sum w_{ij}(1-\cos\theta_{ij})$ 逐项比较（注意 $\frac14\|v_i-v_j\|^2=\frac12(1-\cos\theta_{ij})$），比值由函数 $\frac{\theta/\pi}{(1-\cos\theta)/2}$ 在 $\theta\in[0,\pi]$ 上的最小值决定，该最小值约为 $0.878$。这就是著名的 Goemans–Williamson 保证：随机取整的期望割权重至少是 SDP 值的 $0.878$ 倍，进而至少是 MaxCut 真值的 $0.878$ 倍。 对量子 solver 的意义在于：量子算法负责快速求出 SDP 的近似值或近似 Gram 态，**rounding 及其采样、读出成本是完整应用的一部分**，必须计入端到端的账。若最终需要的只是一个经典割（$n$ 个比特），那么输出模型就是上节的第 4 类——为 rounding 提供样本，而不是输出整个 $X$。 (dequantization-end-to-end)= ## 7. State-input speedups 与 dequantization 还有一类输入模型值得单独讨论：矩阵不是通过稀疏 oracle 给出，而是以 amplitude access（量子态振幅编码）或 sample-and-query access 提供。此时某些低秩矩阵的 trace 类量可以在 $\operatorname{polylog}n$ 时间内估计，早期工作（如基于量子主成分分析的思路）据此宣称对维数有 superpolynomial 的加速。 但这类声明需要打折扣。Tang（Zoo 421）以及 Chia–Gilyén–Li 等人的工作表明：在相似的数据访问假设下（能对行/列按范数采样并查询矩阵元），经典算法可以用 sampling-based 低秩算术模拟许多这样的量子子程序，把"指数加速"压缩为多项式加速。这种现象被称为 **dequantization（去量子化）**。 因此评估一个 state-input 量子 SDP/线性代数加速时，应当追问三个问题： - **量子态是否本来就由物理过程免费产生？** 如果输入态来自真实的量子实验或前级量子线路，制备成本不计，dequantization 无从谈起；如果输入态本身要花 $O(n)$ 以上成本从经典数据制备，账就要重算。 - **经典算法是否也可采样行/列范数？** 若数据存储方式天然支持这种采样（如按范数组织的索引），经典的 sample-and-query 假设就成立，量子优势随之缩水。 - **输出是否只是 value 或低秩 observable？** 输出越小（标量、少量期望值），经典采样越容易模仿；输出越大（完整量子态、逐元矩阵），量子表示的优势越实在。 与输入模型无关，一般 quantum LP/SDP 还存在 worst-case 下界（Zoo 383、425 一并给出）：当 $m\approx n$ 且输入没有稀疏/低秩等结构时，任何量子算法的复杂度必须接近线性于 $mn$。直观地说，无结构输入的每个约束都可能藏着关键信息，$\sqrt m$ 的 Grover 加速已经是极限，不存在普适的指数加速。这与 Grover 搜索的最优性是同一种逻辑。 ## 8. QUBO 与低秩应用 Homogeneous QUBO（无约束二次 0-1 规划）与 Ising 模型可以按与 MaxCut 完全相同的方式做 SDP 松弛：把二元变量写成 $z_i\in\{\pm1\}$，二次目标写成 $z^TWz=\operatorname{Tr}(WX)$（$X_{ij}=z_iz_j$），再把"$X$ 是秩 1 符号矩阵"放松为 $X\succeq0$、$X_{ii}=1$。 这类问题在量子 solver 语境下有一个有利特点：若约束与解具有低秩结构与较小的宽度参数（上文的 $r$），Gibbs 态制备与 trace estimation 子程序对 SDP value 的估计确有实质加速；之后再接经典 rounding 得到 0-1 解。值得注意的是，这一思路的竞争压力是双向的：同一批工作中有些同时改进了 quantum 与 classical 的近似算法，dequantization 的教训始终适用。 这再次说明一个方法论要点："量子 SDP solver"从来不是完整的应用算法，而是 pipeline 中的一个组件。端到端的 approximation ratio 必须按"量子求解 SDP + 经典 rounding + 读出成本"的完整链条来证明，单独引用 solver 的复杂度数字没有意义。 ## 9. 本课小结 - MMW 把候选解写成累计 loss matrices 的 Gibbs state；$\widetilde O(1/\epsilon^2)$ 轮迭代后，要么得到近似可行解，要么得到 dual 不可行证书。regret bound 的 $\sqrt{\ln n}$ 结构是维数温和依赖的根源。 - 量子加速来自三处：Gibbs 态制备（对 $n$ 仅 $\log n$ 依赖）、trace estimation 的振幅估计（$1/\epsilon^2\to1/\epsilon$）、对约束的 Grover 搜索（$m\to\sqrt m$）。 - 复杂度显式依赖 sparsity $s$、primal trace bound $R$、dual 宽度 $r$ 与 $1/\epsilon$；这些参数随 $n$ 增长时优势消失。$r$ 是 dual $\ell_1$/宽度参数，不是矩阵 rank。 - 输出模型决定加速是否真实：完整经典矩阵输出有 $\Omega(n^2)$ 下界；tomography 会消除维度优势。 - State-input 场景受 dequantization 制约；无结构 dense SDP 有接近 $mn$ 的量子下界。 - SDP solver 是 pipeline 组件，最终近似保证必须按含 rounding 与读出的完整算法计算。 ## 练习题 **练习 1【SDP 的 primal/dual 形式与 weak duality】**（→ [第 1 节](#sdp-primal-dual)） 1. 基础：写出本课采用的 primal 形式，说明约束 $\operatorname{Tr}X\le R$ 为什么使 $\rho=X/R$ 可以当作密度矩阵处理，并指出 dual 变量共由多少个标量组成。 2. 进阶：从第 1 节的 primal 出发，用 Lagrange 乘子 $y_j\ge0$、$z\ge0$ 逐一对应约束，重新推导 dual 形式，并指出推导中哪一步对应 weak duality 证明里 $\operatorname{Tr}(MX)\ge0$ 的使用。 > 提示：把含 $X$ 的项整理成 $\operatorname{Tr}\big((\sum_jy_jA_j+zI-C)X\big)$，要求它对一切 $X\succeq0$ 不产生正贡献，即得半正定约束。 **练习 2【MMW 更新规则与 Gibbs 态】**（→ [2.2 节](#mmw-update-gibbs)） 1. 基础：取 $\eta=1$、$\rho_1=I/2$、$M_1=\begin{pmatrix}1&0\\0&-1\end{pmatrix}$，手算 $\rho_2$ 的两个对角元与第二轮损失 $\operatorname{Tr}(M_1\rho_2)$ 的数值。 2. 进阶：用自由能变分原理（Lemma 3）推导：MMW 更新给出的 $\rho_{t+1}$ 恰是 Hamiltonian $H_t=\eta\sum_{\tau\le t}M_\tau$ 的 Gibbs 态，并解释 $\eta$ 在"惩罚损失"与"保持熵"之间的作用。 > 提示：把 $H=H_t$ 代入 $F(\rho)=\operatorname{Tr}(H\rho)-S(\rho)$，其唯一最小点就是 $e^{-H_t}/\operatorname{Tr}e^{-H_t}$。 **练习 3【Regret bound 与参数平衡】**（→ [2.3 节](#mmw-regret-bound)） 1. 基础：写出 regret bound 的 $O(\eta T+\log n/\eta)$ 结构，并分别指出 $\log n/\eta$ 项与 $\eta T$ 项来自初始相对熵还是指数更新的二阶误差。 2. 进阶：从 regret bound $\eta T+\frac{\ln n}{\eta}$ 出发，完整推出最优 $\eta^\star$、总 regret $O(\sqrt{T\ln n})$ 与迭代数 $T=\Theta(\ln n/\epsilon^2)$；若把目标从"平均 regret $\le\epsilon$"改为"$\le\epsilon/2$"，$T$ 如何变化？ > 提示：对 $f(\eta)=\eta T+\ln n/\eta$ 求导置零；精度要求收紧一倍，$T$ 按平方倍增长。 **练习 4【量子子程序的加速来源】**（→ [第 3 节](#quantum-speedup-sources)） 1. 基础：列出每轮迭代的两件繁重任务及对应的量子子程序，并写出两个层面的加速比：单约束期望估计 $O(1/\epsilon^2)\to\widetilde O(1/\epsilon)$ 与约束搜索 $m\to\widetilde O(\sqrt m)$。 2. 进阶：解释为什么量子 Gibbs 态制备对维数 $n$ 只有多项式对数依赖：经典算法仅写下 $\rho_t$ 就需要多少个数？量子的制备成本随哪些参数增长？ > 提示：比较"存储 $n^2$ 个矩阵元"与"寄存器大小 $\log n$、稀疏度 $s$、$\|H_t\|$ 与精度"。 **练习 5【复杂度参数与适用边界】**（→ [第 4 节](#complexity-parameters)） 1. 基础：写出代表性上界 $\widetilde O(\sqrt m\,\operatorname{poly}(\log n,s,R,r,1/\epsilon))$ 中每个因子的来源，并说明 $r$ 为什么不应被误读为矩阵 rank。 2. 进阶：设某 SDP 实例 $m=n=10^6$、$s=O(1)$、$R,r=O(\log n)$、$\epsilon$ 为常数。按第 4 节的结构估算量子与经典（线性扫描约束）求解的差距主要体现在哪些因子上；若改为 $r=\Theta(n)$，结论如何变化？ > 提示：把两边的 $m$ 对 $\sqrt m$、$n$ 对 $\log n$ 逐项相除，再看 poly 因子中 $r$ 的贡献是否会吞掉比值。 **练习 6【输出模型与信息论下界】**（→ [第 5 节](#output-model-lower-bound)） 1. 基础：列举四种输出形态并按信息量从小到大排序，指出哪一种的成本最小。 2. 进阶：比较"输出近似 optimum value"与"输出全部 $X_{ij}$"两种输出模型的信息量与最小成本，并结合第 6 节说明 MaxCut 应用实际需要哪一种。 > 提示：写出 $n^2$ 个矩阵元是任何算法都绕不开的 $\Omega(n^2)$ 下界；想想 rounding 需要的是样本还是完整矩阵。 **练习 7【MaxCut 的 SDP 松弛与 rounding】**（→ [第 6 节](#maxcut-sdp-rounding)） 1. 基础：对权重全为 1 的三角形，验证 Gram 矩阵 $X=\frac32I-\frac12J$ 半正定且对角元为 $1$，并重算 SDP 松弛值 $9/4$ 与真实 MaxCut 值 $2$ 的比 $8/9$。 2. 进阶：对四元环（正方形，4 个顶点、4 条边、权重全为 1）写出 MaxCut SDP 的目标函数，找出最优向量配置并验证：此时 SDP 值与真实 MaxCut 相等（松弛无 gap）。 > 提示：正方形是二部图，把两组顶点放在两个相反的方向（$180^\circ$）即可割开全部 4 条边；再用 $X_{ij}\ge-1$ 证明 4 是上界。 **练习 8【Dequantization 与端到端评估】**（→ [第 7 节](#dequantization-end-to-end)） 1. 基础：说明 dequantization 指什么，并列出评估 state-input 量子加速时应追问的三个问题。 2. 进阶：以 QUBO 的 SDP 松弛（第 8 节）为例，解释为什么不能单独引用"量子 SDP solver 的复杂度"作为应用算法的保证，端到端的近似比应按哪条链条计算？ > 提示：把"量子求解 SDP + 经典 rounding + 读出/采样成本"逐段计入总账。 ## 参考文献与 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。