Hamiltonian Eigenvalue Transformation by Tridiagonal Gadgets

技术摘要：通过三对角小工具实现哈密顿量特征值变换

问题陈述
模拟量子设备实现局部哈密顿量 $H$，但许多连续时间算法需要输入哈密顿量的多项式 $P(H)$ 作为算符。通常情况下，$P(H)$ 是非局部的，这使得在仅支持局部、少体相互作用的硬件上直接实现它是无法做到的。虽然电路模型通过交织 Oracle 调用（以次数作为时间/深度的代价）通过量子奇异值变换（QSVT）解决了这一问题，但模拟模型缺乏一种机制来将任意多项式合成作为一个单一的、时间无关的局部算符。本文解决的具体挑战是：能否找到一个局部哈密顿量，使其在不变子空间上的限制等于给定哈密顿量的特定多项式？

方法论
作者提出了一种使用“小工具”（gadgets）的构造方法——即连接在输入哈密顿量 $H$ 上的短辅助比特链。其核心机制包括：

1. 小工具结构： 构建一个包含 $2m$ 个位点（对于偶次多项式）或 $2n+1$ 个位点（对于奇次多项式）的链。其耦合项在输入 $H$（或标量 $x$）与单位耦合之间交替出现。该链以特定的边界条件终止：偶数链使用失谐 $-\Delta$，奇数链使用正比于输入 $\Delta_o x$ 的耦合。
2. 精确特征值分析： 与传统的基于微扰的小工具（通过近似有效相互作用）不同，这项工作分析了小工具的精确孤立特征值分支 $\lambda(x)$。
   • 对于长度为 $2m$ 的链，孤立特征值 $\lambda^{(m)}_0(x)$ 在 $x=0$ 处的消失阶数恰好为 $2m$。
   • 证明该函数在复圆盘 $|x| < r$（其中 $r < 1$）内是解析的，前提是失谐 $\Delta$ 超过阈值 $\Delta_\star(r)$。
   • 该分支的泰勒展开式为 $\lambda^{(m)}_0(x) = \sum c^{(m)}_k x^{2m+2k}$，其中系数 $c^{(m)}_k$ 在 $m$ 方面是一致有界的。
3. 三角合成： 由于不同长度的链会产生具有不同领先阶数（$x^{2m}$ 对比 $x^{2(m+1)}$）的特征值，它们构成了一个三角族。通过在同一个输入 $H$ 上连接多个不同长度的链并赋予特定的实权重 $\alpha_j$，作者构造了一个加权和 $\Sigma = \sum \alpha_j E_{2j}(H)$。
   • 权重通过求解一个下三角线性系统来逐项匹配目标多项式 $P(x)$ 的系数。
   • 截断误差（超出目标次数的项）随链的数量呈几何级数衰减，前提是输入范数 $\|H\|$ 严格小于解析半径 $r$。
4. 局部实现： 生成的算符 $\Sigma$ 作用于系统加上辅助比特。证明该算符是一个局部性为 $(\kappa + 2)$（其中 $\kappa$ 为 $H$ 的局部性）的单一、时间无关的哈密顿量，作用于由系统特征向量与小工具分支特征向量的张量积所构成的不变子空间。

核心贡献与结果

• 定理 A（解析性与界限）： 证明了目标特征值分支是唯一的，在受控复圆盘内是解析的，并且其泰勒系数是一致有界的。这为合成奠定了数学基础，确保了对于 $\|H\| < r$ 的输入，该级数是收敛的。
• 定理 B（多项式合成）： 证明了任何偶次多项式（以及通过奇次小工具实现的任何多项式）都可以通过单个局部哈密顿量近似到精度 $\epsilon$。
  • 资源成本： 对于度数为 $2\ell$ 的多项式，该构造需要 $O(\ell^2 + \log^2(1/\epsilon))$ 个辅助比特。
  • 局部性： 输出的哈密顿量是 $(\kappa + 2)$-局部的。
  • 能量尺度： 哈密顿量的范数随合成系数的总权重而变化，对于一般多项式，该权重随度数呈拟多项式增长。
• 定理 C（通过迭代进行滤波）： 针对过滤标记本征态（例如在模拟搜索中）的具体应用，作者提出了一种递归方法，利用两个位点链（$m=1$）的精确特征值映射，而不是通过一次性合成高次切比雪夫多项式。
  • 机制： 通过迭代该映射 $k$ 次来折叠能谱，从而隔离出标记态。
  • 效率： 该方法对于 $n$ 比特系统，仅使用 $O(\log n)$ 个辅助比特和 $O(\log n)$-局部项。
  • 能量尺度： 至关重要的是，这种迭代滤波器的能量尺度与反向通带宽度（$\sigma/d$）成多项式关系，且与迭代次数 $k$ 无关；这与单次合成（其能量尺度随度数呈拟多项式增长）不同。
  • 收敛性： 误差随 $k$ 呈几何级数衰减（按 $\varrho^{-k}$），这足以满足模拟搜索的应用需求。

意义与主张
本文声称弥合了理想化连续时间算法（通常使用非局部投影器或高次多项式）与物理可实现的局部设备之间的差距。

• 静态 vs 顺序： 与 QSVT 不同（QSVT 以顺序深度/时间来支付次数代价），该方法以宽度（辅助比特）和能量尺度作为代价，但其变换是一个单一的静态算符。这使得变换后的哈密顿量可以作为更大哈密顿量的一部分，而这是顺序电路协议难以实现的特性。
• 精确 vs 微扰： 该构造依赖于精确特征值分析而非微扰展开，从而避免了为了抑制领先阶误差而需要巨大的失谐量。
• 在模拟搜索中的应用： 作者模拟了在 $n=20$ 的情况下进行模拟搜索的构造过程。结果表明，基于小工具的哈密顿量能够重现理想模拟搜索算法的能谱和最小能隙缩放（$2^{-n/2}$）。
• 权衡： 本文承认能量尺度（即对于固定能量预算下的时间开销）是一种成本。对于一般多项式，该成本随度数呈拟多项式增长。然而，对于滤波这一特定情况（定理 C），能量尺度与问题参数成多项式关系，且与滤波器深度无关，这使得它成为绝热优化中秩一投影器的可行替代方案。

研究结论指出，虽然该构造并不能消除模拟非局部算符所固有的能量成本，但它提供了一种严谨、静态且局部的多项式变换实现方式，为在局部性受限的硬件上实现理想化的模拟算法提供了具体路径。