2024/10/17 by Yupan Liu, Qisheng Wang, Liu, Yupan +1 · 7 citations
Physics and Astronomy · Computer Science · #Quantum Mechanics and Applications #Quantum Information and Cryptography #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.1109/tit.2026.3683891
We investigate the computational complexity of estimating the trace of quantum state powers tr(ρ<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><sup>q</sup></i>) for an <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> qubit mixed quantum state ρ, given its state-preparation circuit of size poly <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(n)</i>. This quantity is closely related to and often interchangeable with the Tsallis entropy S<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><sub>q</sub></i>(ρ) = 1—tr(ρ<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><sup>q</sup></i>)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>—1, where <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i> = 1 corresponds to the von Neumann entropy. For any non-integer <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>≥ 1 + Ω(1), we provide a quantum estimator for S<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>(ρ) with time complexity poly <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(n)</i>, exponentially improving the prior best results of exp<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(n)</i> 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 computable <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">uniform approximations</i> of positive power functions into quantum singular value transformation. Our quantum algorithm reveals a sharp phase transition between the case of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i> = 1 and constant <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i> > 1 in the computational complexity of the Quantum <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>-Tsallis Entropy Difference Problem (TsallisQED <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><sub>q</sub></i> ), particularly deciding whether the difference S<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><sub>q</sub></i>(ρ0)−S<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><sub>q</sub></i> (ρ1) is at least 0.001 or at most −0.001: • For any 1 + Ω (1) ≤ <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i> ≤ 2, TsallisQED <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><sub>q</sub></i> is BQP-complete, which implies that Purity Estimation is also BQP-complete. • For any 1≤<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>≤1+1/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> — 1, TsallisQED q is QSZK-hard, leading to hardness of approximating the von Neumann entropy because S<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><sub>q</sub></i>(ρ) ≤ S (ρ), as long as BQPQSZK. The hardness results are derived from reductions based on new inequalities for the quantum <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>-Jensen–(Shannon–)Tsallis divergence with 1 ≤ <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i> ≤ 2, which are of independent interest.