On estimating the trace of quantum state powers

We investigate the computational complexity of estimating the trace of quantum state powers tr(ρq) for an n-qubit mixed quantum state ρ, given its state-preparation circuit of size poly(n). This quantity is closely related to and often interchangeable with the Tsallis entropy Sq(ρ)=1−tr(ρq)q−1, where q=1 corresponds to the von Neumann entropy. For any non-integer q≥1+Ω(1), we provide a quantum estimator for Sq(ρ) with time complexity poly(n), exponentially improving the prior best results of exp(n) due to Acharya, Issa, Shende, and Wagner (ISIT 2019), Wang, Guan, Liu, Zhang, and Ying (TIT 2024), and Wang, Zhang, and Li (TIT 2024), and Wang and Zhang (ESA 2024). Our speedup is achieved by introducing efficiently computable uniform approximations of positive power functions into quantum singular value transformation.

Our quantum algorithm reveals a sharp phase transition between the case of q=1 and constant q>1 in the computational complexity of the Quantum q-Tsallis Entropy Difference Problem (TsallisQEDq), particularly deciding whether the difference Sq(ρ0)−Sq(ρ1) is at least 0.001 or at most −0.001:
- For any 1+Ω(1)≤q≤2, TsallisQEDq is BQP-complete, which implies that Purity Estimation is also BQP-complete.
- For any 1≤q≤1+1n−1, TsallisQEDq is QSZK-hard, leading to hardness of approximating von Neumann entropy because Sq(ρ)≤S(ρ), as long as BQP⊊QSZK.

The hardness results are derived from reductions based on new inequalities for the quantum q-Jensen-(Shannon-)Tsallis divergence with 1≤q≤2, which are of independent interest.