1. 论文基本信息

1.1. 标题

Quantum thermodynamics and semi-definite optimization (量子热力学与半正定优化)

1.2. 作者

• Nana Liu (刘娜): 上海交通大学自然科学研究院、上海交通大学数学科学学院
• Michele Minervini: 康奈尔大学电气与计算机工程学院
• Dhrumil Patel: 康奈尔大学计算机科学学院
• Mark M. Wilde: 康奈尔大学电气与计算机工程学院

1.3. 发表期刊/会议

预印本，发表于 arXiv。

1.4. 发表年份

2025年。

1.5. 摘要

在量子热力学 (quantum thermodynamics) 中，系统由哈密顿量 (Hamiltonian) 和一系列非对易 (non-commuting) 荷 (charges)（如粒子数或电荷）描述，其重要目标之一是在存在这些守恒荷的情况下确定系统的最小能量 (minimum energy)。在优化理论 (optimization theory) 中，半正定规划 (semi-definite program, SDP) 涉及在线性目标函数 (linear objective function) 上，在正半定算子锥 (cone of positive semi-definite operators) 与仿射空间 (affine space) 的交集上进行优化。这些问题在物理学和优化社区中分别基于不同的动机提出，并使用截然不同的术语进行表述，但在数学上它们本质上是相同的。

通过采纳由量子热力学驱动的 Jaynes 思维模式，作者观察到，上述热力学问题中，最小化自由能 (free energy) 而不是能量，可以得到一个优雅的解决方案，即将其转化为一个关于化学势参数 (chemical potential parameters) 的对偶化学势最大化问题 (dual chemical potential maximization problem)，该问题在化学势参数中是凹的 (concave)。因此，可以采用标准的（随机）梯度上升 (gradient ascent) 方法来找到这些参数的最优值，并且这些方法保证快速收敛。在低温 (low temperature) 下，最小自由能为最小能量提供了一个极好的近似。

接着，作者展示了如何将这种受 Jaynes 启发的梯度上升方法应用于最小化能量的一阶和二阶经典和混合量子-经典算法 (hybrid quantum-classical algorithms)，并等效地用于解决 SDP，同时对算法的运行时间 (runtimes) 提供了保证。本文讨论的方法扎根于量子热力学，因此为解释 Jaynes 开创性工作五十年后发表的算法（包括矩阵乘性权重更新法 (matrix multiplicative weights update method)、矩阵指数梯度更新法 (matrix exponentiated gradient update method) 及其量子算法泛化）为何能有效解决 SDP 提供了物理学上的动机。

1.6. 原文链接

https://arxiv.org/abs/2505.04514v2 PDF 链接: https://arxiv.org/pdf/2505.04514v2.pdf

2. 整体概括

2.1. 研究背景与动机

2.1.1. 量子力学与半正定优化 (Quantum Mechanics and Semi-Definite Optimization) 的内在联系

量子力学 (quantum mechanics) 的基本假设指出，量子系统 (quantum system) 的状态由迹为一的正半定算子 (positive semi-definite operator with trace equal to one) 描述，测量则由一组和为单位算子 (identity operator) 的正半定算子定义。量子信道 (quantum channels) 作为物理演化的通用模型，也与它们的 Choi 矩阵 (Choi matrices) 一一对应，后者也是正半定算子。所有这些矩阵约束都是半正定约束 (semi-definite constraints)，因此量子力学的核心组成部分都表示为受约束的半正定算子。

2.1.2. 量子力学中的优化问题与 SDP

当面临量子力学中的某些优化任务时，例如计算物理系统的最小能量 (minimum energy) 或通信的最优错误概率 (optimal error probabilities)，这些问题通常可以被表述为半正定优化问题 (semi-definite optimization problems)，即 SDP。此外，多体物理 (many-body physics) 和量子通信 (quantum communication) 中的许多问题也可以通过 SDP 解决。因此，半正定优化领域对量子力学做出了巨大贡献，并成为量子信息科学 (quantum information science) 中不可或缺的工具。

2.1.3. SDP 的广泛应用与算法发展

SDP 源于运筹学 (operations research) 和计算机科学 (computer science)，是线性规划 (linear programming) 的一个特例。除了量子力学，SDP 还在组合优化 (combinatorial optimization)、金融 (finance)、作业调度 (job scheduling) 和机器学习 (machine learning) 等领域有广泛应用。这些实际应用推动了快速 SDP 算法的发展，如内点法 (interior-point methods)、矩阵指数梯度更新法 (matrix exponentiated gradient update method, MEG) 和矩阵乘性权重更新法 (matrix multiplicative weights update method, MMW)。

2.1.4. 从量子力学反观 SDP 的潜力

鉴于 SDP 对量子力学的巨大贡献，一个自然的问题是：量子力学能否也为 SDP 提供新的见解？此前，这个问题主要通过开发在量子计算机上解决 SDP 的各种算法来解决，其中一些具有运行时间保证，另一些则基于启发式方法。本文则提出了另一种方法：利用物理直觉和洞察力来理解 SDP 并开发其求解算法。

2.1.5. 论文切入点：量子热力学与 Jaynes 原理

本文的核心切入点是量子热力学 (quantum thermodynamics)，特别是 Jaynes 关于统一信息论 (information theory) 和统计力学 (statistical mechanics) 的开创性工作。该工作在量子信息和热力学领域重新引起关注。论文考虑在存在守恒非对易荷的情况下最小化物理系统的能量问题。通过 Jaynes 的思维模式，将这个物理问题与 SDP 在数学上等同起来，并利用热力学的原理来指导 SDP 算法的设计。

2.2. 核心贡献/主要发现

2.2.1. 能量最小化与自由能最小化的转化

论文指出，直接解决具有守恒非对易荷的能量最小化问题 (7) 困难重重。取而代之的是，可以在严格正温度 $T > 0$ 下最小化系统的自由能 (8)。在足够低的温度下，最小自由能可以很好地近似最小能量。具体地，温度 $T$ 应与系统中的量子比特数 (number of qubits) 成反比。

2.2.2. 化学势最大化对偶问题

通过应用拉格朗日对偶性 (Lagrangian duality) 和量子相对熵 (quantum relative entropy)，可以将自由能最小化问题表达为其对偶形式——一个化学势最大化问题 (14)。这个最大化问题是关于化学势向量 $\mu$ 的凹函数 (concave function)。

2.2.3. 梯度上升求解与快速收敛

由于化学势最大化问题是凹的，可以使用标准的（随机）梯度上升方法快速找到最优的化学势参数 $\mu$。这些方法保证快速收敛到近似最优解。这种方法引出了经典的 Algorithm 1 和混合量子-经典 (HQC) Algorithm 2。

2.2.4. 参数化热态的最优性

分析表明，形式如 (17) 的参数化热态 (parameterized thermal states)，也称为大正则热态 (grand canonical thermal states)、非阿贝尔热态 (non-Abelian thermal states) 或量子玻尔兹曼机 (quantum Boltzmann machines)，是最小化自由能的最优状态。

2.2.5. 算法运行时保证与 SDP 求解

论文展示了这种受 Jaynes 启发的梯度上升方法如何用于最小化能量（通过 Algorithm 1 和 Algorithm 2），以及如何通过简单的归约将一般 SDP (32) 转化为能量最小化问题，从而实现 SDP 的求解，并提供了算法运行时的理论保证。

2.2.6. 二阶方法与几何洞察

通过利用目标函数 (14) 的 Hessian 矩阵的解析形式 (25)，论文还建立了一个二阶方法。Hessian 矩阵与 Kubo-Mori 信息矩阵 (Kubo-Mori information matrix) 的负值相等，这表明化学势参数空间上的欧几里得几何 (Euclidean geometry) 与参数化热态诱导的量子相对熵 (quantum relative entropy) 的几何对齐。这提供了为什么基于量子相对熵的自然梯度上升 (natural gradient ascent) 方法有效的物理动机。

2.2.7. 物理动机揭示现有算法效能

该方法为 Jaynes 开创性工作五十年后出现的 MMW、MEG 及其量子算法泛化等算法为何能有效解决 SDP 提供了物理学上的动机和深层理解。论文还通过样本复杂度分析，将提出的算法与现有的量子 MMW 算法 AG19 进行了比较，并在特定体制下展示了优势。

2.3. 示意图分析

2.3.1. 能量最小化问题求解思路 (Figure 1)

下图清晰地描绘了论文核心思想——如何通过量子热力学直觉求解能量最小化问题：

该图像是求解量子热力学能量最小化问题的示意图。图中展示了能量最小化 E(Q, q) = ext{min}_{ ho ext{ in } ext{D}_d} raket{H}_ ho 和自由能最小化 F_T(Q, q) = ext{min}_{ ho ext{ in } ext{D}_d} raket{H}_ ho - TS( ho) 的关系。通过对偶性，可以转化为化学势最大化问题。该方法可通过梯度上升法有效求解。

• 输入: 哈密顿量 $H$ 和一组非对易守恒荷 $(Q_1, \ldots, Q_c)$，以及它们对应的期望值 $(q_1, \ldots, q_c)$。目标是找到系统的最小能量 $E(\mathcal{Q}, q)$。
• 物理直觉: 鉴于物理系统在严格正温度 $T > 0$ 下运行，作者提出不直接最小化能量，而是在低温度 $T$ 下最小化系统的自由能 $F_T(\mathcal{Q}, \boldsymbol{q})$。
• 数学转化:
  1. 通过拉格朗日对偶性 (Lagrangian duality) 和量子相对熵 (quantum relative entropy)，自由能最小化问题被转化为对偶的化学势最大化问题 (chemical potential maximization)。
  2. 这个对偶问题在化学势向量 $\mu$ 中是凹的 (concave)。
• 求解方法: 由于其凹性，可以利用梯度上升法 (gradient ascent) 快速求解化学势向量 $\mu$ 的最优值。
• 输出: 这种方法导出了解决能量最小化问题的经典和混合量子-经典算法。

2.3.2. 半正定优化问题求解思路 (Figure 2)

下图展示了如何将一般的半正定优化问题 SDP 转化为能量最小化问题，从而可以使用上述热力学启发的方法来求解：

该图像是示意图，展示了解决一般半正定优化问题（SDP）的主要思想。图中包含了从标准SDP到经过修改的SDP的转变过程及其对应的自由能最小化和化学势最大化问题，表现出热力学与优化的关系。关键的公式包括 $\alpha_R = \min_{X \geq 0} \text{Tr}[CX]$ 以及 $\alpha_{R,T} = \min_{\rho \in D_{d+1}} \langle C' \rangle_\rho - TS(\rho)$，阐明了优化算法的样本效率。

