技术摘要：改进量子凸体体积估计的上界与下界

1. 问题陈述

本文探讨了估计高维凸体 $K \subset \mathbb{R}^d$ 体积这一基础问题。设定处于**成员查询模型（membership-oracle model）**中，即算法仅通过一个确定查询点是否在凸体内内的算子来访问 $K$。算法已知同心球 $B(x_0, r) \subseteq K \subseteq B(x_0, R)$，其中半径比 $R/r$ 为多项式级。目标是输出一个估计值 $\hat{V}$，使得以高概率满足 $(1-\varepsilon)\text{vol}(K) \leq \hat{V} \leq (1+\varepsilon)\text{vol}(K)$，并最小化成员查询次数。

虽然经典算法已取得了显著进展，特别是 Jia 等人 [JLLV26] 确立了查询复杂度为 $\tilde{O}(d^{7/2} + d^3/\varepsilon^2)$，但量子对应算法的进展尚未跟上。之前的量子算法 [CCH+23, CH23] 依赖于“撞击与运行”（hit-and-run）随机游走，该算法受限于较慢的混合时间界限（$\tilde{O}(d^3)$），这使得关于能否利用最近关于 Kannan–Lovász–Simonovits (KLS) 猜想的经典突破来构建更高效的量子体积估计器的疑问悬而未决。

2. 方法论

作者提出了一种新的量子算法，通过整合三项主要的底层技术创新来实现改进的查询复杂度：

A. 基于热启动混合的输入相关谱分析

本文引入了一种新的分析方法，用于构建基于均匀热启动混合界限（uniform warm-start mixing bounds）的平稳态反射（stationary-state reflections）（即关于目标分布 $|\pi\rangle$ 的量子反射）。

• 挑战： 标准的量子行走加速依赖于谱间隙（spectral gap）。然而，最坏情况下的混合时间可能很慢，即使特定的输入状态在慢特征空间中的权重很小。之前的量子体积算法依赖于“单启动”（single-start）有效谱间隙论证，作者证明这些论证是不充分的（并在附录 A 中提供了反例）。
• 解决方案： 作者利用了均匀热启动混合（从任何满足 $d\nu/d\pi \leq 2$ 的分布 $\nu$ 开始混合）。他们证明，如果一个马尔可夫链在 $t$ 步内能从每一个 2-热启动开始均匀混合，那么量子输入状态的“慢”分量由其相对于平稳分布的四阶矩范数所限制。
• 结果： 这允许构造出误差为 $\tilde{O}(\eta^{1/4}\|\Psi\|_{4,\pi} + \zeta)$ 的近似反射，且仅需 $\tilde{O}(\sqrt{t})$ 次判别器查询，其中 $\eta$ 是混合误差。这使得反射成本与最坏情况谱间隙解耦，并将其与特定输入的混合时间挂钩。

B. 带有相干预处理的格点 Metropolis 游走

为了实现所需的快速混合，作者在一个固定的有限状态空间 $\Omega_\Lambda = K_0 \cap h\mathbb{Z}^{d+1}$ 上构建了一个格点 Metropolis 游走（lattice Metropolis walk）。

• 离散化： 不同于以往对 hit-and-run 游走的离散化方法（需要复杂的条件采样），该游走使用一种离散的“球体游走”（ball walk），其步长从有限的二进标度列表中抽取。
• 相干预处理： 该游走采用仿射预处理算子 $A$（近似协方差）以确保快速混合。至关重要的是，算法维护了两组交替角色的 qsamples：一组用于相干地估计协方差，进而为另一组预处理游走提供支持。这种“交错”方法使算法能够在冷却计划期间适应物体的几何变化，同时不会破坏量子态。
• 混合时间： 在预处理假设下，该游走从每一个 2-热启动开始在 $\tilde{O}(d^2 \psi_d^{-2})$ 步内完成混合，其中 $\psi_d$ 是 KLS 常数。

C. 具有流式访问能力的量子乘积估计器

