技术摘要：关于量子态幂次的迹估计

问题陈述

本文研究了在给定规模为 $\text{poly}(n)$ 的 $n$ 量子比特混合量子态 $\rho$ 的态制备电路的情况下，估计量子态幂次的迹 $\text{tr}(\rho^q)$ 的计算复杂度。该量与量子 $q$-Tsallis 熵（定义为 $S_q(\rho) = \frac{1 - \text{tr}(\rho^q)}{q - 1}$）有着本质的联系。作者重点关注两个主要的决策问题：

1. 量子 $q$-Tsallis 熵差异问题 (TsallisQED$_q$)： 给定两个多项式规模的量子电路，分别制备状态 $\rho_0$ 和 $\rho_1$，判断是否满足 $S_q(\rho_0) - S_q(\rho_1) \ge 0.001$ 或 $S_q(\rho_1) - S_q(\rho_0) \ge 0.001$。
2. 量子 $q$-Tsallis 熵逼近问题 (TsallisQEA$_q$)： 给定一个制备 $\rho$ 的单一电路和一个阈值 $t(n)$，判断是否满足 $S_q(\rho) - t(n) \ge 0.001$ 或 $S_q(\rho) - t(n) \le -0.001$。

本研究旨在填补现有文献中的空白，即此前已知的有效量子算法仅限于整数 $q \ge 2$（例如通过 SWAP 测试进行纯度估计），或者当状态通过制备电路提供时，对于非整数 $q > 1$ 会导致 $\exp(n)$ 的指数级时间复杂度。

方法论

高效量子算法（上界）

对于 $q \ge 1 + \Omega(1)$ 的情形，作者提出了一种量子算法，实现了多项式时间复杂度，显著改进了以往 $\exp(n)$ 的结果。该方法依赖于三个核心组件：

1. 一致多项式逼近 (Uniform Polynomial Approximation)： 作者引入了对区间 $[0, 1]$ 内正幂函数 $x^q$ 的高效可计算一致逼近。不同于以往使用会导致秩相关误差的分段逼近方法，该方法利用切比雪夫截断（Chebyshev truncations）和 de La 瓦莱·普桑部分和（de La Vallée Poussin partial sums）来构造多项式 $P(x)$，使得 $\max_{x \in [0,1]} |P(x) - \frac{1}{2}x^q| \le \epsilon$，其次数为 $O(1/\epsilon^{1/q})$。
2. 量子奇异值变换 (QSVT)： 利用构造的多项式，通过 QSVT 实现 $\rho^{q-1}$ 的块编码（block-encoding）。
3. Hadamard 测试与振幅估计： 通过对块编码算符和状态 $\rho$ 进行 Hadamard 测试，并结合量子振幅估计来估计迹 $\text{tr}(\rho^q)$，从而达到所需的加性误差 $\epsilon$。

该方法产生的查询复杂度为 $O(1/\epsilon^{1 + \frac{1}{q-1}})$，时间复杂度为 $\text{poly}(n, 1/\epsilon)$，适用于 $q \ge 1 + \Omega(1)$。此外，作者还推导出了一个使用“采样器”（samplizer）技术的样本高效变体，其样本复杂度为 $\tilde{O}(1/\epsilon^{3 + \frac{2}{q-1}})$。

硬度结果（下界）

为了建立计算硬度，作者通过将已知的量子态测试问题归约到 TsallisQED$_q$ 和 TsallisQEA$_q$。

1. 新不等式： 证明依赖于建立 $1 \le q \le 2$ 时量子 $q$-Jensen–Tsallis 散度 ($QJT_q$) 与迹距离 $T(\rho_0, \rho_1)$ 之间的新不等式。具体而言，他们证明了 $QJT_q$ 的数据处理不等式，以及将 $QJT_q$ 与迹距离联系起来的界限，推广了已知的冯·诺依曼熵（$q=1$）的结果。
2. 归约：
   • BQP-硬度： 对于 $1 \le q \le 2$，作者将纯态可区分性问题（PureQSD，该问题是 BQP-hard）归约为常秩变体的 TsallisQED$_q$。这表明，估计常秩态的熵差异捕捉到了 BQP 的全部能力。
   • QSZK/NIQSZK-硬度： 对于 $1 < q \le 1 + \frac{1}{n-1}$ 的情形，通过向广义量子态可区分性（QSD）和量子态接近最大混合态（QSCMM）问题进行归约。这些归约利用了 Tsallis 熵相对于迹距离的界限，表明这些问题是 QSZK-hard 的，并且对于特定的 $q$，是 NIQSZK-hard 的。

核心贡献与结果

1. 复杂度的锐利相变

论文识别了估计 $S_q(\rho)$ 复杂度的锐利相变：

• 易处理区域 ($q \ge 1 + \Omega(1)$)： 问题 TsallisQED$_q$ 和 TsallisQEA$_q$ 包含在 BQP 中。作者提供了一个具有多项式时间复杂度的量子算法，比之前的 $\exp(n)$ 方法快指数级。
• 困难区域 ($1 < q \le 1 + \frac{1}{n-1}$)： 这些问题变为 QSZK-hard（对于特定 $q$ 也是 NIQSZK-hard）。这意味着除非 $\text{BQP} \subseteq \text{QSZK}$，否则在这些区域不存在高效的量子算法。
• 边界情况 ($q=1$)： 对应于冯·诺依曼熵，已知其对于差异问题是 QSZK-complete，对于逼近问题是 NIQSZK-complete。

2. 纯度估计的 BQP-完备性

作为 $1 \le q \le 2$ 时 BQP-硬度结果的直接推论，本文确立了纯度估计（估计 $\text{tr}(\rho^2)$）是 BQP-hard 的。这解决了关于估计量子态幂次的迹是否能完全捕捉量子计算能力的长期疑问。

3. 新的数学工具

• 高效一致逼近： 构建了适用于 QSVT 的 $x^q$ 的高效可计算一致多项式逼近，避免了以往方法的秩相关性。
• QJT$_q$ 不等式： 建立了 $1 \le q \le 2$ 时量子 $q$-Jensen–Tsallis 散度相对于迹距离的新的不等式，包括从联合凸性（joint convexity）导出的数据处理不等式。
• Tsallis 二进制熵界限： 为 $1 \le q \le 2$ 时的 Tsallis 二进制熵 $H_q(x)$ 提供了更紧的界限。

意义与主张

本文声称解决了不同 $q$ 取值范围内估计量子 $q$-Tsallis 熵的计算复杂度问题。

• 算法突破： 它提供了第一个针对非整数 $q \ge 1 + \Omega(1)$ 的高效（多项式时间）量子估计器，克服了先前工作（如 [AISW20, WGL+24, WZL24]）中的指数壁垒。
• 复杂度分类： 它精确地划定了可处理（BQP）与不可处理（QSZK-hard）区域之间的边界，揭示了估计熵的难度会随着 $q$ 从上方趋近于 1 而增加，特别是当 $q$ 在 $O(1/n)$ 范围内接近 1 时。
• 基础洞察： 通过证明纯度估计是 BQP-hard，这项工作确认了，只要是通过电路提供的，估计量子态的简单属性（如纯度）在计算上与一般的 BQP 问题一样难。

作者指出，其结果依赖于假设 $q$ 是大于 1 的常数（对于高效算法），且“困难区域”的硬度结果取决于状态的秩趋于维度 $2^n$。他们明确表示，虽然他们提供了匹配的下界，但对于该困难区域的高效上界仍是一个开放性问题。