• 输入: 一个 SDP，由一组 $d \times d$ 厄米矩阵 $(C, A_1, \ldots, A_c)$ 定义。
• 归约: 参考 [32, Footnote 3] 的归约方法，可以将一个通用 SDP 转化为一个缩放的能量最小化问题 (scaled energy minimization problem)。
• 关键参数: 归约引入了一个参数 $R \geq 0$，它是对原始 SDP 最优解的迹 (trace) 的一个猜测上限。
• 算法性能: 只要 $R$ 不随维度 $d$ 增长过快，由此产生的算法在样本效率 (sample-efficient) 方面是高效的。
• 连接: 能量最小化问题可以通过上述图 1 所示的 Jaynes 启发方法来解决。

3. 预备知识与相关工作

3.1. 基础概念

3.1.1. 量子热力学 (Quantum Thermodynamics)

• 哈密顿量 (Hamiltonian, $H$): 描述量子系统总能量的算符，其本征值对应于系统可能的能量值。
• 非对易荷 (Non-commuting Charges, $Q_i$): 描述系统中守恒量的算符，如粒子数 ($Q_N$) 或电荷 ($Q_e$)。它们与哈密顿量或其他荷可能不对易 (non-commuting)，这意味着它们无法同时被精确测量。
• 量子态 (Quantum State, $\rho$): 量子系统的完整描述，通常用密度矩阵 (density matrix) 表示，是一个正半定 (positive semi-definite) 的厄米 (Hermitian) 算符，其迹 (trace) 为 1。即 $\rho \in \mathcal{D}_d := \{\rho \in \mathbb{M}_d : \rho \ge 0, \mathrm{Tr}[\rho]=1\}$。
• 期望值 (Expectation Value, $\langle O \rangle_\rho$): 测量一个可观测量 (observable) $O$ 在量子态 $\rho$ 下的平均值，计算为 $\mathrm{Tr}[O\rho]$。
• 冯·诺依曼熵 (Von Neumann Entropy, $S(\rho)$): 量子信息论中衡量量子态混合程度或信息不确定性的量，定义为 $S(\rho) = -\mathrm{Tr}[\rho \ln \rho]$。对于纯态 (pure state)，熵为 0；对于最大混合态 (maximally mixed state)，熵最大。
• 自由能 (Free Energy): 热力学中一个重要的状态函数，衡量系统在给定温度下能够转化为有用功的最大能量。对于量子系统，其亥姆霍兹自由能 (Helmholtz free energy) 通常定义为 $\langle H \rangle_\rho - T S(\rho)$，其中 $T$ 是温度。
• 配分函数 (Partition Function, $Z_T(\mu)$): 在统计力学中，它概括了系统在给定温度和化学势下的所有可能的微观状态，是计算宏观热力学量（如自由能、期望值）的关键。本文中定义为 $Z_T(\mu) := \mathrm{Tr}\left[e^{-\frac{1}{T}(H - \mu \cdot Q)}\right]$。
• 化学势 (Chemical Potential, $\mu$): 在热力学中，它衡量当向系统添加一个粒子时，系统的吉布斯自由能 (Gibbs free energy) 的变化。在本文中，它作为拉格朗日乘子 (Lagrangian multiplier) 出现，用于处理守恒荷的约束。
• 大正则热态 (Grand Canonical Thermal State, $\rho_T(\mu)$): 描述与粒子和能量储存库 (reservoir) 交换粒子和能量的系统在热平衡 (thermal equilibrium) 时的量子态。其形式为 $\rho_T(\mu) := \frac{e^{-\frac{1}{T}(H - \mu \cdot Q)}}{Z_T(\mu)}$。它在平衡态统计力学中是核心概念。

3.1.2. 半正定规划 (Semi-Definite Programming, SDP)

• 线性目标函数 (Linear Objective Function): 优化问题的目标，通常是关于决策变量（矩阵 $X$）的迹 (trace) 的线性函数，如 $\mathrm{Tr}[CX]$。
• 正半定算子锥 (Cone of Positive Semi-Definite Operators): 约束条件之一，要求决策矩阵 $X$ 必须是正半定的 ($X \ge 0$)。
• 仿射空间 (Affine Space): 约束条件之二，通常表现为关于决策矩阵 $X$ 的迹的线性等式约束，如 $\mathrm{Tr}[A_i X] = b_i$。
• 标准形式 (Standard Form): SDP 的一种常见表达形式，如 (32) 所示。

3.1.3. 优化理论 (Optimization Theory)

• 梯度上升 (Gradient Ascent): 一种迭代优化算法，用于寻找函数的局部最大值。通过沿着函数梯度的方向（或近似方向）进行步进，逐步逼近最优解。
• 随机梯度上升 (Stochastic Gradient Ascent, SGA): 当无法计算精确梯度时，使用梯度的随机估计值进行更新的梯度上升变体。通常用于大规模数据集或量子算法中，梯度估计带有噪声。
• 凹性 (Concavity): 如果函数 f(x) 满足 $f(\lambda x_1 + (1-\lambda) x_2) \ge \lambda f(x_1) + (1-\lambda) f(x_2)$，则称其为凹函数。凹函数的局部最大值也是全局最大值，这使得梯度上升等方法能够收敛到全局最优。
• Lipschitz 常数 (Lipschitz Constant): 衡量函数变化“平滑”程度的常数。对于梯度，Lipschitz 常数 $L$（也称为平滑度参数 (smoothness parameter)）限制了梯度变化的速度。即 $\|\nabla f(x_1) - \nabla f(x_2)\| \le L \|x_1 - x_2\|$。
• Hessian 矩阵 (Hessian Matrix): 函数的二阶偏导数组成的方阵。它描述了函数的局部曲率。对于凹函数，Hessian 矩阵是负半定的。
• Kubo-Mori 信息矩阵 (Kubo-Mori Information Matrix): 量子信息几何 (quantum information geometry) 中的一个概念，是量子态流形的度量张量 (metric tensor) 之一，衡量量子态之间信息的差异。它与费雪信息矩阵 (Fisher information matrix) 类似，但在非对易情景下更具普适性。
• 自然梯度 (Natural Gradient): 一种优化方法，它通过考虑参数空间本身的几何结构（由费雪信息矩阵或 Kubo-Mori 信息矩阵定义）来调整梯度方向，从而实现更高效的收敛。

3.1.4. 量子计算 (Quantum Computing)

• 观测值 (Observables): 量子力学中可测量的物理量，用厄米算符表示。在量子计算机上，通过测量量子比特 (qubits) 来估计其期望值。
• Pauli 矩阵 (Pauli Matrices): 一组 $2 \times 2$ 的复数厄米矩阵，是量子力学中描述自旋-1/2粒子的基本工具。它们及其张量积 (tensor products)（称为 Pauli 字符串 (Pauli strings)）构成量子算符的常用基底。
• 混合量子-经典算法 (Hybrid Quantum-Classical Algorithms, HQC): 结合量子计算机和经典计算机的算法。通常，量子计算机执行量子态制备 (state preparation) 和测量 (measurement) 等任务，而经典计算机则处理优化、参数更新等经典计算任务。
• 热态制备 (Thermal State Preparation): 在量子计算机上制备特定温度下的量子热态的技术，是许多量子算法（包括本文提出的 HQC 算法）的关键子程序。

3.2. 前人工作

