We consider the quantum thermal statistics à la Gibbs–Shannon–Szilard–Jaynes based on q-entropies Sq[ρ]=(q−1)−1(1−tr(ρq)) (0<q≠1) and the non-standard ‘‘internal energy’’ functionals Uq[ρ]=tr(ρqH) proposed by C. Tsallis [J. Stat. Phys. 52, 479–487 (1988)].
We investigate the computational complexity of estimating the trace of quantum state powers tr(ρq) for annqubit 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, whereq= 1 corresponds to the von Neumann entropy. For any non-integerq≥ 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)| Wang, Zhang, and Li (TIT 2024), and Wang and Zhang (TIT 2025). Our speedup is achieved by introducing efficiently computableuniform approximationsof positive power functions into quantum singular value transformation. Our quantum algorithm reveals a sharp phase transition between the case ofq= 1 and constantq> 1 in the computational complexity of the Quantumq-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, TsallisQEDqis BQP-complete, which implies that Purity Estimation is also BQP-complete. • For any 1≤q≤1+1/n— 1, TsallisQED q is QSZK-hard, leading to hardness of approximating the von Neumann entropy because Sq(ρ) ≤ S (ρ), as long as BQPQSZK. The hardness results are derived from reductions based on new inequalities for the quantumq-Jensen–(Shannon–)Tsallis divergence with 1 ≤q≤ 2, which are of independent interest.
In this paper we investigate the inequality Sq(ρ123) + Sq(ρ2) ≤ Sq(ρ12) + Sq(ρ23) (∗) where ρ123 is a state on a finite dimensional Hilbert space H1 ⊗ H2 ⊗ H3, and Sq is the Tsallis entropy. It is well-known that the strong subadditivity of the von Neumnann entropy can be derived from the monotonicity of the Umegaki relative entropy. Now, we present an equivalent form of (*), which is an inequality of relative quasi-entropies. We derive an inequality of the form Sq(ρ123) + Sq(ρ2) ≤ Sq(ρ12) + Sq(ρ23) + fq(ρ123), where f1(ρ123) = 0. Such a result can be considered as a generalization of the strong subadditivity of the von Neumnann entropy. One can see that (*) does not hold in general (a picturesque example is included in this paper), but we give a sufficient condition for this inequality, as well.