On estimating the quantum $\ell_α$ distance

We study the computational complexity of estimating the quantum $\ell_α$ distance ${\mathrm{T}_α}(ρ_0,ρ_1)$, defined via the Schatten $α$-norm $\|A\|_α = \mathrm{tr}(|A|^α)^{1/α}$, given $\operatorname{poly}(n)$-size state-preparation circuits of $n$-qubit quantum states $ρ_0$ and $ρ_1$. This quantity serves as a lower bound on the trace distance for $α> 1$. For any constant $α> 1$, we develop an efficient rank-independent quantum estimator for ${\mathrm{T}_α}(ρ_0,ρ_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 $α$-norm (QSD$_α$), which involves deciding whether ${\mathrm{T}_α}(ρ_0,ρ_1)$ is at least $2/5$ or at most $1/5$. This dichotomy arises between the cases of constant $α> 1$ and $α=1$: - For any $1+Ω(1) \leq α\leq O(1)$, QSD$_α$ is $\mathsf{BQP}$-complete. - For any $1 \leq α\leq 1+\frac{1}{n}$, QSD$_α$ is $\mathsf{QSZK}$-complete, implying that no efficient quantum estimator for $\mathrm{T}_α(ρ_0,ρ_1)$ exists unless $\mathsf{BQP} = \mathsf{QSZK}$. The hardness results follow from reductions based on new rank-dependent inequalities for the quantum $\ell_α$ distance with $1\leq α\leq \infty$, which are of independent interest.