3.2.1. Jaynes 的开创性工作 (Jaynes' Seminal Work)

• 统一信息论与统计力学: E. T. Jaynes 在 1957 年的系列论文中，开创性地将信息论中的最大熵原理 (maximum entropy principle) 引入统计力学，为平衡态统计力学提供了信息论基础。他指出，在已知某些平均约束条件（如平均能量）下，最大化熵的分布就是平衡态分布。
• 本文的连接: 本文的核心思想——通过对偶性将自由能最小化问题转化为化学势最大化问题，并利用其凹性进行梯度上升求解——正是受到了 Jaynes 思想的启发。Jaynes 曾考虑过在已知哈密顿量和非对易守恒荷的情况下最大化热力学系统的熵，并观察到类似的对偶和凹性性质。

3.2.2. 优化社区的算法

• 矩阵指数梯度更新法 (Matrix Exponentiated Gradient Update Method, MEG) [26]: 这种方法在 Bregman 散度 (Bregman divergences) 的框架下解决优化问题，并且在物理学术语中，参数化热态被认为是解决这类优化问题的最优方案。然而，该方法最初的动机并非来自量子热力学。
• 矩阵乘性权重更新法 (Matrix Multiplicative Weights Update Method, MMW) [27-29]: 这种方法是乘性权重更新法在矩阵上的推广，主要源于在线学习 (online learning) 和线性优化 (linear optimization) 中的零和博弈 (zero-sum games) 理论。它也涉及对参数化热态的更新，但其最初的动机和量子热力学之间的联系并不明确。

3.2.3. 量子 SDP 求解器 (Quantum SDP Solvers)

• 早期量子算法 [30-36]: 已有多种在量子计算机上解决 SDP 的算法被提出，其中一些提供了理论上的运行时间加速，另一些则基于启发式方法。例如，AG19 [31] 提出了一个基于 MMW 方法的量子算法。
• 启发式量子算法 [37-41]: 还有一些基于变分量子算法 (variational quantum algorithms) 的启发式方法，如量子玻尔兹曼机 (quantum Boltzmann machines) 和变分量子特征求解器 (variational quantum eigensolvers, VQE) 的变体，用于解决 SDP 或相关的能量最小化问题。

3.3. 技术演进

该领域的技术演进可以概括为以下几个阶段：

1. Jaynes (1950s-1960s): 信息论与统计力学的融合，最大熵原理确立了平衡态分布的理论基础，并揭示了相关对偶问题的凹性。
2. 优化社区 (1990s-2000s): 随着 SDP 在运筹学和计算机科学中的兴起，内点法、MEG 和 MMW 等经典算法被开发出来，提供了解决大规模 SDP 的有效工具。
3. 量子信息科学 (2000s-至今): 随着量子计算的发展，SDP 作为量子力学核心部分的数学工具，其在量子计算机上的求解成为研究热点。出现了多种量子 SDP 求解算法，试图实现量子加速。
4. 本文工作 (2020s): 回归物理学的直觉，特别是量子热力学和 Jaynes 的思想，从物理学原理出发，为 SDP 算法提供新的动机和设计思路，并为现有算法的有效性提供物理学解释。

3.4. 差异化分析

本文的方法与现有工作相比，核心区别和创新点在于：

• 物理动机: 现有许多 SDP 算法，包括 MMW 和 MEG，虽然可能在数学上与热力学原理相关联，但其原始动机来自优化理论、在线学习或博弈论。本文明确地将量子热力学原理作为算法设计的核心指导，提供了物理学上的直觉和解释。
• Jaynes 思想的直接应用: 论文直接采纳 Jaynes 的思想，将能量最小化问题转化为自由能最小化，再通过对偶性转化为化学势最大化。这种转化步骤是其核心贡献，因为它自然地引出了一个凹的优化问题，可以高效地通过梯度上升求解。
• 算法设计:
  • 经典算法 (Algorithm 1): 基于精确梯度上升，为能量最小化问题提供了有保证的收敛性。
  • 混合量子-经典算法 (Algorithm 2): 结合量子计算机进行期望值估计（参数化热态制备和测量）和经典计算机进行梯度更新，为处理量子系统提供了实际路径。
  • 二阶方法 (Second-order Method): 引入了对 Hessian 矩阵的量子估计方法，可以实现更快的收敛，并揭示了其与 Kubo-Mori 信息矩阵的联系，从而连接到信息几何中的自然梯度。
• 对现有算法的物理学解释: 论文不仅提出了新算法，更重要的是，它提供了一个统一的物理学框架，来解释为何 MMW、MEG 等算法在解决 SDP 时表现出色，为这些算法的有效性提供了新的物理学原理层面的动机。
• 样本复杂度分析: 对其提出的 HQC 算法进行了详细的样本复杂度分析，并与现有量子 MMW 算法 AG19 进行比较，在特定情况下显示出更好的缩放特性。

4. 方法论

4.1. 方法原理

本文方法的核心原理是利用量子热力学的物理直觉来解决能量最小化问题和半正定规划 (SDP)。其基本思想可以概括为以下几个步骤：

1. 问题转化：从能量最小化到自由能最小化

   • 直接最小化量子系统在守恒荷约束下的能量 (7) 是一个复杂问题。
   • 物理直觉指出，真实系统在正温度下运行。因此，转而最小化系统在低温度 $T$ 下的亥姆霍兹自由能 (Helmholtz free energy) (8)。
   • 在低温下，最小自由能可以很好地近似最小能量 (11)。

2. 对偶性转化：从自由能最小化到化学势最大化

   • 通过拉格朗日对偶性 (Lagrangian duality) 和量子相对熵 (quantum relative entropy)，自由能最小化问题被转化为一个对偶问题，即化学势最大化问题 (14)。
   • 这一转化揭示了优化变量（化学势 $\mu$）与系统宏观性质（守恒荷的期望值 $q$）之间的深刻联系。

3. 优化求解：梯度上升法

   • 关键发现是化学势最大化问题的目标函数 $f(\mu)$ (23) 是凹函数 (concave function)。
   • 凹函数的局部最大值即全局最大值，因此可以使用标准的（随机）梯度上升法 (gradient ascent) 有效且快速地找到最优化学势向量 $\mu^*$。
   • 该方法依赖于计算梯度的期望值 (18)，这在量子计算机上可以通过制备参数化热态 (parameterized thermal states) (17) 并测量观测值来实现。

4. SDP 求解：问题归约

   • 通过特定的问题归约 (problem reduction)（引理 1 和引理 3），可以将一般形式的 SDP (32) 转化为能量最小化问题。
   • 因此，上述热力学启发的方法也可以用于解决 SDP。

5. 二阶方法与信息几何

   • 进一步利用 Hessian 矩阵 (25) 的解析形式，可以开发二阶优化方法。

   • Hessian 矩阵与 Kubo-Mori 信息矩阵 (Kubo-Mori information matrix) 的负值相等，这为自然梯度法 (natural gradient method) 提供了物理学上的动机和几何解释。

     这种方法的核心在于将抽象的优化问题与具体的物理系统行为联系起来，利用物理系统的热力学性质（如自由能、化学势、热平衡态）来指导优化算法的设计和分析。

4.2. 核心方法详解

4.2.1. 能量最小化问题 (Energy Minimization Problem)

首先，论文定义了在量子热力学中感兴趣的能量最小化问题。给定一个哈密顿量 $H$ 和一组 $c$ 个非对易守恒荷 $Q_1, \ldots, Q_c$ 作用在一个 $d$ 维量子系统上。

• 算符集合: $$\mathcal{Q} \equiv (H, Q_1, \dots, Q_c)$$ 其中，$H$ 和 $Q_i$ 都是 $d \times d$ 的厄米矩阵（在量子力学中也称为观测值 (observables)）。$H$ 描述系统能量，$Q_i$ 描述守恒量。
• 约束向量: $$q \equiv (q_1, \ldots, q_c) \in \mathbb{R}^c$$ 它指定了在量子态 $\rho \in \mathcal{D}_d$ 下守恒荷的期望值： $$\langle Q_i \rangle_\rho = q_i \quad \forall i \in [c]$$ 其中，$\mathcal{D}_d := \{\rho \in \mathbb{M}_d : \rho \ge 0, \mathrm{Tr}[\rho]=1\}$ 表示 $d \times d$ 密度矩阵的集合，$\mathbb{M}_d$ 表示 $d \times d$ 复矩阵的集合，$\langle \mathcal{O} \rangle_\rho \equiv \mathrm{Tr}[\mathcal{O}\rho]$ 表示观测值 $\mathcal{O}$ 在态 $\rho$ 下的期望值，$[c] := \{1, \ldots, c\}$。
• 能量最小化任务: $$E(\mathcal{Q}, q) := \min_{\rho \in \mathcal{D}_d} \left\{ \langle H \rangle_\rho : \langle Q_i \rangle_\rho = q_i \quad \forall i \in [c] \right\} \quad (7)$$ 这个任务的目标是在满足守恒荷期望值约束的量子态中，找到使系统能量最小的态，并计算该最小能量。

4.2.2. 通过自由能最小化进行近似 (Approximation by Free Energy Minimization)

直接找到 (7) 的解析解或最优态是困难的。论文提出，可以考虑真实物理系统在严格正温度 $T > 0$ 下运行，转而寻找在温度 $T$ 下的最小自由能。

• 自由能最小化任务: $$F_T(\mathcal{Q}, q) := \min_{\rho \in \mathcal{D}_d} \left\{ \langle H \rangle_\rho - T S(\rho) : \langle Q_i \rangle_\rho = q_i \quad \forall i \in [c] \right\} \quad (8)$$ 其中，$\langle H \rangle_\rho - T S(\rho)$ 是亥姆霍兹自由能 (Helmholtz free energy)，冯·诺依曼熵 (von Neumann entropy) 定义为 $S(\rho) := -\mathrm{Tr}[\rho \ln \rho]$ (9)。
• 近似精度: 在低温 $T$ 下，确定 $F_T(\mathcal{Q}, q)$ 可以近似 $E(\mathcal{Q}, q)$。近似精度由以下冯·诺依曼熵的界限给出： $$0 \le S(\rho) \le \ln d \quad (10)$$ 这导致了能量和自由能之间的界限： $$E(\mathcal{Q}, q) \ge F_T(\mathcal{Q}, q) \ge E(\mathcal{Q}, q) - T \ln d \quad (11)$$ 这个不等式 (11) 澄清了： $$\lim_{T \to 0} F_T(\mathcal{Q}, q) = E(\mathcal{Q}, q) \quad (12)$$ 为了实现 $\delta > 0$ 的近似误差（即 $|E(\mathcal{Q}, q) - F_T(\mathcal{Q}, q)| \le \delta$），温度 $T$ 应该设置为 $T = \delta / \ln d$ (即与系统中量子比特数成反比)。

4.2.3. 化学势最大化 (Chemical Potential Maximization)

为了确定误差为 $\delta$ 的最小能量 $E(\mathcal{Q}, q)$，我们可以转而计算低温 $T = \delta / \ln d$ 下的自由能 $F_T(\mathcal{Q}, q)$。通过拉格朗日对偶性 (Lagrangian duality) 和量子相对熵 (quantum relative entropy) $D(\omega || \tau) := \mathrm{Tr}[\omega (\ln \omega - \ln \tau)]$ (13)，可以得到 $F_T(\mathcal{Q}, q)$ 的替代表达式：

• 对偶表达式: $$F_T(\mathcal{Q}, q) = \sup_{\mu \in \mathbb{R}^c} \left\{ \mu \cdot q - T \ln Z_T(\mu) \right\} \quad (14)$$ 其中，$Z_T(\mu)$ 表示配分函数 (partition function)： $$Z_T(\mu) := \mathrm{Tr}\left[e^{-\frac{1}{T}(H - \mu \cdot Q)}\right] \quad (15)$$ 并且使用了速记 $\mu \cdot Q \equiv \sum_{i \in [c]} \mu_i Q_i$ (16)。向量 $\mu \in \mathbb{R}^c$ 在数学上对应于 (8) 中约束的拉格朗日乘子，在量子热力学中，其分量被称为化学势 (chemical potentials)。 这个对偶表达式 (14) 是温度缩放的对数配分函数 $T \ln Z_T(\mu)$ 的勒让德变换 (Legendre transformation) 或芬切尔对偶 (Fenchel dual)。
• 最优态: 此外，(14) 的等式意味着 (8) 中的最优态 $\rho$ 是唯一的，由如下形式的大正则热态 (grand canonical thermal state) $\rho_T(\mu^*)$ 给出： $$\rho_T(\mu) := \frac{e^{-\frac{1}{T}(H - \mu \cdot Q)}}{Z_T(\mu)} \quad (17)$$ 其中 $\mu^*$ 表示 (14) 中的最优值。

4.2.3.1. 对偶表达式 (14) 的推导 (Appendix B)

• 从自由能最小化问题 (8) 开始： $$F_T(\mathcal{Q}, q) = \min_{\rho \in \mathcal{D}_d} \left\{ \mathrm{Tr}[H\rho] - T S(\rho) : \mathrm{Tr}[Q_i\rho] = q_i \quad \forall i \in [c] \right\}$$
• 引入拉格朗日乘子 $\mu_i$ 处理约束 $\mathrm{Tr}[Q_i\rho] = q_i$： $$F_T(\mathcal{Q}, q) = \min_{\rho \in \mathcal{D}_d} \left\{ \mathrm{Tr}[H\rho] - T S(\rho) + \sup_{\mu \in \mathbb{R}^c} \sum_{i \in [c]} \mu_i (q_i - \mathrm{Tr}[Q_i\rho]) \right\}$$
• 交换最小化和最大化（通过 Sion 极小极大定理，因为目标函数在 $\rho$ 中是凹的，在 $\mu$ 中是线性的，且定义域是凸紧集）： $$F_T(\mathcal{Q}, q) = \sup_{\mu \in \mathbb{R}^c} \min_{\rho \in \mathcal{D}_d} \left\{ \mu \cdot q + \mathrm{Tr}[H\rho] - T S(\rho) - \sum_{i \in [c]} \mu_i \mathrm{Tr}[Q_i\rho] \right\} \quad (B5)$$
• 现在关注内部的最小化问题： $$\min_{\rho \in \mathcal{D}_d} \left\{ \mu \cdot q + \mathrm{Tr}[H\rho] - T S(\rho) - \sum_{i \in [c]} \mu_i \mathrm{Tr}[Q_i\rho] \right\} \quad (B7)$$ 通过一系列代数和量子相对熵 (Umegaki relative entropy) 的识别，这个表达式可以被简化。关键步骤是将 $\mathrm{Tr}[H\rho] - T S(\rho) - \sum_{i \in [c]} \mu_i \mathrm{Tr}[Q_i\rho]$ 重写为 $T \cdot D(\rho || \rho_T(\mu)) - T \ln Z_T(\mu)$ 的形式，其中 $D(\rho || \rho_T(\mu)) \ge 0$。 $$\begin{array}{l} \displaystyle = T \min_{\rho \in \mathcal{D}_d} \left\{ \frac{\mu \cdot q}{T} + \frac{1}{T} \mathrm{Tr}[H\rho] - S(\rho) - \sum_{i=1}^c \frac{\mu_i}{T} \mathrm{Tr}[Q_i\rho] \right\} \\ \displaystyle = T \min_{\rho \in \mathcal{D}_d} \left\{ \frac{\mu \cdot q}{T} - S(\rho) - \mathrm{Tr}\left[\rho \left(-\frac{1}{T}\left(H - \sum_{i \in [c]} \mu_i Q_i\right)\right)\right] \right\} \\ \displaystyle = T \min_{\rho \in \mathcal{D}_d} \left\{ \frac{\mu \cdot q}{T} - S(\rho) - \mathrm{Tr}\left[\rho \ln \exp\left(-\frac{1}{T}\left(H - \sum_{i \in [c]} \mu_i Q_i\right)\right)\right] \right\} \\ \displaystyle = T \min_{\rho \in \mathcal{D}_d} \left\{ \frac{\mu \cdot q}{T} - S(\rho) - \mathrm{Tr}[\rho \ln (\rho_T(\mu) Z_T(\mu))] \right\} \\ \displaystyle = T \min_{\rho \in \mathcal{D}_d} \left\{ \frac{\mu \cdot q}{T} - S(\rho) - \mathrm{Tr}[\rho \ln \rho_T(\mu)] - \ln Z_T(\mu) \right\} \\ \displaystyle = T \min_{\rho \in \mathcal{D}_d} \left\{ \frac{\mu \cdot q}{T} + D(\rho || \rho_T(\mu)) - \ln Z_T(\mu) \right\} \\ \end{array}$$ 由于量子相对熵 $D(\rho || \rho_T(\mu)) \ge 0$，且当 $\rho = \rho_T(\mu)$ 时取等号，因此最小值为 0。 $$= \mu \cdot q - T \ln Z_T(\mu) \quad (B13)$$
• 将此结果代回 (B5) 的 $\sup$ 运算中，就得到了 (14)： $$F_T(\mathcal{Q}, q) = \sup_{\mu \in \mathbb{R}^c} \left\{ \mu \cdot q - T \ln Z_T(\mu) \right\} \quad (B14)$$

4.2.4. 梯度上升求解 (Solution using Gradient Ascent)

最优化学势向量 $\mu^*$ 通常没有封闭形式。但 (14) 中的对数配分函数 $\ln Z_T(\mu)$ 是 $\mu$ 的凸函数。Jaynes 证明了目标函数 $f(\mu) := \mu \cdot q - T \ln Z_T(\mu)$ (23) 的梯度分量由以下公式给出：

• 梯度: $$\frac{\partial}{\partial \mu_i} \left( \boldsymbol{\mu} \cdot \boldsymbol{q} - T \ln Z_T(\boldsymbol{\mu}) \right) = q_i - \langle Q_i \rangle_{\rho_T(\boldsymbol{\mu})} \quad (18)$$ 推导 (Appendix C. Lemma 5):
  1. 从 $f(\mu)$ 的定义出发，对其求偏导： $$\frac{\partial}{\partial \mu_i} f(\boldsymbol{\mu}) = q_i - T \frac{\partial}{\partial \mu_i} \ln Z_T(\boldsymbol{\mu}) = q_i - T \frac{1}{Z_T(\boldsymbol{\mu})} \frac{\partial}{\partial \mu_i} Z_T(\boldsymbol{\mu}) \quad (C9), (C10)$$
  2. 利用 Duhamel 公式和 [67] 的引理 10，可以计算 $\frac{\partial}{\partial \mu_i} Z_T(\boldsymbol{\mu})$： $$\frac{\partial}{\partial \mu_i} e^{-\frac{1}{T}(H - \mu \cdot Q)} = \frac{1}{T} \int_0^1 ds \, e^{-\frac{1}{T}(H - \mu \cdot Q)(1-s)} Q_i e^{-\frac{1}{T}(H - \mu \cdot Q)s} \quad (C3)$$ 以及更紧凑的形式： $$= \frac{1}{2T} \{\Phi_\mu(Q_i), e^{-\frac{1}{T}(H - \mu \cdot Q)}\} \quad (C4)$$ 其中 $\Phi_\mu$ 是一个量子信道 (quantum channel)。 对 $Z_T(\mu)$ 求偏导并利用迹的循环不变性： $$\frac{\partial}{\partial \mu_i} Z_T(\mu) = \mathrm{Tr}\left[\frac{\partial}{\partial \mu_i} e^{-\frac{1}{T}(H - \mu \cdot Q)}\right] = \mathrm{Tr}\left[ \frac{1}{T} Q_i e^{-\frac{1}{T}(H - \mu \cdot Q)} \right] \quad (C14)$$
  3. 将此结果代回 (C10)： $$q_i - T \frac{1}{Z_T(\mu)} \frac{1}{T} \mathrm{Tr}\left[Q_i e^{-\frac{1}{T}(H - \mu \cdot Q)}\right] = q_i - \mathrm{Tr}[Q_i \rho_T(\mu)] = q_i - \langle Q_i \rangle_{\rho_T(\mu)} \quad (C17)$$ 由于目标函数 $f(\mu)$ 是凹函数，可以使用标准梯度上升算法 (gradient ascent) 寻找最大值，该算法保证在 $O(1/\varepsilon)$ 步内收敛到距离全局最大值 $\varepsilon$ 的点。

4.2.4.1. 算法 1 (Algorithm 1): 经典梯度上升

以下是计算最小能量 $E(\mathcal{Q}, q)$ 的算法蓝图：

Algorithm 1 1: Input:

• Observables $H$ and $(Q_i)_{i \in [c]}$

• Constraint values $(q_i)_{i \in [c]}$

• Smoothness parameter $L$ (平滑度参数)

• Hilbert space dimension $d$

• Desired error $\varepsilon > 0$

• Radius $r$: An upper bound on $\|\mu^*\|$, where $\mu^*$ is the optimal solution to (14) 2: Set $T \leftarrow \varepsilon / (4 \ln d)$ 3: Initialize $\boldsymbol{\mu}^0 \leftarrow (0, \ldots, 0)$ 4: Set learning rate $\eta \in (0, 1/L]$ 5: Choose $M = \lceil L r^2 / \varepsilon \rceil$ 6: for $m = 1$ to $M$ do 7: $\boldsymbol{\mu}^m \leftarrow \boldsymbol{\mu}^{m-1} + \eta (q - \langle Q \rangle_{\rho_T(\boldsymbol{\mu}^{m-1})})$ 8: end for 9: Return $\boldsymbol{\mu}^M \cdot q + \langle H - \boldsymbol{\mu}^M \cdot Q \rangle_{\rho_T(\boldsymbol{\mu}^M)}$

• 符号说明:

  • $q - \langle Q \rangle_{\rho_T(\mu^{m-1})}$ 是一个 $c$ 维向量，其第 $i$ 个分量为 $q_i - \langle Q_i \rangle_{\rho_T(\mu^{m-1})}$。

• 输出: 算法 1 的输出 $\tilde{E}$ (19) 是 $E(\mathcal{Q}, q)$ 的 $\varepsilon$-近似估计值。 $$\tilde{E} \equiv \langle H \rangle_{\rho_T(\boldsymbol{\mu}^M)} + \boldsymbol{\mu}^M \cdot (q - \langle Q \rangle_{\rho_T(\boldsymbol{\mu}^M)}) = \boldsymbol{\mu}^M \cdot q + \langle H - \boldsymbol{\mu}^M \cdot Q \rangle_{\rho_T(\boldsymbol{\mu}^M)} \quad (19)$$ 这个输出表达式 (19) 比 $f(\mu^M) = \mu^M \cdot q - T \ln Z_T(\mu^M)$ (21) 更简单，因为它只涉及矩阵迹，并且更适合泛化到混合量子-经典算法。

• 直观解释: 算法 1 从 $\mu^0 = (0, \ldots, 0)$ 开始，对应于哈密顿量 $H$ 的热态 $\rho_T(0) = e^{-H/T} / \mathrm{Tr}[e^{-H/T}]$。如果第 $i$ 个约束被违反（即 $q_i > \langle Q_i \rangle$），算法增加第 $i$ 个化学势 $\mu_i$ 的幅度。这在热力学上意味着系统变得更有利于从储库中获得荷，从而增加 $\langle Q_i \rangle$ 使其接近 $q_i$。反之则减少 $\mu_i$。这个过程持续到荷守恒达到平衡，最终状态将近似满足约束并近似最小化能量。

• 误差分析 (Appendix D): 算法 1 有三个误差来源：

  1. 用有限温度 $T$ 下的 $F_T(\mathcal{Q}, q)$ 近似 $E(\mathcal{Q}, q)$。
  2. 梯度上升未能达到自由能的精确全局最小值。
  3. 输出 $\tilde{E}$ 而不是 $f(\mu^M)$。 通过设置 $T = \varepsilon_1 / \ln d = \varepsilon / (4 \ln d)$，可以控制第一项误差 $|E(\mathcal{Q}, q) - F_T(\mathcal{Q}, q)| \le \varepsilon_1$。通过选择足够的步数 $M$，可以控制第二项误差 $|F_T(\mathcal{Q}, q) - f(\mu^M)| \le \varepsilon_2$。第三项误差 $|f(\mu^M) - \tilde{E}|$ 等于 $T S(\rho_T(\mu^M))$，可以被 $T \ln d$ 上界限制。最终总误差为 $2\varepsilon_1 + \varepsilon_2 + \varepsilon_3$，通过选择 $\varepsilon_1 = \varepsilon_2 = \varepsilon_3 = \varepsilon/4$，可以保证总误差 $\le \varepsilon$。

4.2.5. 平滑度参数分析 (Analysis of the Smoothness Parameter)

算法 1 收敛的关键在于平滑度参数 $L \ge 0$，它定义为梯度的 Lipschitz 常数 (Lipschitz constant) [65, Definition 2.24]： $$\| \nabla_\mu f(\nu_1) - \nabla_\mu f(\nu_2) \| \le L \| \nu_1 - \nu_2 \| \quad \forall \nu_1, \nu_2 \in \mathbb{R}^c \quad (22)$$ 其中 $f(\mu) := \mu \cdot q - T \ln Z_T(\mu)$ (23)。$L$ 控制梯度在 $\mu$ 变化时能够改变的最大量。对于平滑函数， $L$ 也可以取为 Hessian 矩阵最大奇异值 (largest singular value) 的上界 [65, Lemma 2.26]。

• Hessian 矩阵: Jaynes 也提出了 $f(\mu)$ 的 Hessian 矩阵的矩阵元公式 [44, page 200]。其负值被称为 Kubo-Mori 信息矩阵 (Kubo-Mori information matrix) $I_{ij}^{\mathrm{KM}}(\mu)$： $$\frac{\partial^2}{\partial \mu_i \partial \mu_j} f(\mu) = - I_{ij}^{\mathrm{KM}}(\mu) \quad (24)$$ $$I_{ij}^{\mathrm{KM}}(\mu) = \frac{1}{T} \int_0^1 ds ~ \mathrm{Tr}[\rho_T(\mu)^s Q_i \rho_T(\mu)^{1-s} Q_j] - \frac{1}{T} \langle Q_i \rangle_{\rho_T(\mu)} \langle Q_j \rangle_{\rho_T(\mu)} \quad (25)$$ 推导 (Appendix C. Lemma 6): 从 $\frac{\partial}{\partial \mu_j} f(\mu) = q_j - \mathrm{Tr}[Q_j \rho_T(\mu)]$ (C18) 出发，再次对 $\mu_i$ 求偏导。利用 $\rho_T(\mu)$ 的结构和对数配分函数的导数，最终得到： $$\frac{\partial^2}{\partial \mu_i \partial \mu_j} f(\mu) = \frac{1}{T} \left( \langle Q_i \rangle_{\rho_T(\mu)} \langle Q_j \rangle_{\rho_T(\mu)} - \frac{1}{2} \mathrm{Tr}[\{\Phi_\mu(Q_i), Q_j\} \rho_T(\mu)] \right) \quad (C28)$$ 这等价于 Kubo-Mori 信息矩阵的负值。
• Hessian 矩阵元的上界: 利用三角不等式和霍尔德不等式 (Hölder's inequality) 的多元推广，可以得到 Hessian 矩阵元的幅值的上界： $$\left| \frac{\partial^2}{\partial \mu_i \partial \mu_j} f(\mu) \right| \le \frac{2}{T} \|Q_i\| \|Q_j\| \quad (26)$$ 推导 (Appendix C. Lemma 7): 利用 (C28) 的表达式和算符范数 (operator norm) 的性质，包括 $\|\{\mathcal{A}, \mathcal{B}\}\| \le 2\|\mathcal{A}\|\|\mathcal{B}\|$ 和 $\|\Phi_\mu(Q_i)\| \le \|Q_i\|$，可以得出此上界。
• 平滑度参数 $L$: $L$ 可以设置为 Hessian 矩阵最大奇异值的上界。 $$L = \frac{2}{T} \sum_{i \in [c]} \|Q_i\|^2 \quad (27)$$ 推导 (Appendix C. Lemma 9): Hessian 矩阵 $F(\mu)$ 是负半定的（因为 $f(\mu)$ 是凹的），所以其谱范数 (spectral norm) $\|F(\mu)\|$ 可以被其迹范数 (trace norm) $|F(\mu)|_1$ 上界限制。 $$\|F(\mu)\| \le |F(\mu)|_1 = -\mathrm{Tr}[F(\mu)] = - \sum_{i \in [c]} \frac{\partial^2}{\partial \mu_i^2} f(\mu) \le \sum_{i \in [c]} \left| \frac{\partial^2}{\partial \mu_i^2} f(\mu) \right| \quad (C40)$$ 结合 (26) 的结果，得到 $L = \frac{2}{T} \sum_{i \in [c]} \|Q_i\|^2$。
• 收敛步数 $M$: 结合 (27) 和 Appendix D 的误差分析，算法 1 收敛到 $\varepsilon$-近似最优解所需的步数 $M$ 为： $$M = \left\lceil \frac{Lr^2}{\varepsilon} \right\rceil = \left\lceil \left( \frac{2}{T} \sum_{i \in [c]} \|Q_i\|^2 \right) \frac{r^2}{\varepsilon} \right\rceil = \left\lceil \frac{8r^2 \ln d}{\varepsilon^2} \sum_{i \in [c]} \|Q_i\|^2 \right\rceil \quad (28)$$
• 学习率 $\eta$: 步长 $\eta$ 应满足： $$0 < \eta \le \frac{1}{L} = \frac{T}{2 \sum_{i \in [c]} \|Q_i\|^2} = \frac{\varepsilon}{8 (\ln d) \sum_{i \in [c]} \|Q_i\|^2} \quad (29)$$

4.2.6. 半正定优化作为能量最小化 (Semi-definite Optimization as Energy Minimization)

标准的半正定规划 (SDP) 形式如下： $$\alpha := \min_{X \ge 0} \left\{ \mathrm{Tr}[CX] : \mathrm{Tr}[A_i X] = b_i \quad \forall i \in [c] \right\} \quad (32)$$ 其中 $C, A_i$ 是 $d \times d$ 厄米矩阵，$b_i \in \mathbb{R}$。

• 直接对应: 如果 (32) 中的一个约束是 $\mathrm{Tr}[X]=1$ (即某个 $A_i = I$ 且 $b_i = 1$)，那么这个 SDP 就与能量最小化问题 (7) 完全相同，只需进行以下识别： $$C \leftrightarrow H, \quad A_i \leftrightarrow Q_i, \quad b_i \leftrightarrow q_i \quad \forall i \in [c] \quad (33)$$ 此时，算法 1 可以直接用来解决 SDP，其步数由 (28) 给出。
• 一般 SDP 的归约: 如果没有 $\mathrm{Tr}[X]=1$ 约束，可以进行一些调整，将其归约到 (7) 的能量最小化形式。首先定义一个修改后的 SDP： $$\alpha_R := \min_{X \ge 0} \left\{ \mathrm{Tr}[CX] : \mathrm{Tr}[X] \le R, \mathrm{Tr}[A_i X] = b_i \quad \forall i \in [c] \right\} \quad (34)$$ 其中 $R > 0$ 是对原始 SDP 最优解的迹的一个猜测上限。
  • 引理 1 ([32]): 以下等式成立： $$\alpha_R = R \cdot \min_{\rho \in \mathcal{D}_{d+1}} \left\{ \langle C' \rangle_\rho : \langle A_i' \rangle_\rho = b_i' \quad \forall i \in [c] \right\} \quad (37)$$ 其中 C' := C \oplus [0], A_i' := A_i \oplus [0], $b_i' := b_i/R \quad \forall i \in [c]$ (38)。 证明 (Appendix E):
    1. 引入松弛变量 (slack variable) $z \ge 0$ 将 $\mathrm{Tr}[X] \le R$ 变为等式约束 $\mathrm{Tr}[X] + z = R$。
    2. 进行变量代换 $W = X/R, y = z/R, b_i' = b_i/R$，将问题转化为 $\mathrm{Tr}[W]+y=1$ 的形式。
    3. 定义一个 $(d+1) \times (d+1)$ 维的量子态 $\rho = \begin{pmatrix} W & v \\ v^\dagger & y \end{pmatrix}$，其中 $v \in \mathbb{C}^d$ 使得 $\rho \ge 0$。
    4. 定义 C' := C \oplus [0] 和 A_i' := A_i \oplus [0]。
    5. 这样，$\mathrm{Tr}[C W] = \mathrm{Tr}[C' \rho]$，$\mathrm{Tr}[A_i W] = \mathrm{Tr}[A_i' \rho]$，且 $\mathrm{Tr}[\rho] = \mathrm{Tr}[W]+y=1$。从而将 SDP 归约为了一个能量最小化问题，其解需要乘以 $R$。
• 求解一般 SDP 的步数: 在引理 1 的归约下，为了使近似 $\alpha_R$ 的总误差为 $\varepsilon$，需要将能量最小化问题 (37) 求解到 $\varepsilon/R$ 的误差。因此，算法 1 所需的步数 $M$ 为： $$M = \left\lceil 8 \left( \frac{Rr}{\varepsilon} \right)^2 \ln(d+1) \sum_{i \in [c]} \|A_i\|^2 \right\rceil \quad (39)$$ 这里进行了替换 $\varepsilon \to \varepsilon/R$ 和 $d \to d+1$。$r$ 是对最优对偶变量 $\mu^*$ 范数 $\|\mu^*\|$ 的上界，温度 $T = \frac{\varepsilon}{4R \ln(d+1)}$。

4.2.7. 混合量子-经典算法 (Hybrid Quantum-Classical Algorithms, HQC)

基于上述发展，论文提出了用于能量最小化和 SDP 的 HQC 算法。

• 核心修改: 将 Algorithm 1 提升为 HQC 算法，只需两项关键修改：
  1. (Q) 中的每个观测值都可以在量子计算机上测量。
  2. 参数化热态 $\rho_T(\mu)$ (17) 可以在量子计算机上制备。
• 变分量子算法性质: HQC 算法中，量子计算机专门用于估计期望值 $\langle Q_i \rangle_{\rho_T(\mu)}$ 和 $\langle H - \mu \cdot Q \rangle_{\rho_T(\mu)}$，通过重复制备热态 $\rho_T(\mu)$ 并测量观测值。这使其成为一种变分量子算法 (variational quantum algorithm)，但与许多现有 VQA 不同，它保证收敛到近似全局最优解。
• 随机梯度上升 (Stochastic Gradient Ascent, SGA): 由于量子计算机只能产生期望值的估计值，算法性能需在 SGA 框架下分析。
• 假设: 假设系统维度 $d = 2^n$ (即 $n$ 个量子比特)。所有观测值 $H$ 和 $Q_i$ 都可以有效地在量子计算机上测量，即它们可以写成 Pauli 矩阵张量积的简洁线性组合： $$\mathcal{H} = \sum_{\vec{j}} h_{\vec{j}} \sigma_{\vec{j}}, \quad (40) \\ Q_i = \sum_{\vec{j}} a_{i, \vec{j}} \sigma_{\vec{j}}, \quad (41)$$ 其中 $\vec{j}$ 是多指标，$\sigma_{\vec{j}}$ 是 Pauli 字符串 (Pauli string)。所有系数 $h_{\vec{j}}, a_{i, \vec{j}}$ 都是非负的。它们的 $L_1$ 范数 $\|h\|_1 = \sum_{\vec{j}} |h_{\vec{j}}|$ 和 $\|a_i\|_1 = \sum_{\vec{j}} |a_{i, \vec{j}}|$ (44), (45) 是 $n$ 的多项式。

4.2.7.1. 算法 2 (Algorithm 2): 混合量子-经典能量最小化

以下是提出的 HQC 算法：

Algorithm 2 1: Input:

• Observables $H$ and $(Q_i)_{i \in [c]}$ (as given in (40)(41))

• Constraint values $(q_i)_{i \in [c]}$

• Hilbert space dimension $d$

• Accuracy $\varepsilon > 0$

• Error probability $\delta \in (0, 1)$

• Radius $r$: An upper bound on $\|\mu^*\|$, where $\mu^*$ is the optimal solution to (14) for $T = \varepsilon / (4 \ln d)$ 2: Initialize $\boldsymbol{\mu}^0 \leftarrow (0, \ldots, 0)$ 3: Set learning rate $\eta$ as in (51) 4: Set number of iterations, $M$, as in (52) 5: for $m = 1$ to $M$ do 6: for $i = 1$ to $c$ do 7: $\tilde{Q}_i \leftarrow \mathsf{estimate\_obs}(\boldsymbol{\mu}^{m-1}, (a_{i, \vec{j}})_{\vec{j}}, \varepsilon, \delta)$ (估计 $\langle Q_i \rangle_{\rho_T(\mu^{m-1})}$) 8: $\bar{g}_i(\boldsymbol{\mu}^{m-1}) \leftarrow q_i - \tilde{Q}_i$ 9: end for 10: Update: $\boldsymbol{\mu}^m \leftarrow \Pi_{\mathcal{X}}(\boldsymbol{\mu}^{m-1} + \eta \bar{g}(\boldsymbol{\mu}^{m-1}))$ (投影到可行域) 11: end for 12: Set $\overline{\boldsymbol{\mu}^M} \leftarrow \frac{1}{M} \sum_{m=1}^M \boldsymbol{\mu}^m$ (取平均) 13: Set $\bar{g}_{\vec{j}} \leftarrow h_{\vec{j}} - \sum_{i \in [c]} [\overline{\boldsymbol{\mu}^M}]_i a_{i, \vec{j}}$, for all $\vec{j}$ 14: $\tilde{G} \leftarrow \mathsf{estimate\_obs}(\overline{\boldsymbol{\mu}^M}, (\bar{g}_{\vec{j}})_{\vec{j}}, \varepsilon/4, \delta)$ (估计 $\langle H - \overline{\boldsymbol{\mu}^M} \cdot Q \rangle_{\rho_T(\overline{\boldsymbol{\mu}^M})}$) 15: Return Output $\overline{\boldsymbol{\mu}^M} \cdot q + \tilde{G}$

• SGA 更新规则: $$\boldsymbol{\mu}^{m+1} = \Pi_{\mathcal{X}} \big( \boldsymbol{\mu}^m + \eta \overline{g}(\boldsymbol{\mu}^m) \big) \quad (46)$$ 其中 $\mathcal{X}$ 是包含最优解 $\mu^*$ 的半径为 $r$ 的欧几里得球。$\Pi_{\mathcal{X}}(y)$ 是将 $y$ 投影到 $\mathcal{X}$ 上的欧几里得投影 (Euclidean projection) (47)。

• 无偏梯度估计: 随机梯度 $\overline{g}(\mu)$ 必须是无偏的，即 $\mathbb{E}[\overline{g}(\mu)] = \nabla_\mu f(\mu)$ (49)。 $$\frac{\partial f(\mu)}{\partial \mu_i} = q_i - \langle Q_i \rangle_{\rho_T(\mu)} \quad (50)$$

• estimate_obs 子程序 (Algorithm 3, Appendix F2): 用于估计期望值 $\langle Q_i \rangle_{\rho_T(\mu)}$ 或 $\langle H - \overline{\boldsymbol{\mu}^M} \cdot Q \rangle_{\rho_T(\overline{\boldsymbol{\mu}^M})}$。 Algorithm 3 estimate_obs($\boldsymbol{\mu}$, $(a_{\vec{j}})_{\vec{j}}$, $\varepsilon$, $\delta$) 1: Input:

  • chemical potential vector $\boldsymbol{\mu} \in \mathbb{R}^c$
  • non-negative coefficients $(a_{\vec{j}})_{\vec{j}}$ for the Pauli strings $(\sigma_{\vec{j}})_{\vec{j}}$
  • accuracy $\varepsilon > 0$
  • error probability $\delta \in (0, 1)$ 2: $N \leftarrow \lceil 2 \|a\|_1^2 \ln(2/\delta) / \varepsilon^2 \rceil$ (所需样本数) 3: for $n = 0$ to N-1 do 4: Sample a multi-index $\vec{j}$ with probability $a_{\vec{j}} / \|a\|_1$ 5: Prepare a register in the state $\rho_T(\boldsymbol{\mu})$, measure $\sigma_{\vec{j}}$, and store the measurement outcome $b_n$ 6: Set $Y_n \leftarrow \|a\|_1 (-1)^{b_n}$ 7: end for 8: Return $\overline{Y} \leftarrow \frac{1}{N} \sum_{n=0}^{N-1} Y_n$

  estimate_obs 的样本复杂度 (Lemma 11, Appendix F3a): 为了以 $1-\delta$ 的成功概率产生 $\varepsilon$-近似估计，所需样本数 $N_i$ 为： $$N_i = \left\lceil \frac{2 \|a_i\|_1^2 \ln(2/\delta)}{\varepsilon^2} \right\rceil \quad (F17)$$ 这基于 Hoeffding 不等式 (Hoeffding's inequality)，利用了 $Y_n$ 的范围为 $[-\|a_i\|_1, \|a_i\|_1]$。

• 学习率 $\eta$ 和迭代次数 $M$: 根据 SGA 的收敛理论 [66, Theorem 6.3]，设置如下： $$\eta := \left[ \frac{8 \ln d}{\varepsilon} \sum_{i \in [c]} \|a_i\|_1^2 + \frac{\sigma}{r} \sqrt{\frac{M}{2}} \right]^{-1} \quad (51)$$ $$M := \left\lceil \frac{16 r^2}{\varepsilon^2} \left( 2\sigma^2 + 8 (\ln d) \sum_{i \in [c]} \|a_i\|_1^2 \right) \right\rceil \quad (52)$$ 其中 $\sigma^2$ 是随机梯度的方差上界： $$\sigma^2 := c \varepsilon^2 + \delta \sum_{i \in [c]} \|a_i\|_1^2 \quad (53)$$ (Appendix F3b 详细推导了方差 $\sigma^2$。)

4.2.7.2. HQC 算法的收敛性 (Convergence of HQC Algorithm for Energy Minimization)

定理 2 (Theorem 2): 假设 $H$ 和 $Q_i$ （如 (40) 和 (41) 定义）是哈密顿量和观测值，$h$ 和 $a_i$ 是它们的 Pauli 系数向量。对于给定的 $\varepsilon > 0$ 和 $\delta \in (0, 1)$，为了以不小于 $1-\delta$ 的成功概率获得能量最小化问题 (7) 最优值的 $\varepsilon$-近似估计 $\hat{E}$ (即 $\mathrm{Pr}\left[|E(\mathcal{Q}, q) - \mathbb{E}[\hat{E}]| \le \varepsilon\right] \ge 1-\delta$)，Algorithm 2 的样本复杂度（热态样本数）为： $$O \left( \frac{r^2 \ln(1/\delta) \ln d}{\varepsilon^4} \left[\max\left\{ \sum_{i \in [c]} \|a_i\|_1^2, \|h\|_1 \right\}\right]^2 \right) \quad (55)$$

• 说明: 期望值 $\mathbb{E}$ 是针对 SGA 更新的 $M$ 步的随机性，概率 $\mathrm{Pr}$ 是针对最终估计 $\hat{E}$ 的随机性。
• 复杂度特点: 样本复杂度是 $\varepsilon^{-1}, c, r, \|h\|_1, \|a_i\|_1$ 的多项式。如果 $c, r, \|h\|_1, \|a_i\|_1$ 都是 $n$ 的多项式，则样本复杂度与量子比特数 $n$ 和逆精度 $\varepsilon^{-1}$ 成多项式关系。

4.2.7.3. SDP 的扩展 (Extension to Semi-definite Optimization)

通过将一般 SDP 映射到能量最小化问题，Algorithm 2 也可以用于解决 SDP。

• 引理 3: 以下等式成立： $$\alpha_R = R \cdot \min_{\rho \in \mathcal{D}_{2d}} \left\{ \langle C'' \rangle_\rho : \langle A_i'' \rangle_\rho = b_i' \quad \forall i \in [c] \right\} \quad (57)$$ 其中 $C'' := C \otimes |0\rangle\langle0|$, $A_i'' := A_i \otimes |0\rangle\langle0|$, $b_i' := b_i/R \quad \forall i \in [c]$ (58)。 证明 (Appendix G): 该证明与引理 1 类似，但不是通过直接嵌入到更大的密度矩阵，而是使用辅助量子比特 (ancilla qubit) $|0\rangle\langle0|$，将 $d \times d$ 矩阵提升到 $2d \times 2d$ 矩阵。
• SDP 求解的样本复杂度: 样本复杂度 (55) 通过将 $\varepsilon \to \varepsilon/R$ 和 $d \to 2d$ 泛化，可以得到解决一般 SDP 的样本复杂度： $$O \left( \frac{r^2 R^4 n \ln(1/\delta)}{\varepsilon^4} \left[\max\left\{ \sum_{i \in [c]} \|A_i\|^2, \|C\| \right\}\right]^2 \right) \quad (59)$$ 这表明，SDP 求解的样本复杂度在迹因子 $R$ 和系统扩展（单个量子比特）方面只引入了多项式开销 (polynomial overhead)。

4.2.8. 二阶随机梯度上升 (Second-order Stochastic Gradient Ascent)

为了加速收敛，可以引入二阶方法，即利用 Hessian 矩阵的信息。

• Hessian 矩阵元的替代表达式: $f(\mu)$ 的 Hessian 矩阵的 (i, j)-th 元素 (62) 可以写为： $$\frac{\partial^2}{\partial \mu_i \partial \mu_j} f(\mu) = \frac{1}{T} \left( \langle Q_i \rangle_{\rho_T(\mu)} \langle Q_j \rangle_{\rho_T(\mu)} - \frac{1}{2} \langle \{\Phi_\mu(Q_i), Q_j\} \rangle_{\rho_T(\mu)} \right) \quad (62)$$ 其中 $\Phi_\mu$ 是量子信道 (quantum channel) (60)，p(t) 是高峰帐篷概率密度函数 (high-peak-tent probability density function) (61)。

• 与 Kubo-Mori 信息矩阵的关系: (62) 等于参数化热态族 $(\rho_T(\mu))_{\mu \in \mathbb{R}^c}$ 的 Kubo-Mori 信息矩阵的负值： $$\frac{\partial^2}{\partial \mu_i \partial \mu_j} f(\mu) = - I_{ij}^{\mathrm{KM}}(\mu) \quad (63)$$

• 估计 Hessian 元素: 可以使用类似于 [68] 中提出的方法来估计 Kubo-Mori 信息矩阵的元素。Appendix H 中详细描述了 Algorithm 4 estimate-anticommutator.hessian。 Algorithm 4 estimate-anticommutator.hessian($\boldsymbol{\mu}$, $(a_{i, \vec{v}})_{\vec{v}}$, $(a_{j, \vec{v}})_{\vec{v}}$, $\varepsilon$, $\delta$) (Appendix H) 此算法用于估计 (H1) 的第二项 $\frac{1}{2} \langle \{\Phi_\mu(Q_i), Q_j\} \rangle_{\rho_T(\mu)}$。它涉及：

  1. 初始化控制寄存器 (control register) $|1\rangle\langle1|$。

  2. 制备系统寄存器 (system register) 为态 $\rho_T(\mu)$。

  3. 采样多指标 $\bar{\ell}, \vec{k}$ 和时间 $t$。

  4. 对控制寄存器应用 Hadamard 门。

  5. 应用受控 Pauli 门 (controlled-Pauli operation) 和哈密顿量模拟 (Hamiltonian simulation) $e^{i(H-\mu\cdot Q)t/T}$。

  6. 再次对控制寄存器应用 Hadamard 门。

  7. 测量控制寄存器和系统寄存器，根据测量结果计算 $Y_n = (-1)^{\lambda_n + \gamma_n}$。

  8. 重复 $N$ 次并取平均。 量子电路如图 3 所示，它估计了两个算符的反对易子 (anticommutator) 的期望值。

     该图像是一个量子电路示意图，展示了量子态 $|1\rangle$ 经 Hadamard 门操作后，如何与其他量子门结合，以实现特定的量子操作。整体流程中包含了 $e^{i(H-\mu\cdot Q)t/T}$ 的演变，表明哈密顿量与化学势之间的关联，进一步连接到后续的测量操作。

• 牛顿法 (Newton's Method) 与自然梯度上升 (Natural Gradient Ascent): 目标函数 $f(\mu)$ 是平滑和凹的，因此二阶方法（如牛顿法）可以提供比一阶方法更快的局部收敛速度。由于 Hessian 矩阵与 Kubo-Mori 信息矩阵相等，牛顿步与 Kubo-Mori 几何中的自然梯度步相同 [88]。

  • 更新规则: $$\boldsymbol{\mu}^{m+1} = \boldsymbol{\mu}^m - \eta \Delta_m \quad (64)$$ 其中 $\Delta_m$ 是方程 $I^{\mathrm{KM}}(\mu^m) \Delta_m = \overline{g}(\mu^m)$ 的解 (65)。通过求解 (65)，梯度被重新缩放，使其与量子相对熵定义的几何中最速下降方向对齐。

5. 实验设置

5.1. 数据集

本文主要是一个理论性工作，提出了算法框架和收敛性保证，因此没有使用具体的数值数据集进行传统意义上的实验。其分析和保证是针对抽象的量子系统和 SDP 问题，假设能够访问到以下信息：

• 系统描述: 哈密顿量 $H$ 和守恒荷 $Q_i$ 的矩阵表示（或其 Pauli 分解系数）。
• 约束值: 守恒荷的期望值 $q_i$。
• 系统维度: 希尔伯特空间维度 $d$ (或量子比特数 $n$，$d=2^n$)。
• 参数 $R$ 和 $r$: 分别是对 SDP 最优解的迹和最优化学势向量范数的上界猜测。

若原文提供了数据集中的具体样本示例（如一句话、一张图），请务必一并展示，以帮助读者直观理解数据形态。 本文没有提供任何具体的数据集样本示例，其分析是完全抽象的。

5.2. 评估指标

本文提出的算法和理论分析主要关注以下评估指标：

5.2.1. 精度 ($\varepsilon$)

• 概念定义: 表示算法输出结果与真实最优值之间的最大允许误差。
• 数学公式: $|E(\mathcal{Q}, q) - \hat{E}| \le \varepsilon$ 或 $|\alpha - \hat{\alpha}| \le \varepsilon$。
• 符号解释:
  • $E(\mathcal{Q}, q)$: 量子能量最小化问题的真实最优能量。
  • $\hat{E}$: 算法对 $E(\mathcal{Q}, q)$ 的估计值。
  • $\alpha$: SDP 问题的真实最优值。
  • $\hat{\alpha}$: 算法对 $\alpha$ 的估计值。
  • $\varepsilon$: 期望的近似误差。

5.2.2. 成功概率 ($1-\delta$)

• 概念定义: 表示算法在给定误差范围内找到近似最优解的概率。
• 数学公式: $\mathrm{Pr}[\text{event}] \ge 1-\delta$。
• 符号解释:
  • $\mathrm{Pr}[\text{event}]$: 某个事件发生的概率，例如估计值在 $\varepsilon$ 误差范围内。
  • $\delta$: 失败概率，通常是一个小的正数。

5.2.3. 样本复杂度 (Sample Complexity)

• 概念定义: 衡量算法达到指定精度和成功概率所需的热态样本 (thermal state samples) 总数。在量子算法的背景下，这通常指的是量子计算机制备和测量量子态的次数。这是衡量量子算法效率的关键指标。
• 数学公式: 具体公式见方法论中的 (55) 和 (59)。
• 符号解释:
  • $r$: 最优化学势向量范数 $\|\mu^*\|$ 的上界。
  • $R$: SDP 最优解的迹的上限。
  • $n$: 量子比特数 ( $d=2^n$ )。
  • $c$: 守恒荷 (或约束) 的数量。
  • $\|a_i\|_1$: 观测值 $Q_i$ 的 Pauli 系数 $L_1$ 范数。
  • $\|h\|_1$: 哈密顿量 $H$ 的 Pauli 系数 $L_1$ 范数。
  • $\|A_i\|$: 矩阵 $A_i$ 的算符范数 (operator norm)。
  • $\|C\|$: 矩阵 $C$ 的算符范数。
  • $\varepsilon$: 期望的精度。
  • $\delta$: 期望的失败概率。

5.3. 对比基线

本文的理论分析和样本复杂度比较，主要与以下算法进行：

• 经典梯度上升 (Classical Gradient Ascent): Algorithm 1 的收敛性分析作为基线，展示了在理想（精确梯度）情况下的性能。
• 矩阵乘性权重更新法 (Matrix Multiplicative Weights Update, MMW) 和 矩阵指数梯度更新法 (Matrix Exponentiated Gradient Update, MEG): 论文在概念层面讨论了其方法与这些经典优化算法的关系和动机上的差异。这些算法在优化社区被广泛用于解决 SDP。
• AG19 量子 MMW 算法 (AG19 Quantum MMW Algorithm) [31]: 这是目前最先进的量子 SDP 求解算法之一，本文将其提出的 Algorithm 2 的样本复杂度与 AG19 算法进行了详细的理论比较，以评估其在量子加速方面的潜力。AG19 算法的样本复杂度为 $O \left( \frac{r^4 R^4 \ln(1/\delta) \ln d}{\varepsilon^4} \right)$ (67)。

6. 实验结果与分析

由于本文是一个理论性工作，主要提出了算法框架和收敛性保证，因此没有传统意义上的实验结果表格或图表。本节将重点分析论文中给出的理论保证和与其他算法的比较。

6.1. 核心结果分析

6.1.1. 经典梯度上升算法 (Algorithm 1) 的收敛性

论文为 Algorithm 1 提供了明确的收敛性保证，其所需的迭代次数 $M$ 由以下公式给出： $$M = \left\lceil \frac{8r^2 \ln d}{\varepsilon^2} \sum_{i \in [c]} \|Q_i\|^2 \right\rceil \quad (28)$$

• 分析: 迭代次数 $M$ 与目标精度 $\varepsilon$ 的平方成反比，与希尔伯特空间维度 $d$ 的对数成正比，与最优化学势向量范数 $r$ 的平方成正比，并与守恒荷算符范数平方和 $\sum_{i \in [c]} \|Q_i\|^2$ 成正比。这意味着在经典设置中，该算法可以有效收敛。

6.1.2. 混合量子-经典算法 (Algorithm 2) 的样本复杂度

对于能量最小化问题，Algorithm 2 的样本复杂度（即制备热态的样本总数）由以下定理给出： 定理 2 (能量最小化样本复杂度): $O \left( \frac{r^2 \ln(1/\delta) \ln d}{\varepsilon^4} \left[\max\left\{ \sum_{i \in [c]} \|a_i\|_1^2, \|h\|_1 \right\}\right]^2 \right) \quad (55)$

• 分析:
  • 精度依赖: 样本复杂度对精度 $\varepsilon$ 具有 $\varepsilon^{-4}$ 的依赖关系。
  • 维度依赖: 对数维度 $\ln d$ (即量子比特数 $n$) 呈线性依赖。
  • 荷数量依赖: 与守恒荷数量 $c$ 的多项式（隐式在 $\|a_i\|_1$ 中，通常 $\|a_i\|_1$ 是 $n$ 的多项式，与 $c$ 无直接关系，但在 $\sigma^2$ 中有 $c$ 的直接线性依赖，导致 overall 也有 $c^2$ 的依赖）。
  • 参数范数依赖: 与最优化学势半径 $r$ 的平方成正比，与哈密顿量和荷的 Pauli 系数 $L_1$ 范数最大值的平方成正比。
  • 优势: 该算法作为一种 HQC 方法，在理论上提供了收敛到近似全局最优解的保证，并且复杂度在许多参数上是多项式依赖的。

6.1.3. 解决一般 SDP 的样本复杂度

通过引理 3 的归约，Algorithm 2 可以用于解决一般 SDP。其样本复杂度为： $$O \left( \frac{r^2 R^4 n \ln(1/\delta)}{\varepsilon^4} \left[\max\left\{ \sum_{i \in [c]} \|A_i\|^2, \|C\| \right\}\right]^2 \right) \quad (59)$$

• 分析:
  • 精度依赖: 同样是 $\varepsilon^{-4}$。
  • SDP 特定参数: 引入了 $R^4$ 的依赖（其中 $R$ 是对最优解迹的估计）和 $n$ 的线性依赖（来自 $\ln d \to \ln(2d) = n+1$）。
  • 算符范数依赖: 与 $A_i$ 和 $C$ 的算符范数最大值的平方成正比。
  • 开销: 相比能量最小化，由于归约引入了 $R$ 因子和系统维度加倍（$d \to 2d$），SDP 求解的样本复杂度会略有增加，但仍保持多项式依赖。

6.1.4. 与现有量子 MMW 算法 (AG19) 的比较

论文将 Algorithm 2 解决 SDP 的样本复杂度 (66) 与 AG19 算法的样本复杂度 (67) 进行了比较。

• Algorithm 2 (本文算法) 样本复杂度: $$O \left( \frac{r^2 c^2 R^4 \ln(1/\delta) \ln d}{\varepsilon^4} \right) \quad (66)$$
• AG19 算法样本复杂度: $$O \left( \frac{r^4 R^4 \ln(1/\delta) \ln d}{\varepsilon^4} \right) \quad (67)$$
• 比较分析:
  • 共同依赖: 两种算法都对 $\varepsilon^{-4}$、 $R^4$、$\ln(1/\delta)$ 和 $\ln d$ 具有相同的依赖。
  • $r$ 依赖: 本文算法对最优化学势半径 $r$ 的依赖是 $r^2$，而 AG19 是 $r^4$。这表明本文算法在 $r$ 方面有二次改进 (quadratic improvement)。
  • $c$ 依赖: AG19 算法的样本复杂度与约束数量 $c$ 无关，而本文算法具有 $c^2$ 的依赖（尽管在 (59) 中没有直接显示 $c^2$，但在推导 $\sigma^2$ (F38) 时，其依赖于 $c\varepsilon^2$，这个 $c$ 会传递到 $M$ (52) 中，从而导致总样本复杂度中出现 $c^2$ 依赖）。
  • 权衡:
    • 当 $r \gg c$ 时（即最优化学势向量范数很大，而约束数量相对较少），本文算法具有显著优势，因为它对 $r$ 的依赖更低。
    • 当 $r$ 随 $c$ 线性增长时（例如在像 MAXCUT 这样的组合优化问题中），两种算法的性能可能相当。

6.1.5. 二阶方法与几何洞察

• 论文指出了 Hessian 矩阵与 Kubo-Mori 信息矩阵负值相等 (63) 的重要性。这意味着目标函数 $f(\mu)$ 的欧几里得曲率 (Euclidean curvature) 与由量子相对熵诱导的信息几何曲率 (information-geometric curvature) 相吻合。
• 这提供了理论基础，说明为什么牛顿法（二阶方法）中的一步等同于在 Kubo-Mori 几何下的自然梯度 (natural gradient) 一步。理论上，自然梯度可以提供更快的收敛速度，尤其是在参数空间几何高度非均匀时。
• 然而，论文并未提供二阶方法的具体样本复杂度分析，这被列为未来的研究方向。

6.2. 数据呈现 (表格)

本文未提供任何实验结果的表格。

6.3. 消融实验/参数分析

论文没有进行传统的消融实验或参数分析，因为其核心是算法的理论构建和收敛性分析。然而，论文对关键参数的选择和影响进行了理论探讨：

• 温度 $T$ 的选择: $T = \varepsilon / (4 \ln d)$。这个选择是为了将自由能对能量的近似误差控制在 $\varepsilon/4$ 范围内，显示了温度与所需精度和系统维度之间的权衡。
• 半径 $r$ 的重要性: $r$ 是最优化学势向量范数 $\|\mu^*\|$ 的上界。它直接影响迭代次数 $M$ 和样本复杂度。如果 $r$ 估计过小，算法可能无法找到最优解；如果过大，则会增加计算开销。论文强调需要对搜索空间的大小有一个粗略的猜测。
• 缩放因子 $R$ 的影响: 在 SDP 归约中， $R$ 是对最优 SDP 解的迹的猜测上限。它对 SDP 求解的样本复杂度有 $R^4$ 的依赖，这表明 $R$ 的准确估计对于算法效率至关重要。

7. 总结与思考

7.1. 结论总结

本文通过将量子热力学与半正定优化 (SDP) 连接起来，为 SDP 求解提供了深刻的物理学动机和一套新的算法框架。

• 核心思想: 论文从 Jaynes 的思维模式出发，将存在守恒非对易荷的量子能量最小化问题 (7) 转化为在低温下的自由能最小化问题 (8)。
• 对偶转化: 进而，通过拉格朗日对偶性 (Lagrangian duality) 和量子相对熵 (quantum relative entropy)，将自由能最小化问题转化为一个关于化学势向量 $\mu$ 的凹函数最大化问题 (14)。
• 算法提出: 基于此凹性，论文提出了经典的梯度上升算法 (Algorithm 1) 和混合量子-经典随机梯度上升算法 (Algorithm 2)，并对它们的收敛性提供了理论保证。
• SDP 泛化: 通过巧妙的问题归约 (引理 1 和引理 3)，这些算法被推广到解决一般形式的 SDP (32)，并给出了相应的样本复杂度分析。
• 二阶方法与物理动机: 论文还探讨了二阶梯度上升方法，并指出 Hessian 矩阵与 Kubo-Mori 信息矩阵 (Kubo-Mori information matrix) 的负值相等，为矩阵乘性权重更新法 (MMW) 和矩阵指数梯度更新法 (MEG) 等现有算法的有效性提供了物理学上的深层解释。
• 竞争优势: 在与现有量子 SDP 求解器（如 AG19 量子 MMW 算法）的理论比较中，本文提出的算法在对最优化学势向量范数 $r$ 的依赖方面显示出优势。

7.2. 局限性与未来工作

7.2.1. 局限性

• 约束条件泛化: 尽管框架可以扩展到混合等式和不等式约束（通过对不等式约束的化学势限制为非负值），但本文主要关注等式约束。
• 强凹性优势: 算法的收敛性依赖于目标函数的凹性。如果对偶问题表现出强凹性 (strong concavity)（例如在准局部算符 (quasilocal operators) 的情况下），收敛速度会更快，但本文的通用设置并未假设这一条件。
• 热态制备完美性: 算法分析假设完美的热态制备。在实际的量子设备中，不完美的状态制备会引入梯度估计中的偏差。
• 参数估计: 算法需要对最优化学势范数 $r$ 和 SDP 最优解迹 $R$ 有一个预估上限，这在实际应用中可能是一个挑战。

7.2.2. 未来工作

• 二阶方法的样本复杂度分析: 对二阶方法（牛顿法）进行严格的样本复杂度分析，量化其计算开销与收敛加速之间的权衡。
• SDP 框架的泛化: 将框架推广到更广泛的 SDP 类别，例如带有不等式约束或非线性目标函数的优化问题。
• 广义散度探索: 探索广义散度（如 Rényi 相对熵 (Rényi relative entropies)）在连接自由能最小化与对偶问题中的作用。
• 连续变量约束: 涵盖连续变量约束，将其应用于由常微分方程和偏微分方程描述的动态系统。
• 连续时间训练过程: 将训练过程推广到连续时间模拟，连接到量子体制下的复制器动力学 (replicator dynamics) 和量子零和博弈 (quantum zero-sum games)。
• 量子优势的条件: 深入研究 HQC 算法实现量子优势的条件。这需要识别经典模拟热态困难而量子计算机能有效制备的特定问题类别（例如，具有非局域关联或高纠缠的系统），并开发更高效的低温热化量子子程序。

7.3. 个人启发与批判

7.3.1. 个人启发

• 物理直觉的强大: 这篇论文最引人入胜之处在于，它展示了看似与优化问题无关的物理学原理（量子热力学）如何能够为算法设计提供深刻的直觉和坚实的理论基础。Jaynes 的最大熵原理与优化中的对偶性之间的连接是如此优雅和普适。
• 统一性框架: 论文提供了一个统一的框架，不仅提出了新的算法，更重要的是，为 MMW 和 MEG 等现有算法的有效性提供了物理学解释，这对于理解这些算法的鲁棒性和设计原理具有重要意义。
• HQC 算法的潜力: 提出的 HQC 算法结合了量子计算机在态制备和测量上的能力与经典计算机在优化逻辑上的优势，为解决复杂的量子多体问题和 SDP 提供了一条有前景的路径。在保证收敛性的前提下，这比许多纯粹启发式的变分量子算法更具吸引力。
• 信息几何的实践应用: Hessian 矩阵与 Kubo-Mori 信息矩阵的联系，清晰地展现了信息几何在优化算法中的实际指导作用，为自然梯度方法的有效性提供了直观理解。

7.3.2. 批判

• 低温热态制备的挑战: 论文指出，要实现精确的能量最小化，温度 $T$ 需要与 $\ln d$ 成反比，这意味着对于大量量子比特系统，需要非常低的温度。然而，现有的量子热态制备方法在低温下通常效率低下且具有挑战性。这可能成为 HQC 算法实现实际量子优势的一个主要瓶颈。
• 参数 $r$ 和 $R$ 的先验知识: 算法需要对最优化学势范数 $r$ 和 SDP 最优解的迹 $R$ 有一个预估上限。在许多实际问题中，这些先验知识可能难以获得，或者粗略的估计可能导致过高的样本复杂度。
• 样本复杂度的高阶依赖: 尽管样本复杂度是多项式依赖，但 $\varepsilon^{-4}$ 和 $R^4$ 的依赖在大规模问题和高精度要求下仍然可能非常高昂，这限制了算法在实际应用中的可扩展性。
• 非对易荷的实现: 虽然 Pauli 算符的分解提供了一种测量观测值的方法，但对于任意的非对易荷，其在量子硬件上的高效实现和测量可能仍需进一步研究。
• 理论与实践的差距: 论文主要集中在理论分析和渐近复杂度上，对于实际量子硬件上的噪声、错误率和制备时间等因素考虑较少。将这些理论算法转化为能在嘈杂中等规模量子设备 (NISQ) 上运行的实用方案，仍有很长的路要走。