# Double-Bracket 量子算法：等谱梯度流、群交换子与虚时间演化 量子计算机擅长执行酉演化 $e^{-itH}$，但许多经典数值任务——矩阵对角化、特征值排序、基态制备——本质上不是酉的。Double-bracket flow 提供了一座桥梁：它是一条始终停留在 $H$ 的 unitary orbit（酉轨道）上的矩阵微分方程，因而原则上可以全部由酉操作实现；同时它又是一条梯度流，会单调地把矩阵"推向"对角形。这条思路最早由 Brockett 在 1980 年代末提出，Helmke 与 Moore 在专著 *Optimization and Dynamical Systems*（Zoo 521）中把它发展成一套"用微分方程做数值线性代数"的系统理论；2022 年 Gluza（Zoo 522）将其量子化，提出 double-bracket quantum algorithm，随后又有了面向基态制备、量子虚时间演化与 QSP 的一系列工作（Zoo 523–526）。 经典的 double-bracket 算法处理 $d\times d$ 矩阵时，每一步都要计算矩阵对易子 $[N,H]$ 并做矩阵乘法，代价是 $O(d^\omega)$ 量级的浮点运算。当矩阵来自 $n$ 量子比特的 Hamiltonian 时 $d=2^n$，经典逐步跟踪流就是指数代价——这正是想借助量子计算机绕开的瓶颈。但正如我们将看到的，量子实现也有自己的陷阱：每一步迭代会改变 Hamiltonian 本身，下一步又需要模拟更新后的 Hamiltonian，直接内联展开会让电路深度随迭代数指数增长。因此目前 Zoo 把这类算法的加速比标为 unknown；本文的目标是把整个框架的数学结构、量子合成方法与这个深度瓶颈逐一讲清楚。 **阅读准备。** 我们假设读者熟悉本站前几章的内容：Hermitian 算符与谱、酉演化与 Hamiltonian simulation（product formula 的思想）、Grover/相位估计的基本复杂度记账方式。除对易子 $[A,B]=AB-BA$、反对易子 $\{A,B\}=AB+BA$、Frobenius 范数 $\|A\|_F^2=\operatorname{Tr}(A^\dagger A)$ 之外，不需要其他特殊工具。 :::{admonition} 本课知识点 :class: tip 1. **[从对角化到 double-bracket 方程](#double-bracket-equation)**——能写出 $\dot H=[[N,H],H]$ 并说明两层对易子的计算顺序，解释这条流为何"不寻找新的特征值，而是在固定谱上旋转矩阵朝向"，从而把对角化与排序统一成同一类等谱旋转。 2. **[等谱性与酉轨道](#isospectral-unitary-orbit)**——能证明 $K=[N,H]$ 反厄米，并借助辅助方程 $\dot U=KU$ 推出 $H(t)=U(t)H(0)U(t)^\dagger$，列出特征值、迹幂、行列式等沿流不变的谱量。 3. **[Lyapunov 单调性与特征值排序](#lyapunov-monotonicity-sorting)**——能推导 $\frac{d}{dt}\operatorname{Tr}(NH)=\|[N,H]\|_F^2\ge 0$，刻画稳定点条件 $[N,H]=0$，并用非简并对角 $N$ 与 von Neumann 迹不等式说明稳定点即对角形、特征值顺序由 $N$ 的对角元顺序决定。 4. **[离散迭代与谱的精确保持](#discrete-bracket-iteration)**——能写出 $H_{k+1}=e^{\eta_k[N,H_k]}H_ke^{-\eta_k[N,H_k]}$，证明它按构造精确保持 Hermiticity 与谱，验证与连续流的一阶一致性，并比较固定 $N$ 与逐步变分选 $N$ 两种策略。 5. **[2×2 手算例子](#two-by-two-example)**——能对 $2\times 2$ Hermitian 矩阵手算一步迭代：计算 $K_0$、一阶更新 $H_1$ 与 Lyapunov 增量，核对 $\Delta F=\eta\|[N,H_0]\|_F^2$ 及各守恒量。 6. **[群交换子乘积公式](#group-commutator-synthesis)**——能用 BCH 公式推导 $e^{i\sqrt\eta N}e^{i\sqrt\eta H_k}e^{-i\sqrt\eta N}e^{-i\sqrt\eta H_k}=e^{-\eta[N,H_k]+O(\eta^{3/2})}$，说明 $\sqrt\eta$ 阶项相消、$\eta$ 阶对易子幸存的原因，并列出无需 ancilla 与 postselection 的资源优势。 7. **[递归深度指数增长](#recursive-depth-explosion)**——能解释"模拟更新后的 Hamiltonian"如何导出深度递推 $D_{k+1}\gtrsim cD_k+O(1)$，求解出 $D_k=\Theta(c^k)$，并定性比较以宽度换深度的代价转移。 8. **[虚时间演化的 projector 方程](#qite-projector-flow)**——能推导归一化虚时间演化的 projector 方程 $\dot\rho=-\{H,\rho\}+2\operatorname{Tr}(H\rho)\,\rho$，并利用 $\rho^2=\rho$、$\rho H\rho=\langle H\rangle\rho$ 证明它与 Brockett double bracket $[[\rho,H],\rho]$ 逐项恒等。 ::: (double-bracket-equation)= ## 1. 从对角化问题到等谱流 给定 Hermitian 矩阵 $H_0$（比如某个量子体系的 Hamiltonian），**对角化 (diagonalization)** 是找酉矩阵 $V$ 使 $$ V H_0 V^\dagger = \operatorname{diag}(\lambda_1,\dots,\lambda_d). $$ 一旦完成，特征值可以从对角元直接读出，特征向量就是 $V$ 的列。排序 (sorting) 是它的弱化版：只要求把特征值按指定顺序排到对角线上。 经典数值线性代数对付这个问题的武器是 QR 迭代、Jacobi 旋转等。Brockett 的观察是：这类迭代背后有一条连续的微分方程 $$ \dot H = [[N,H],H], $$ 其中 $N$ 是一个我们自由选择的 Hermitian 矩阵，$\dot H = dH/dt$。注意方程右边出现了**两层对易子**——先算 $[N,H]$，再与 $H$ 对易——这就是 "double bracket" 名字的由来。有些文献采用整体差一个负号的约定（即 $\dot H = [H,[N,H]]$），两种约定只是时间反演的关系，本文固定用上式。 这条方程的妙处在于两点，分别对应下面两节的内容： - 它**自动保持谱不变**：$H(t)$ 始终是 $H(0)$ 的酉共轭，特征值从头到尾不动； - 它**是一条梯度流**：存在 Lyapunov 函数 $\operatorname{Tr}(NH)$ 沿流单调变化，稳定点恰好是与 $N$ 对易的矩阵，而在合适的 $N$ 下"与 $N$ 对易"就意味着"在 $N$ 的基下对角"。 也就是说，这条流不"寻找"新的特征值，而是在固定谱的前提下把矩阵旋转到对角形。理解了这一点，后面所有构造——离散步长、量子合成、虚时间演化的联系——就都有了一个统一的图景：它们都是在 unitary orbit 上做受控的旋转。 (isospectral-unitary-orbit)= ## 2. Double-bracket 流与等谱性 设 $H, N$ 都是 Hermitian 矩阵。定义生成元 $$ K(H) := [N,H] = NH - HN. $$ **$K(H)$ 是 anti-Hermitian（反厄米）的**，即 $K^\dagger = -K$。验证只用对易子取共轭转置的恒等式 $[A,B]^\dagger = (AB-BA)^\dagger = B^\dagger A^\dagger - A^\dagger B^\dagger$ 与 $H^\dagger = H$、$N^\dagger = N$： $$ K^\dagger = (NH - HN)^\dagger = H^\dagger N^\dagger - N^\dagger H^\dagger = HN - NH = -K. $$ 于是 double-bracket 方程可以写成更对称的形式 $$ \dot H = [K(H), H], $$ 即"用一个反厄米生成元去共轭地驱动 $H$"。熟悉量子力学的读者会认出这就是 Heisenberg 方程 $\dot H = i[\mathcal K, H]$ 的形状，只不过这里的"Hamiltonian" $\mathcal K = -iK$ 本身随 $H$ 变化（方程是非线性的）。 **等谱性。** 我们证明 $H(t)$ 与 $H(0)$ 酉等价。考虑辅助的酉演化方程 $$ \dot U = K(H)\,U,\qquad U(0) = I, $$ 并令 $H(t) := U(t)\,H(0)\,U(t)^\dagger$。先说明 $U(t)$ 确实是酉的：对 $U^\dagger U$ 求导，用 $\dot U = KU$ 以及取共轭得到的 $\dot U^\dagger = U^\dagger K^\dagger = -U^\dagger K$，有 $$ \frac{d}{dt}(U^\dagger U) = \dot U^\dagger U + U^\dagger \dot U = -U^\dagger K U + U^\dagger K U = 0, $$ 所以 $U^\dagger U$ 不随时间变，恒等于初始值 $I$；同理 $UU^\dagger = I$。再验证这样定义的 $H(t)$ 满足 double-bracket 方程。对乘积逐项求导： $$ \dot H = \dot U H(0) U^\dagger + U H(0) \dot U^\dagger. $$ 第一项代入 $\dot U = KU$ 得 $K\,U H(0) U^\dagger = KH$；第二项代入 $\dot U^\dagger = -U^\dagger K$ 得 $-U H(0) U^\dagger K = -HK$。合起来 $$ \dot H = KH - HK = [K(H), H], $$ 正是要证的方程（解的唯一性保证这就是原方程的解）。 结论：对一切 $t$，$H(t) = U(t)H(0)U(t)^\dagger$ 与 $H(0)$ **相似且酉等价**，因此 - 特征值（含重数）不变； - 所有 trace powers $\operatorname{Tr}(H^m)$ 不变——这由迹的循环性 $\operatorname{Tr}(U H_0^m U^\dagger) = \operatorname{Tr}(H_0^m U^\dagger U) = \operatorname{Tr}(H_0^m)$ 直接看出； - 行列式、秩、范数等谱函数全部不变。 改变的是**特征向量**，即矩阵相对于固定基（比如 $N$ 的特征基）的朝向。由此得到对这类算法能力边界的第一个重要认识： > Double-bracket 流**不能**把错误的特征值"优化成"目标谱——它只在固定谱的 unitary orbit 上移动，能做的一切就是重排与对角化。想要改变谱（例如制备基态、降低能量），必须借助其他机制，例如后文虚时间演化一节中对 projector 的处理。 (lyapunov-monotonicity-sorting)= ## 3. Lyapunov 函数、稳定点与特征值排序 知道了流"在哪里移动"，接下来回答"往哪里移动"。取标量函数 $$ F(H) = \operatorname{Tr}(NH), $$ 并计算它沿流的变化率。代入 $\dot H = [[N,H],H]$： $$ \frac{dF}{dt} = \operatorname{Tr}\big(N\,[[N,H],H]\big). $$ 化简这一步需要一个迹的恒等式：对任意矩阵 $A,B,C$，由迹的循环性 $\operatorname{Tr}(ABC)=\operatorname{Tr}(CAB)=\operatorname{Tr}(BCA)$ 可得 $$ \operatorname{Tr}\big(A[B,C]\big) = \operatorname{Tr}(ABC) - \operatorname{Tr}(ACB) = \operatorname{Tr}(BCA) - \operatorname{Tr}(BAC) = \operatorname{Tr}\big(B[C,A]\big). $$ 取 $A=N$、$B=K=[N,H]$、$C=H$： $$ \frac{dF}{dt} = \operatorname{Tr}\big(K\,[H,N]\big) = \operatorname{Tr}\big(K\cdot(-K)\big) = -\operatorname{Tr}(K^2). $$ 最后一步用了 $[H,N] = -[N,H] = -K$。而 $K$ 是反厄米的，即 $K^\dagger = -K$，所以 $K^2 = -K^\dagger K$，于是 $$ \frac{dF}{dt} = -\operatorname{Tr}(K^2) = \operatorname{Tr}(K^\dagger K) = \|[N,H]\|_F^2 \ge 0, $$ 其中倒数第二步是 Frobenius 范数的定义 $\|K\|_F^2 = \operatorname{Tr}(K^\dagger K) = \sum_{ij}|K_{ij}|^2$。这就是原文核心公式 $$ \frac{dF}{dt} = \operatorname{Tr}(N[[N,H],H]) = -\operatorname{Tr}([N,H]^2) = \|[N,H]\|_F^2 \ge 0 $$ 的完整推导。它给出两条信息： - **单调性**：$\operatorname{Tr}(NH)$ 沿流单调不减（取相反符号的约定下单调不增），流不会打转或振荡； - **稳定点刻画**：导数为零当且仅当 $\|[N,H]\|_F = 0$，即 $$ [N,H] = 0, $$ 流的稳定点恰好是与 $N$ 对易的矩阵。 **对角化从何而来。** 两个 Hermitian 矩阵对易，当且仅当它们可以被同一组正交归一基同时对角化。现在取 $$ N = \operatorname{diag}(n_1, n_2, \dots, n_d),\qquad n_1 < n_2 < \cdots < n_d $$ 为**非简并**的对角矩阵（所有 $n_i$ 互不相同）。若 $[N,H]=0$，直接算矩阵元：$[N,H]_{ij} = (n_i - n_j)H_{ij}$，它等于零而 $n_i \ne n_j$（$i\ne j$），迫使 $H_{ij} = 0$——$H$ 的所有非对角元都必须消失。所以在这条流的稳定点上，$H$ 自动在 $N$ 的基下成为对角矩阵：流把 $H$ 对角化了。 **排序从何而来。** 流收敛到对角形后，对角元就是 $H$ 的特征值，但排列顺序由初值与动力学决定。哪个排列对应 $\operatorname{Tr}(NH)$ 的最大值？这是 **von Neumann trace inequality** 回答的问题：对 Hermitian 矩阵， $$ \operatorname{Tr}(NH) \le \sum_{i} n_i^{\downarrow}\,\lambda_i^{\downarrow}, $$ 其中 $n_i^\downarrow$、$\lambda_i^\downarrow$ 分别表示 $N$ 与 $H$ 的特征值按降序排列，等号在两个矩阵"同序对齐"时取到（这本质上是重排不等式的矩阵版本）。因此，把 $N$ 的对角元按希望的次序放好，流就会把 $H$ 的特征值按对应次序排上对角线——**选择 $N$ 的顺序即完成了 eigenvalue sorting**。 **几何图景。** 上面的推导还有一个干净的几何解释：所有与 $H_0$ 酉等价的 Hermitian 矩阵构成一个流形（unitary orbit），其切空间恰好由 $[K,H]$（$K$ 取遍反厄米矩阵）这类对易子张成；而函数 $\operatorname{Tr}(NH)$ 在普通矩阵空间中的"欧氏梯度"是 $N$，把它投影到 orbit 的切空间上得到的正是 $[N,H]$ 方向的流。所以 double-bracket 方程是 **unitary manifold 上的 Riemannian gradient flow（黎曼梯度流）**：对易子扮演了"把欧氏梯度投影到切空间"的角色。这个视角（Brockett、Helmke–Moore）解释了为什么同一框架能统一处理 QR 分解、线性规划与排序：它们都是同一类等谱梯度流在不同目标函数下的化身。 (discrete-bracket-iteration)= ## 4. 离散 double-bracket 迭代 连续流不能直接上电路，需要离散化。最自然的第一步是 Euler：$H_{k+1} \approx H_k + \eta_k[[N,H_k],H_k]$。但这步更新只在一阶精度上保持 Hermiticity 与谱，误差会逐步累积。更好的方案是**沿切方向走一小段，再指数化回到轨道上**：每一步先算切向量（对易子），再做一次精确的酉共轭： $$ K_k = [N, H_k],\qquad U_k = e^{\eta_k K_k},\qquad H_{k+1} = U_k H_k U_k^\dagger. $$ 因为 $K_k$ 反厄米，$\eta_k K_k$ 仍反厄米，$U_k$ 是精确酉的（反厄米矩阵的指数是酉矩阵），所以 $H_{k+1}$ **精确地**保持 Hermiticity 与整个谱——不是近似，而是构造上自动成立。这正是"在轨道上移动"与"离开轨道再投影回来"的本质区别，也是这套迭代适合量子化的原因：量子计算机天然执行酉共轭。 与连续流的一致性由小步长展开保证。对 $e^{\eta K}$ 做 Taylor 展开 $e^{\eta K} = I + \eta K + \frac{\eta^2}{2}K^2 + \cdots$： $$ \begin{aligned} H_{k+1} &= \big(I + \eta_k K_k + O(\eta_k^2)\big)\,H_k\,\big(I - \eta_k K_k + O(\eta_k^2)\big)\\ &= H_k + \eta_k\,(K_k H_k - H_k K_k) + O(\eta_k^2)\\ &= H_k + \eta_k\,[K_k, H_k] + O(\eta_k^2)\\ &= H_k + \eta_k\,[[N,H_k],H_k] + O(\eta_k^2). \end{aligned} $$ 第二行展开时 $\eta^2$ 及以上的项全部收入 $O(\eta_k^2)$；第三行认出对易子；第四行代回 $K_k = [N,H_k]$。于是一步离散迭代与连续流走 $\eta_k$ 时间在一阶上完全一致，第 3 节的单调性分析在小步长下逐字成立。 $N$ 的选择有两种策略：可以**全程固定**为非简并对角矩阵（分析最简单，就是上面讨论的情形）；也可以**每轮变分地选择**——在第 $k$ 步选一个使非对角范数下降最快的 $N_k$（例如对齐当前 $H_k$ 对角元顺序的对角矩阵）。Gluza 的量子对角化算法（Zoo 522）采用的正是后一种 per-step 变分选择，以获得更快的实测收敛；代价是每步要多做一次对角元估计。 (two-by-two-example)= ## 5. 小例子：2×2 矩阵的一步迭代 把上面的公式在一个可以手算的例子里完整过一遍。取 $$ H_0 = \begin{pmatrix} a & b\\ b & c\end{pmatrix}\quad(a,b,c\in\mathbb R),\qquad N = \begin{pmatrix} n_1 & 0\\ 0 & n_2\end{pmatrix},\quad n_1 < n_2. $$ **第一步：算对易子 $K_0 = [N, H_0]$。** $$ NH_0 = \begin{pmatrix} n_1 a & n_1 b\\ n_2 b & n_2 c\end{pmatrix},\qquad H_0 N = \begin{pmatrix} n_1 a & n_2 b\\ n_1 b & n_2 c\end{pmatrix}, $$ 相减得 $$ K_0 = \begin{pmatrix} 0 & (n_1-n_2)b\\ (n_2-n_1)b & 0\end{pmatrix} = (n_1-n_2)b\begin{pmatrix} 0 & 1\\ -1 & 0\end{pmatrix}. $$ 记 $k := (n_1-n_2)b$。注意 $\begin{pmatrix}0&1\\-1&0\end{pmatrix} = i\sigma_y$，所以 $K_0 = ik\sigma_y$ 确实是反厄米的（$i$ 乘 Hermitian 矩阵），与第 2 节的一般结论一致。 **第二步：算一阶更新 $H_1 = H_0 + \eta[K_0, H_0] + O(\eta^2)$。** 逐次乘法： $$ K_0 H_0 = \begin{pmatrix} kb & kc\\ -ka & -kb\end{pmatrix},\qquad H_0 K_0 = \begin{pmatrix} -kb & ka\\ -kc & kb\end{pmatrix}, $$ $$ [K_0, H_0] = K_0H_0 - H_0K_0 = \begin{pmatrix} 2kb & k(c-a)\\ k(c-a) & -2kb\end{pmatrix}. $$ 于是一步之后（到一阶） $$ H_1 \approx \begin{pmatrix} a + 2\eta k b & b + \eta k(c-a)\\ b + \eta k(c-a) & c - 2\eta k b\end{pmatrix}. $$ **第三步：检查各种守恒与单调性。** - 迹不变：对角元变化 $+2\eta kb$ 与 $-2\eta kb$ 相消，$\operatorname{Tr}H_1 = a + c$，与谱不变性相容（行列式同样在一阶不变，留作习题）。 - 对角元的"能量"按 $N$ 排序方向流动：因为 $n_1 < n_2$ 且不妨设 $b>0$ 时 $k = (n_1-n_2)b < 0$，所以 $a \mapsto a + 2\eta k b$ 是**减小**、$c$ 对应增大——小的特征值向配对小 $n_1$ 的位置集中，正是 von Neumann 不等式预言的"同序对齐"。 - Lyapunov 函数的增量： $$ \Delta F = \operatorname{Tr}(N H_1) - \operatorname{Tr}(N H_0) = n_1(2\eta kb) + n_2(-2\eta kb) = 2\eta(n_1-n_2)kb = 2\eta(n_1-n_2)^2 b^2 \ge 0. $$ 与第 3 节公式对照：$\|[N,H_0]\|_F^2 = |K_{12}|^2 + |K_{21}|^2 = 2k^2 = 2(n_1-n_2)^2b^2$，故 $\Delta F = \eta\|[N,H_0]\|_F^2$，正好是连续流 $dF/dt = \|[N,H]\|_F^2$ 走 $\eta$ 时间的一阶结果。数字与公式严丝合缝。 **第四步：精确的一步（不展开）。** 因为 $K_0 = ik\sigma_y$ 且 $\sigma_y^2 = I$： $$ U_0 = e^{\eta K_0} = \cos(\eta k)\,I + i\sin(\eta k)\,\sigma_y, $$ 即 Bloch 球上绕 $y$ 轴的旋转，共轭 $U_0H_0U_0^\dagger$ 精确保持两个特征值 $\frac{a+c}{2} \pm \sqrt{\left(\frac{a-c}{2}\right)^2 + b^2}$。迭代若干步后非对角元 $b$ 被逐步压低，$H_k$ 趋向对角形——用 $2\times2$ 的眼睛就能看到"流把矩阵转到对角"的全过程。 (group-commutator-synthesis)= ## 6. Group commutator：在量子计算机上合成生成元 离散迭代里唯一非平凡的量子操作是 $U_k = e^{\eta_k[N,H_k]}$。量子计算机能直接做的是**单个** Hamiltonian 的演化 $e^{itH_k}$、$e^{itN}$（假设我们有对应的 simulation oracle，比如 $H_k$、$N$ 是局域或稀疏的），而生成元是两个算符的**对易子**。经典的解决办法是 **group commutator product formula（群交换子乘积公式）**：把两段正演化和两段逆演化交替串联，使一阶项相消、领头的幸存项恰好是对易子。 **断言（符号约定如下）**： $$ e^{i\sqrt{\eta}\,N}\,e^{i\sqrt{\eta}\,H_k}\,e^{-i\sqrt{\eta}\,N}\,e^{-i\sqrt{\eta}\,H_k} = e^{-\eta\,[N,H_k] + O(\eta^{3/2})}. $$ （各因子的次序可调换，调换后只改变对易子的符号；按需要的旋转方向选择。） **推导。** 工具是 Baker–Campbell–Hausdorff (BCH) 公式 $$ e^{A}e^{B} = \exp\Big(A + B + \tfrac12[A,B] + \tfrac1{12}[A,[A,B]] - \tfrac1{12}[B,[A,B]] + \cdots\Big), $$ 它的含义是：两个指数的乘积仍是单个指数，指数由 $A+B$ 加上一系列嵌套对易子构成，每个嵌套对易子的阶数（所含 $A,B$ 因子总数）递增。对我们的四段乘积分两步用 BCH。 先算左半 $e^{i\sqrt\eta N}e^{i\sqrt\eta H_k}$：取 $A = i\sqrt\eta N$、$B = i\sqrt\eta H_k$，则 $A+B = i\sqrt\eta(N+H_k)$ 是 $\sqrt\eta$ 阶，而 $$ \tfrac12[A,B] = \tfrac12(i\sqrt\eta)(i\sqrt\eta)[N,H_k] = -\tfrac{\eta}{2}[N,H_k] $$ 是 $\eta$ 阶，更高阶的嵌套对易子都是 $\eta^{3/2}$ 阶及以上。所以 $$ e^{i\sqrt\eta N}e^{i\sqrt\eta H_k} = \exp\Big(i\sqrt\eta(N+H_k) - \tfrac{\eta}{2}[N,H_k] + O(\eta^{3/2})\Big). $$ 同理算右半 $e^{-i\sqrt\eta N}e^{-i\sqrt\eta H_k}$，注意 $(-i\sqrt\eta)(-i\sqrt\eta) = -\eta$，对易子项的系数同样是 $-\eta/2$： $$ e^{-i\sqrt\eta N}e^{-i\sqrt\eta H_k} = \exp\Big(-i\sqrt\eta(N+H_k) - \tfrac{\eta}{2}[N,H_k] + O(\eta^{3/2})\Big). $$ 最后把两个大指数再做一次 BCH 合并。记 $X = i\sqrt\eta(N+H_k) - \frac{\eta}{2}[N,H_k]$、$Y = -i\sqrt\eta(N+H_k) - \frac{\eta}{2}[N,H_k]$，则： - 一阶项：$X + Y$ 中 $\pm i\sqrt\eta(N+H_k)$ 精确相消，剩下 $-\eta[N,H_k]$——这就是目标生成元； - 二阶交叉项 $\frac12[X,Y]$：领头贡献是 $\frac12[i\sqrt\eta(N+H_k),\, -i\sqrt\eta(N+H_k)] = \frac{\eta}{2}[N+H_k, N+H_k] = 0$（任何算符与自身对易为零），非零贡献都来自 $\sqrt\eta$ 阶与 $\eta$ 阶的交叉，即 $\eta^{3/2}$ 阶； - 所有更高阶嵌套对易子同理是 $\eta^{3/2}$ 阶及以上。 合起来即 $e^{-\eta[N,H_k] + O(\eta^{3/2})}$，断言得证。 这个构造的两个特性值得强调： - **它不需要辅助比特，也不需要 controlled-$U$。** 整个乘积只是对原有 simulation oracle 的正向/反向调用，因此不需要 postselection、不需要块编码框架——这是 double-bracket 路线相对 LCU/QSVT 类方法在资源开销上的一个卖点。 - **误差可以系统性压低。** 上面是二阶（误差 $\eta^{3/2}$）的公式；存在对称化的高阶 group commutator formulas，通过更精心地安排正反向演化的次序，把误差压到 $\eta$ 的更高幂，代价是每步调用次数增加。选择哪一阶公式，是在"步数"与"每步深度"之间的权衡，与 product-formula 模拟中的常见权衡完全同构。 合成出 $e^{\eta_k[N,H_k]}$ 之后，用它共轭 $H_k$ 就完成了一步 double-bracket 迭代。记账时注意：**输入 Hamiltonian 的局域/稀疏模拟成本、以及 product-formula 误差所要求的步长，都必须计入总复杂度**——$\eta$ 越小，单步误差越小，但达到固定收敛目标所需的步数越多。 (recursive-depth-explosion)= ## 7. 递归深度为什么爆炸 上一节留下了一个致命的细节：第 $k$ 步需要模拟的是**更新后的** Hamiltonian $H_k$，而不是原始的 $H_0$。粗看这不是问题——因为 $H_k$ 始终与 $H_0$ 酉等价， $$ H_k = V_k H_0 V_k^\dagger,\qquad V_k = U_{k-1}\cdots U_1 U_0, $$ 所以模拟 $H_k$ 可以归结为模拟 $H_0$： $$ e^{itH_k} = V_k\,e^{itH_0}\,V_k^\dagger. $$ 这个恒等式的验证：把右边指数展开，$V_k H_0 V_k^\dagger$ 的幂满足 $(V_kH_0V_k^\dagger)^m = V_k H_0^m V_k^\dagger$（中间的 $V_k^\dagger V_k = I$ 逐对相消），逐项求和即得。 问题出在**嵌套**上。第 $k$ 步的 group commutator 要调用 $e^{itH_k}$ 常数次（二阶公式是 4 次），每次展开成 $V_k e^{itH_0} V_k^\dagger$ 又包含整个 $V_k$——而 $V_k$ 本身是此前所有 $U_j$ 的乘积，每个 $U_j$ 又各自是一个调用了 $e^{itH_j}$ 的 group commutator。如果直接把一切内联展开成只含 $e^{itH_0}$ 的电路，电路深度的递推形如 $$ D_{k+1} \gtrsim c\,D_k + O(1),\qquad c > 1, $$ 其中 $c$ 是每步 group commutator 对"上一步演化"的调用次数（二阶公式里 $c$ 至少是 4 量级的常数），$O(1)$ 是新增的对 $e^{itH_0}$ 的直接调用。这个递推可以显式求解：反复迭代得 $$ D_k \gtrsim c^k D_0 + O(1)\cdot\frac{c^k - 1}{c - 1} = \Theta(c^k), $$ 即**电路深度随迭代步数指数增长**。每一步看似只加了常数个工作，但"模拟被更新过的 Hamiltonian"这件事把代价乘进了递归里。数值实验上，只跑少数几步的 double-bracket 迭代确实可行且有用（例如作为对角化的预处理或近端优化）；但渐近地看，原始形态的量子对角化算法并不高效——它没有一个对任意输入都多项式的深度上界。 有没有办法绕过递归？一个方向是**用空间换深度**，思想上类似量子动态规划 / 并行化：把中间步骤产生的酉变换或量子态显式地**保存**下来（存成电路描述、或制备成多份 copies 存在额外寄存器里），后续步骤直接调用存档，而不是从头递归重算。这样可以把深度从指数压回多项式量级，但代价是宽度（量子比特数）与 state-preparation 成本相应增长——递归并没有消失，只是从"深度账单"转移到了"宽度与制备账单"上。Zoo 519–520 讨论的正是这类 depth–width tradeoff 与相关的 map/Hermitian-preserving exponentiation 技术。 (qite-projector-flow)= ## 8. 虚时间演化是 projector 上的 double bracket Double-bracket 框架还有一层出人意料的对应：**纯态量子虚时间演化 (quantum imaginary-time evolution, QITE) 在 projector 层面恰好是一条 Brockett double-bracket 流**。这一节把这个恒等式完整推出来。 **第一步：建立归一化虚时间演化的方程。** 未归一化的虚时间态是 $|\tilde\psi(\tau)\rangle = e^{-\tau H}|\psi_0\rangle$，归一化因子记 $Z(\tau) = \langle\tilde\psi|\tilde\psi\rangle$，物理态为 $$ |\psi(\tau)\rangle = \frac{e^{-\tau H}|\psi_0\rangle}{\sqrt{Z(\tau)}}. $$ 我们关心的是它的密度矩阵（rank-one projector）$\rho(\tau) = |\psi(\tau)\rangle\langle\psi(\tau)| = |\tilde\psi\rangle\langle\tilde\psi|/Z$ 满足的方程。需要三个求导事实： - $d|\tilde\psi\rangle/d\tau = -H|\tilde\psi\rangle$（指数函数求导），同理 $d\langle\tilde\psi|/d\tau = -\langle\tilde\psi|H$； - $\dot Z = \langle\tilde\psi|(-H)|\tilde\psi\rangle + \langle\tilde\psi|(-H)|\tilde\psi\rangle = -2\langle\tilde\psi|H|\tilde\psi\rangle = -2Z\langle H\rangle$，其中 $\langle H\rangle := \operatorname{Tr}(H\rho)$ 是归一化态的能量期望； - 商的求导：$\frac{d}{d\tau}\frac{|\tilde\psi\rangle\langle\tilde\psi|}{Z} = \frac{-H|\tilde\psi\rangle\langle\tilde\psi| - |\tilde\psi\rangle\langle\tilde\psi|H}{Z} - \frac{|\tilde\psi\rangle\langle\tilde\psi|\,\dot Z}{Z^2}$。 代入 $\dot Z = -2Z\langle H\rangle$ 与 $\rho = |\tilde\psi\rangle\langle\tilde\psi|/Z$，第二项成为 $+2\langle H\rangle\rho$，于是 $$ \dot\rho = -\{H,\rho\} + 2\operatorname{Tr}(H\rho)\,\rho, $$ 其中 $\{H,\rho\} = H\rho + \rho H$ 是反对易子。这就是归一化纯态虚时间演化的 projector 方程：第一项来自 $e^{-\tau H}$ 的"衰减"，第二项来自归一化的"补偿"。 **第二步：把 double bracket 算出来。** 对 rank-one projector 有 $\rho^2 = \rho$（因为 $|\psi\rangle\langle\psi|\psi\rangle\langle\psi| = |\psi\rangle\langle\psi|$）。展开： $$ \begin{aligned} [[\rho,H],\rho] &= (\rho H - H\rho)\rho - \rho(\rho H - H\rho)\\ &= \rho H\rho - H\rho^2 - \rho^2 H + \rho H\rho\\ &= 2\rho H\rho - \{H,\rho\}, \end{aligned} $$ 第三行用了 $\rho^2 = \rho$。而 rank-one projector 满足恒等式 $$ \rho H\rho = |\psi\rangle\langle\psi|H|\psi\rangle\langle\psi| = \langle\psi|H|\psi\rangle\,|\psi\rangle\langle\psi| = \langle H\rangle\,\rho, $$ （中间的 $\langle\psi|H|\psi\rangle$ 是个数，可以提到算符外面）。代回： $$ [[\rho,H],\rho] = -\{H,\rho\} + 2\langle H\rangle\,\rho. $$ **第三步：对照。** 第二步的结果与第一步的 $\dot\rho$ 逐项相同，所以 $$ \dot\rho = [[\rho,H],\rho], $$ 这正是 double-bracket 形状：生成元 $[\rho, H]$ 是两个 Hermitian 矩阵的对易子（反厄米），外层再与 $\rho$ 对易。换句话说，**pure-state QITE 正是 projector unitary orbit 上的 Brockett double-bracket flow**。这个对应解释了 DB-QITE 类算法（Zoo 523–525）为什么成立：虚时间演化本身是非酉的（$e^{-\tau H}$ 不保持范数），但归一化后的 projector 始终可以用酉共轭来到达——非酉动力学被"投影"回了酉轨道上，全程保持纯度，且无需 postselection。 **收敛性与代价的定性图景。** 虚时间演化的标准分析在这里适用：若基态唯一、初态与基态的 overlap $\gamma = |\langle\psi_0|\psi_{\mathrm{gs}}\rangle|$ 非零，则激发态分量被 $e^{-\tau H}$ 以能量 gap $\Delta$ 为速率指数压制，对固定尺寸的体系，收敛所需虚时间 $\tau \sim \Delta^{-1}\log(1/(\gamma\varepsilon))$，步数是这一量级的多项式。但必须保留原文的警告：**当 system size 增长时，gap 可能指数变小、初始 overlap 可能指数变小、而每步 group-commutator 电路的深度还可能随步数指数增长**——三个潜在的指数因子叠在一起，所以这条路线的高效性是问题依赖的，不能作为通用结论。 ## 9. DB-QSP 与其他任务 Double-bracket 的 commutator synthesis 还有更广泛的用途，这里按原文范围概述并保留其保留条款。 - **DB-QSP。** 交替使用"信号算符的演化"与"double-bracket 共轭旋转"，可以构造对 Hamiltonian 的多项式变换，形成一种**无 postselection 的 QSP 变体**。但目前已知构造的 runtime 可以**指数于多项式次数**（本质上仍是第 7 节递归深度的影子），所以 DB-QSP 尚不能替代高效的标准 QSP/QSVT，它的价值更多在于概念统一与免辅助比特。 - **与经典数值算法的联系。** Brockett–Helmke–Moore 的经典理论表明，double-bracket 型的等谱流统一关联 QR decomposition、linear programming、sorting 与 matrix diagonalization：这些任务都可以写成某个 unitary orbit 上的梯度流。每搬一个应用到量子侧，都必须**单独**给出该应用的 convergence 保证与 implementation complexity，不能从框架的存在性直接继承。 - **Zoo 的 speedup 标注。** 综合第 7、8 节的讨论，Zoo 目前把这一类算法的 speedup 标为 unknown 是合理的：算法框架有明确的收敛方向（purposeful convergence），在若干近端数值场景有优势；但原始递归深度缺乏通用的 polynomial bound，任何多项式加速声称都必须附带额外的结构假设（例如小步数、好的 gap 与 overlap、或宽度换深度的预处理）。 ## 10. Source 审计勘误 Zoo 页面在引用经典 DBF 文献时有编号错位：页面把 classical DBF 的引用写作 anchor `HM`、显示编号 321，而实际 bibliography 中对应条目是 $$ \text{Helmke--Moore,\ \emph{Optimization and Dynamical Systems},\ 编号\ 521} $$ （anchor `HM12`）。编号 321 实为无关的 quantum Lovász local lemma 条目。此外 RPP24/RPP22 两个 anchor 的命名与年份也存在不一致。本教程一律按论文标题与实际 521–526 的记录引用，不以页面显示编号为准。 ## 11. 小结 - Double-bracket flow $\dot H = [[N,H],H]$ 是 unitary orbit 上的等谱 Riemannian gradient flow：对易子 $[N,H]$ 反厄米，共轭驱动自动保持整个谱。 - $\operatorname{Tr}(NH)$ 沿流单调，稳定点满足 $[N,H]=0$；取非简并对角 $N$ 时稳定点即对角形，von Neumann trace inequality 决定特征值的最终排序。 - 离散迭代用共轭 $H_{k+1} = e^{\eta_k[N,H_k]}H_k e^{-\eta_k[N,H_k]}$ 精确保持谱；group commutator product formula 用四段正/反演化合成 $e^{\eta[N,H_k]}$，无需 ancilla 与 postselection。 - 但模拟"更新后的 Hamiltonian"引入递归 $D_{k+1}\gtrsim cD_k + O(1)$，电路深度随迭代数指数增长；可用额外宽度与 state preparation 换取深度，属 depth–width tradeoff。 - 归一化纯态虚时间演化的 projector 方程恒等于 Brockett double bracket：非酉动力学被投影回酉轨道，保持纯度、免 postselection；但 gap、overlap 与每步深度的系统尺寸标度都可能指数差，高效性是问题依赖的。 ## 练习题 **练习 1【从对角化到 double-bracket 方程】**（→ [第 1 节](#double-bracket-equation)） 1. 基础：写出 double-bracket 方程，标出两层对易子的计算顺序（先 $[N,H]$，再与 $H$ 对易），并说明"排序"与"对角化"两个任务各自的要求差在哪里。 2. 进阶：证明：若 $H(t)$ 是 $\dot H = [[N,H],H]$ 的解，则 $H(-t)$ 是相反约定 $\dot H = [H,[N,H]]$ 的解——即两种约定只是时间反演。 > 提示：先证恒等式 $[H,[N,H]] = -[[N,H],H]$，再对 $H(-t)$ 用链式法则求导。 **练习 2【等谱性与酉轨道】**（→ [第 2 节](#isospectral-unitary-orbit)） 1. 基础：设 $N,H$ 均为 Hermitian，证明 $K=[N,H]$ 是反厄米的；并列出沿 double-bracket 流不变的三类谱量。 2. 进阶：从辅助方程 $\dot U = K(H)U$、$U(0)=I$ 出发，证明 $U(t)$ 是酉矩阵、$H(t)=U(t)H(0)U(t)^\dagger$ 满足 $\dot H=[K(H),H]$，并用迹的循环性说明 $\operatorname{Tr}(H^m)$ 沿流不变。 > 提示：对 $U^\dagger U$ 求导并使用 $K^\dagger = -K$；迹部分用 $\operatorname{Tr}(U H_0^m U^\dagger) = \operatorname{Tr}(H_0^m U^\dagger U)$。 **练习 3【Lyapunov 单调性与特征值排序】**（→ [第 3 节](#lyapunov-monotonicity-sorting)） 1. 基础：取 $N=\operatorname{diag}(n_1,\dots,n_d)$（$n_i$ 互不相同），由矩阵元等式 $[N,H]_{ij}=(n_i-n_j)H_{ij}$ 说明稳定点条件 $[N,H]=0$ 为何迫使 $H$ 的全部非对角元为零。 2. 进阶：补全第 3 节的推导：从迹的循环性出发，完整验证 $\operatorname{Tr}\big(A[B,C]\big) = \operatorname{Tr}\big(B[C,A]\big)$，并由此得到 $d\operatorname{Tr}(NH)/dt = \|[N,H]\|_F^2$；指出每一步用到 $N,H$ Hermitian 的位置，再陈述 von Neumann 迹不等式并说明"选择 $N$ 的顺序即完成特征值排序"。 > 提示：反厄米性给出 $K^2 = -K^\dagger K$，与 $\|K\|_F^2 = \operatorname{Tr}(K^\dagger K)$ 对照。 **练习 4【离散迭代与谱的精确保持】**（→ [第 4 节](#discrete-bracket-iteration)） 1. 基础：写出离散迭代的三个公式 $K_k=[N,H_k]$、$U_k=e^{\eta_k K_k}$、$H_{k+1}=U_k H_k U_k^\dagger$，并解释为什么说它按构造精确保持 Hermiticity 与谱，而 Euler 步 $H_k+\eta_k[[N,H_k],H_k]$ 只有一阶精度。 2. 进阶：展开共轭 $e^{\eta K}H e^{-\eta K}$ 到二阶，写出一阶项与二阶项各自的对易子结构，并由此说明一阶截断就是 Euler 步 $H + \eta[[N,H],H]$。 > 提示：$e^{\eta K} = I + \eta K + \frac{\eta^2}{2}K^2 + \cdots$，两侧一阶项符号相反；二阶项为 $\frac{\eta^2}{2}[K,[K,H]]$。 **练习 5【2×2 手算例子】**（→ [第 5 节](#two-by-two-example)） 1. 基础：对 $H_0=\begin{pmatrix}a&b\\b&c\end{pmatrix}$（$a,b,c\in\mathbb R$）与 $N=\operatorname{diag}(n_1,n_2)$（$n_1 提示：$K_0 = ik\sigma_y$ 且 $\sigma_y^2 = I$，故 $U_0 = \cos(\eta k)I + i\sin(\eta k)\sigma_y$ 是绕 $y$ 轴的旋转。 **练习 6【群交换子乘积公式】**（→ [第 6 节](#group-commutator-synthesis)） 1. 基础：写出二阶 group commutator 乘积公式（四段正/反演化的串联）及其误差阶 $O(\eta^{3/2})$，并列出该构造相对 LCU/QSVT 类方法的两个资源优势。 2. 进阶：用 BCH 公式逐步推导第 6 节的 group commutator 公式，明确 $\sqrt\eta$ 阶项为何相消、$\eta$ 阶项为何幸存、误差为何从 $\eta^{3/2}$ 阶开始。 > 提示：先用 BCH 分别合并左、右两个乘积，再把两个大指数合并，逐项跟踪 $\eta$ 的幂次。 **练习 7【递归深度指数增长】**（→ [第 7 节](#recursive-depth-explosion)） 1. 基础：解释第 $k$ 步为什么必须模拟更新后的 $H_k$ 而不是原始的 $H_0$，写出深度递推 $D_{k+1} \gtrsim cD_k + O(1)$，并说明其中常数 $c$ 的来源。 2. 进阶：求解递推 $D_{k+1} = cD_k + d$（$c>1$，$d$ 为常数）的显式表达式，并讨论：若用额外量子比特把中间酉变换显式存档、以宽度换深度，需要付出怎样的宽度与制备代价随 $k$ 增长？（定性即可。） > 提示：$D_k = c^k D_0 + d\,\frac{c^k-1}{c-1}$。 **练习 8【虚时间演化的 projector 方程】**（→ [第 8 节](#qite-projector-flow)） 1. 基础：写出归一化纯态虚时间演化的 projector 方程 $\dot\rho = -\{H,\rho\} + 2\operatorname{Tr}(H\rho)\,\rho$，并说明两项分别来自 $e^{-\tau H}$ 的"衰减"与归一化的"补偿"。 2. 进阶：证明 rank-one projector 的恒等式 $\rho H\rho = \langle H\rangle\rho$，并用它验证 $\dot\rho = [[\rho,H],\rho]$ 与 $\dot\rho = -\{H,\rho\} + 2\langle H\rangle\rho$ 逐项相等。 > 提示：$\rho^2 = \rho$，且 $\langle\psi|H|\psi\rangle$ 是可提到算符外的标量。 ## 参考文献与 Zoo 覆盖 - 实际 Zoo 521：Helmke--Moore, *Optimization and Dynamical Systems*（页面误标 321）。 - Zoo 522：Marek Gluza, [Double-Bracket Quantum Algorithms for Diagonalization](https://arxiv.org/abs/2206.11772). - Zoo 523--526：ground-state preparation、DB-QITE、Riemannian geometry 与 DB-QSP。 - Zoo 519--520、250：depth--width tradeoff、Hermitian-preserving map exponentiation 与 density-matrix exponentiation。