标题： 在估计量子$\ell_α$距离 显示英文标题

标题： On estimating the quantum $\ell_α$ distance

摘要： 我们研究在给定 $\operatorname{poly}(n)$大小的状态制备电路的 $n$量子比特量子态 $\rho_0$和 $\rho_1$的情况下，通过施坦纳 $\alpha$-范数 $\|A\|_{\alpha} = \mathrm{tr}(|A|^{\alpha})^{1/\alpha}$定义的量子 $\ell_{\alpha}$距离 ${\mathrm{T}_\alpha}(\rho_0,\rho_1)$的计算复杂性。 这个量为$\alpha > 1$的迹距离提供了一个下界。 对于任何常数$\alpha > 1$，我们开发了一个高效的与秩无关的量子估计器，用于${\mathrm{T}_\alpha}(\rho_0,\rho_1)$，其时间复杂度为$\operatorname{poly}(n)$，相比 Wang、Guan、Liu、Zhang 和 Ying（TIT 2024）之前的最佳结果$\exp(n)$实现了指数级加速。 我们的改进利用了在量子奇异值变换中可高效计算的带符号正幂函数的统一多项式逼近，从而消除了对量子态秩的依赖。 我们的量子算法揭示了与Schatten$\alpha$-范数的量子态可区分性问题(QSD$_{\alpha}$)的计算复杂性中的二分法，该问题涉及判断${\mathrm{T}_\alpha}(\rho_0,\rho_1)$是否至少为$2/5$或至多为$1/5$。 这种二分法出现在常数$\alpha > 1$和$\alpha=1$的情况下： - 对于任何$1+\Omega(1) \leq \alpha \leq O(1)$，QSD$_{\alpha}$是$\mathsf{BQP}$-完备的。 - 对于任何$1 \leq \alpha \leq 1+\frac{1}{n}$，QSD$_{\alpha}$是$\mathsf{QSZK}$完全的，这意味着除非$\mathsf{BQP} = \mathsf{QSZK}$，否则不存在有效的量子估计器用于$\mathrm{T}_\alpha(\rho_0,\rho_1)$。硬度结果来自于基于新的与秩相关的不等式对于量子$\ell_{\alpha}$距离与$1\leq \alpha \leq \infty$的约简，这些不等式具有独立的兴趣。 显示英文摘要

摘要： We study the computational complexity of estimating the quantum $\ell_{\alpha}$ distance ${\mathrm{T}_\alpha}(\rho_0,\rho_1)$, defined via the Schatten $\alpha$-norm $\|A\|_{\alpha} = \mathrm{tr}(|A|^{\alpha})^{1/\alpha}$, given $\operatorname{poly}(n)$-size state-preparation circuits of $n$-qubit quantum states $\rho_0$ and $\rho_1$. This quantity serves as a lower bound on the trace distance for $\alpha > 1$. For any constant $\alpha > 1$, we develop an efficient rank-independent quantum estimator for ${\mathrm{T}_\alpha}(\rho_0,\rho_1)$ with time complexity $\operatorname{poly}(n)$, achieving an exponential speedup over the prior best results of $\exp(n)$ due to Wang, Guan, Liu, Zhang, and Ying (TIT 2024). Our improvement leverages efficiently computable uniform polynomial approximations of signed positive power functions within quantum singular value transformation, thereby eliminating the dependence on the rank of the quantum states. Our quantum algorithm reveals a dichotomy in the computational complexity of the Quantum State Distinguishability Problem with Schatten $\alpha$-norm (QSD$_{\alpha}$), which involves deciding whether ${\mathrm{T}_\alpha}(\rho_0,\rho_1)$ is at least $2/5$ or at most $1/5$. This dichotomy arises between the cases of constant $\alpha > 1$ and $\alpha=1$: - For any $1+\Omega(1) \leq \alpha \leq O(1)$, QSD$_{\alpha}$ is $\mathsf{BQP}$-complete. - For any $1 \leq \alpha \leq 1+\frac{1}{n}$, QSD$_{\alpha}$ is $\mathsf{QSZK}$-complete, implying that no efficient quantum estimator for $\mathrm{T}_\alpha(\rho_0,\rho_1)$ exists unless $\mathsf{BQP} = \mathsf{QSZK}$. The hardness results follow from reductions based on new rank-dependent inequalities for the quantum $\ell_{\alpha}$ distance with $1\leq \alpha \leq \infty$, which are of independent interest.