体积通过沿冷却计划（模拟退火）的归一化常数比例的递推乘积进行估计。

• 桥接采样（Bridge Sampling）： 作者将经典桥接采样与量子相位估计相结合。算法并非单独高精度地估计每个比例，而是将比例的对数编码到哈密顿量的特征相位中。
• 流式访问： 估计器使用流式访问 qsamples：它逐个处理独立的 qsample，通过相位回馈（phase kickback）将带符号的对数贡献累积到共享的相位寄存器中，然后丢弃该 qsample。
• 复杂度： 这种方法使用 $\tilde{O}(m/\varepsilon)$ 次反射来估计 $m$ 个比例的乘积，优于之前工作 [CH23] 的 $\tilde{O}(m^{3/2}/\varepsilon)$ 界限。

3. 核心贡献与结果

上界

本文提出了一个具有如下查询复杂度的量子体积估计算法：
$$\tilde{O}\left( \frac{d^{5/2}}{\psi_d} + \frac{d^{3/2}}{\psi_d \varepsilon} \right)$$
使用当前 KLS 常数的最佳界限（$\psi_d^{-1} = O(\log^{1/4} d)$），该式简化为：
$$\tilde{O}\left( d^{5/2} + \frac{d^{3/2}}{\varepsilon} \right)$$
对比：

• 对比之前的量子界限： 在两个项上都优于之前的最佳量子界限 $\tilde{O}(d^3 + d^{5/2}/\varepsilon)$ [CCH+23] 和 $\tilde{O}(d^3 + d^{9/4}/\varepsilon)$ [CH23]。
• 对比经典界限： 与最佳经典界限 $\tilde{O}(d^{7/2} + d^3/\varepsilon^2)$ [JLLV26] 相比，该量子算法在 $\varepsilon$ 相关项上实现了二次方级改进（$d^{3/2}/\varepsilon$ 对比 $d^3/\varepsilon^2$），并在维度相关项上实现了线性因子级的改进（$d^{5/2}$ 对比 $d^{7/2}$）。

下界

作者证明了对于常数相对误差，存在一个线性量子查询下界：
$$\Omega(d)$$
这改进了之前的 $\Omega(\sqrt{d})$ 下界 [CCH+23]。

• 构造： 证明过程构造了两类以原点为中心的椭球分布。一类分布对应于行列式为 $+1$ 的正交矩阵，另一类对应于行列式为 $-1$ 的正交矩阵。
• 不可区分性： 作者表明，对于任何少于 $d$ 个查询点的集合，这两类分布下的成员位乘积的期望值是相同的。通过量子多项式方法，区分这些分布（以及因此区分它们的体积，两者相差一个常数因子）需要 $\Omega(d)$ 次查询。

4. 重要性与主张

本文声称解决了关于 KLS 猜想的进展是否能转化为更高效的量子体积估计这一开放性问题。这项工作的意义在于：

1. 弥合经典与量子间的差距： 它证明了通过转向均匀热启动混合而非单启动谱间隙论证，可以有效地利用由 KLS 猜想（通过伴随工作 [Zha26]）得出的更快的混合时间。
2. 技术新颖性： 引入基于四阶矩范数的输入相关谱分析以及带有相干预处理的格点 Metropolis 游走，为涉及连续分布和马尔可夫链的量子算法提供了新的工具包。
3. 最优性： 线性下界表明，上界中对维度 $d$ 的依赖极有可能是接近最优的，因为上界（$d^{5/2}$）与下界（$d$）之间的差距相对于之前的差距而言已经相对较小。
4. 算法框架： “流式”量子乘积估计器提供了一种通用的技术，用于估计退火计划中期望的乘积，这可能适用于其他吉布斯配分函数问题。

作者强调，这些改进是针对成员查询复杂度的。门复杂度仍是问题参数的多项式函数，尽管指数并未经过优化。这项工作依赖于 KLS 常数被多项式对数因子限制的假设，这一条件得到了近期经典研究结果的支持。