【报告摘要】Let $A$ be a log-local Hamiltonian acting on $n$ qubits, and let $f(x)$ be an analytic function whose approximate degree is at least $\Omega({\rm poly}(n))$. We show that computing $2^{-n} \tr[f(A)]$ to additive error $1/{\rm poly}(n)$ is DQC1-complete. This result subsumes all previously known special cases and, more importantly, identifies the approximate degree as the fundamental parameter governing the complexity of normalized trace estimation. As another hardness result, we prove that any classical algorithm for estimating the normalized trace of f(A) requires exponentially many queries in the approximate degree, establishing an exponential quantum–classical separation. In contrast to previous approaches, our proof relies on a clean combination of circuit-to-Hamiltonian constructions, periodic Jacobi operators, and tools from polynomial approximation theory, including the Chebyshev equioscillation theorem.

【报告人简介】 邵长鹏，副研究员，主要从事量子算法和量子复杂性理论方面的研究